队列实验报告

　一．实验项目名称

　循环队列和链式队列的创建 二、实验目的 1、掌握队列的特点(先进先出 FIFO)及基本操作,如入队、出队等， 2、队列顺序存储结构、链式存储结构和循环队列的实现，以便在实际问题背景下灵活应用。

　三、实验内容 1．链式队列的实现和运算 2．循环队列的实现和运算 四、主要仪器设备及耗材 VC++6.0 运行环境实现其操作 五．程序算法 (1) 循环队列操作的算法 1> 进队列 Void

　enqueue (seqqueue

　&q, elemtype

　x) {

　if ((q.rear+1)%maxsize = = q.front)

　cout<<”overflow”; else

　{

　 q.rear=(q.rear+1)%maxsize; //编号加 1 或循环

　 回第一个单元

　 q.queue[q.rear]=x;

　} } 2> 出队列 Void

　dlqueue(seqqueue

　&q ) {

　if (q.rear= =q.front)

　cout<<”underflow”;

　else

　 q.front =(q.front+1)%maxsize; } 3> 取对头元素

　elemtype

　gethead(seqqueue q ) { if

　(q.rear= =q.front)

　{ cout<<”underflow”；

　return

　NULL;}

　 else

　 return

　 q.queue[(q.front+1)%maxsize];

　//front 指向队头前一个位置 } 4> 判队列空否

　 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<iostream.h> #define MAXN

　20 struct seq { char queue[MAXN]; 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)

　 cout<<"overflow";

　else {

　q.rear=(q.rear+1)%MAXN;

　q.queue[q.rear]=x;

　} //return(0); } void dlq(seq &q) { if (q.rear == q.front) cout<<"underflow"; else

　q.front=(q.front+1)%MAXN; }

　 int gethead(seq &q)

　//取队头元素

　 {if (q.rear == q.front)

　//判断是否队列为空 cout<<"underflow"; else return q.queue[(q.front+1)%MAXN]; }

　main() {seq

　q; 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); y=gethead( q); cout<<"执行一次删除队头后，队头为="<<y<<endl; } b. 链队列的源代码 #include <iostream.h>

　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)

　 {

　 cout<<p->data<<"->";

　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 时结束："<<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; } 六.程序输入数据及实验结果 a.循环队列实验结果

　 c. 链队列实验结果

　七、思考讨论题或体会或对改进实验的建议

　（1）体会 a．C++语言知识不懂，需要好好学习； b．对单链表不够熟悉，要多练习创建单链表及其基本操作。

　八、参考资料 a.《数据结构》 李根强主编

　 中国国水利水电出版社 b.《C++语言程序设计》 郑莉

　董渊 何江舟编

　清华大学出版社

推荐访问： 队列 实验 报告