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

实验二 堆栈和队列基本操作的编程实现【实验目的】堆栈和队列基本操作的编程实现要求：堆栈和队列基本操作的编程实现（2学时，验证型），掌握堆栈和队列的建立、进栈、出栈、进队、出队等基本操作的编程实现，存储结构可以在顺序结构或链接结构中任选，也可以全部实现。也鼓励学生利用基本操作进行一些应用的程序设计。【实验性质】验证性实验（学时数：2H）【实验内容】内容：把堆栈和队列的顺序存储（环队）和链表存储的数据进队、出队等运算其中一部分进行程序实现。可以实验一的结果自己实现数据输入、数据显示的函数。利用基本功能实现各类应用，如括号匹配、回文判断、事物排队模拟、数据逆序生成、多进制转换等。【实验分析、说明过程】 分析：进栈操作先创建一个以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)）。队列分析：用链式存储结构实现的队列称为链队列，一个链队列需要一个队头指针和一个队尾指针才能唯一确定。队列中元素的结构和前面单链表中的结点的结构一样。为了操作方便，在队头元素前附加一个头结点，队头指针就指向头结点。【思考问题】1. 栈的顺序存储和链表存储的差异？ 答：栈的顺序存储有后进先出的特点，最后进栈的元素必须最先出来，进出栈是有序的，在对编某些需要按顺序操作的程序有很大的作用。 链表存储：通过链表的存储可以实现链表中任意位置的插入元素，删除任意元素，可以实现无序进出。2. 还会有数据移动吗？为什么？答:栈的顺序存储不会有数据移动，移动的只是指向该数据地址的指针。3. 栈的主要特点是什么？队列呢？答：栈拥有后进先出的特点；队列拥有先进先出的特点。4. 栈的主要功能是什么？队列呢？答：栈作为数据结构，其主要的用途是保存一批数据的逆序信息，从而产生逆序数据。队列也是一种数据结构，其主要的用途按顺序保存一批数据，并且有序的队数据进行处理。5. 为什么会有环状队列？ 答：为了解决“假溢出”的问题，把顺序结构的头尾进行相连，造出了一个所谓 的“环状队列”。【实验小结】 (总结本次实验的重难点及心得、体会、收获) 本次实验主要是对堆栈和队列的顺序存储和链表存储的数据进队、出队等运算中一部分程序进行完善，程序的复杂度也是逐步增加，这让我们对栈和队列的认识也逐步加深。 在做本次实验中，自己亲自动手后，我栈和队列的知识又有了更深层次的了解，掌握了栈“后进先出”和队列“先进先出”的特点，学会了栈和队列的一些基本应用实例，实验的目的就是学会用栈和队列这两种数据结构进行编程，进行一些实际问题的处理，经过本次实验，我对学习也有了一些新的感悟，学了的知识要时常复习，经常巩固，不懂的知识要及时向老师或者同学请教，争取把这门课程学的更好！【附录-实验代码】#include#include#includetypedef int elemtype;typedef struct node /队列结点类型定义 elemtype data; /队列的数据元素类型 struct node *next; /指向后继结点的指针NODE;typedef struct /定义链队 NODE *front,*rear;/定义链队队头和队尾指针LINKQUEUE;void initqueue(LINKQUEUE *QL)/队列的初始化QL-front=(NODE *)malloc(sizeof(NODE);/队列为带头结点的链队列QL-front-next=NULL;QL-rear=QL-front;LINKQUEUE *pushqueue(LINKQUEUE *QL,elemtype x) /将元素x插入到链队列QL中，作为QL的新队尾QL-rear-next=(NODE *)malloc(sizeof(NODE);QL-rear-next-data=x;QL-rear=QL-rear-next;QL-rear-next=NULL;return QL;elemtype popqueue(LINKQUEUE *QL) /若链队列不为空，则删除队头元素，返回其元素值NODE *newnode;newnode=QL-front-next;if(newnode=NULL)return 0;newnode=QL-front;QL-front=QL-front-next;free(newnode);return(QL-front-data);void printqueue(LINKQUEUE *QL)/队列的显示NODE *p;p=QL-front-next;if(p=NULL)printf(队列空!);while(p!=NULL)if(p-next=NULL) printf(%d,p-data);else printf(%ddata); p=p-next;printf(n);void main() LINKQUEUE *p; int choice,elemdata,x=0; p=(LINKQUEUE *)malloc(sizeof(LINKQUEUE); initqueue(p); while(1) printf( 欢迎使用队列操作小程序：n); printf(t1、元素入队n); printf(t2、元素出队n); printf(t3、显示队列n); printf(t4、清屏幕n); printf(t5、退出程序n);printf( 请选择你的操作：); scanf(%d,&choice); switch(choice) case 1:printf(请输入进队元素：); scanf(%d,&elemdata); p=pushqueue(p,elemdata); printf(队列中的元素为：n); printqueue(p); system(pause); break; case 2:x=popqueue(p); if(x!=0) printf(元素%d出队!n,x); printf(队列中的元素为：n); printqueue(p);