《堆栈和队列的基本操作》由会员分享，可在线阅读，更多相关《堆栈和队列的基本操作（14页珍藏版）》请在金锄头文库上搜索。
1、实践教学*1* *1* *1*、t*、t*、t*、t*、t*、t*、! *1* *1* *1*询州坯7犬学软件学院2012学年秋季学期上机实验 扌报告册课程名称：实验名称：指导教师：小组成员：*堆栈和队列的基本操作（上机二）一 实验目的1. 熟悉栈这种特殊现行结构特性；2. 熟悉并掌握栈在顺序存储结构和链表存储结构下的基本运算；3. 熟悉队列这种特殊线性结构的特性；4. 熟悉掌握队列在链表存储结构下的基本运算；二 实验原理堆栈顺序存储结构下的基本算法堆栈链式存储结构下的基本算法队列顺序存储结构下的基本算法队列顺序存储结构下的基本算法1、堆栈的定义：堆栈是一种只允许在表的一端进行插入和删除运算的
2、特殊 的线性表。允许进行插入和删除运算的一端称为栈顶，另一端称为栈底，当 链表中没有元素时，称为空栈。2、堆栈的插入运算称为入栈或者进栈，删除运算称为出栈或者退栈，栈顶 的当前位置是动态的，标识栈顶当前位置的指针称为栈顶指针。每次进栈的 数据元素都放在原当前栈顶元素之前成为新的栈顶元素，每次退栈的数据元 素都是原当前栈顶元素，最后进入堆栈的数据元素总是最先退出堆栈。3、堆栈的存储结构：（1） 顺序存储结构：栈的顺序存储结构称为顺序栈。顺序栈的本质是顺 序表的简化。（2） 链式存储结构：栈的链式存储结构称为链栈，通常用单链表示。链 栈的插入和删除操作只需处理栈顶的情况。4、队列的定义：队列是允许
3、在表的一端进行插入，而在表的另一端进行删 除的特殊线性表。允许进行插入的一端称为队尾，允许进行删除的一端称为 队头。队列的插入运算称为进队或者入队，删除运算称为出队或者离队，因 此队列又称为先进先出表。5、队列的存储结构 队列的存储结构同线性表一样，可以分为顺序结构和链式结构。（1） 顺序存储结构：用顺序存储结构存储队列称为顺序队列。顺序队列会出 现假溢出问题，解决办法是用首尾相接的书顺序存储结构，称为循环队列。在队 列中，只要涉及队头或者队尾指针的修改都要对其求模。（2） 链式存储结构：用链式存储结构存储的队列称为链队列。链队列的基本 操作的实现基本上也是单链表操作的简化。通常附设头结点，并
4、设置队头指针指 向头结点，队尾指针指向终端结点。插入数据时只考虑在链队列的尾部进行，删 除数据时只考虑在链队列的头部进行。三 实验内容进行堆栈（包括顺序结构、链式结构）和队列的基本操作：初始化栈、判 断栈空、出栈、取出栈顶元素、入栈、显示栈中所有元素等运算。四 程序代码：链式队列：#include#include#define NULL 0 typedef int QElemType;typedef struct QNodeQElemType data; struct QNode *next; QNode,*QueuePtr;typedef structQueuePtr front;Queue
5、Ptr rear;LinkQueue;void CreateQueue(LinkQueue *Q) int a;QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode);if(!p) prin tf(“ 创建失败);else p-next=NULL;Q-front=p;Q-rear=p; scanf(%d,&a);while(a!=-1) p=(QueuePtr)malloc(sizeof(QNode); p-next=NULL;if(!p) prin tf(“ 创建失败);else p-data=a;Q-rear-next=p;Q-rear=p;scanf(%
6、d,&a);void PrintfQueue(LinkQueue *Q)QueuePtr p;for(p=Q-front-next;p!=NULL;p=p-next)printf( %d,p-data);void EnQueue(LinkQueue *Q,QElemType x)QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode); if(!p) prin tf(“ 创建失败);else p-data=x;p-next=NULL;Q-rear-next=p;Q-rear=p;void DeQueue(LinkQueue *Q,QElemType *f) Qu
7、euePtr p;if(Q-front=Q-rear) printf(nError); else p=Q-front-next;*f=p-data; Q-front-next=p-next;if(Q-rear=p) Q-rear=Q-front; free(p);void DeleteQueue(LinkQueue *Q) QueuePtr p;for(;Q-front!=NULL;free(p) p=Q-front;Q-front=Q-front-next;void main() int *f,e;LinkQueue Queue,*Q;e=0;f=&e;Q=&Queue;prin tf( n
8、*输入队列的元素依次为:*n); printf(n (直到用户输入数字-1为止)n);CreateQueue(Q); printf(n初始队列为:)；PrintfQueue(Q);printf(n要入队的元素为:)； scanf(%d,&e)；EnQueue(Q,e)； printf(n入队后的队列为:)；PrintfQueue(Q)；DeQueue(Q,f)； printf(n出队的元素为:)； printf(%d,e)；printf(n出队后的队列为:)； PrintfQueue(Q)； printf(n)；DeleteQueue(Q)； printf(n)；链式栈：#include #i
9、nclude typedef int ElemType； typedef struct linknodeElemType data；/数据域struct linknode *next； /指针域LiStack； /链栈类型的定义 /初始化栈 void InitStack(LiStack *&s) s=(LiStack *)malloc(sizeof(LiStack)； s-next=NULL；/销毁栈 void ClearStack(LiStack *&s) LiStack *p=s-next； while(p!=NULL)free(s)； s=p； p=p-next；free(s)； /求战
10、的长度void StackLength(LiStack *s)int i=0;LiStack *p; p=s-next;while(p!=NULL)i+; p=p-next;prin tf(目前此栈的长度为：dn,i);/判断栈是否为空栈void StackEmpty(LiStack *s)if(s-next=NULL)printf(目前此栈是空栈n);elseprintf(目前此栈不是空栈n);/进栈void Push(LiStack *&s,ElemType e)LiStack *p;p=(LiStack *)malloc(sizeof(LiStack); p-data=e;p-next二
11、s-next;/插入*p结点作为第一个数据结点s-next=p;/出栈void Pop(LiStack *&s,ElemType &e)LiStack *p;if(s-next=NULL)printf(目前此栈是空栈，此次出栈失败了！ n);elsep=s-next; /p指向第一个数据结点 e=p-data;s-next=p-next;free(p);prin tf(此次出栈成功，出栈元素是:dn,e);/取栈顶元素void GetTop（LiStack *s,ElemType &e）LiStack *p;p=s-next;if（p=NULL）prin tf（目前此栈是空栈，此次取栈顶元素失
12、败了n）; elsee=p-data;printf（此次取栈顶的元素是：dn，e）;/显示栈中元素void DispStack（LiStack *s）LiStack *p;p=s-next;if（p=NULL）prin tf（此栈目前是空栈n）；elseprin tf（下面输出链栈里的各个元素:n）； while（p!=NULL）printf（%d ,p-data）; p=p-next;printf（n）;void main（）LiStack *s;int e;InitStack（s）;printf（*欢迎使用链栈操作*n）;prin tf（ *请输入第一个进栈元素:*n）; scanf（%d
13、,&e）;while（e!=0）Push(s,e);DispStack(s); StackLength(s);prin tf(“ *请输入一个进栈元素：*n); printf(若不需继续输入 请按数字0)n);scanf(%d,&e);StackEmpty(s); GetTop(s,e);int i;prin tf(如果你想出栈元素，请按数字1n); scanf(%d,&i);while(i=1) Pop(s，e);DispStack(s);StackLength(s);prin tf(如果你想继续出栈元素，请按1n); prin tf(“ *按下其他键退出本栈操作*n); scanf(%d，&i);printf(链栈的基本运算,到此操作完毕了哦！ n);顺序队列：#include #define QueueSize 100 typedef char ElemType;typedef struct ElemType dataQueueSize; /*保存队中元素*/ int front，rear;/*队头和队尾指针*/ SqQueue;void InitQueue(SqQueue &qu)qu.rear=qu.front=-1;/*指针初始化*/int EnQueue(SqQueue &qu，ElemType x) if (qu.rear+1)%Q
