山东大学数据结构第二次实验实验报告.doc
《山东大学数据结构第二次实验实验报告.doc》由会员分享,可在线阅读,更多相关《山东大学数据结构第二次实验实验报告.doc(13页珍藏版)》请在咨信网上搜索。
实验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 str[6]; //定义数组,存储操作指令 Stack Top=NULL; //初始化Top为NULL 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; } void CreateStack(Stack Top) //生成栈 { int LEN,x; Stack Bottom = Top; //令Top和Bottom指向同一空间 Bottom->pNext = NULL; printf("请输入想要入栈的元素个数:"); scanf("%d",&LEN); for(int i = 0; i < LEN; i++) { printf("请输入第%d个元素(从栈顶到栈底):",i+1); scanf("%d",&x); Stack pNew = (Stack)malloc(sizeof(Node)); pNew->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) //判断栈是否为空,为空就不能进行出栈操作 { 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) 生成栈 ①初始化栈。 ②生成栈成功。 2)Push 输入push,进行入栈操作,得到新的栈序列。 3) Pop ①输入pop,进行出栈操作,弹出栈顶元素9,并且得到新的栈序列。 ②如果不断进行pop操作,当栈为空时会出现pop失败。 4)其余操作 ①结束进程 输入指令end可以结束进程,不会出现要求输入下一步指令。 ②输入错误的指令 若在指令输出端输入错误指令,则要求重新输入指令直到输入正确指令 2. 队列(循环数组实现) 实验源程序: #include "stdafx.h" #include "stdio.h" #include "stdlib.h" #include "malloc.h" #include "string.h" #define maxsize 11 typedef struct pQueue { int queue[maxsize]; 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 str[10]; Queue Q=QueueInit(); //初始化队列 printf("请输入想要入队元素个数(小于%d):",maxsize); while(1) { scanf("%d",&n); if(n<maxsize)break; printf("请重新输入想要入队元素个数(小于%d):",maxsize); } CreateQueue(Q,n); //生成队列 printf("队列中的元素依次为:"); TraverseQueue(Q); printf("请输入下一步操作指令(Enqueue,Dequeue or end):"); while(1) { scanf("%s",str); //获取操作指令 if(strcmp(str,"Enqueue")==0) { printf("请输入想要入队的元素:"); scanf("%d",&x); if(EnQueue(Q,x)) //入队 { printf("元素%d入队后队列中元素依次为:",x); TraverseQueue(Q); } printf("请输入下一步操作指令(Enqueue,Dequeue or end):"); } if(strcmp(str,"Dequeue")==0) { if(IsEmpty(Q)==0) { printf("元素%d出队后队列中元素依次为:",DeQueue(Q));//出队 TraverseQueue(Q); printf("请输入下一步操作指令(Enqueue,Dequeue or end):"); } else { printf("队列为空,出队失败\n"); printf("请输入下一步操作指令(Enqueue,Dequeue or end):"); } } if(strcmp(str,"end")==0) break; //跳出循环 if(strcmp(str,"Enqueue")!=0&&strcmp(str,"Dequeue")!=0&&strcmp(str,"end")!=0) { printf("输入指令错误,请重新输入指令:"); } } printf("判断队列是否为空:",x); //判断队列是否为空 if(IsEmpty(Q)==1) printf("队列为空\n"); else printf("队列不为空\n"); return 0; } Queue QueueInit() //初始化队列 { Queue Q=(Queue)malloc(sizeof(Aqueue)); if(Q!=NULL) { Q->rear=-1; Q->front=-1; printf("初始化队列成功\n"); return Q; } exit(1); } void CreateQueue(Queue Q,int n) //生成队列 { for(int i=0;i<n;i++) { printf("请输入队列中第%d个元素:",i+1); Q->rear=Q->rear+1; scanf("%d",&Q->queue[Q->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; } int EnQueue(Queue Q,int x) //入队 { if(IsFull(Q)) { printf("队列已满,入队失败\n"); return 0; } Q->rear=(Q->rear+1)%maxsize; Q->queue[Q->rear]=x; return 1; } int DeQueue(Queue Q) //出队 { Q->front=(Q->front+1)%maxsize; return Q->queue[Q->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->queue[front]); } printf("\n"); } 实验结果如下: 实验结果: 1)生成队列; ①初始化队列。 ②生成队列成功。 2) Enqueues入列; 操作指令输入Enqueue,将66入列。 3) Isempty判断是否队列为空。 ①队列不为空。 ②队列为空 4)其他操作 ①若输入的元素个数超过数组能接受长度,需重新输入。 ②队列为满时,入队失败 ③出队操作。 5)ADT队列的应用。 ADT队列的应用实例: ①当多个任务分配给打印机时,为了防止冲突,创建一个队列,把任务入队,按先入先出的原则处理任务。 ②当多个用户要访问远程服务端的文件时,也用到队列,满足先来先服务的原则。 ③当在公交站排队等待进站时也会用到队列,先到的人先上车,相当于出队,后到的人要先排队,相当于入队。 ④CPU的分时系统也用到队列,系统根据请求的时间先后处理它们,而这些请求就相当于在队列中排列等待处理。- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 山东大学 数据结构 第二次 实验 报告
咨信网温馨提示:
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,个别因单元格分列造成显示页码不一将协商解决,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【丰****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【丰****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,个别因单元格分列造成显示页码不一将协商解决,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【丰****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【丰****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。
关于本文