数据结构栈和队列C语言实现

1、数学与信息技术学院20162017（下）学年计科专业2015级数据结构实验报告 4 学号： 姓名：汪继超实验名称栈的应用完成时间2017.05.03一实验目的和要求：一 掌握栈和队列的概念及其两种数据结构的特点，懂得在什么样的问题中应用利用哪种结构。二 熟练掌握在两种存储结构上实现栈的基本运算，特别注意栈满及栈空的条件及它们的描述方法。掌握两个顺序栈共享存储空间的概念。三 熟练掌握循环队列和链队列的基本运算，特别注意队满和队空的描述方法。四 加强编辑与调试C语言程序的能力。二.实验原理 栈和队列是两种特殊的线性表。栈是限定只能在表的一端进行插入和删除的线性表，它又称为“后进先出”表；队列则是限

2、定只能在表的一端进行插入，在表的另一端进行删除的线性表，它又称为“先进先出”表。由于栈和队列都是线性表的一种特例，所以它们都可以使用顺序存储结构和链式存储结构，栈的顺序存储结构称为顺序栈，栈的链式存储结构称为链栈；而队列的顺序存储结构称为顺序队列，队列的链式存储结构称为链队。顺序存储结构可用一维数组来实现，而链式存储结构可用指针来实现。三.实验内容假设称正读和反读都相同的字符序列为“回文”，试写一个算法判别读入的一个以”为结束符的字符序列是否是“回文”。实验过程：/*注：此程序为栈的操作实现与应用*/#include#include#include#include#include#define

3、 STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef int SElemType;typedef int QElemType;/*栈的存储结构*/typedef structSElemType *base; /*栈低指针*/SElemType *top; /*栈顶指针*/int stacksize; /*栈当前已分配的所有空间，不是已使用的空间长度*/SqStack;/*start*队列的存储结构*/typedef struct QNodeQElemType data; struct QNode *next;QNode,*QueuePtr;t

4、ypedef structQueuePtr front;QueuePtr rear;LinkQueue;/*队列的存储结构*end*/*函数声明*/SElemType GetTop(SqStack *S);void Push(SqStack *S,SElemType e);bool SEmpty(SqStack *S);SElemType Pop(SqStack *S);void main();/括号匹配-startvoid match(SqStack *S)char str20;int i=0,flag;fflush(stdin);printf(n Please enter a string

5、: );scanf(%s,&str);while(stri!=0&flag!=0)switch(stri)case (:Push(S,();break;case ):if(*(S-top-1)=()flag=1;Pop(S);else flag=0;break;case :Push(S,);break;case :if(*(S-top-1)=)flag=1;Pop(S);else flag=0;break;case :Push(S,);break;case :if(*(S-top-1)=)flag=1;Pop(S);else flag=0;break;default :flag=0;break

6、;i+;if(flag=1)&(SEmpty(S)=0)printf(n success!n);else printf(n error!n);/括号匹配-end/Queue逆置-startLinkQueue * InitQ()LinkQueue *Q;Q=(LinkQueue *)malloc(sizeof(LinkQueue);Q-front=Q-rear=(QueuePtr)malloc(sizeof(QNode);if(!Q-front) exit(1);Q-front-next=NULL;printf(Successful Q!);return Q;void EnQ(LinkQueue

7、 *Q,QElemType e) /入队QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode);if(!p) exit(1);p-data=e;p-next=NULL;Q-rear-next=p;Q-rear=p;int DeQ(LinkQueue *Q) /出队int e;QueuePtr p;if(Q-front=Q-rear) return 0;elsep=Q-front-next;e=p-data;Q-front-next=p-next;if(Q-rear=p) Q-rear=Q-front;free(p);return e;void algo3(Lin

8、kQueue *Q,SqStack *S) /逆置int d;while(!(Q-front=Q-rear)d=DeQ(Q);Push(S,d);while(SEmpty(S) EnQ(Q,Pop(S);void tes(LinkQueue *Q,SqStack *S) /逆置主调函数int i,e,n;printf(n您要输入的数据条数是：);scanf(%d,&n);printf(n请输入需逆置数据：);for(i=0;ifront=Q-rear)printf(%3d,DeQ(Q);printf(n);free(Q);/Queue逆置-end/回文-startvoid Huiwen(Lin

9、kQueue *Q,SqStack *S)char str20;int i=0,flag;fflush(stdin);printf(n Please enter a string: );scanf(%s,&str);while(stri!=0)Push(S,stri);EnQ(Q,stri);i+;while(SEmpty(S)&flag!=0)if(DeQ(Q)=Pop(S) flag=1;else flag=0;if(flag=1)printf(n success!n);else printf(n error!n);/回文-endSqStack * InitStack() /*1.初始化栈

10、*/SqStack *S;S=(SqStack *)malloc(sizeof(SqStack);S-base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S | !S-base) exit(1);S-top=S-base;S-stacksize=STACK_INIT_SIZE;return S;bool SEmpty(SqStack *S) /*2.判栈空*/if(S-top=S-base)return 0;else return 1; /*1表示栈不空*/void Push(SqStack *S,SElemType e

11、) /*3.入栈*/if(S-top-S-base = S-stacksize )S-base=(SElemType *)realloc(S-base,(S-stacksize+STACKINCREMENT)*sizeof(SElemType);if(!S-base) exit(1);printf(n空间不够，开辟新空间成功！n);S-top=S-base+S-stacksize;S-stacksize +=STACKINCREMENT;*S-top+=e;SElemType Pop(SqStack *S) /*4.出栈*/if(S-top=S-base)return 0;printf(nTh

12、e sequence stack is empty!);else return *(-S-top);void display(SqStack *S) /*5.打印*/int e;SqStack *T;T=InitStack(); /*1.新构建一个栈T*/while(SEmpty(S)e=Pop(S);Push(T,e);/*2.将出栈打印的元素入栈T*/printf(%5d,e); /*当栈不空依次打印*/while(SEmpty(T) Push(S,Pop(T);/*3.将栈T中元素出栈并入栈到栈S中*/free(T);printf(n);int StackLength(SqStack *

13、S) /*6.统计栈长度*/printf(n统计得栈的长度为：%dn,(S-top-S-base);return (S-top-S-base);void search(SqStack *S,SElemType e) /*7.查找*/int count=0,flag=0;SqStack *T;T=InitStack();while(SEmpty(S)if(e=GetTop(S)count+;flag=1;printf(n%d 已找到元素：%dn,count,e);Push(T,Pop(S);while(SEmpty(T) Push(S,Pop(T);free(T);if(flag=0) prin

14、tf(n没有找到元素：%dn,e);void modify(SqStack *S,SElemType e) /*8.修改*/int e1,count=0,flag=0,a;SqStack *T;T=InitStack();while(SEmpty(S)if(e=GetTop(S) count+;flag=1;printf(n%d 已找到元素：%dn,count,e);printf(n1.修改 2.不修改：);scanf(%d,&a);switch(a)case 1:e1=Pop(S);printf(n将元素%d修改为：,e); scanf(%d,&e1);Push(S,e1);printf(n

15、修改成功！n);/除输入1之外的情况都不做任何操作Push(T,Pop(S);while(SEmpty(T) Push(S,Pop(T);free(T);if(flag=0) printf(n没有找到元素：%dn,e);void ClearStack(SqStack *S) /*9.清空栈*/S-top=S-base;printf(n清空栈成功！n);void DestoryStatck(SqStack *S) /*10.销毁栈*/ S-top=S-base; free(S-base); S-base=NULL; S-top=NULL;S-stacksize=0;free(S); printf

16、(n销毁栈成功！n); SElemType GetTop(SqStack *S) /*11.取栈顶元素*/if(S-top=S-base)printf(nThe sequence stack is empty!n);return 0;else return *(S-top-1); /*区别于Pop中的*-S-top,*(S-top-1)不改变S-top指针的指向*/进制转换模块-startvoid jinzhizhuanhuan(SqStack *S)char a;int n,x,x1,q;dodosystem(cls);printf( 欢迎来到十进制转换为二至九进制桟运算中心nn);prin

17、tf(请输入您要转换为的进制数2-9：);fflush(stdin);scanf(%d,&n);if(n9|n9|n=0 & n=11) flag=1;elseflag=0;system(cls); printf(您输入有误，请重新选择!n);while(flag=0);while(flag=1)switch(n) /*当程序执行到这里时，表明跳出上一个do-while */case 1:S=InitStack();printf(n初始化栈成功！n);break; /*1.初始化栈，因为程序一开始做了初始化，所以这里是做重复工作，仅只是作为初学者强调栈初始化概念！*/case 2:c=SEmp

18、ty(S);if(c=0) printf(n当前栈为空！n);else printf(n当前栈不为空！n);break; /*2.判栈空*/case 3:printf(n请输入您要入栈的元素条数：);scanf(%d,&n);if(n=0)printf(n输入不合法！n);break;printf(n请依次输入入栈的元素：);for(i=0;itop=S-base) printf(nThe sequence stack is empty!n);else printf(n元素%d已出栈！n,Pop(S);break; /*4.出栈*/case 5:printf(n栈当前数据：);display(

19、S);break; /*5.打印*/case 6:StackLength(S);break; /*6.统计栈长度*/case 7:printf(n请输入您要查找的元素：);scanf(%d,&e);search(S,e);break; /*7.查找*/case 8:printf(n请输入您要修改的元素：);scanf(%d,&e);modify(S,e);break; /*8.修改*/case 9:ClearStack(S);break; /*9.清空栈*/case 10:DestoryStatck(S);break; /*10.销毁栈*/case 11:if(S-top=S-base) pr

20、intf(nThe sequence stack is empty!n);else printf(n取得栈顶元素：%d n,GetTop(S);break; /*11.取栈顶元素*/case 0:main();break;default:printf(n您输入有误，请重新选择!n);break;/goto start;printf(n是否继续进行(y or n): );fflush(stdin);/清空在此前输入缓冲区a=getchar();if(a=y|a=Y)flag=1;system(cls); /*清屏*/Menu2(); /*调用菜单函数*/printf(请再次选择你需要操作的步骤(

21、0-11): );fflush(stdin); /清空在此前输入缓冲区scanf(%d,&n);else flag=0;/栈的全部操作实现模块-endvoid Menu() printf( 欢迎使用栈的操作实现与应用系统 nn);printf( *菜单*n); printf( * 1.栈运算之十进制整数转换 2.栈的操作实现 *n); printf( * 3.逆置实现 4.括号匹配 *n); printf( * 5.回文检测 0.退出 *n);printf( *n); void main()char b;int n;LinkQueue *Q;Q=InitQ();SqStack *S;S=InitStack();system(color 0A);system(title 汪继超:);while(b!=0)system(cls);Menu();printf(n请选择你需要操作的步骤(0-4): );fflush(stdin); /*清空在此前输入缓冲区*/scanf(%d,&n);switch(n)case 1:jinzhizhuanhuan(S);break;c