数据结构课程实验实训报告堆栈和队列的基本操作.doc

数据结构课程实验实训报告堆栈和队列的基本操作132020年4月19日文档仅供参考，不当之处，请联系改正。数据结构课程实验实训报告实验名称栈与队列实验序号3学 号14302043姓 名陈前方班 级信管本二实验日期 .11.15指导教师金照林成 绩一、实验目的和要求目的：掌握堆栈和队列数据结构描述，学会针对堆栈和队列的基本操作。要求：掌握C语言结构化程序设计思想，结构数据类型，指针数据类型。二、实验具体内容及步骤1. 实现课本中链式堆栈（p64-p66）的基本操作，并编制主函数实际运行验证其正确性。2. 链式堆栈设计。要求：（1） 用链式堆栈设计实现堆栈，堆栈的操作集合包括：初始化、非空否、入栈、出栈、取栈顶数据元素。（2） 设计一个主函数对链式堆栈进行测试。测试方法为依次把数据元素1、2、3、4、5入栈，然后出栈并在屏幕上显示出栈的数据元素。（3） 定义数据元素的数据类型为如下形式的结构体：typedef structchar taskName10; /任务名int taskNo; /任务号DataType;首先设计一个包含5个数据的测试数据，然后设计一个主函数对链式堆栈进行测试。测试的方法为：依次把5个元素入栈，然后出栈并在屏幕上显示出栈的数据元素。3. 实现课本中顺序循环队列（p75-p77）的基本操作，并编制主函数实际运行验证其正确性。4. 对顺序循环队列，常规的方法是使用队尾指针和队头指针，队尾指针用于指示当前的队尾位置下标，队头指针用于指示当前的队头位置下标。现要求：（1） 设计一个使用队头指针和计数器的顺序循环队列抽象数据类型，其中操作包括：初始化、入队列、出队列、取队头元素和判断队列是否为空。（2） 设计一个测试主函数进行测试。三、实验结果与分析（程序代码按序粘贴在下面，并将运行结果截图）1#include#include typedef int DataType; typedef struct snode DataType data; struct snode *next; LSNode; /*初始化操作：*/ void StackInitiate(LSNode *head) /*初始化带头结点链式堆栈*/ if(*head = (LSNode *)malloc(sizeof(LSNode) = NULL) exit(1); (*head)-next = NULL; /*判非空操作：*/ int StackNotEmpty(LSNode *head) /*判堆栈是否非空，非空返回1；空返回0*/ if(head-next = NULL) return 0; else return 1; /*入栈操作：*/ int StackPush(LSNode *head, DataType x) /*把数据元素x插入链式堆栈head的栈顶作为新的栈顶 */ LSNode *p; if(p = (LSNode *)malloc(sizeof(LSNode) = NULL) printf(内存空间不足无法插入! n); return 0; p-data = x; p-next = head-next; /*新结点链入栈顶*/ head-next = p; /*新结点成为新的栈顶*/ return 1; /*出栈操作：*/ int StackPop(LSNode *head, DataType *d) /*出栈并把栈顶元素由参数d带回*/ LSNode *p = head-next; if(p = NULL) printf(堆栈已空出错！); return 0; head-next = p-next; /*删除原栈顶结点*/ *d = p-data; /*原栈顶结点元素赋予d*/ free(p); /*释放原栈顶结点内存空间*/ return 1; /*取栈顶数据元素操作：*/ int StackTop(LSNode *head, DataType *d) /*取栈顶元素并把栈顶元素由参数d带回*/ LSNode *p = head-next; if(p = NULL) printf(堆栈已空出错！); return 0; *d = p-data; return 1; /*撤销*/ void Destroy(LSNode *head) LSNode *p, *p1; p = head;while(p != NULL) p1 = p; p = p-next; free(p1); void main(void) LSNode *myStack; int i, x; StackInitiate(&myStack);for(i=0;i5;i+)if(StackPush(myStack,i+1)=0)printf(error!n);return;if(StackTop(myStack,&x)=0)printf(error!n);return;elseprintf(The element of local top is :%dn,x);printf(The sequence of outing elements is:n);while(StackNotEmpty(myStack)StackPop(myStack, &x);printf(%d , x);printf(n);Destroy(myStack);printf(This program is made by10273206n);2#include#include #define MaxStackSize 100typedef int DataType; typedef struct DataType stackMaxStackSize; int top; SeqStack; /*初始化操作：*/ void StackInitiate(SeqStack *S) /*初始化带头结点链式堆栈*/ S-top=0; int StackNotEmpty(SeqStack S) if(S.toptop=MaxStackSize)printf(堆栈已满无法插入!n);return 0;elseS-stackS-top=x;S-top+;return 1; int StackPop(SeqStack *S, DataType *d) if(S-toptop-;*d=S-stackS-top;return 1; int StackTop(SeqStack S, DataType *d) if(S.top=0)printf(堆栈已空!n);return 0;else*d=S.stackS.top-1;return 1; void main(void) SeqStack myStack;int i,x;StackInitiate(&myStack);for(i=0;irear=0;Q-front=0;Q-count=0;int QueueNotEmpty(SeqCQueue Q)if(Q.count!=0)return 1;elsereturn 0;int QueueAppend(SeqCQueue *Q,DataType x)if(Q-count0&Q-rear=Q-front)printf(队列已满无法插入！n);return 0; elseQ-queueQ-rear=x;Q-rear=(Q-rear+1)%MaxQueueSize;Q-count+;return 1;int QueueDelete(SeqCQueue *Q,DataType *d)if(Q-count=0)printf(队列已空无数据元素出队列!n);return 0;else*d=Q-queueQ-front;Q-front=(Q-front+1)%MaxQueueSize;Q-count-;return 1;int QueueGet(SeqCQueue Q,DataType *d)if(Q.count=0)printf(队列已空无数据可取n);return 0;else*d=Q.queueQ.front;return 1;void main(void) SeqCQueue myQueue; int i,x; QueueuInitiate(&myQueue);for(i=0;irear=0;Q-front=0;Q-count=0;int QueueNotEmpty(SeqCQueue Q)if(Q.front!=Q.rear)return 1;elsereturn 0;int QueueAppend(SeqCQueue *Q,DataType x)if(Q-front=(Q-rear+1)%MaxQueueSize)printf(队列已满无法插入！n);return 0; elseQ-queueQ-rear=x;Q-rear=(Q-rear+1)%MaxQueueSize;Q-count+;return 1;int QueueDelete(SeqCQueue *Q,DataType *d)if(Q-front=Q-rear)printf(队列已空无数据元素出队列!n);return 0;else*d=Q-queueQ-front;Q-front=(Q-front+1)%MaxQueueSize;Q-count-;return 1;int QueueGet(SeqCQueue Q,DataType *d)if(Q.front=Q.rear)printf(队列已空无数据可取n);return 0;else*d=Q.queueQ.front;return 1;void main(void) SeqCQueue myQueue; int i,x; QueueuInitiate(&myQueue);for(i=0;i5;i+)if(QueueAppend(&myQueue,i+1)=0)printf(error!n);return;if(QueueGet(myQueue,&x)=0)printf(error!n);return;elseprintf(队头元素是 :%dn,x);printf(依次出栈数据元素顺序是:n);while(QueueNotEmpty(myQueue)QueueDelete(&myQueue,&x);printf(%d ,x);四、指导老师评语指导老师签名：