《数据结构》实验指导及报告书
2014 / 2015 学年 第 1学期
姓 名：
学 号：
班 级：
******
计算机科学与工程学院
2014
实验二 栈和队列
一、实验目的
1、掌握栈的结构特性及其入栈，出栈操作；
2、掌握队列的结构特性及其入队、出队的操作，掌握循环队列的特点及其操作。
二、实验内容和要求
1、阅读下面程序，将函数Push和函数Pop补充完整。要求输入元素序列1 2 3 4 5 e，运行结果如下所示。
#include #include #define ERROR 0 #define OK 1 #define STACK_INT_SIZE 10 /*存储空间初始分配量*/ #define STACKINCREMENT 5 /*存储空间分配增量*/ typedef int ElemType; /*定义元素的类型*/ typedef struct{ ElemType *base; ElemType *top; int stacksize; /*当前已分配的存储空间*/ }SqStack; int InitStack(SqStack *S); /*构造空栈*/ int push(SqStack *S,ElemType *e); /*入栈*/ int Pop(SqStack *S,ElemType *e); /*出栈*/ int CreateStack(SqStack *S); /*创建栈*/ void PrintStack(SqStack *S); /*出栈并输出栈中元素*/ int InitStack(SqStack *S){ S->base=(ElemType *)malloc(STACK_INT_SIZE *sizeof(ElemType)); if(!S->base) return ERROR; S->top=S->base; S->stacksize=STACK_INT_SIZE; return OK; }/*InitStack*/ int Push(SqStack *S,ElemType e){ }/*Push*/ int Pop(SqStack *S,ElemType *e){ }/*Pop*/ int CreateStack(SqStack *S){ int e; if(InitStack(S)) printf("Init Success!\\n"); else{ printf("Init Fail!\\n"); return ERROR; } printf("input data:(Terminated by inputing a character)\\n"); while(scanf("%d",&e)) Push(S,e); return OK; }/*CreateStack*/ void PrintStack(SqStack *S){ ElemType e; while(Pop(S,&e)) printf("%3d",e); }/*Pop_and_Print*/ int main(){ SqStack ss; printf("\\n1-createStack\\n"); CreateStack(&ss); printf("\\n2-Pop&Print\\n"); PrintStack(&ss); return 0; } ●算法分析：输入元素序列1 2 3 4 5，为什么输出序列为5 4 3 2 1？体现了栈的什么特性？ #include #include #define ERROR 0 #define OK 1 #define STACK_INT_SIZE 10 /*存储空间初始分配量*/ #define STACKINCREMENT 5 /*存储空间分配增量*/ typedef int ElemType; /*定义元素的类型*/ typedef struct{ ElemType *base; ElemType *top; int stacksize; /*当前已分配的存储空间*/ }SqStack; int InitStack(SqStack *S); /*构造空栈*/ int Push(SqStack *S,ElemType *e); /*入栈*/ int Pop(SqStack *S,ElemType *e); /*出栈*/ int CreateStack(SqStack *S); /*创建栈*/ void PrintStack(SqStack *S); /*出栈并输出栈中元素*/ int InitStack(SqStack *S){ S->base=(ElemType *)malloc(STACK_INT_SIZE *sizeof(ElemType)); if(!S->base) return ERROR; S->top=S->base; S->stacksize=STACK_INT_SIZE; return OK; }/*InitStack*/ int 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) return ERROR; S->top=S->base+S->stacksize; S->stacksize+=STACKINCREMENT; } *S->top++=e; return OK; }/*Push*/ int Pop(SqStack *S,ElemType *e){ if(S->top=S->base)return ERROR; e= --S->top; return OK; }/*Pop*/ int CreateStack(SqStack *S){ int e; if(InitStack(S)) printf("Init Success!\\n"); else{ printf("Init Fail!\\n"); return ERROR; } printf("input data:(Terminated by inputing a character)\\n"); while(scanf("%d",&e)) Push(S,e); return OK; }/*CreateStack*/ void PrintStack(SqStack *S){ ElemType e; while(Pop(S,&e)) printf("%3d",e); }/*Pop_and_Print*/ int main(){ SqStack ss; printf("\\n1-createStack\\n"); CreateStack(&ss); printf("\\n2-Pop&Print\\n"); Pop(&ss, &e); PrintStack(&ss); return 0; } 2、在第1题的程序中，编写一个十进制转换为二进制的数制转换算法函数（要求利用栈来实现），并验证其正确性。 ●实现代码 #include #include #define ERROR 0 #define OK 1 #define STACK_INIT_SIZE 10 /*存ä?储ä¡é空?间?初?始º?分¤?配?量¢?*/ #define STACKINCREMENT 5 /*存ä?储ä¡é空?间?分¤?配?增?量¢?*/ typedef int SElemType; /*定¡§义°?元a素?的Ì?类¤¨¤型¨ª*/ typedef struct { SElemType *base; SElemType *top; int stacksize; }SqStack; int InitStack(SqStack &S); int CreateStack(SqStack *S); int GetTop(SqStack S,SElemType &e); int Push(SqStack &S,SElemType e); int Pop(SqStack &S,SElemType &e); void conversion(); void main() { int e; SqStack S; CreateStack(S); GetTop( S, e); Push( S, e); conversion(); } int InitStack(SqStack &S) { S.base=(SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType)); if(!S.base)return ERROR; S.top=S.base; S.stacksize=STACK_INIT_SIZE; } int CreateStack(SqStack &S) { int e; if(InitStack(S)) printf("Init Success!\\n"); else{ printf("Init Fail!\\n"); return ERROR; } printf("input data:(Terminated by inputing a character)\\n"); while(scanf("%d",&e)) Push(S,e); return OK; } int GetTop(SqStack S,SElemType &e) { if(S.top==S.base) return ERROR; e=*(S.top-1); return OK; } int Push(SqStack &S,SElemType e) { if(S.top-S.base>=S.stacksize) { S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType)); if(!S.base)return ERROR; S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } } int Pop(SqStack &S,SElemType &e) { if(S.top==S.base)return ERROR; e= *--S.top; return OK; } void conversion() { int n,e; SqStack S; printf("input data:\\n"); scanf("%d",n); while(n) { Push(S,n); n=n/2; } Pop(S,e); printf("%d",e); } 3、阅读并运行程序，并分析程序功能。 #include #include #include #define M 20 #define elemtype char typedef struct { elemtype stack[M]; int top; } stacknode; void init(stacknode *st); void push(stacknode *st,elemtype x); void pop(stacknode *st); void init(stacknode *st) { st->top=0; } void push(stacknode *st,elemtype x) { if(st->top==M) printf("the stack is overflow!\\n"); else { st->top=st->top+1; st->stack[st->top]=x; } } void pop(stacknode *st) { st->top=st->top-1; } int main() { char s[M]; int i; printf("create a empty stack!\\n"); stacknode *sp; sp=malloc(sizeof(stacknode)); init(sp); printf("input a expression:\\n"); gets(s); for(i=0;i if(s[i]=='(') push(sp,s[i]); if(s[i]==')') pop(sp); } if(sp->top==0) printf("'('match')'!\\n"); else printf("'('not match')'!\\n"); return 0; } ●输入：2+((c-d)*6-(f-7)*a)/6 ●运行结果： ●输入：a-((c-d)*6-(s/3-x)/2 ●运行结果： ●程序的基本功能： 以下为选做实验： 4、设计算法，将一个表达式转换为后缀表达式，并按照后缀表达式进行计算，得出表达式得结果。 ●实现代码 5、假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点（不设队头指针），试编写相应的置空队列、入队列、出队列的算法。 实现代码： 三、实验小结 四、教师评语下载本文
