目录
——栈
1. 栈的基本操作
【问题描述】
设一个顺序栈，进行出栈和入栈操作。
【输入形式】输入若干个整数（不超过1000），依次入栈；（提示：scanf("%d",&e)==1来作为输入判断）
【输出形式】依次出栈并输出元素值，以空格分隔。
【样例输入】23 45 67 14 -9 20 100 89 45 30
【样例输出】30 45 89 100 20 -9 14 67 45 23
【评分标准】必须使用顺序栈结构实现。栈的基本操作以算法函数形式实现。
#include<stdio.h>
#include<malloc.h>
#define MAX 10
#define IN 10
typedef struct Stack{
int *base;
int *top;
int size;
}Stack,*PStack;
int Init(PStack S){
S->base=(int *)malloc(sizeof(int)*MAX);
S->top=S->base;
S->size=MAX;
}
int Push(PStack S,int e){
if(S->top-S->base>=S->size){
S->base=(int *)realloc(S->base,(S->size+IN)*sizeof(int));
S->top=S->base+S->size;
S->size+=IN;
}
*S->top++=e;
return 1;
}
int Pop(PStack S,int *e){
if(S->base==S->top){
return 0;
}
S->top--;
*e=*S->top;
return 1;
}
int Empty(PStack S){
if(S->base==S->top) return 1;
else return 0;
}
int main(){
Stack S;
int e;
Init(&S);
while(scanf("%d",&e)==1){
Push(&S,e);
}
while(!Empty(&S)){
Pop(&S,&e);
printf("%d ",e);
}
return 0;
}
2. 栈的应用-数制转换
【问题描述】
利用栈实现十进制向二进制的转换。
【输入形式】
输入若干个十进制正整数，输出它们的二进制形式。（提示：输入采用scanf("%d",&x)==1）
【输出形式】
输出每个十进制正整数的二进制形式。
【样例输入】
5
7
20
255
128
127
1000
50000
65535
【样例输出】
101
111
10100
11111111
10000000
1111111
1111101000
1100001101010000
1111111111111111
【评分标准】
利用栈的基本操作实现转换。
#include<stdio.h>
#include<malloc.h>
#define MAX 10
#define IN 10
typedef struct Stack{
int *base;
int *top;
int size;
}Stack,*PStack;
int Init(PStack S){
S->base=(int *)malloc(sizeof(int)*MAX);
S->top=S->base;
S->size=MAX;
return 1;
}
int Push(PStack S,int e){
while(S->top-S->base>=S->size){
S->base=(int *)realloc(S->base,sizeof(int)*(S->size+IN));
S->top=S->base+S->size;
S->size+=IN;
}
*S->top++=e;
return 1;
}
int Pop(PStack S,int *e){
if(S->base==S->top){
return 0;
}
S->top--;
*e=*S->top;
return 1;
}
int Empty(PStack S){
if(S->base==S->top) return 1;
else return 0;
}
int Convert(PStack S,int x){
int e;
while(x){
Push(S,x%2);
x/=2;
}
while(!Empty(S)){
Pop(S,&e);
printf("%d",e);
}
printf("\n");
return 1;
}
int main(){
int x;
Stack S;
while(scanf("%d",&x)==1){
Init(&S);
Convert(&S,x);
}
return 0;
}
3. 函数：判断表达式括弧是否匹配
【问题描述】编写算法函数：判断一表达式中的括号是否配对，包括中括号[]、小括号()两种类型。
【输入形式】输入一个只包含中括号和小括号的字符串。
【输出形式】输出匹配结果：若匹配，输出match，如输入“[()][()()]()”，输出“match”；不匹配，输出not match，如输入“[](()]”，输出“not match”。
【样例输入】
[()][()()]()【样例输出】
match【样例说明】检测数据包括多种。
#include<stdio.h>
#include<malloc.h>
#define MAX 10
#define IN 10
typedef struct Stack{
char *base;
char *top;
int size;
}Stack,*PStack;
int Init(PStack S){
S->base=(char *)malloc(sizeof(char)*MAX);
S->top=S->base;
S->size=MAX;
return 1;
}
int Push(PStack S,char e){
while(S->top-S->base>=S->size){
S->base=(char *)realloc(S->base,(S->size+IN)*sizeof(char));
S->top=S->base+S->size;
S->size+=IN;
}
*S->top++=e;
return 1;
}
int Pop(PStack S,char *e){
if(S->base==S->top){
return 0;
}
S->top--;
*e=*S->top;
return 1;
}
int Get(PStack S,char *e){
if(S->base==S->top){
return 0;
}
*e=*(S->top-1);
}
int Empty(PStack S){
if(S->base==S->top) return 1;
else return 0;
}
int Measure(PStack S,char *s){
char e;
while(*s){
if(*s=='('||*s=='['){
Push(S,*s);
}else{
if(Empty(S)) return 0;
Pop(S,&e);
if(*s==')'){
if(e!='(') return 0;
}else{
if(e!='[') return 0;
}
}
s++;
}
if(!Empty(S)) return 0;
return 1;
}
int main(){
char s[100];
Stack S;
Init(&S);
scanf("%s",&s);
if(Measure(&S,s)==1) printf("match\n");
else printf("not match\n");
return 0;
}
——队列
4. 顺序循环队列的基本操作
【问题描述】
实现循环队列的基本操作。（循环队列最大长度不超过20）
【输入形式】
输入若干个整数（以空格分隔，非整数结束输入），其中0表示做出队操作，不为0的整数为入队元素。
【输出形式】
若出队错误输出“error”；
若最后队列为空，则输出“empty”；
若最后队列非空，依次输出队列的全部元素。
【样例输入1】
1 0 2 0 0 3 0 0 0 a
【样例输出1】
error
【样例输入2】
1 0 2 0 3 0 a
【样例输出2】
empty
【样例输入3】
1 2 3 0 0 4 0 5 a
【样例输出3】
4 5
【评分标准】
补充代码完成程序功能，不得修改程序中其他函数。
#include<stdio.h>
#include<malloc.h>
#define MAX 10
typedef struct Queue{
int *base;
int front;
int rear;
}Queue,*PQueue;
int Init(PQueue Q){
Q->base=(int *)malloc(sizeof(int)*MAX);
Q->front=Q->rear=0;
return 1;
}
int En(PQueue Q,int e){
if((Q->rear+1)%MAX==Q->front){
return 0;
}
Q->base[Q->rear]=e;
Q->rear=(Q->rear+1)%MAX;
return 1;
}
int De(PQueue Q,int *e){
if(Q->front==Q->rear) return 0;
*e=Q->base[Q->front];
Q->front=(Q->front+1)%MAX;
return 1;
}
int Empty(PQueue Q){
if(Q->front==Q->rear) return 1;
else return 0;
}
int main(){
int e,t;
Queue Q;
Init(&Q);
while(scanf("%d",&e)==1){
if(e!=0) En(&Q,e);
else De(&Q,&t);
}
if(Empty(&Q)) printf("empty\n");
else{
while(!Empty(&Q)){
De(&Q,&t);
printf("%d ",t);
}
}
return 0;
}
5. 链队列基本操作
【问题描述】
使用带头结点的单链表实现队列，完成该队列的入队、出队、判断队空操作。
【输入形式】
输入若干个整数（以空格分隔），其中0表示做出队操作，不为0的整数为入队元素。
【输出形式】
依次输出队列的全部元素，若队列为空，则输出“empty”
【样例输入1】
1 2 3 4 5 6
【样例输出1】1 2 3 4 5 6
【样例输入2】
1 2 3 0 0 4 0 5
【样例输出2】4 5
【样例输入3】
1 0 2 0 3 0
【样例输出3】empty
【样例输入4】
1 0 2 0 0 3 0 0 0
【样例输出4】empty
【评分标准】
填充函数，实现队列的基本操作，不得增加其他函数。
#include<stdio.h>
#include<malloc.h>
typedef struct Node{
int base;
struct Node *next;
}Node,*PNode;
typedef struct Queue{
Node *front,*rear;
}Queue,*PQueue;
int Init(PQueue Q){
PNode p=(PNode)malloc(sizeof(Node));
p->next=NULL;
Q->front=Q->rear=p;
return 1;
}
int En(PQueue Q,int e){
PNode q=(PNode)malloc(sizeof(Node));
q->next=NULL;
q->base=e;
Q->rear->next=q;
Q->rear=q;
return 1;
}
int Empty(PQueue Q){
if(Q->front==Q->rear) return 1;
else return 0;
}
int De(PQueue Q,int *e){
PNode p;
p=Q->front->next;
if(Empty(Q)) return 0;
*e=p->base;
if(Q->front->next==Q->rear){
Q->front->next=NULL;
Q->rear=Q->front;
}else{
Q->front->next=p->next;
free(p);
}
return 1;
}
int main(){
Queue Q;
Init(&Q);
int e;
while(scanf("%d",&e)==1){
if(e) En(&Q,e);
else De(&Q,&e);
}
if(Empty(&Q)) printf("empty\n");
else{
while(!Empty(&Q)){
De(&Q,&e);
printf("%d ",e);
}
}
return 0;
}