2022年山东大学数据结构第二次实验实验报告.pdf

实验 2 ADT栈与队列的编程与实现实验目的 ：加深对抽象数据类型ADT栈和队列的理解；实验原理 ：参照课本p.64-66 ，及 Figure3.39-3.44；课本 p.82-83 ，及 Figure3.57-3.60. 实验内容 ：编写程序实现ADT栈的定义，及常用操作（数组或指针实现）：1)生成栈；2)Push 3)Pop 编写程序实现ADT队列的定义，及常用操作：1)生成队列；2)Enqueues 入列；3)Isempty 判断是否队列为空。实验要求 ：1)实现 ADT栈的结构及操作；2)实现 ADT队列的结构及操作，并给出应用。1.栈（链表实现）实验源程序：#include stdafx.h #include stdio.h #include stdlib.h #include malloc.h #include string.h typedef struct node /定义一个栈的结构 int data; struct node *pNext; /pNext 为指向栈中下一个空间的指针Node,*pNode; typedef pNode Stack; Stack InitStack() ; /初始化栈void CreateStack(Stack Top); /生成栈bool Empty(Stack Top); /判断栈是否为空void Push(Stack Top,int n); /进行压栈操作void Pop(Stack Top); /进行出栈操作void TraverseStack(Stack Top); /遍历栈的函数void DeleteStack(Stack Top); /清空栈的函数int main() /主函数 int n; char str6; /定义数组，存储操作指令Stack Top=NULL; /初始化 Top 为 NULL精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 1 页，共 13 页 - - - - - - - - - - Top=InitStack(); /初始化栈CreateStack(Top); /生成栈TraverseStack(Top); /遍历栈printf( 请输入下一步操作指令(push,pop or end):); while(1) scanf(%s,str); /获取操作指令if(strcmp(str,push)=0) printf( 请输入入栈的元素:); scanf(%d,&n); Push(Top,n); /进栈操作TraverseStack(Top); printf( 请输入下一步操作指令(push,pop or end):); if(strcmp(str,pop)=0) Pop(Top); /出栈操作TraverseStack(Top); printf( 请输入下一步操作指令(push,pop or end):); if(strcmp(str,end)=0) break; /跳出循环if(strcmp(str,push)!=0&strcmp(str,pop)!=0&strcmp(str,end)!=0) printf( 输入指令错误，请重新输入指令:); DeleteStack(Top); /释放栈空间return 0; Stack InitStack() /进行栈的初始化的函数 Stack Top = (Stack)malloc(sizeof(Node); /分配内存空间给栈顶if(Top=NULL) printf( 动态分配内存失败n); exit(1); printf( 初始化栈成功 n); Top-pNext = NULL; /栈顶指针的指向置为NULL ；return Top; 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 2 页，共 13 页 - - - - - - - - - - void CreateStack(Stack Top) /生成栈 int LEN,x; Stack Bottom = Top; /令 Top 和 Bottom 指向同一空间Bottom-pNext = NULL; printf( 请输入想要入栈的元素个数:); scanf(%d,&LEN); for(int i = 0; i data = x; /将输入的数放在栈data 单元中Bottom-pNext = pNew; /Bottom 指向新分配空间的单元pNew-pNext = NULL; /令 pNew 指向 NULL Bottom = pNew; /让新分配空间的单元成为栈底 printf( 生成栈成功 n); bool IsEmpty(Stack Top) / 判断栈是否为空 return Top-pNext=NULL; void Push(Stack Top,int n) /进行进栈操作的函数 Stack pNew = (Stack)malloc(sizeof(Node); /定义一个新节点，并分配内存空间if(pNew=NULL) printf( 未能动态分配内存，进栈失败n); return ; pNew-data = n; pNew-pNext = Top-pNext; Top-pNext = pNew; void Pop(Stack Top) /进行出栈操作函数 Stack p=Top-pNext; if (IsEmpty(Top)=true) /判断栈是否为空，为空就不能进行出栈操作 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 3 页，共 13 页 - - - - - - - - - - printf( 栈为空， Pop 失败 n); return ; else printf( 弹出的栈顶元素为:); printf(%d n,p-data); /显示出栈元素Top-pNext=p-pNext; free(p); void TraverseStack(Stack Top) /遍历栈，获取栈中的数值 printf( 现在栈中的元素从栈顶到栈底依次为:); Stack p = Top-pNext; if(p=NULL)printf(栈空 ); while(p!=NULL) printf(%d ,p-data); p = p-pNext; printf(n); void DeleteStack(Stack Top) /释放栈空间 Stack p,q ; p=Top-pNext; while (p != NULL) q=p-pNext; free(p); p=q; Top-pNext=NULL; 实验结果：1） 生成栈精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 4 页，共 13 页 - - - - - - - - - - 初始化栈。生成栈成功。2）Push输入 push，进行入栈操作，得到新的栈序列。3）Pop 输入 pop，进行出栈操作，弹出栈顶元素9, 并且得到新的栈序列。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 5 页，共 13 页 - - - - - - - - - - 如果不断进行pop 操作，当栈为空时会出现pop 失败。4)其余操作结束进程输入指令end可以结束进程，不会出现要求输入下一步指令。输入错误的指令若在指令输出端输入错误指令，则要求重新输入指令直到输入正确指令精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 6 页，共 13 页 - - - - - - - - - - 2. 队列（循环数组实现）实验源程序 ：#include stdafx.h #include stdio.h #include stdlib.h #include malloc.h #include string.h #define maxsize 11 typedef struct pQueue int queuemaxsize; int rear; / 最后元素的位置 int front; / 最前元素的位置的前一个位置Aqueue,*Queue; Queue QueueInit(); / 初始化队列void CreateQueue(Queue Q,int n); / 生成队列int IsFull(Queue Q); / 判断队列是否为满int IsEmpty(Queue Q); / 判断队列是否为空int EnQueue(Queue Q,int x); / 入队int DeQueue(Queue Q); / 出队void TraverseQueue(Queue Q); / 遍历队列int main() / 主函数 int n,x; char str10; Queue Q=QueueInit(); / 初始化队列 printf(请输入想要入队元素个数( 小于 %d):,maxsize); while(1) 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 7 页，共 13 页 - - - - - - - - - - scanf(%d,&n); if(nrear=-1; Q-front=-1; printf(初始化队列成功 n); return Q; exit(1); void CreateQueue(Queue Q,int n) / 生成队列 for(int i=0;irear=Q-rear+1; scanf(%d,&Q-queueQ-rear); printf(生成队列成功 n); int IsFull(Queue Q) / 判断队列是否为满 if(Q-front=-1) Q-front=maxsize-1; return (Q-rear+1)%maxsize=Q-front; int IsEmpty(Queue Q) / 判断队列是否为空 return Q-front=Q-rear; 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 9 页，共 13 页 - - - - - - - - - - int EnQueue(Queue Q,int x) / 入队 if(IsFull(Q) printf(队列已满 , 入队失败 n); return 0; Q-rear=(Q-rear+1)%maxsize; Q-queueQ-rear=x; return 1; int DeQueue(Queue Q) / 出队 Q-front=(Q-front+1)%maxsize; return Q-queueQ-front; void TraverseQueue(Queue Q) / 遍历队列，获取队列中的数值 if(IsEmpty(Q)=1) printf(队列为空 n); return; int front=Q-front; int rear=Q-rear; while (front!=rear) front=(front+1)%maxsize; printf(%d ,Q-queuefront); printf(n); 实验结果如下：实验结果：1）生成队列；初始化队列。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 10 页，共 13 页 - - - - - - - - - - 生成队列成功。2） Enqueues 入列；操作指令输入Enqueue，将 66入列。3） Isempty 判断是否队列为空。队列不为空。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 11 页，共 13 页 - - - - - - - - - - 队列为空4）其他操作若输入的元素个数超过数组能接受长度，需重新输入。队列为满时，入队失败精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 12 页，共 13 页 - - - - - - - - - - 出队操作。5）ADT队列的应用。ADT队列的应用实例：当多个任务分配给打印机时，为了防止冲突，创建一个队列，把任务入队，按先入先出的原则处理任务。当多个用户要访问远程服务端的文件时，也用到队列，满足先来先服务的原则。当在公交站排队等待进站时也会用到队列，先到的人先上车，相当于出队， 后到的人要先排队，相当于入队。CPU的分时系统也用到队列，系统根据请求的时间先后处理它们，而这些请求就相当于在队列中排列等待处理。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 13 页，共 13 页 - - - - - - - - - -