顺序队、链队实验报告

1、重庆工商大学数据结构课程实验报告封面专业班级： 12计算机一班 学 号： 2012131152 学生姓名： 古应波 实验室： 10412 实验题目： 顺序队列、链队列的操作 指导教师： 梁新元 成绩： 日期：2013年 10 月 日 第 6 周 星期 3 节次 4-5 评分表实验报告质量序号项目总分自评分互评分组长评分教师评分1算法思想22算法描述33实验数据与结果104总结45排版2源程序质量6正确性637友好性48可读性49健壮性410创新与多样性4合计总分评分人签字目录一、 实验题目1二、 实验目的1三、 实验内容1四、 实验要点与要求1五、 算法思想1六、 算法描述及流程图4七、 实验

2、数据及实验结果5八、 程序组成结构示意图5九、 顺序队列调试截图6十、 链队列调试截图8十一、 顺序队列源代码9十二、 链队列源代码12第 1 页 共 16 页实验报告的内容与要求1、 实验题目顺序队列、链队列的基本操作2、 实验目的了解顺序队列、链队列的结构特点及有关概念，掌握其基本操作算法。3、 实验内容实现顺序队列和链队列的初始化、进队、出队、销毁操作4、 实验要点与要求1. 处理的数据类型即ElemType的类型基本版要求：整型、字符型扩展版要求：字符串型（基础较好的同学）2. 必须采用函数调用 5、 算法思想队列的特点是一端进，另一端出，由此需要定义队首指针和队尾指针，分别用于出队和

3、进队的相关操作bool InQuene(SqQuene *&q,ElemType d)/入队元素if(q->rear=MaxSize-1)cout<<"队满！"<<endl;return false;q->rear+;q->dataq->rear=d;return true;判断队列为满的条件为队尾指针指向数组最大处，由于出队的方式所限，顺序队会出现假溢出的情况，为了解决这个问题，可以采用环队或者链队代替。链队算法如下bool InNode(SqNode *&n,ElemType &e)QNode *q

4、;q=(QNode *)malloc(sizeof(QNode);q->data=e;q->next=NULL;if(n->rear=NULL)n->front=n->rear=q;elsen->rear->next=q;n->rear=q;cout<<"入队成功！"<<endl;return true;和所有的链式储存模式一样，在进行新填数据的时候都需要分配空间，修改相应的指针域，链式储存模式没有队列最大值的性质就解决了顺序队列假溢出的问题6、 算法描述及流程图7、 实验数据及实验结果序号测试类型输入

5、数据期望输出结果实际输出结果测试结论合法数据1,2,a,b,1,2,a,b,1,2,a,b测试成功，程序正确执行非法数据-11.5go-11.5go-1压栈成功.5丢失g 压栈成功o丢失不符合程序预设的数据处理类型，程序执行，但是得不到期望的结果8、 程序组成结构示意图9、 顺序队列调试截图10、 链队列调试截图11、 顺序队列源代码/实现顺序队列的入队，出队，遍历操作/采用字符型储存数据,指针型引用做形参#include<iostream>#include<malloc.h>#define MaxSize 100using namespace std;typedef

6、char ElemType;typedef struct MyQueneElemType dataMaxSize;int front;int rear;int count;int no;SqQuene;void Init(SqQuene *&q);/初始化void Destory(SqQuene *&q);/销毁队列bool InQuene(SqQuene *&q,ElemType d);/入队bool OutQuene(SqQuene *&q,ElemType &d);/出队对首元素void DispQuene(SqQuene *&q,Elem

7、Type d);/列取当前队列所有元素void Search(SqQuene *q,ElemType d);/搜索元素void Init(SqQuene *&q)/初始化队列q=(SqQuene *)malloc(sizeof(SqQuene);q->front=q->rear=-1;q->count=-1;q->no=0;void Destory(SqQuene *&q)/销毁队列free(q);bool InQuene(SqQuene *&q,ElemType d)/入队元素if(q->rear=MaxSize-1)cout<&l

8、t;"队满！"<<endl;return false;q->rear+;q->dataq->rear=d;return true;bool OutQuene(SqQuene *&q,ElemType &d)/出队元素if(q->front=q->rear)return false;q->front+;d=q->dataq->front;return true;void DispQuene(SqQuene *&q,ElemType d)/遍历队列元素cout<<"所有元素

9、:"for(int i=q->front+1;i<=q->rear;i+)q->front+;d=q->dataq->front;cout<<" "<<d;cout<<endl;q->front=q->count;void main()SqQuene *q;ElemType d;int n,choose;Init(q);for(;)cout<<" <*>"<<endl;cout<<" <* 1.入队

10、元素 *>"<<endl;cout<<" <* 2.出队元素 *>"<<endl;cout<<" <* 3.遍历队列 *>"<<endl;cout<<" <* 4.退出 *>"<<endl;cout<<" <*>"<<endl;cout<<"请选择:"cin>>choose;switch(choose)

11、case 1:docout<<"输入您需要入队的个数(n<="<<MaxSize<<"):"cin>>n;q->no=q->no+n;while(n>MaxSize|n<1);for(int i=0;i<n;i+)cout<<"元素"<<i+1<<":"cin>>d;InQuene(q,d);cout<<endl;break;case 2:if(q->front=q-

12、>rear)cout<<"n队列为空，请入队数据！"<<endl;break;elsecout<<"输入您需要出队的个数(n<="<<q->no<<"):"cin>>n;if(n>q->no)cout<<"需要弹出元素个数比实际元素多，将弹出队列所有元素！"<<endl;n=q->no;for(int i=0;i<n;i+)cout<<"元素"&l

13、t;<i+1<<":"OutQuene(q,d);q->count+;cout<<d<<endl;q->no-;break;case 3:if(q->front=q->rear)cout<<"n队列为空，请入队数据！"<<endl;break;elseDispQuene(q,d);break;case 4:exit(0);Destory(q);12、 链队列源代码/实现链队列的初始化、销毁、元素进队、出队等操作/采用字符型数据存储模式，指针型引用做形参#includ

14、e<iostream>#include<malloc.h>using namespace std;typedef char ElemType;typedef struct MyNodeElemType data;struct MyNode *next;QNode;typedef structQNode *front;QNode *rear;SqNode;void Init(SqNode *&n)n=(SqNode *)malloc(sizeof(SqNode);n->front=n->rear=NULL;void Destory(SqNode *&a

15、mp;n)free(n);bool InNode(SqNode *&n,ElemType &e)QNode *q;q=(QNode *)malloc(sizeof(QNode);q->data=e;q->next=NULL;if(n->rear=NULL)n->front=n->rear=q;elsen->rear->next=q;n->rear=q;cout<<"入队成功！"<<endl;return true;bool OutNode(SqNode *&n,ElemType

16、&e)QNode *p;if(n->rear=NULL)cout<<"队列为空n"<<endl;return false;p=n->front;n->front=n->front->next;e=p->data;free(p);return true;void main()SqNode *n;ElemType e;int choose;Init(n);for(;)cout<<" <*>"<<endl;cout<<" <* 1.入队元素 *>"<<endl;cout<<" <* 2.出队元素 *>"<<endl;cout<<" <* 3.退出 *>"<<endl;cout<<" <*>"<<endl;co