数据结构：实现队列的基本操作.doc

福建农林大学计算机与信息学院计算机类课程设计报告课程名称：算法与数据结构课程设计题目：实现队列的基本操作姓 名：刘磊系：计算机科学与技术专 业：计算机科学与技术年 级：2010级学 号：102260010004指导教师：宁正元职 称：教授2012年 09月12日福建农林大学计算机与信息学院计算机类课程设计结果评定评语：成绩：指导教师签字：任务下达日期：评定日期：目录1、课程设计目的12、课程设计要求13、课程设计方案24、课程设计内容24.1详细设计24.2调试分析34.3用户使用说明34.4测试结果44.5源程序55、总结9参考文献12 实现队列的基本操作1、课程设计目的 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能。 提高综合运用所学的理论知识和方法以及独立分析和解决问题的能力。2、 课程设计要求抽象数据类型的定义：typedef char QElemType;typedef struct QNodeQElemType data;struct QNode *next;QNode,*QueuePtr;typedef structQueuePtr front;QueuePtr rear;LinkQueue;主程序的流程：首先定义一些变量；然后输出目录，提示用户选择操作；接下来就是一个switch语句，根据用户的选择进行操作；最后case 1，case2，case 3，case 4，case 5，case 6，case 7，case 8，case 8，case 0分别实现“创建队列，销毁队列，清空队列，判断队列是否为空，返回队列长度，获取队头元素，插入新的队尾元素，删除队头元素并返回其值，遍历队列，退出程序”功能。各程序模块之间的层次(调用)关系：主函数调用实现各个功能的子函数以实现对应的功能。 3、课程设计方案任选一种存储方式表示队列,用C+语言编程实现队列的以下基本操作:1） InitQueue( ):构造一个空队列2） DestroyQueue( ):销毁队列3） ClearQueue( ):将队列清空4） QueueEmpty( ):判定队列是否为空队列5） QueueLength( ):返回Q的元素个数6） GetHead( ):获取Q的队头元素7） EnQueue( ):向队列Q中插入新元素8） DeQueue( ):删除队列Q中的元素9） QueueTraverse( ):依次读取队列Q中的每个元素输入的形式：字符，以0结束。输入值的范围：字母皆可。输出的形式：队列。程序所能达到的功能：创建队列，销毁队列，清空队列，判断队列是否为空，返回队列长度，获取队头元素，插入新的队尾元素，删除队头元素并返回其值，遍历队列，退出程序。测试数据：目录：A-创建队列B-销毁队列 C-清空队列D-判断队列是否为空E-返回队列长度F-获取队头元素G-插入新的队尾元素H-删除队头元素并返回其值I-遍历队列K-退出程序请输入您选择的操作：输入：A请输入您要创建的队列(按0结束)输入：shujujiegou0队列创建成功输入：H遍历结果为：shujujiegou输入：D该队列不为空输入: E该队列长度为：11输入：F队头元素为：s输入：H队头元素已删除，其值为：s输入：I遍历结果为：hujujiegou输入：G请输入您要添加的队尾元素(按#结束)s#新的队尾元素插入成功！输入：I遍历结果为：hujujiegous输入：C队列已清空输入：D该队列为空队列输入：I队列为空输入：B队列销毁成功输入：KPress any key to continue4、 课程设计内容1.详细设计创建空队列status InitQueue(LinkQueue &Q)Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front) return OVERFLOW;Q.front-next=NULL; return OK;销毁队列status DestroyQueue(LinkQueue &Q)while(Q.front)Q.rear=Q.front-next;free(Q.front);Q.front=Q.rear;return OK;清空队列void ClearQueue(LinkQueue &Q)Q.front=Q.rear;Q.front-next=NULL;判断队列是否为空status QueueEmpty(LinkQueue &Q)if(Q.front=Q.rear)return TRUE;elsereturn FALSE;返回队列长度 int QueueLength(LinkQueue Q)int i=0;while(!(Q.front=Q.rear)Q.front=Q.front-next;+i;return i;获取队头元素status EnQueue(LinkQueue &Q,QElemtype &e)QNode *p;p=(QueuePtr)malloc(sizeof(QNode); if(!p) return OVERFLOW; p-data=e; p-next=NULL; Q.rear-next=p; Q.rear=p; return OK;插入新的队尾元素status EnQueue(LinkQueue &Q,QElemtype &e)QNode *p;p=(QueuePtr)malloc(sizeof(QNode); if(!p) return OVERFLOW; p-data=e; p-next=NULL; Q.rear-next=p; Q.rear=p; return OK;删除队头元素并返回其值status DeQueue(LinkQueue &Q, QElemtype &e)QNode *p;if(Q.front=Q.rear)return ERROR;p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p) Q.rear=Q.front;free(p);return OK;遍历队列status QueueTraverse(LinkQueue Q)QNode *p;p=Q.front-next;while(p-next) coutdatanext;return TRUE;2. 调试分析a，调试过程中遇到的问题的解决以及对设计与实现的回顾讨论和分析调试过程中遇到的主要问题就是类型匹配问题，通过反复分析比较主函数定义的变量类型与子函数引用的类型得到了解决。当初设计的时候首先就是根据算法把功能模块子函数写出来，然后写主函数，主函数先创建一个目录，逐个调用子函数实现各个功能。最后调试修改就完成了。调试分析是最重要的一步，也是能学到很多东西的一步，这步做好了，程序也就基本实现了。b，算法的时空分析和改进设想主函数的时间复杂度主要由所创建队列的长度l所决定，即T(n)=O(l);其他函数的时间复杂度也和它们要执行的变量长度有关，比如遍历算法就和它所要遍历队列的长度l有关，也是O(l)。c，经验和体会调试是最让人头疼的一步，但也是最让人受益的一步，所以调试的时候一定要有耐心，这步好了，成功也就不远了。3、用户使用说明用户根据目录选择需要进行的操作目录：A-创建队列B-销毁队列 C-清空队列D-判断队列是否为空E-返回队列长度F-获取队头元素G-插入新的队尾元素H-删除队头元素并返回其值I-遍历队列K-退出程序请输入您选择的操作：输完后按Enter键，然后根据提示进行操作即可。4、测试结果输入：A请输入您要创建的队列(按0结束)输入：shujujiegou#队列创建成功输入：I遍历结果为：qwertyuioa0输入：D该队列不为空输入: E该队列长度为：10输入：F队头元素为：s输入：H队头元素已删除，其值为：s输入：I遍历结果为：hujujiegou输入：G请输入您要添加的队尾元素(按0结束)s#新的队尾元素插入成功！输入：I遍历结果为：hujujiegous输入：C队列已清空输入：D该队列为空队列输入：I队列为空输入：B队列销毁成功输入：KPress any key to continue5.源程序：#include#include#include#define NULL 0typedef char QElemType;typedef struct QNodeQElemType data;struct QNode *next;QNode,*QueuePtr;typedef structQueuePtr front;QueuePtr rear;LinkQueue;status InitQueue(LinkQueue &Q)Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front) return OVERFLOW;Q.front-next=NULL; return OK;status DestroyQueue(LinkQueue &Q)while(Q.front)Q.rear=Q.front-next;free(Q.front);Q.front=Q.rear;return OK;void ClearQueue(LinkQueue &Q)Q.front=Q.rear;Q.front-next=NULL;status QueueEmpty(LinkQueue &Q)if(Q.front=Q.rear)return TRUE;elsereturn FALSE;int QueueLength(LinkQueue Q)int i=0;while(!(Q.front=Q.rear)Q.front=Q.front-next;+i;return i;status GetHead(LinkQueue Q, QElemtype &e)if(!(Q.front=Q.rear)e=Q.front-next-data; return e;elsereturn ERROR;status EnQueue(LinkQueue &Q,QElemtype &e)QNode *p;p=(QueuePtr)malloc(sizeof(QNode); if(!p) return OVERFLOW; p-data=e; p-next=NULL; Q.rear-next=p; Q.rear=p; return OK;status DeQueue(LinkQueue &Q, QElemtype &e)QNode *p;if(Q.front=Q.rear)return ERROR;p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p) Q.rear=Q.front;free(p);return OK;status QueueTraverse(LinkQueue Q)QNode *p;p=Q.front-next;while(p-next)coutdatanext;return TRUE;void main()LinkQueue q;QElemtype e;char ch1, ch2;InitQueue(q);cout请选择:endl;ch1=Y;while(ch1=Y) printf(nA-创建队列); printf(nB-判断队列是否为空); printf(nC-队长);printf(nD-队头元素);printf(nE-遍历队列);printf(nF-删除队头元素并返回); printf(nG-清空队列 ); printf(nH-销毁队列 ); cout nK-退出操作endl;cout你要选择的操作：endl;scanf(n%c,&ch2);switch(ch2)case h:case H:DestroyQueue(q);printf(队列已销毁n);break;case g:case G:ClearQueue(q);printf(队列已清空n);break;case b:case B:if(QueueEmpty(q)printf(为空n);elseprintf(不为空);break;case c:case C: printf(队列长度:n);coutQueueLength(q)endl;break;case d:case D:printf(队头元素:n); GetHead(q,e);coutee;if(e!=0) EnQueue(q,e);while(e!=48);doif(e=0)cout请输入你要插入的元素：e;if(e!=0)EnQueue(q,e);while(e!=0);break;case f:case F:printf(删除队头元素为:n); cout DeQueue(q,e)endl;break;case e:case E:printf(遍历结果:n);QueueTraverse(q);break;case k: case K:ch1=n;break;defau