实验二 栈和队列的应用

实验目的
本次实验的目的在于使学生深入了解栈和队列的特征，掌握在实际问题背景下的灵活运用。
实验要求
正确设计和实现本程序，记录输出结果。
实验内容
1．队列的各种基本操作实现。
2．十进制数向N进制数据的转换。（栈的应用）

附：代码

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define OVERFLOW 0
#define OK 1
#define ERROR 0
//顺序栈的定义
#define STACK_INIT_SIZE 100//存储空间初始分配量
#define STACKINCREMENT 20
//存储空间分配增量
typedef int SElemType;
 //SElemType可以是任何相应的数据类型如int,float或char
typedef struct{ SElemType*base; //*base指向数组向量 SElemType*top; int stacksize; //栈的当前可使用的最大容量
}SqStack;
//-------------------------
//初始化顺序栈
int InitStack(SqStack *S){ //在此插入必要的语句 S->base=(SElemType *) malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S->base) exit(OVERFLOW); S->top = S->base; S->stacksize = STACK_INIT_SIZE; return OK;
}
//------------------------
//插入元素e为新的栈顶元素
void Push(SqStack *S,SElemType e){ //栈满，追加存储空间 //printf("####%d ",e); if(S->top-S->base>=S->stacksize){ S->base=(SElemType *) realloc(S->base , (S->stacksize + STACKINCREMENT)*sizeof(SElemType)); if(!S->base) exit(OVERFLOW); S->top = S->base+S->stacksize; S->stacksize = S->stacksize + STACKINCREMENT; } *(S->top)++ = e; //printf("****%d ",e);
}
//---------------------
int Pop(SqStack *S){//若栈不空，则删除S的栈顶元素，并将其值返回。若栈空，返回ERROR //若栈不空，则删除栈顶元素，用e返回其值 if(S->top==S->base) return ERROR; return *--(S->top);
}
//--------------
void PrintStack(SqStack *S){//顺序打印栈内元素值 int k; for(k=0;k<S->top-S->base;k++) printf("%d",S->base[k]);
}
int main(){ SqStack *S; int i,e,n; /**(初始化)函数申明 int InitStack(SqStack &S); //（进栈）函数申明 void Push(SqStack &S,SelemType e); //(出栈)函数申明 int Pop(SqStck &s); //(打印站内数据)函数申明 void PrintStack(SqStack &S); //初始化栈 **/ printf("进栈元素数量n\n"); int n1; scanf("%d",&n1); n=n1; InitStack(S); //欲建立的顺序表长度，调试阶段用指定数据，调试完后改用scanf（） // //scanf("%d",&n); printf("请输入%d个时栈元素值：",n); for(i=1;i<=n;i++){ scanf("%d",&e); Push(S,e); } printf("进栈元素依次如下：\n"); PrintStack(S); printf("\n"); //欲出栈元素个数，调试阶段用指定数据，调试完后赋值 n=2; //printf("出栈元素数量n\n"); //scanf("%d",&n); printf("\n出栈元素值依次为：\n"); for(i=1;i<=n;i++){ e=Pop(S); if(e) printf("%d",e); } printf("\n"); printf("栈内元素为 : \n"); PrintStack(S);
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
  
79
  
80
  
81
  
82
  
83
  
84
  
85
  
86
  
87
  
88
  
89
  
90
  
91
  
92
  
93
  
94
  
95
  
96
  
97
  
98
  
99
  
100
  
101
  
102
  
103
 

二进制转换为十进制代码（栈的实现）：
请用c：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#define STACK_INIT_SIZE 20
#define STACKINCREMENT 10
typedef char ElemType ;
typedef struct{ ElemType *base; ElemType *top; int stacksize;
}sqStack;

initStack(sqStack *s){ ///内存中开辟一段连续空间作为栈空间，首地址赋值给s->base s->base=(ElemType *)malloc(STACK_INIT_SIZE *sizeof(ElemType)); if(!s->base) exit(0);///分配空间失败 s->top = s->base; ///最开始，栈顶就是栈底 s->stacksize = STACK_INIT_SIZE;
}
Push(sqStack *s,ElemType e){ if(s->top - s->base >= s->stacksize){ ///栈满，追加空间 s->base =(ElemType *)realloc(s->base,(s->stacksize+STACKINCREMENT)*sizeof(ElemType)); ///分配失败 if(!s->base)exit(0); s->top=s->base+s->stacksize; ///设置栈的最大容量 s->stacksize=s->stacksize + STACKINCREMENT ; } *(s->top)=e; ///放入数据 s->top++; ///top指向下个地址
}
int StackLen(sqStack s){ return (s.top-s.base);
}
Pop(sqStack *s,ElemType *e){ if(s->top==s->base) return ; *(s->top--); *e=*(s->top); ///*e=*--s->top;
}
DestroyStack(sqStack *s){ free(s->base); ///释放掉内存空间 s->base = s->top = NULL; ///栈底栈顶指针置NULL s->stacksize = 0; ///设置栈的最大容量为0
}

int main(){ ElemType c; sqStack s; int len,i,sum=0; printf("Please input a Binary digit（输入二进制数，以‘#’结束）：\n"); initStack(&s); ///创建一个栈，用来存放二进制字符串 ///输入0/1字符表示的二进制数，以#结束 scanf("%c",&c); while(c!='#'){ Push(&s,c); scanf("%c",&c); } getchar(); ///得到栈中的元素个数，即二进制数的长度 len = StackLen(s); for(i=0;i<len;i++){ Pop(&s,&c); sum+=(c-48)*pow(2,i); ///转换为十进制 } printf("Decimal is %d\n",sum); DestroyStack(&s); ///释放栈空间 getchar();
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
  
79
  
80
 

文章来源: chenhx.blog.csdn.net，作者：谙忆，版权归原作者所有，如需转载，请联系作者。

原文链接：chenhx.blog.csdn.net/article/details/49592525