实验三队列实验报告.doc

计算机科学与技术系 实 验 报 告 专业名称 计算机科学与技术 课程名称 数据结构与算法 项目名称 实验三队列实验 班 级 学 号 1 姓 名 同组人员 无 实验日期 实验三 队列实验实验题目：建立含有若干个元素的循环队列和链队列，并分别实现循环队列和链队列的入队和出对操作。（1）先实现循环队列的入队和出队操作 1.问题分析本程序要求实现建立含有若干个元素的循环队列，并实现循环队列的入队和出队操作。完成该实验需要以下4个子任务：定义一个循环队列的存储结构，定义队列的基本算法。定义一个display（）函数实现队列元素的输出看入队是否成功通过队列的基本算法实现队列的出队操作在主函数中完成操作测试数据设计如下：1 2 3 4 5 62.概要设计为了实现上述程序功能，需要：声明一个循环队列定义出队列的基本算法，通过键盘输入5个整数，入队，出队 在主函数中先往队列里输入5个元素，然后入队，输出，看入队是否成功，然后出队，再调用display（）函数看是否出队。1） 本程序包含7个函数：1主函数main()2.置空队：InitQueue()3.判对空: QueueEmpty()4.判队满：QueueFull()5.入队:Add()6.出队:Delete()7.display() 各函数关系如下： InitQueue() QueueEmpty()Main () QueueFull() Add()Main Delete()display()3、 详细设计实现概要设计中定义的所有的数据类型，对每个操作给出了算法和代码，主程序和模块都需要代码。（1）循环队列 #define maxlen 10typedef structint data maxlen;int front;int rear;SeqQueue;(2)队列基本算法 SeqQueue *InitQueue(SeqQueue *q) /建立一个空循环队列q=(SeqQueue *)malloc(sizeof (SeqQueue);q-front=0;q-rear=0;return q;int QueueFull (SeqQueue *q) /判断队列是否为满if (q-front=(q-rear+1)%maxlen)return 1;else return 0;int QueueEmpty(SeqQueue *q)/判断队列是否为空if (q-rear=q-front)return 1;else return 0;void Add (SeqQueue *q,int x) /入队if(!QueueFull(q)q-rear=(q-rear+1)%maxlen;q-dataq-rear=x;else printf (queue full);void Delete(SeqQueue *q) /出队if (!QueueEmpty(q)q-front=(q-front+1)%maxlen;else printf (queue Empty);(3）用display()函数输出循环队列元素void display(SeqQueue *q)/输出循环队列q的元素int i;if(q-front!=q-rear)/循环队列非空，输出队列元素printf(输出循环队列元素：); i=q-front;doi=(i+1)%maxlen;printf(%d,q-datai);while(i!=q-rear);elseprintf(队列为空！);（4）在主函数中先往队列里输入5个元素，输出，看入队是否成功，然后出队，再调用display（）函数看是否出队。int main()SeqQueue *q;int i,y;q=InitQueue(q);/建立空循环队列printf(请输入5个元素);for(i=0;i5;i+)/入队5个元素scanf(%d,&y);Add(q,y);display(q);/输出循环队列元素for(i=0;i5;i+)/把5个元素出队Delete(q);printf(n请输入1个元素);scanf(%d,&y);/再入队一个元素Add(q,y);display(q);/再输出循环队列元素return 0;4、调试分析 编译无错误5、用户使用说明 程序名为class1.exe，在DEBUG文件夹里面。运行环境Visual c+ 6.0。6、测试结果7、附录#include #include #define maxlen 10typedef structint data maxlen;int front;int rear;SeqQueue;SeqQueue *InitQueue(SeqQueue *q) /建立一个空循环队列q=(SeqQueue *)malloc(sizeof (SeqQueue);q-front=0;q-rear=0;return q;int QueueFull (SeqQueue *q) /判断队列是否为满if (q-front=(q-rear+1)%maxlen)return 1;else return 0;int QueueEmpty(SeqQueue *q)/判断队列是否为空if (q-rear=q-front)return 1;else return 0;void Add (SeqQueue *q,int x) /入队if(!QueueFull(q)q-rear=(q-rear+1)%maxlen;q-dataq-rear=x;else printf (queue full);void Delete(SeqQueue *q) /出队if (!QueueEmpty(q)q-front=(q-front+1)%maxlen;else printf (queue Empty);void display(SeqQueue *q)/输出循环队列q的元素int i;if(q-front!=q-rear)/循环队列非空，输出队列元素printf(输出循环队列元素：); i=q-front;doi=(i+1)%maxlen;printf(%d,q-datai);while(i!=q-rear);elseprintf(队列为空！);int main()SeqQueue *q;int i,y;q=InitQueue(q);/建立空循环队列printf(请输入5个元素);for(i=0;i5;i+)/入队5个元素scanf(%d,&y);Add(q,y);display(q);/输出循环队列元素for(i=0;ifront=(LinkList *)malloc(sizeof(LinkList);q-front-next=NULL;q-rear=q-front;return q;int QueueEmpty(LinkQueue *q)/判断队列是否为空if (q-rear=q-front)return 1;else return 0;LinkQueue *Add (LinkQueue *q,int x) /入队LinkList *p;p=(LinkList *)malloc(sizeof (LinkList);p-data=x;p-next=NULL;q-rear-next=p;q-rear=p;return q;LinkQueue *Delete(LinkQueue *q)/出队LinkList *p;if (!QueueEmpty(q)p=q-front-next; q-front-next=p-next;if(p-next=NULL)q-rear=q-front;free(p);return q;else printf (queue Empty);(3）用display()函数输出链队列元素void display(LinkQueue *q)/输出链队列的元素LinkList *p;p=q-front-next;if(p!=NULL)printf(输出链队元素);while(p!=NULL)printf(%2d,p-data);p=p-next;else printf(n链队为空);（4）在主函数中先往队列里输入5个元素，输出，看入队是否成功，然后出队，再调用display（）函数看是否出队。int main()int i,y=0;SetQueue();/建立空链队列display(q); printf(n请输入5个元素);for(i=0;i5;i+)/入队5个元素scanf(%d,&y);Add(q,y);display(q);for(i=0;i5;i+)/把5个元素出队Delete(q);display(q);/看是否出队成功return 0;4、调试分析 编译无错误5、用户使用说明 程序名为class12exe，在DEBUG文件夹里面。运行环境Visual c+ 6.0。6、测试结果7、附录#include #include #define maxlen 10typedef struct nodeint data;struct node *next;LinkList;typedef structLinkList *front,*rear;LinkQueue;LinkQueue *q;LinkQueue *SetQueue() /建立一个空链队列 q=(LinkQueue *)malloc(sizeof (LinkQueue);q-front=(LinkList *)malloc(sizeof(LinkList);q-front-next=NULL;q-rear=q-front;return q;int QueueEmpty(LinkQueue *q)/判断队列是否为空if (q-rear=q-front)return 1;else return 0;LinkQueue *Add (LinkQueue *q,int x) /入队LinkList *p;p=(LinkList *)malloc(sizeof (LinkList);p-data=x;p-next=NULL;q-rear-next=p;q-rear=p;return q;LinkQueue *Delete(LinkQueue *q)/出队LinkList *p;if (!QueueEmpty(q)p=q-front-next; q-front-next=p-next;if(p-next=NULL)q-rear=q-front;free(p);return q;else printf (queue Empty);void display(LinkQueue *q)/输出链队列的元素LinkList *p;p=q-front-next;if(p!=NULL)printf(输出链队元素);while(p!=NULL)printf(%2d,p-data);p=p-next;else printf(n链队为空);int main()int i,y=0;SetQueue();/建立链队列display(q); printf(n请输入5个元素);for(i=0;i5;i+)/入队5个元素scanf(%d,&y);Add(q,y);display(q);for(i=0;ifront=0;q-rear=0;return q;int QueueFull (SeqQueue *q) /判断队列是否为满if (q-front=(q-rear+1)%maxlen)return 1;else return 0;int QueueEmpty(SeqQueue *q)/判断队列是否为空if (q-rear=q-front)return 1;else return 0;char GetHead(SeqQueue *q) /取栈顶元素if(!QueueEmpty(q)return q-data(q-front+1)%maxlen;else printf(queue Empty);void Add (SeqQueue *q,char x) /入队if(!QueueFull(q)q-rear=(q-rear+1)%maxlen;q-dataq-rear=x;else printf (queue full);void Delete(SeqQueue *q) /出队if (!QueueEmpty(q)q-front=(q-front+1)%maxlen;else printf (queue Empty);(3）用print()函数验证程序void print(SeqQueue *q)char x,y,t;x=e;y=c;Add(q,h);Add(q,r);Add(q,y);x=GetHead(q);Delete(q);Add(q,x);x=GetHead(q);Delete(q);Add(q,a);while (QueueEmpty(q)=0)y=GetHead(q);Delete(q);printf(%c,y);printf(%c,x);（4）在主函数中调用print（）函数验证程序int main()SeqQueue *q;q=InitQueue(q);print(q);return 0;4、调试分析 编译无错误5、用户使用说明 程序名为class2.exe，在DEBUG文件夹里面。运行环境Visual c+ 6.0。6、测试结果7、附录#include #include #define maxlen 10typedef structchar data maxlen;int front;int rear;SeqQueue;SeqQueue *InitQueue(SeqQueue *q) /建立一个空循环队列q=(SeqQueue *)malloc(sizeof (SeqQueue);q-front=0;q-rear=0;return q;int QueueFull (SeqQueue *q) /判断队列是否为满if (q-front=(q-rear+1)%maxlen)return 1;else return 0;int QueueEmpty(SeqQueue *q)/判断队列是否为空if (q-rear=q-front)return 1;else return 0;char GetHead(SeqQueue *q) /取栈顶元素if(!QueueEmpty(q)return q-data(q-front+1)%maxlen;else printf(queue Empty);void Add (SeqQueue *q,char x) /入队if(!QueueFull(q)q-rear=(q-rear+1)%maxlen;q-dataq-rear=x;else printf (queue full);void Delete(SeqQueue *q) /出队if (!QueueEmpty(q)q-front=(q-front+1)%maxlen;else printf (queue Empty);void print(SeqQueue *q)char x,y,t;x=e;y=c;Add(q,h);Add(q,r);Add(q,y);x=GetHead(q);Delete(q);Add(q,x);x=GetHead(q);Delete(q);Add(q,a);while (QueueEmpty(q)=0)y=GetHead(q);Delete(q);printf(%c,y);printf(%c,x);int main()SeqQueue *q;q=InitQueue(q);print(q);return 0;