数据结构实验报告 队列.doc

数据结构实验报告题目：编制一个顺序队列的实现和运算的程序班级：11级网络工程姓名（学号）：丁晓娟、杨梦莹、锁佩琳、张凤友、胡景林、倪华夏完成日期：2013.4.17一、 需求分析1、演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中的规定命令；相应的输入数据和运算显示在其后。2、程序执行命令包括：1)构造一个顺序队列2）对其进行插入元素3)对其进行删除元素4)对其取对头元素5)对其求队列的长度3、测试数据：可由使用者自己输入二、概要设计adt queue 数据对象:d=ai|aielemset,i=1,2,n,n=0数据关系:r=| ai-1,aid,i=2,n/约定其中a1端为队列头，an端为队列尾基本操作： initqueue (&q) 操作结果：构造一个空队列q 。 destroyqueue(&q)初始条件:队列q已存在。 操作结果:队列q被销毁，不再存在。clearqueue(&q)初始条件:队列q已存在。操作结果:将q清为空队列。queueempty(&q)初始条件:队列q已存在。操作结果:若q为空队列，则返回true,否则返回false。queuelength(&q)初始条件:队列q已存在。操作结果:返回q的元素个数，即对列的长度。gethead(q,&e)初始条件:q为非空队列。操作结果:用e返回q的对头元素。enqueue(&q,e)初始条件:队列q已存在。操作结果:插入元素e为新的队尾元素。dequeue(&q,&e)初始条件:q为非空队列。操作结果:删除q的对头元素，并用e返回其值。 adt queue三、详细设计#include#include#include#define maxqsize 100 /队列最大长度typedef int status;typedef int qelemtype;/顺序队列操作int t;/全称变量typedef struct qelemtype *base;/初始化的动态分配存储空间int front;/头指针，若队列不为空，指向队列头元素int rear;/尾指针，若队列不为空，指向队列尾元素的下一个位置 squeue;int display(squeue &q)if(q.front=q.rear)printf(队为空);return 0;/判断队是否为空else printf(输出顺序队列的元素为：); for(int i=q.front;in;for(i=0;in;i+)printf(请输入%d个数据：,i+1); scanf(%d,&e);q.baseq.rear=e;q.rear=q.rear+1; display(q);return 1;int enqueue(squeue &q,qelemtype e)/插入元素e为q的新的队尾元素 cout输入要插入顺序队列的元素:e;if(q.rear+1)%maxqsize=q.front)return 0;/队列满q.baseq.rear=e;q.rear=q.rear+1;display(q);return 1;int dequeue(squeue &q,qelemtype &e)/若队列不为空，则删除q的队头元素，用e返回其值，应返回ok；/否则返回errorif(q.front=q.rear)return 0;e=q.baseq.front;printf(删除队头元素为：%dn,e);q.front+;return 1;/循环队列操作typedef structqelemtype *base;int front;int rear;sqqueue;void display(sqqueue &q)int i=q.front; /让i等于队头位置的值if(q.front=q.rear) printf(队列为空n!); elseprintf(输出队列的元素为: );while(i!=q.rear) printf(%d ,q.basei); i=(i+1)%maxqsize;printf(nn);status initqueue(sqqueue &q)q.base=(qelemtype *)malloc(maxqsize*sizeof(qelemtype);if(!q.base)coutoverflowendl;q.front=q.rear=0;return 1;status enqueue(sqqueue &q,qelemtype e)/插入e为q的队尾元素if(q.rear+1)%maxqsize=q.front)return 0;/队列满cout输入插入的元素:e;q.baseq.rear=e;q.rear=(q.rear+1)%maxqsize;return 1;status creat_q(sqqueue &q)initqueue(q);qelemtype e;int n,i;if(q.rear+1)%maxqsize=q.front)cout队列已满endl;cout输入循环队列的元素个数:n;for(i=0;in;i+)enqueue(q,e);display(q);return 1;status dequeue(sqqueue &q,qelemtype e)/若队列不为空，删除q队头的元素if(q.front=q.rear)return 0;e=q.baseq.front;cout删除的元素是:eendl;q.front=(q.front+1)%maxqsize;return 1;/链队列操作typedef struct qnodeqelemtype data;struct qnode *next;qnode,*queueptr;typedef struct queueptr front;/队头指针queueptr rear;/队尾指针linkqueue;void display(linkqueue &q)queueptr p;if(q.front=q.rear)cout队列为空.endl;else cout输出队列的元素为:next;while(p)coutdata;p=p-next;cout ;coutendl;status initqueue(linkqueue &q)/构造一个空队列q.front=q.rear=(queueptr)malloc(sizeof(qnode);if(!q.front)coutoverflownext=null;cout链队列初始化成功.endl;return 1;status creat_q(linkqueue &q)initqueue(q);queueptr p;int i,n;cout输入构造的链队列的元素个数:n;for(i=0;in;i+)p=(queueptr)malloc(sizeof(qnode);cout输入第i+1个元素p-data;p-next=null;q.rear-next=p;q.rear=p;display(q);return 1;status enqueue(linkqueue &q,qelemtype e)/插入e为q的队尾元素queueptr p;p=(queueptr)malloc(sizeof(qnode);if(!p)coutoverflowendl;cout输入想插入链队尾的数:e;p-data=e;p-next=null;q.rear-next=p;q.rear=p;return 1;status dequeue(linkqueue &q,qelemtype &e)/若队列不空，删除q的队头元素queueptr p;if(q.front=q.rear)return 0;p=q.front-next;e=p-data;q.front-next=p-next;if(q.rear=p)q.rear=q.front;cout删除的元素为:eendl;free(p);return 1;/定义一个主函数void main()int m,n,i;for(i=0;i30;i+)cout*;coutendl;cout按1，执行顺序队列相关操作.endl;cout按2，执行循环队列相关操作.endl;cout按3，执行链队列相关操作.endl;for(i=0;i30;i+)cout*;coutendl;cout按13，选择要执行的功能.m;switch(m)case 1:squeue q;int i,m,n; qelemtype e;initqueue(q); creat_q(q);printf(n*n);cout按1,向顺序队尾插入元素.endl;cout按2,删除顺序队头元素:endl; printf(*n); cout输入想执行的次数:n;for(i=0;in;i+)cout输入一个数选择功能:m;switch(m)case 1:enqueue(q,e);break;case 2:cout执行删除操作.endl;dequeue(q,e);display(q);break;default:cout输入有误！endl;break;case 2:sqqueue q;qelemtype e;int m,n,i,j;creat_q(q);for(i=0;i30;i+)cout*;coutendl;cout按1，执行循环队列插入操作.endl;cout按2，执行循环队列删除队头元素操作.endl;for(i=0;i30;i+)cout*;coutendl;cout输入想执行的次数:n;for(i=0;in;i+)cout输入一个数选择功能:m;switch(m)case 1:enqueue(q,e);display(q);break;case 2:cout执行删除操作.endl;dequeue(q,e);display(q);break;default:cout输入有误！endl;break;case 3:linkqueue q;qelemtype e;int m,n,i,j;creat_q(q);for(i=0;i30;i+)cout*;coutendl;cout按1，执行链队列插入操作:endl;cout按2，执行链队列删除队头元素操作:endl;for(i=0;i30;i+)cout*;coutendl;cout输入想执行的次数:n;for(i=0;in;i+)cout输入一个数选择功能:m;switch(