数据结构实验报告队列.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,ai>| 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<iostream.h>#include<malloc.h>#include<stdio.h>#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;i<q.rear;i+)printf("%d ",q.basei); printf("nn"); return 1;/显示队的元素status initqueue (squeue &q)/构造一个空队列Qq.base=(qelemtype *)malloc(maxqsize *sizeof(qelemtype );if(!q.base) return 0;/存储分配失败q.front=q.rear=0;return 1;int creat_q(squeue &q) /初始化一个队列 initqueue(q); qelemtype e; int i,n;printf("创建一个顺序队列,输入队列中的元素个数为:");cin>>n;for(i=0;i<n;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<<"输入要插入顺序队列的元素:"<<endl;cin>>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)cout<<"overflow"<<endl;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<<"输入插入的元素:"<<endl;cin>>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<<"输入循环队列的元素个数:"<<endl;cin>>n;for(i=0;i<n;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<<"删除的元素是:"<<e<<endl;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<<"输出队列的元素为:"<<endl;p=q.front->next;while(p)cout<<p->data;p=p->next;cout<<" "cout<<endl;status initqueue(linkqueue &q)/构造一个空队列q.front=q.rear=(queueptr)malloc(sizeof(qnode);if(!q.front)cout<<"overflow"<<endl;/存储分配失败q.front->next=NULL;cout<<"链队列初始化成功."<<endl;return 1;status creat_q(linkqueue &q)initqueue(q);queueptr p;int i,n;cout<<"输入构造的链队列的元素个数:"<<endl;cin>>n;for(i=0;i<n;i+)p=(queueptr)malloc(sizeof(qnode);cout<<"输入第"<<i+1<<"个元素"<<endl;cin>>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)cout<<"overflow"<<endl;cout<<"输入想插入链队尾的数:"<<endl;cin>>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<<"删除的元素为:"<<e<<endl;free(p);return 1;/定义一个主函数void main()int m,n,i;for(i=0;i<30;i+)cout<<"*"cout<<endl;cout<<"按1，执行顺序队列相关操作."<<endl;cout<<"按2，执行循环队列相关操作."<<endl;cout<<"按3，执行链队列相关操作."<<endl;for(i=0;i<30;i+)cout<<"*"cout<<endl;cout<<"按13，选择要执行的功能."<<endl;cin>>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<<"输入想执行的次数:"<<endl;cin>>n;for(i=0;i<n;i+)cout<<"输入一个数选择功能:"<<endl;cin>>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;i<30;i+)cout<<"*"cout<<endl;cout<<"按1，执行循环队列插入操作."<<endl;cout<<"按2，执行循环队列删除队头元素操作."<<endl;for(i=0;i<30;i+)cout<<"*"cout<<endl;cout<<"输入想执行的次数:"<<endl;cin>>n;for(i=0;i<n;i+)cout<<"输入一个数选择功能:"<<endl;cin>>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;i<30;i+)cout<<"*"cout<<endl;cout<<"按1，执行链队列插入操作:"<<endl;cout<<"按2，执行链队列删除队头元素操作:"<<endl;for(i=0;i<30;i+)cout<<"*"cout<<endl;cout<<"输入想执行的次数:"<<endl;cin>>n;for(i=0;i<n;i+)cout<<"输入一个数选择功能:"<<endl;cin>>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;default:cout<<"输入有误！"<<endl;四、调试分析1、选择要执行的操作2、输入数据3、选择要执行的功能4、输入需要插入或删除的数据五、测试结果1、开始界面2、顺序队列相关操作3、循环队列相关操作4、链队列相关操作