《数据结构实验报告-栈和队列39120.pdf》由会员分享，可在线阅读，更多相关《数据结构实验报告-栈和队列39120.pdf（13页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、-实验三栈和队列【实验目的】1、掌握栈的构造特性及其入栈，出栈操作；2、掌握队列的构造特性及其入队、出队的操作，掌握循环队列的特点及其操作。3、理解掌握递归调用程序设计思想。【实验学时】4 学时【实验预习】答复以下问题：1、栈的顺序存储表示 2、单链队列的存储表示 3、循环队列的顺序存储表示【实验容和要求】1、按照要求完成程序 e*p3_1.c，实现顺序栈的相关操作。以下具有返回值的函数，假设操作完成，返回 OK，操作失败返回 ERROR。函数需返回的其他数据，使用函数参数返回。调试及测试数据并给出结果：初始化栈；连续进栈 3，5，7，9，13；获取当前栈顶元素；返回当前栈长度；判断当前栈是否
2、为空；栈元素依次出栈；判断当前栈是否为空；清空栈；利用栈实现数制转换，测试整数 8 和 255；判断表达式括号是否匹配，测试以下三个表达式：表达式 1：1*(2+3)/4；表达式 2：(3+4)*7-(8-9)；表达式 3：(1+2)*(3+4)-(5+6)*3)e*p3_1.c 局部代码如下：#include#include#include-#define ERROR 0#define OK 1#define STACK_INT_SIZE 10 /*存储空间初始分配量*/#define STACKINCREMENT 5 /*存储空间分配增量*/typedef int ElemType;/*定
3、义元素的类型*/*1-补充栈的顺序存储分配表示，采用定长和可变长度存储均可*/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 PopSq(SqStack*S);int GetTop(SqStack*S,ElemType*e);/*获取栈顶元素*/int ClearStack(SqStack*S);/
4、*清空栈*/int StackEmpty(SqStack*S);/*判断栈是否为空*/int StackLength(SqStack*S);/*求栈的长度*/void conversion();/*十进制转换为二进制*/void Correct();/*判断表达式括号是否匹配*/*2-初始化栈函数*/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;retu
5、rn OK;/*InitStack*/*3-入栈函数*/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*/*4-出栈函数*/int Pop(SqStack*S,El
6、emType*e)if(S-top=S-base)return ERROR;-S-top;*e=*S-top;return OK;/*Pop*/int PopSq(SqStack*S)if(S-top=S-base)return ERROR;-S-top;return OK;/*5-返回栈顶元素函数*/int GetTop(SqStack*S,ElemType*e)if(S-top=S-base)return ERROR;*e=*(S-top-1);return OK;/*GetTop*/*6-清空栈函数*/int ClearStack(SqStack*S)if(InitStack(S)pri
7、ntf(Init Success!);return OK;-else printf(Init Fail!);return ERROR;/*ClearStack*/*8-判断栈是否为空*/int StackEmpty(SqStack*S)if(S-base=S-top)return OK;else return ERROR;/*StackEmpty*/*9-返回栈的长度函数*/int StackLength(SqStack*S)return S-top-S-base;/*StackLength*/*10-十进制整数转换为二进制并输出函数*/void Conversion()int e;SqSta
8、ck sq;InitStack(&sq);int count;printf(input count:);scanf(%d,&count);while(count!=0)Push(&sq,count%2);count=count/2;while(Pop(&sq,&e)printf(%d,e);/*Conversion*/*11-判断表达式括弧是否匹配假设只有一种小括弧函数*/void Correct()SqStack sqs;InitStack(&sqs);-char a100,c;int i=0;printf(input:);while(c=getchar()!=n)ai+=c;for(i=0
9、;istrlen(a);i+)if(ai=()Push(&sqs,ai);if(ai=)PopSq(&sqs);if(StackEmpty(&sqs)printf(OK!);else printf(error!);/*Correct*/*定义菜单字符串数组*/int menu_select()char*menu=n*MENU*n,1.Init Satckn,/*初始化顺序栈*/2.Push Elementn,/*入栈*/3.Get TopElementn,/*获得栈顶元素*/4.Return StackLengthn,/*返回栈的长度*/5.Stack IsEmptyn,/*判断是否栈空*/6
10、.Pop Elementn,/*出栈*/7.Clear Stackn,/*清空栈*/8.Conversionn,/*利用栈进展数制转换*/9.Correctn,/*利用栈进展括号匹配*/0.Quitn,/*退出*/n*MENU*n ;char s3;/*以字符形式保存选择号*/int c,i;/*定义整形变量*/for(i=0;i11;i+)/*输出主菜单数组*/-printf(%s,menui);do printf(nEnter you choice(09):);/*在菜单窗口外显示提示信息*/scanf(%s,s);/*输入选择项*/c=atoi(s);/*将输入的字符串转化为整形数*/w
11、hile(c9);/*选择项不在 09 之间重输*/return c;/*返回选择项，主程序根据该数调用相应的函数*/int main()SqStack ss;int e;InitStack(&ss);for(;)switch(menu_select()case 1:printf(n1-Init Satck:n);if(InitStack(&ss)printf(Init OK!n);else printf(Init ERROR!n);break;case 2:printf(n2-Push Element:n);printf(input data(Terminated by inputing a
12、 character):);while(scanf(%d,&e)=1)if(Push(&ss,e)printf(Push%d OK!n,e);else printf(Push%d ERROR!n,e);printf(input data:(Terminated by inputing a character);getchar();break;case 3:printf(n3-Get TopElement:n);if(GetTop(&ss,&e)printf(Top is%d,e);else-printf(Stack is Empty!);break;case 4:printf(n4-Retur
13、n StackLength:n);printf(StackLength is%d,StackLength(&ss);break;case 5:printf(n5-Stack IsEmpty:n);if(StackEmpty(&ss)printf(Stack is Empty!);else printf(Stack is not Empty!);break;case 6:printf(n6-Pop Element:n);if(StackEmpty(&ss)printf(Stack is Empty!);else printf(All elements of Stack:);while(Pop(&
14、ss,&e)printf(%d,e);break;case 7:printf(n7-ClearStack:n);ClearStack(&ss);printf(ClearStack OK!);break;case 8:printf(n8-Conversion:n);Conversion();break;case 9:printf(n9-Correct:n);getchar();-Correct();break;case 0:e*it(0);return 0;2、按照要求完成程序 e*p3_2.c，实现循环队列的相关操作。以下具有返回值的函数，假设操作完成，返回 OK，操作失败返回 ERROR。函
15、数需返回的其他数据，使用函数参数返回。调试及测试数据并给出结果：初始化队列；返回当前队列长度；连续入队 2，4，6，8，10；获取当前队头元素；返回当前队列长度；判断当前队列是否为空；队列元素依次出队；判断当前队列是否为空；e*p3_2.c 局部代码如下：#include#include#define ERROR 0#define OK 1#define MA*QSIZE 100 typedef int QElemType;/*定义元素的类型*/*1-循环队列顺序存储表示*/typedef struct QElemType*base;int front;int rear;SqQueue;/*2
16、-构造一个空循环队列*/int InitQueue(SqQueue*Q)Q-base=(QElemType*)malloc(MA*QSIZE*sizeof(QElemType);if(!Q-base)return ERROR;Q-front=Q-rear=0;return OK;-/*InitQueue*/*3-返回循环队列的长度*/int QueueLength(SqQueue*Q)return Q-rear-Q-front;/*QueueLentgh*/*4-入队操作*/int EnQueue(SqQueue*Q,QElemType e)if(Q-rear+1)%MA*QSIZE=Q-fr
17、ont)return ERROR;Q-baseQ-rear=e;Q-rear=(Q-rear+1)%MA*QSIZE;return OK;/*EnQuese*/*5-出队操作*/int DeQueue(SqQueue*Q,QElemType*e)if(Q-front=Q-rear)return ERROR;*e=Q-baseQ-front;Q-front=(Q-front+1)%MA*QSIZE;return OK;/*DeQueue*/*6-判断队列是否为空*/int QueueEmpty(SqQueue*Q)if(Q-rear=Q-front)return OK;else return E
18、RROR;/*QueueEmpty*/*7-取队头元素*/int GetHead(SqQueue*Q,QElemType*e)if(Q-rear=Q-front)/队列空的判断-return ERROR;*e=Q-baseQ-front;/将队头元素赋值给 e Q-front=(Q-front+1)%MA*QSIZE;/front 指针向后一位置，假设到最后，则转到数组头部 return OK;/*GetHead*/*销毁队列*/int DestroyQueue(SqQueue*Q)if(Q-base)Q-rear=Q-front=0;free(Q-base);return OK;/*Dest
19、royQueue*/*定义菜单字符串数组*/int menu_select()char*menu=n*MENU*n,1.Init Queuen,/*初始化循环队列*/2.Get QueueLengthn,/*求队列的长度*/3.EnQueuen,/*入队操作*/4.Get Headn,/*取队头元素*/5.Queue IsEmptyn,/*判断是否队空*/6.DeQueuen,/*出队操作*/0.Quitn,/*销毁队列并退出*/n*MENU*n ;char s3;int c,i;for(i=0;i=8;i+)printf(%s,menui);do printf(nEnter you choi
20、ce(06):);scanf(%s,s);c=atoi(s);while(c6);return c;-/*主函数*/int main()SqQueue qq;int e;InitQueue(&qq);for(;)switch(menu_select()case 1:printf(n1-Init Queue:n);if(InitQueue(&qq)printf(Init OK!n);else printf(Init ERROR!n);break;case 2:printf(n2-Get QueueLength:n);printf(Queue length is%d,QueueLength(&qq
21、);break;case 3:printf(n3-EnQueue:n);printf(please input data:);scanf(%d,&e);if(EnQueue(&qq,e)printf(%d EnQueue OK!n,e);else printf(EnQueue Error!n);break;case 4:printf(n4-Get Head:n);if(GetHead(&qq,&e)printf(Head is%dn,e);else printf(Get Head Error!n);break;case 5:printf(n5-QueueEmpty:n);if(QueueEmp
22、ty(&qq)printf(Queue is Empty!);else printf(Queue is not Empty);break;-case 6:printf(n6-DeQueue:n);printf(Queue is:);while(!QueueEmpty(&qq)if(DeQueue(&qq,&e)printf(%d,e);break;case 0:DestroyQueue(&qq);e*it(0);return 0;3、递归汉诺塔问题 利用递归算法程序设计编写程序 e*p3_3.c，解决 n 阶汉诺塔问题A 柱为起始，C 柱为目的。请将程序补充完整，并分别调试盘子数为 3，7 的
23、情况。e*p3_3.c 局部代码如下：#include int step=1;void hanoi(char A,int n,char B,char C)if(n=1)printf(第%d 步：n,step+);printf(将%c 柱子上唯一的 1 个盘子移到%c 柱子！n,A,C);else printf(先将%c 柱子上的多余的%d 个盘子移到%c 柱子中过程：n,A,n-1,B);hanoi(A,_n-1_,C,_B_);printf(第%d 步：n,step+);printf(将%c 柱子上的最大的盘子移到%c 柱子中！n,A,C);printf(接下来将%c 柱子上的%d 个盘子移
24、到%c 柱子中过程：n,B,n-1,C);hanoi(B,_n-1_,A,_C_);int main()int n;-char A,B,C;A=A;B=B;C=C;printf(输入 A 柱子上盘子的个数：);scanf(%d,&n);hanoi(A,n,B,C);printf(n 移动完毕);return 0;4、拓展实验：设计程序实现简单四则算术运算。要求说明：1从键盘接收算术表达式，以#表示接收完毕；2输出算术表达式的值；3操作数仅限于非负整数，操作符只能是+、-、*、/、4可以判断表达式的合法性如括号的匹配 提示：借助栈来完成，将一个表达式转换为后缀表达式，并按照后缀表达式进展计算，得出表达式得结果。【实验小结】