队列实验报告.doc

一实验项目名称 循环队列和链式队列的创建二、实验目的1、掌握队列的特点(先进先出FIFO)及基本操作,如入队、出队等，2、队列顺序存储结构、链式存储结构和循环队列的实现，以便在实际问题背景下灵活应用。三、实验内容1链式队列的实现和运算2循环队列的实现和运算四、主要仪器设备及耗材VC+6.0运行环境实现其操作五程序算法(1) 循环队列操作的算法1进队列Void enqueue (seqqueue &q, elemtype x) if (q.rear+1)%maxsize = = q.front) cout出队列Void dlqueue(seqqueue &q ) if (q.rear= =q.front) cout取对头元素elemtype gethead(seqqueue q ) if (q.rear= =q.front) cout判队列空否 int empty(seqqueue q ) if (q.rear= =q.front) reurn 1;else return 0; （2）.链队列操作的算法1.链队列上的初始化 void INIQUEUE( linkqueue &s) link *p; p=new link; p-next=NULL; /p是结构体指针类型，用- s.front=p; /s是结构体变量，用. s.rear=p; /头尾指针都指向头结点2.入队列void push(linkqueue &s, elemtype x) link *p; /p是结构体指针类型，用- p=new link; p-data=x; p-next=s.rear-next; /s是结构体变量，用.s.rear-next=p; s.rear=p; /插入最后3判队空int empty( linkqueue s ) if (s.front= =s.rear) return 1; else return 0;4.取队头元素 elemtype gethead( linkqueue s ) if (s.front= =s.rear) return NULL; else retuen s.front-next-data;5.出队列 void pop(linkqueue &s) link *p; p=s.front-next;if (p-next= =NULL)/链队列中只有一个元素,需要修改rear指针 s.front-next=NULL; s.rear=s.front;else s.front-next =p-next;/rear不用变delete (p);六.程序源代码a. 循环队列源代码#include#define MAXN 20struct seqchar queueMAXN;int front , rear; ;void iniq(seq &q)q.front=q.rear=MAXN-1;void enq(seq &q,char x)if(q.rear+1)%MAXN=q.front)coutoverflow;else q.rear=(q.rear+1)%MAXN; q.queueq.rear=x;/return(0);void dlq(seq &q)if (q.rear = q.front)coutunderflow;elseq.front=(q.front+1)%MAXN;int gethead(seq &q) /取队头元素 if (q.rear = q.front) /判断是否队列为空coutunderflow;elsereturn q.queue(q.front+1)%MAXN;main()seq q;int i,y;iniq(q);cout输入元素入队0为止i;while(i)enq( q,i);cini;y=gethead( q);cout队头为=yendl;dlq( q);y=gethead( q);cout执行一次删除队头后，队头为=yendl;b. 链队列的源代码#include typedef struct QNode char data; QNode *next;QNode,*QueuePtr;typedef struct QueuePtr front; QueuePtr rear;LinkQueue;InitQueue(LinkQueue &Q) Q.front=Q.rear=new QNode;Q.front-next=NULL;return 0;EnQueue(LinkQueue &Q,char e)QueuePtr p; p=new QNode;p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;return 0;void disp(LinkQueue &Q) /打印队列QueuePtr p;p=Q.front-next;while(p!=NULL) coutdata; p=p-next;DeQueue(LinkQueue &Q,char &e) QueuePtr p; if(Q.front=Q.rear)return 1;p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;delete p;return 0;void main() LinkQueue Q;char e,e1; InitQueue(Q);cout输入队列元素,0时结束：e; while(e!=0)EnQueue(Q,e);cine;cout队列为：endl;disp(Q);DeQueue(Q,e1);coutendl执行一次删除队头，删除的元素是:e1endl;cout队列为:endl;disp(Q);coutendl;六.程序输入数据及实验结果a.循环队列实验结果c. 链队列实