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

1、武汉工商学院数据结构课程实验实训报告实验名称栈与队列实验序号3学号14302043姓名陈前方班级信管本二实验日期2015.11.15指导教师金照林成绩一、实验目的和要求目的：掌握堆栈和队列数据结构描述，学会针对堆栈和队列的基本操作。要求：掌握C语言结构化程序设计思想，结构数据类型，指针数据类型。二、实验具体内容及步骤1,实现课本中链式堆栈(p64-p66)的基本操作，并编制主函数实际运行验证其正确性。2.链式堆栈设计。要求：(1) 用链式堆栈设计实现堆栈，堆栈的操作集合包括：初始化、非空否、入栈、出栈、取栈顶数据元素。(2) 设一个主函数对链式堆栈进行测试。测试方法为依次把数据元素1、2、3、

2、4、5入栈，然后出栈并在屏幕上显示出栈的数据兀素。(3) 定义数据元素的数据类型为如下形式的结构体：typedefstructchartaskName10;/任务名inttaskNo;/任务号DataType;首先设一个包含5个数据的测试数据，然后设一个主函数对链式堆栈进行测试。测试的方法为：依次把5个兀素入栈，然后出栈并在屏幕上显示出栈的数据儿系。3,实现课本中顺序循环队列(p75-p77)的基本操作，并编制主函数实际运行验证其正确性。4,对顺序循环队列，常规的方法是使用队尾指针和队头指针，队尾指针用于指示当前的队尾位置下标，队头指针用于指示当前的队头位置下标。现要求：(1)设一个使用队头指

3、针和计数器的顺序循环队列抽象数据类型，其中操作包括：初始化、入队列、出队列、取队头元素和判断队列是否为空。(2)设计一个测试主函数进行测试。武汉工商学院三、实验结果与分析(程序代码按序粘贴在下面，并将运行结果截图)1.#include<stdio.h>#include<stdlib.h>typedefintDataType;typedefstructsnodeDataTypedata;structsnode*next;LSNode;/*初始化操作：*/voidStackInitiate(LSNode*head)/*初始化带头结点链式堆栈*/if(*head=(LSNod

4、e*)malloc(sizeof(LSNode)=NULL)exit(1);(*head)->next=NULL;/*判非空操作：*/intStackNotEmpty(LSNode*head)/*判堆栈是否非空，非空返回1;空返回0*/if(head->next=NULL)return0;elsereturn1;/*入栈操作：*/intStackPush(LSNode*head,DataTypex)/*把数据元素x插入链式堆栈head的栈顶作为新的栈顶*/LSNode*p;if(p=(LSNode*)malloc(sizeof(LSNode)=NULL)printf("内

5、存空间不足无法插入！n");return0;p->data=x;p->next=head->next;/*新结点链入栈顶*/head->next=p;/*新结点成为新的栈顶*/return1;/*出栈操作：*/intStackPop(LSNode*head,DataType*d)/*出栈并把栈顶元素由参数d带回*/LSNode*p=head->next;if(p=NULL)printf("堆栈已空出错！")；return0;head->next=p->next;/*删除原栈顶结点*/*d=p->data;/*原栈顶结

6、点元素赋予d*/free(p);/*释放原栈顶结点内存空间*/return1;/*取栈顶数据元素操作：*/intStackTop(LSNode*head,DataType*d)/*取栈顶元素并把栈顶元素由参数d带回*/LSNode*p=head->next;if(p=NULL)printf("堆栈已空出错！");return0;武汉工商学院*d=p->data;return1;/*撤销*/voidDestroy(LSNode*head)(LSNode*p,*p1;p=head;while(p!=NULL)(p1=p;p=p->next;free(p1);v

7、oidmain(void)(LSNode*myStack;inti,x;StackInitiate(&myStack);for(i=0;i<5;i+)(if(StackPush(myStack,i+1)=0)(printf("error!n");return;if(StackTop(myStack,&x)=0)(printf("error!n");return;elseprintf("Theelementoflocaltopis:%dn",x);printf("Thesequenceofoutingel

8、ementsis:n");while(StackNotEmpty(myStack)(StackPop(myStack,&x);printf("%d",x);printf("n");Destroy(myStack);printf("Thisprogramismadeby10273206n");武汉工商学院)2.#include<stdio.h>#include<stdlib.h>#defineMaxStackSize100typedefintDataType;typedefstructDataT

9、ypestackMaxStackSize;inttop;SeqStack;/*初始化操作：*/voidStackInitiate(SeqStack*S)/*初始化带头结点链式堆栈*/S->top=0;intStackNotEmpty(SeqStackS)if(S.top<=0)return0;elsereturn1;/*入栈操作：*/武汉工商学院intStackPush(SeqStack*S,DataTypex)if(S->top>=MaxStackSize)printf("堆栈已满无法插入！n");return0;elseS->stackS-

10、>top=x;S->top+;return1;intStackPop(SeqStack*S,DataType*d)if(S->top<=0)printf("堆栈已空无数据元素出栈！n");return0;elseS->top-;*d=S->stackS->top;return1;intStackTop(SeqStackS,DataType*d)if(S.top<=0)printf("堆栈已空！n");return0;else*d=S.stackS.top-1;return1;voidmain(void)Se

11、qStackmyStack;武汉工商学院inti,x;StackInitiate(&myStack);for(i=0;i<5;i+)(if(StackPush(&myStack,i+1)=0)(printf("错误n");return;if(StackTop(myStack,&x)=0)(printf("错误n");return;elseprintf("当前栈顶元素为：dn",x);printf("依次出栈的数据元素序列如下：n");while(StackNotEmpty(myStac

12、k)(StackPop(&myStack,&x);printf("%d",x);武汉工商学院3.#include"stdio.h"#include"string.h"#include"stdlib.h"#defineMaxQueueSize100typedefintDataType;typedefstructDataTypequeueMaxQueueSize;intrear;intfront;intcount;SeqCQueue;voidQueueuInitiate(SeqCQueue*Q)Q-&g

13、t;rear=0;Q->front=0;Q->count=0;intQueueNotEmpty(SeqCQueueQ)if(Q.count!=0)return1;elsereturn0;intQueueAppend(SeqCQueue*Q,DataTypex)if(Q->count>0&&Q->rear=Q->front)printf("队列已满无法插入！n");return0;elseQ->queueQ->rear=x;Q->rear=(Q->rear+1)%MaxQueueSize;Q->

14、count+;return1;武汉工商学院intQueueDelete(SeqCQueue*Q,DataType*d)(if(Q->count=0)(printf("队列已空无数据元素出队列！n");return0;else(*d=Q->queueQ->front;Q->front=(Q->front+1)%MaxQueueSize;Q->count-;return1;intQueueGet(SeqCQueueQ,DataType*d)(if(Q.count=0)(printf("队列已空无数据可取n");return

15、0;else(*d=Q.queueQ.front;return1;voidmain(void)(SeqCQueuemyQueue;inti,x;QueueuInitiate(&myQueue);for(i=0;i<5;i+)(if(QueueAppend(&myQueue,i+1)=0)(printf("error!n");return;if(QueueGet(myQueue,&x)=0)武汉工商学院printf("error!n");return;elseprintf("队头元素是：dn",x);pri

16、ntf("依次出栈数据元素顺序是：n");while(QueueNotEmpty(myQueue)QueueDelete(&myQueue,&x);printf("%d",x);4.#include"stdio.h"#include"string.h"#include"stdlib.h"#defineMaxQueueSize100typedefintDataType;typedefstructDataTypequeueMaxQueueSize;intrear;武汉工商学院intf

17、ront;intcount;SeqCQueue;voidQueueuInitiate(SeqCQueue*Q)(Q->rear=0;Q->front=0;Q->count=0;intQueueNotEmpty(SeqCQueueQ)(if(Q.front!=Q.rear)return1;elsereturn0;intQueueAppend(SeqCQueue*Q,DataTypex)(if(Q->front=(Q->rear+1)%MaxQueueSize)(printf("队列已满无法插入！n");return0;else(Q->que

18、ueQ->rear=x;Q->rear=(Q->rear+1)%MaxQueueSize;Q->count+;return1;intQueueDelete(SeqCQueue*Q,DataType*d)(if(Q->front=Q->rear)(printf("队列已空无数据元素出队列！n");return0;else(*d=Q->queueQ->front;武汉工商学院Q->front=(Q->front+1)%MaxQueueSize;Q->count-;return1;intQueueGet(SeqCQueueQ,DataType*d)if(Q.front=Q.rear)printf("队列已空无数据可取n");return0;else*d=Q.queueQ.front;return1;voidmain(void)SeqCQueuemyQueue;inti,x;QueueuInitiate(&myQueue);for(i=0;i<5;i+)if(QueueAppend(&a