堆栈和队列的基本操作

《堆栈和队列的基本操作》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、实践教学*******************软件学院2012学年秋季学期上机实验报告册课程名称：_________________________实验名称：_________________________指导教师：_________________________小组成员：*****************************************************堆栈和队列的基本操作(上机二）一实验目的1.熟悉栈这种特殊现行结构特性；2.熟悉并掌握栈在顺序存储结构和链表存储结构下的基本运算；3.熟悉

2、队列这种特殊线性结构的特性；4.熟悉掌握队列在链表存储结构下的基本运算；二实验原理堆栈顺序存储结构下的基本算法堆栈链式存储结构下的基本算法队列顺序存储结构下的基本算法队列顺序存储结构下的基本算法1、堆栈的定义：堆栈是一种只允许在表的一端进行插入和删除运算的特殊的线性表。允许进行插入和删除运算的一端称为栈顶，另一端称为栈底，当链表中没有元素时，称为空栈。2、堆栈的插入运算称为入栈或者进栈，删除运算称为出栈或者退栈，栈顶的当前位置是动态的，标识栈顶当前位置的指针称为栈顶指针。每次进栈的数据元素都放在原当前栈顶元素之前成为

3、新的栈顶元素，每次退栈的数据元素都是原当前栈顶元素，最后进入堆栈的数据元素总是最先退出堆栈。3、堆栈的存储结构：（1）顺序存储结构：栈的顺序存储结构称为顺序栈。顺序栈的本质是顺序表的简化。（2）链式存储结构：栈的链式存储结构称为链栈，通常用单链表示。链栈的插入和删除操作只需处理栈顶的情况。4、队列的定义：队列是允许在表的一端进行插入，而在表的另一端进行删除的特殊线性表。允许进行插入的一端称为队尾，允许进行删除的一端称为队头。队列的插入运算称为进队或者入队，删除运算称为出队或者离队，因此队列又称为先进先出表。5、队列的

4、存储结构队列的存储结构同线性表一样，可以分为顺序结构和链式结构。（1）顺序存储结构：用顺序存储结构存储队列称为顺序队列。顺序队列会出现假溢出问题，解决办法是用首尾相接的书顺序存储结构，称为循环队列。在队列中，只要涉及队头或者队尾指针的修改都要对其求模。（2）链式存储结构：用链式存储结构存储的队列称为链队列。链队列的基本操作的实现基本上也是单链表操作的简化。通常附设头结点，并设置队头指针指向头结点，队尾指针指向终端结点。插入数据时只考虑在链队列的尾部进行，删除数据时只考虑在链队列的头部进行。三实验内容进行堆栈（包括顺序

5、结构、链式结构）和队列的基本操作：初始化栈、判断栈空、出栈、取出栈顶元素、入栈、显示栈中所有元素等运算。四程序代码：链式队列：#include#include#defineNULL0typedefintQElemType;typedefstructQNode{QElemTypedata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;voidCreateQu

6、eue(LinkQueue*Q){inta;QueuePtrp;p=(QueuePtr)malloc(sizeof(QNode));if(!p)printf("创建失败");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)printf("创建失败");else{p->data=a;Q->rear->next=p;Q->rear=

7、p;scanf("%d",&a);}}}}voidPrintfQueue(LinkQueue*Q){QueuePtrp;for(p=Q->front->next;p!=NULL;p=p->next){printf("%d",p->data);}}voidEnQueue(LinkQueue*Q,QElemTypex){QueuePtrp;p=(QueuePtr)malloc(sizeof(QNode));if(!p)printf("创建失败");else{p->data=x;p->next=NULL;Q->rear->

8、next=p;Q->rear=p;}}voidDeQueue(LinkQueue*Q,QElemType*f){QueuePtrp;if(Q->front==Q->rear)printf("Error");else{p=Q->front->next;*f=p->data;Q->front->next=p->next;if(Q->rear==