《数据结构实验报告-栈和队列》由会员分享,可在线阅读,更多相关《数据结构实验报告-栈和队列(13页珍藏版)》请在金锄头文库上搜索。
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 ClearStac
4、k(SqStack *S); /*清空栈*/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-
5、stacksize=STACK_INT_SIZE; return 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 O
6、K;/*Push*/*4-出栈函数*/int Pop(SqStack *S,ElemType *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;/*GetT
7、op*/*6-清空栈函数*/int ClearStack(SqStack *S) if(InitStack(S) printf(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-b
8、ase;/*StackLength*/*10-十进制整数转换为二进制并输出函数*/void Conversion() int e; SqStack 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; In
9、itStack(&sqs); char a100,c; int i=0; printf(input :); while(c=getchar()!=n) ai+=c; for(i=0;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. Pu
10、sh Elementn, /*入栈*/ 3. Get TopElementn, /*获得栈顶元素*/ 4. Return StackLengthn, /*返回栈的长度*/ 5. Stack IsEmptyn, /*判断是否栈空*/ 6. 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); /*将输入的字符串转化为整形数*/ while (c9); /*选择项不在09之间重输*/ return c; /*返回选择项,主程序根据该数调用相应的函数*/int main() SqStack ss; int e; InitStack(&ss