队列实验报告.doc

1、队列实验报告一实验工程名称循环队列和链式队列的创立 二、实验目的 1、掌握队列的特点(先进先出 FIFO)及根本操作,如入队、出队等， 2、队列顺序存储构造、链式存储构造和循环队列的实现，以便在实际问题背景下灵敏应用。三、实验内容 1链式队列的实现和运算 2循环队列的实现和运算 四、主要仪器设备及耗材 VC+6.0 运行环境实现其操作 五程序算法 (1) 循环队列操作的算法 1> 进队列 Voidenqueue (seqqueue&q, elemtype_) if (q.rear+1)%ma_size = = q.front)cout<<”overflow”; els

2、eq.rear=(q.rear+1)%ma_size; /编号加 1 或循环回第一个单元q.queueq.rear=_; 2> 出队列 Voiddlqueue(seqqueue&q ) if (q.rear= =q.front)cout<<”underflow”;elseq.front =(q.front+1)%ma_size; 3> 取对头元素 elemtypegethead(seqqueue q ) if(q.rear= =q.front) cout<<”underflow”；returnNULL;elsereturnq.queue(q.fron

3、t+1)%ma_size;/front 指向队头前一个位置 4> 判队列空否int empty(seqqueue q ) if(q.rear= =q.front)reurn 1;else return 0; 2.链队列操作的算法 1> .链队列上的初始化voidINIQUEUE( linkqueue&s)link_p;p=newlink;p->ne_t=NULL;/p 是构造体指针类型，用->s.front=p;/s 是构造体变量，用. s.rear=p;/头尾指针都指向头结点 2>.入队列 voidpush(linkqueue &s, elemt

4、ype_) link_p;/p 是构造体指针类型，用->p=newlink;p->data=_;p->ne_t=s.rear->ne_t;/s 是构造体变量，用.s.rear->ne_t=p;s.rear=p;/插入最后 3> 判队空 intempty( linkqueues ) if (s.front= =s.rear) return 1;else return 0; 4>.取队头元素elemtypegethead( linkqueue s ) if (s.front= =s.rear)returnNULL;elseretuens.front->

5、;ne_t->data; 5>.出 出 队列voidpop(linkqueue &s) link_p;p=s.front->ne_t; if (p->ne_t= =NULL)/链队列中只有一个元素,需要修改 rear 指针s.front->ne_t=NULL;s.rear=s.front; elses.front->ne_t =p->ne_t;/rear 不用变 delete (p); 六 六.程序代码 a.循环队列代码 #include<iostream.h> #define MA_N20 struct seq char queu

6、eMA_N; int front, rear;void iniq(seq&q) q.front=q.rear=MA_N-1; void enq(seq &q,char _) if(q.rear+1)%MA_N=q.front)cout<<“overflow”;else q.rear=(q.rear+1)%MA_N;q.queueq.rear=_; /return(0); void dlq(seq &q) if (q.rear = q.front) cout<<“underflow”; else q.front=(q.front+1)%MA_N;

7、int gethead(seq &q)/取队头元素if (q.rear = q.front)/判断是否队列为空 cout<<“underflow”; else return q.queue(q.front+1)%MA_N; main seqq; int i,y; iniq(q); cout<<“输入元素入队 0 为止”<<endl; cin>>i; while(i) enq( q,i); cin>>i; y=gethead( q); cout<<“队头为=”<<y<<endl; dlq( q

8、); y=gethead( q); cout<<“执行一次删除队头后，队头为=”<<y<<endl; b.链队列的代码 #include <iostream.h>typedef struct QNode char data;QNode _ne_t;QNode,_QueuePtr;typedef struct QueuePtr front; QueuePtr rear; LinkQueue;InitQueue(LinkQueue &Q) Q.front=Q.rear=new QNode;Q.front->ne_t=NULL;retur

9、n 0; EnQueue(LinkQueue &Q,char e) QueuePtr p;p=new QNode;p->data=e;p->ne_t=NULL;Q.rear->ne_t=p;Q.rear=p;return 0; void disp(LinkQueue &Q) /打印队列QueuePtr p;p=Q.front->ne_t;while(p!=NULL)cout<<p->data<<“->”;p=p->ne_t;DeQueue(LinkQueue &Q,char &e) QueuePt

10、r p;if(Q.front=Q.rear)return 1;p=Q.front->ne_t; e=p->data;Q.front->ne_t=p->ne_t;if(Q.rear=p)Q.rear=Q.front;delete p;return 0; void mainLinkQueue Q;char e,e1;InitQueue(Q);cout<<“输入队列元素,0 时完毕：”<<endl;cin>>e;while(e!="0")EnQueue(Q,e);cin>>e;cout<<“队列为：”<<endl;disp(Q);DeQueue(Q,e1);cout<<endl<<“执行一次删除队头，删除的元素是:”<<e1<<endl;cout<<“队列为:”<<endl;disp(Q);cout<<endl; 六.程序