数据结构实验-栈和队列基本操作

1、大 学数据结构课程实验报告实 验 名 称：栈和队列基本操作的实现及应用实验室(中心)： 学 生 信 息： 专 业 班 级： 指 导 教 师 ： 教师评阅意见： 签名： 年 月 日实验成绩：实验完成时间： 2016 年 章: 错误！文档中没有指定样式的文字。2实验二 栈和队列基本操作的实现及应用一、实验目的1. 掌握栈的顺序表示和实现2. 掌握队列的链式表示和实现二、实验内容及要求1. 编写一个程序实现顺序栈的各种基本运算。2. 实现队列的链式表示和实现。三、实验设备及软件计算机、Microsoft Visual C+ 6.0软件四、设计方案（算法设计） 采用的数据结构本程序栈数据的逻辑结构为线

2、性结构，存储结构为顺序存储；队列的数据逻辑结构依然为线性结构，存储结构为链式结构。 设计的主要思路章: 实验二 栈和队列基本操作的实现及应用151. 初始化顺序栈2. 插入元素3. 删除栈顶元素4. 取栈顶元素5. 遍历顺序栈6. 置空顺序栈7. 初始化并建立链队列8. 入链队列9. 出链队列10. 遍历链队列 算法描述1、栈Sta InitSta(SqSta &S)/构造一个空栈Sta DesSta(SqSta &S)/销毁栈Sta StaDisplay(SqSta &S)/显示栈Sta GetTop(SqSta S,Type &e) /若栈不空，则用e返回S

3、的栈顶元素，并返 回OK；否则返回ErrorSta Push(SqSta &S,Type e) /插入元素e为新的栈顶元素Sta Pop(SqSta &S,Type &e)/若栈不为空，则删除栈顶元素，用e返回其值，并返回OK；否则返回ErrorSta StaEmp(SqSta S) /若为空栈，则返回True，否则返回False。2、队列Sta InitLQ(LQ &); /初始化一个队列Sta DesLQ(LQ &); /销毁一个队列int LQLength(LQ &Q); /队列的长度Sta EnLQ(LQ &,Type); /将一

4、个元素入队列Sta DeLQ(LQ &,Type &); /将一个元素出队列Sta DisplayLQ(LQ); /显示队列中所有元素五、程序代码1、栈#include <stdio.h>#include <stdlib.h>#include <conio.h>#define True 1#define False 0#define OK 1#define Error 0#define InFea -1#define OverFlow -2typedef int Sta;typedef int Type;#define StaSize 100

5、#define StaInc 10typedef struct Type *base; Type *top; int stacksize; SqSta;Sta InitSta(SqSta &S)/构造一个空栈S.base = (Type *) malloc(StaSize*sizeof(Type);if(!S.base) exit(OverFlow); S.top = S.base;S.stacksize = StaSize;return OK;Sta DesSta(SqSta &S)/销毁栈if(S.base) free(S.base);S.top = S.base = NU

6、LL;return OK;Sta StaDisplay(SqSta &S)/显示栈Type * p=S.base;int i = 0;if(S.base = S.top) printf("提示:堆栈已空!nn"); return OK;while( p < S.top)printf("%d:%d",+i,*p+);printf("nn");return OK;Sta GetTop(SqSta S,Type &e) /若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回Errorif(S.top=S.base)

7、return Error;e=*(S.top-1);return OK;Sta Push(SqSta &S,Type e)/插入元素e为新的栈顶元素if(S.top-S.base>=S.stacksize)/栈满，追加存储空间S.base=(Type*) realloc(S.base,(S.stacksize+StaInc)*sizeof(Type);if( ! S.base ) exit(OverFlow);S.top = S.base + S.stacksize;S.stacksize += StaInc;* S.top + = e;return OK;Sta Pop(SqS

8、ta &S,Type &e)/若栈不为空，则删除栈顶元素，用e返回其值，并返回OK；否则返回Error if (S.top = S.base) return Error; e = * -S.top; return OK;Sta StaEmp(SqSta S)/若为空栈，则返回True，否则返回False。if(S.top = S.base) return True;else return False;void main()SqSta St;Sta temp;int F=1,ch;int e;printf("本程序用于实现顺序结构的堆栈的操作,可以进行入栈，出栈，取栈顶

9、元素等操作.nn");InitSta(St); while(F)printf("请输入需要进行操作的序号:nn");printf("1.显示栈中所有元素 n");printf("2.入栈操作 n");printf("3.出栈操作 n");printf("4.取栈顶元素 n");printf("5.退出程序 n");scanf("%d",&ch);switch(ch)case 1:StaDisplay(St);break;case 2:pr

10、intf("提示:请输要入栈的一个整数元素:n");scanf("%d",&e); temp=Push(St,e); /入栈运算if(temp!=OK) printf("提示:堆栈已满!入栈失败!nn");else printf("提示:成功入栈!nn"); StaDisplay(St);break;case 3:temp=Pop(St,e); /出栈运算if(temp=Error) printf("提示:堆栈已空!nn"); else printf("提示:成功出栈一个元素:

11、%dnn",e); StaDisplay(St);break;case 4:temp=GetTop(St,e); /取得栈顶元素if(temp=Error) printf("提示堆栈已空!nn");else printf("提示:栈顶元素是:%dnn",e);break;default:F=0;printf("提示:程序结束，按任意键退出!nn");getch();DesSta(St);2、队列#include <conio.h>#include <stdio.h>#include <stdli

12、b.h>#define True 1#define False 0#define OK 1#define Error 0#define InFea -1#define OverFlow -2typedef int Sta;typedef int Type;typedef struct QNode/定义结点结构 Type data; struct QNode *next; QNode,*QueuePtr;typedef struct LQ/定义队列结构 QueuePtr front; QueuePtr rear; LQ;Sta InitLQ(LQ &); /初始化一个队列Sta D

13、esLQ(LQ &); /销毁一个队列int LQLength(LQ &Q); /队列的长度Sta EnLQ(LQ &,Type); /将一个元素入队列Sta DeLQ(LQ &,Type &); /将一个元素出队列Sta DisplayLQ(LQ); /显示队列中所有元素void main()LQ LQ;Type e;int F=1,ch,len;Sta temp;printf("本程序用于实现链式结构队列的操作,可以进行入队列、出队列等操作.nn");InitLQ(LQ); while(F)printf("请输入需要进行

14、操作的序号:nn");printf("1.显示队列所有元素n");printf("2.入队列操作n");printf("3.出队列操作n");printf("4.求队列的长度n");printf("5.退出程序n");scanf("%d",&ch);switch(ch) case 1:DisplayLQ(LQ); break;case 2:printf("提示:请输入要人队的一个整数元素:n");scanf("%d",

15、&e); EnLQ(LQ,e);/入队DisplayLQ(LQ);break;case 3:temp=DeLQ(LQ,e); /出队if(temp=OK)printf("提示:出队一个元素:%dnn",e);DisplayLQ(LQ);else printf("提示:队列为空!nn");break;case 4:len=LQLength(LQ);printf("提示:队列的长度为:%dnn",len);break;default:F=0;printf("提示:程序运行结束，按任意键退出!nn");getch

16、();Sta InitLQ(LQ &Q)/队列初始化Q.front=Q.rear=(QueuePtr) malloc(sizeof(QNode); Q.front->next=NULL;return OK;Sta DesLQ(LQ &Q)/销毁一个队列QueuePtr p;Type e;while(Q.front!=Q.rear)DeLQ(Q,e);free(Q.front);Q.front=Q.rear=NULL;return OK;int LQLength(LQ &Q)/队列的长度int i=0;QueuePtr p=Q.front;while(p!=Q.re

17、ar)+i;p=p->next;return i;Sta EnLQ(LQ &Q,Type e)/入队列QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode);p->data=e; p->next=NULL;Q.rear->next=p; Q.rear=p; return OK;Sta DeLQ(LQ &Q,Type &e)/出队列QueuePtr p;if(Q.front=Q.rear) return Error; p=Q.front->next; e=p->data; Q.front->next=p->next; if(Q.rear=p) Q.rear=Q.front; return OK; Sta DisplayLQ(LQ Q)/显示队列中所有元素QueuePtr p;int i=0;p=Q.front->next;if(p=NULL)printf("提示:队列为空!nn");elsewhi