数据结构队列实验报告.doc

数据结构实验报告院系 应用科技学院 专业 电子信息工程 姓名 学号 10 级 电信 班 2011 年 11 月 11日1.实验目的：（1）掌握链接存储队列的进队和出队等基本操作。（2）掌握环行队列的进队和出队等基本操作。（3）加深对队列结构的理解，逐步培养解决实际问题的编程能力。2.实验要求：(1)编写链接队列的基本操作函数。typedef struct QNodeint data;struct QNode *next;QNode,*QueuePtr;typedef structQueuePtr front;/队头指针QueuePtr rear;/队尾指针LinkQueue;进队操作 EnQueue(LinkQueue &Q, int e)出队操作，队空DeQueue(LinkQueue &Q, int &e)输出队列中元素 0utputQueue(LinkQueue Q)(2)调用上述函数实现下列操作，操作步骤如下。调用进队函数建立一个队列。读取队列中的第一个元素。从队列中删除元素。输出队列中的所有元素。注意 每完成一个步骤就必须及时输出队列中元素，以便观察操作结果。(3)编写环型队列的基本操作函数。#define MAXSIZE 100 /最大队列长度,最多只能插入MAXSIZE-1个数据typedef struct int *base; /初始化的动态分配存储空间int front; /头指针，若队列不为空，指向队列头元素int rear; /为指针，若队列不为空，指向队列尾元素的下一个位置SqQueue;进队操作，返回1为队满 EnQueue(SqQueue &Q, int e)出队操作，返回1为队空 DeQueue(SqQueue &Q, int &e)输出队列中元素 OutputQueue(SqQueue &Q)(4)调用上述函数实现下列操作，操作步骤如下:调用进队函数建立一个队列。读取队列中的第一个元素。从队列中删除元素。输出队列中的所有元素。注意 每完成一个步骤就必须及时输出队列中元素，以便观察操作结果。3.调试内容：/链接队列（1）建立一个队列的功能1.输入的形式和输入值的范围：输入若干正整数，用空格分隔，用0来表示结束。2.输出的形式：按输入顺序输出。3.测试数据：输入5 2 3 6 9 0后，输出5 2 3 6 9（2）取队头元素功能1.取出队头元素是：52.输出队列元素是：5 2 3 6 9（3）删除队头元素功能1.删除队列数据元素是：52.输出队列元素是：2 3 6 9（4）输出队列所有元素功能输出队列所有元素是：2 3 6 9（5）结束功能输入0结束程序!/环型队列（1）初始化队列（2）建立一个队列的功能1.输入的形式和输入值的范围：输入若干正整数，用空格分隔，用0来表示结束。2.输出的形式：按输入顺序输出。3.测试数据：输入11 12 13 14 15 0后，输出11 12 13 14 15（3）取队头元素功能1.取出队头元素是：112.输出队列元素是：11 12 13 14 15（4）删除队头元素功能1.删除队列数据元素是：112.输出队列元素是：12 13 14 15（5）输出队列所有元素功能输出队列所有元素是：12 13 14 15（6）进队功能1.输入进队的元素：162.输出所有的（7）结束功能输入0结束程序!4.代码注释：/链接队列#include #include typedef struct Queueint data;struct Queue *next;Queue,*QueuePtr;typedef structQueuePtr front; /对头指针QueuePtr rear; /队尾指针LinkQueue;/*构造队列*/void InitQueu(LinkQueue &Q)Q.front=Q.rear=(QueuePtr)malloc(sizeof(Queue);Q.front-next=NULL;printf(构造成功!n);/*进队函数*/int EnQueue(LinkQueue &Q,int &e)QueuePtr p;p=(QueuePtr)malloc(sizeof(Queue);if(!p)return 0;p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;return 1;/*出队函数*/void DeQueue(LinkQueue &Q,int &e)QueuePtr p;if(Q.front=Q.rear)printf(该队列为空!n);p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;free(p);printf(出对成功!n);/*取对头函数*/void GetQueue(LinkQueue &Q,int &e)QueuePtr p;if(Q.front=Q.rear)printf(队列为空，无对头。n);p=Q.front-next;e=p-data;/*输出函数*/void OutQueue(LinkQueue Q) if(Q.rear =Q.front ) printf(队列为空，无元素值。n); Queue *head=Q.front-next ;while(head!=NULL) printf(%d,head-data );printf( ); head=head-next ;/*主函数*/void main()char ch;int e;LinkQueue Q;doprintf(ttt -队列操作- );printf(nttt*);printf(nttt* 0-退出 *);printf(nttt* 1-初始化 *);printf(nttt* 2-创建链队列 *);printf(nttt* 3-进队操作 *);printf(nttt* 4-出对操作 *);printf(nttt* 5-取对头元素 *);printf(nttt* 6-输出链队列的元素 *);printf(nttt*n);printf(请选择菜单号(0-6): ); ch=getchar();switch(ch)case 0:printf(您确定要退出吗(y/n): );scanf(%c,&ch);ch=getchar();if(ch=y)printf(退出程序!n);elseprintf(请继续n);getchar();break;case 1:InitQueu(Q);getchar();break;case 2: printf(请输入一个队列以0结束: ); scanf(%d,&e); while(e!=0) if(EnQueue(Q,e)!=0) scanf(%d,&e); printf(链队的元素有: n); OutQueue(Q); getchar(); break;case 3:printf(请输入要进队的元素e: );scanf(%d,&e);if(e=0)printf(进队失败!n);elseEnQueue(Q,e);printf(进队成功!n);printf(链队的元素有: n);OutQueue(Q);getchar();break;case 4:DeQueue(Q,e);printf(链队的元素有: n);OutQueue(Q);getchar();break;case 5:GetQueue(Q,e);printf(对头元素为：%dn,e);printf(链队的元素有: );OutQueue(Q);getchar();break;case 6:printf(链队的元素有: n);OutQueue(Q);getchar();break;default :getchar();printf(输入错误，请重新输入n);while(ch!=y);/环型队列#include #include #define MAXSIZE 100 /最大队列长度,最多只能插入MAXSIZE-1个数据typedef struct int *base; /初始化的动态分配存储空间int front; /头指针，若队列不为空，指向队列头元素int rear; /为指针，若队列不为空，指向队列尾元素的下一个位置SqQueue;void InitQueue(SqQueue &Q) Q.base=(int *)malloc(MAXSIZE * sizeof(int);if(!Q.base) printf(构造失败!n);Q.front=Q.rear=0;printf(构造成功!n);int EnQueue(SqQueue &Q, int e) if(Q.rear+1) % MAXSIZE = Q.front) return 0; Q.baseQ.rear=e; Q.rear=(Q.rear+1)%MAXSIZE;return 1;void GetQueue(SqQueue &Q,int &e) if(Q.front=Q.rear) printf(该循环队列为空，无对头元素!n);e=Q.baseQ.front; printf(取对头成功!n);void DeQueue(SqQueue &Q, int &e) if(Q.front=Q.rear) printf(该循环队列为空!n); e = Q.baseQ.front; Q.front=(Q.front+1) %MAXSIZE; printf(出对成功!n);void OutQueue(SqQueue &Q) int i; if(Q.front=Q.rear) printf(该循环队列为空!n); for(i=Q.front;iQ.rear;i+) printf(%d ,Q.basei); printf(n);/*主函数*/void main()char ch;int e;SqQueue Q;doprintf(ttt -队列操作- );printf(nttt*);printf(nttt* 0-退出 *);printf(nttt* 1-初始化 *);printf(nttt* 2-创建链队列 *);printf(nttt* 3-进队操作 *);printf(nttt* 4-取对头元素 *);printf(nttt* 5-出对操作 *);printf(nttt* 6-输出链队列的元素 *);printf(nttt*n);printf(请选择菜单号(0-6): ); ch=getchar();switch(ch)case 0:printf(您确定要退出吗(y/n): );scanf(%c,&ch);ch=getchar();if(ch=y)printf(退出程序!n);elseprintf(请继续n);getchar();break;case 1:InitQueue(Q);getchar();break;case 2: printf(请输入一个队列以0结束: ); scanf(%d,&e); while(e!=0) if(EnQueue(Q,e)!=0) scanf(%d,&e); printf(循环队列的元素有: ); OutQueue(Q); getchar(); break;case 3:printf(请输入要进队的元素e: );scanf(%d,&e);if(e=0)printf(进队失败!n);elseEnQueue(Q,e);printf(进队成功!n);printf(循环队列的元素有: );OutQueue(Q);getchar();break;case 4:printf(对头元素为：%dn,e=Q.baseQ.front);GetQueue(Q,e);printf(循环队列的元素有