栈和队列基本操作实验报告

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

1、实验二堆栈和队列基本操作的编程实现【实验目的】堆栈和队列基本操作的编程实现要求：堆栈和队列基本操作的编程实现（2学时，验证型），掌握堆栈和队列的建立、进栈、出栈、进队、出队等基本操作的编程实现，存储结构可以在顺序结构或链接结构中任选，也可以全部实现。也鼓励学生利用基本操作进行一些应用的程序设计。【实验性质】验证性实验（学时数：2H）【实验内容】内容：把堆栈和队列的顺序存储（环队）和链表存储的数据进队、出队等运算其中一部分进行程序实现。可以实验一的结果自己实现数据输入、数据显示的函数。利用基本功能实现各类应用，如括号匹配、回文判断、事物排队模拟、数据逆序生成、多进制转换

2、等。【实验分析、说明过程】分析：进栈操作先创建一个以x为值的新结点p，其data域值为x则进栈操作步骤如下：将新结点p的指针域指向原栈顶S（执行语句p->next=S）。将栈顶S指向新结点p（执行语句S=p）。注：进栈操作的①与②语句执行顺序不能颠倒，否则原S指针其后的链表将丢失。出栈操作先将结点栈顶S数据域中的值赋给指针变量*x，则删除操作步骤如下：结点p指针域指向原栈顶S（执行语句p=S）。栈顶S指向其的下一个结点（执行语句S=S->next）释放p结点空间（执行语句free(p)）。队列分析：用链式存储结构实现的队列称为链队列，一个链队列需要一个队头指针和一个队

3、尾指针才能唯一确定。队列中元素的结构和前面单链表中的结点的结构一样。为了操作方便，在队头元素前附加一个头结点，队头指针就指向头结点。【思考问题】1.栈的顺序存储和链表存储的差异？答：栈的顺序存储有‘后进先出’的特点，最后进栈的元素必须最先出来，进出栈是有序的，在对编某些需要按顺序操作的程序有很大的作用。链表存储：通过链表的存储可以实现链表中任意位置的插入元素，删除任意元素，可以实现无序进出。2.还会有数据移动吗？为什么？答:栈的顺序存储不会有数据移动，移动的只是指向该数据地址的指针。3.栈的主要特点是什么？队列呢？答：栈拥有‘后进先出’的特点；队列拥有‘先进先出’的特

4、点。4.栈的主要功能是什么？队列呢？答：栈作为数据结构，其主要的用途是保存一批数据的逆序信息，从而产生逆序数据。队列也是一种数据结构，其主要的用途按顺序保存一批数据，并且有序的队数据进行处理。1.为什么会有环状队列？答：为了解决“假溢出”的问题，把顺序结构的头尾进行相连，造出了一个所谓的“环状队列”。【实验小结】(总结本次实验的重难点及心得、体会、收获)本次实验主要是对堆栈和队列的顺序存储和链表存储的数据进队、出队等运算中一部分程序进行完善，程序的复杂度也是逐步增加，这让我们对栈和队列的认识也逐步加深。在做本次实验中，自己亲自动手后，我栈和队列的知识又有了更深层次的了

5、解，掌握了栈“后进先出”和队列“先进先出”的特点，学会了栈和队列的一些基本应用实例，实验的目的就是学会用栈和队列这两种数据结构进行编程，进行一些实际问题的处理，经过本次实验，我对学习也有了一些新的感悟，学了的知识要时常复习，经常巩固，不懂的知识要及时向老师或者同学请教，争取把这门课程学的更好！【附录-实验代码】#include#include#includetypedefintelemtype;typedefstructnode//队列结点类型定义{elemtypedata;//队列的数据元素类型structno

6、de*next;//指向后继结点的指针}NODE;typedefstruct{//定义链队NODE*front,*rear;//定义链队队头和队尾指针}LINKQUEUE;voidinitqueue(LINKQUEUE*QL)//队列的初始化{QL->front=(NODE*)malloc(sizeof(NODE));//队列为带头结点的链队列QL->front->next=NULL;QL->rear=QL->front;}LINKQUEUE*pushqueue(LINKQUEUE*QL,elemtypex){//将元素x插入到链队列QL中，作为QL的新队尾QL->r

7、ear->next=(NODE*)malloc(sizeof(NODE));QL->rear->next->data=x;QL->rear=QL->rear->next;QL->rear->next=NULL;returnQL;}elemtypepopqueue(LINKQUEUE*QL){//若链队列不为空，则删除队头元素，返回其元素值NODE*newnode;newnode=QL->front->next;if(newnode==NULL)return0;newnode=QL->front;QL->front=QL->front->next;fr