数据结构堆栈与队列实验报告

1实验二堆栈和队列实验目的：1.熟悉栈这种特殊线性结构的特性；2.熟练并掌握栈在顺序存储结构和链表存储结构下的基本运算；3.熟悉队列这种特殊线性结构的特性；3.熟练掌握队列在链表存储结构下的基本运算。实验原理：堆栈顺序存储结构下的基本算法；堆栈链式存储结构下的基本算法；队列顺序存储结构下的基本算法；队列链式存储结构下的基本算法；实验内容：第一题链式堆栈设计。要求（1）用链式堆栈设计实现堆栈，堆栈的操作集合要求包括：初始化StackInitiate（S）,非空否StackNotEmpty(S)，入栈StackiPush(S,x),出栈StackPop（S,d）,取栈顶数据元素StackTop(S,d);（2）设计一个主函数对链式堆栈进行测试。测试方法为：依次把数据元素1，2，3，4，5入栈，然后出栈并在屏幕上显示出栈的数据元素；（3）定义数据元素的数据类型为如下形式的结构体，Typedefstruct{chartaskName[10];inttaskNo;}DataType;首先设计一个包含5个数据元素的测试数据，然后设计一个主函数对链式堆栈进行测试，测试方法为：依次吧5个数据元素入栈，然后出栈并在屏幕上显示出栈的数据元素。第二题对顺序循环队列，常规的设计方法是使用対尾指针和对头指针，对尾指针用于指示当前的対尾位置下标，对头指针用于指示当前的対头位置下标。现要求：（1）设计一个使用对头指针和计数器的顺序循环队列抽象数据类型，其中操作包括：初始化，入队列，出队列，取对头元素和判断队列是否为空；（2）编写主函数进行测试。程序代码：第一题：（1）源程序LinStack.h如下：#defineNULL0typedefstructsnode{DataTypedata;structsnode*next;}LSNode;/*（1）初始化StackInitiate(LSNode**head)*/voidStackInitiate(LSNode**head)/*初始化带头结点链式堆栈*/2{if((*head=(LSNode*)malloc(sizeof(LSNode)))==NULL)exit(1);(*head)-next=NULL;}/*（2）非空否StackNotEmpty(LSNode*head)*/intStackNotEmpty(LSNode*head)/*判断堆栈是否为空，非空返回1，否则返回0*/{if(head-next==NULL)return0;elsereturn1;}/*（3）入栈StackPush(LSNode*head,DataTypex)*/intStackPush(LSNode*head,DataTypex)/*把数据元素x插压入链式堆栈head的栈顶作为新的栈顶，*//*入栈成功返回1，否则返回0*/{LSNode*p;if((p=(LSNode*)malloc(sizeof(LSNode)))==NULL){printf(Thememoryspaceisnotenough!\n);return0;}p-data=x;p-next=head-next;/*新结点入栈*/head-next=p;/*新结点成为新的栈顶*/return1;}/*（4）出栈StackPop(SLNode*head,DataType*d)*/intStackPop(LSNode*head,DataType*d)/*出栈并把栈顶数据元素值带到参数d，*//*出栈成功返回1，否则返回0*/{LSNode*p;p=head-next;if(p==NULL){printf(TheStackhasbeenempty!\n);return0;}head-next=p-next;*d=p-data;free(p);return1;}/*（5）取栈顶数据元素StackTop(LSNode*head,DataType*d)*/intStackTop(LSNode*head,DataType*d)/*取栈顶数据元素并由参数d带回，*//*成功返回1，否则返回0*/{LSNode*p;p=head-next;3if(p==NULL){printf(TheStackhasbeenempty!\n);return0;}*d=p-data;return1;}/*（6）撤销动态申请空间Destroy(LSNode*head)*/voidDestroy(LSNode*head){LSNode*p,*p1;p=head;while(p!=NULL){p1=p;p=p-next;free(p1);}}（2）测试函数如下：#includestdio.h/*该文件包含printf()函数*/#includestdlib.h/*该文件包含exit()函数*/#defineNULL0typedefintDataType;#includeLinStack.hvoidmain(void){LSNode*myStack;inti,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(Theelementoflocaltopis:%d\n,x);printf(Thesequenceofoutingelementsis:\n);while(StackNotEmpty(myStack)){4StackPop(myStack,&x);printf(%d,x);}Destroy(myStack);}（3）设计结构体和测试函数如下：#includestdio.h#includestdlib.h#includemalloc.htypedefstruct{chartaskName[10];inttaskNo;}DataType;#includeLinStack.hvoidmain(){LSNode*myStack;FILE*fp;DataTypetask,x;if((fp=fopen(task.dat,r))==NULL){printf(不能打开文件task.dat!\n);exit(0);}StackInitiate(&myStack);while(!feof(fp)){fscanf(fp,%s%d,&task.taskName,&task.taskNo);StackPush(myStack,task);}fclose(fp);while(StackNotEmpty(myStack)){StackPop(myStack,&x);printf(%s%d\n,x.taskName,x.taskNo);}Destroy(myStack);}其中task.dat为：第一个1第二个2第三个3第四个4第五个5第二题：原函数设计如下：5typedefstruct{DataTypequeue[MaxQueueSize];intfront;/*队头指针*/intcount;/*计数器*/}SeqCQueue;/*==========================*//*(1)初始化QueueInitiate(SeqCQueue*Q)*/voidQueueInitiate(SeqCQueue*Q)/*初始化顺序循环队列Q*/{Q-front=0;/*定义初始队头指针下标*/Q-count=0;/*定义初始计数器值*/}/*==========================*//*(2)非空否QueueNotEmpty(SeqCQueueQ)*/intQueueNotEmpty(SeqCQueueQ)/*判断顺序循环队列Q非空否，非空时返回1，否则返回0*/{if(Q.count!=0)return1;elsereturn0;}/*==========================*//*(3)入队列QueueAppend(SeqCQueue*Q,DataTypex)*/intQueueAppend(SeqCQueue*Q,DataTypex)/*把数据元素x插入顺序循环队列Q的队尾，成功时返回1，否则返回0*/{if(Q-count==MaxQueueSize){printf(Thequeueisfull!\n);return0;}else{intr;r=Q-front+Q-count;Q-queue[r]=x;Q-count++;return1;}}/*==========================*//*(4)出队列QueueDelete(SeqCQueue*Q,DataType*d)*/intQueueDelete(SeqCQueue*Q,DataType*d)6/*删除顺序循环队列队头数据元素并赋值d，成功时返回1，否则返回0*/{if(Q-count==0){printf(Thequeueisempty!\n);return0;}else{*d=Q-queue[Q-front];Q-front=(Q-front+1)%MaxQueueSize;Q-count--;return1;}}/*==========================*//*(6)取对头数据元素QueueGet(SeqCQueueQ,DataType*d)*/intQueueGet(SeqCQueueQ,DataType*d)/*取顺序循环队列队头数据元素并赋值d，成功时返回1，否则返回0*/{if(Q.count==0){printf(Thequeueisempty!\n);return0;}else{*d=Q.queue[Q.front];return1;}}（2）测试函数如下：#includestdio.h#defineMaxQueueSize100typedefintDataType;#includeSeqQueue.hvoidmain(void){inti,j,d;SeqCQueuemyQueue;QueueInitiate(&myQueue);7printf(%d\n,QueueNotEmpty(myQueue));/*判空*/for(i=0;i=10;i++){if(QueueAppend(&myQueue,i+1)==0)break;}printf(%d\n,myQueue.count);/*输出元素个数*/for(j=0;j=9;j++){if(QueueDelete(&myQueue,&d)==0)break;printf(%d,d);/*出队列并显示元素*/}printf(\n);printf(%d\n,QueueNotEmpty(myQueue));/*再次判空*/}实验结果：（1）测试函数输出结果如下：（2）测试设计的结构体结果如下：（3）测试仅使用头指针和计数器的队列结果如下：8总结与思考只使用对头指针和计数器的循环队列，实现方法和加上尾指针只有在入队列操作时有所不同，其他的都一样；而此时，入队列元素的位置就由对头指针和计数器决定，此算法的清晰度（可读性）比不上有尾指针的循环队列；但是在判空以及循环具体操作时更为方便；在以结构体数据类型的操作中，要注意的是，取数据元素时也要用结构体类型的变量去取出，输出时也一样。