《数据结构--04队列的基本操作.doc》由会员分享，可在线阅读，更多相关《数据结构--04队列的基本操作.doc（10页珍藏版）》请在三一文库上搜索。
1、数据结构实验报告院系 光电与信息工程学院 专业 电子信息工程姓名 学号 电话 2011级 2班 2013年4月20日1实验题目 实验4 .对列的基本操作2需求分析 （1）编写链接队列的基本操作函数，调用上述函数实现下列操作，操作步骤如下：调用进队函数建立一个队列。读取队列中的第一个元素。从队列中删除元素。输出队列中的所有元素。（2）编写环型队列的基本操作函数。调用上述函数实现下列操作，操作步骤如下:调用进队函数建立一个队列。读取队列中的第一个元素。从队列中删除元素。输出队列中的所有元素。链接队列：进队操作 EnQueue(LinkQueue *Q, QElemType e)出队操作，队空 De
2、Queue(LinkQueue *Q, QElemType *e)输出队列中元素 0utputQueue(LinkQueue Q)环型队列：进队操作，返回1为队满 EnQueue(SqQueue *Q, QElemType e)出队操作，返回1为队空 DeQueue(SqQueue *Q, QElemType *e)输出队列中元素 outPutQMeue(SqQueue Q)输入形式：整型数。 3概要设计（1）链接队列 ADT QNode 数据对象：D=ai|aiIntegerSet,i=0,1,2,n,n0 结构关系：R=|ai,ai+1 D 基本操作： InitQueue(LinkQueu
3、e *Q) 操作前提：Q是一个未初始化的链接队列 操作结果：将Q初始化为一个空的链接队列 EnQueue(LinkQueue *Q, QElemType e) 操作前提：链接队列Q已存在 操作结果：将元素e插入到链接队列中 DeQueue(LinkQueue *Q, QElemType *e) 操作前提：链接队列Q已存在 操作结果：将链接队列Q中队头元素删除，删除的元素值通过e返回 0utputQueue(LinkQueue Q) 操作前提：链接队列Q已存在操作结果：将链接队列Q中的元素显示到屏幕上 本程序包含5个函数： 主函数main() 初始化链接队列函数 InitQueue() 进队函数
4、EnQueue() 出队函数DeQueue() 输出队列中元素函数 OutputStack()各函数调用关系：主函数main调用其他四个函数 主函数的伪码main() 定义变量i，n，m； 定义一个LinkQueue 变量Lq 初始化 Lq；输入队列元素的个数； For循环（i=1;i=n;i+）调用EnQueue函数；输出队列中元素；调用DeQueue函数；显示删除的队头元素；显示Lq； （2）环形队列ADT SqQueue 数据对象：D=ai|aiIntegerSet,i=0,1,2,n,n0 结构关系：R=|ai,ai+1 D 基本操作： InitQueue(SqQueue &Q) 操作
5、前提：Q是一个未初始化的环型队列 操作结果：将Q初始化为一个空的环型队列 EnQueue(SqQueue *Q,int e) 操作前提：环型队列Q已存在 操作结果：将元素e插入到队列中 DeQueue(SqQueue *Q,int *e) 操作前提：环型队列Q已存在 操作结果：将环型队列Q中队头元素删除，删除的元素值通过e返回 outPutQMeue(SqQueue *Q) 操作前提：环型队列Q已存在操作结果：将环型队列Q中的元素显示到屏幕上 本程序包含5个函数： 主函数main() 初始化链接队列函数 InitQueue() 进队函数EnQueue() 出队函数DeQueue() 输出队列中
6、元素函数 OutputStack()各函数调用关系：主函数main调用其他四个函数函数的伪码main（）定义SqQueue 变量sq;定义整型变量n,i,m;构造空的环型队列；输入队列的长度；For循环（i=1;ifront=Q-rear=申请新结点; Q-front-next=NULL;（2）进队 void Push(SqStack &S,int e) 定义QueuePtr变量 p；p=申请新的空间；如果申请失败，结束程序 p-data=e;p-next=NULL;如果是第一个元素则Q-front-next=p;Q-rear-next=p; Q-rear=p;(3)出队int Pop(SqS
7、tack *S,int e) 定义QueuePtr变量 p；如果队空则返回0；p=Q-front-next;*e=p-data;Q-front-next=p-next;如果Q-rear=p则Q-rear=Q-front;；释放p的空间；返回1；（4）输出元素int OutputQueue(LinkQueue Q) 定义QueuePtr变量 p；如果队空则返回0；p=Q.front-next;while(p)printf(%d ,p-data);p=p-next;printf(n);返回1;（2）环形队列 类型定义typedef structint *base;int front;int rea
8、r;SqQueue;基本操作的伪码算法（1）初始化void InitQueue(SqQueue &Q) Q.base=申请新的空间；如果申请失败，结束程序；Q.front=Q.rear=0;（2）进队 int EnQueue(SqQueue *Q,int e) 如果队满了则返回1；Q-baseQ-rear=e;Q-rear=(Q-rear+1)%MAXQSIZE;返回0；出队int DeQueue(SqQueue *Q,int *e)DeQueue(SqQueue *Q,int *e) 如果队空则返回1； *e=Q-baseQ-front;Q-front=(Q-front+1)%MAXQSIZ
9、E;返回0；（4）输出元素 void outPutQMeue(SqQueue *Q) 定义整型变量i；For循环（i=Q-front;irear;i+)输出Q-basei；换行；5 调试分析 链接队列：调试是出现错误，经过检查发现在某些地方分号用中文表示，出现空指针问题。环型队列：出现空指针问题，内存不能读取等6 使用说明 （1）链接队列：程序执行过程如下：提示用户输入元素个数；用户按要求输入一个整型数；程序输出构造好的链接队列；调用出队函数，并把剩余元素显示在屏幕上；（2）环型队列：程序执行过程如下：提示用户输入队列元素个数；用户按要求输入一个整型数；程序用输入的整型数构建一个环型队列，并输
10、出队列元素；调用出栈函数，删除栈顶，显示栈中元素； 7 测试结果（1）链接队列构造一个空的链接队列后，屏幕显示：请输入队列的元素个数：输入5后，屏幕显示建立的队列元素：1 2 3 4 5调用出队函数后，屏幕显示：2 3 4 5（2）环形队列建立空队列，程序运行后屏幕显示：输入队列元素的长度输入5后，屏幕显示队列的元素：1 2 3 4 5接着屏幕又显示：队列中的第一个元素为：1调用出队函数，然后输入队列中元素：2 3 4 58. 参考文献数据结构（c语言版）9附录源程序文件如下：（1）链接队列 #include #include typedef struct QNode int data; st
11、ruct QNode *next; QNode,*QueuePtr; typedef struct QueuePtr front; QueuePtr rear; LinkQueue; void InitQueue(LinkQueue *Q) Q-front=Q-rear=(QNode *)malloc(sizeof(QNode); Q-front-next=NULL; void EnQueue(LinkQueue *Q,int e) QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode); if(!p)exit(1); p-data=e; p-next=NUL
12、L; if(Q-front-next=NULL) Q-front-next=p; Q-rear-next=p; Q-rear=p; int DeQueue(LinkQueue *Q,int *e) QueuePtr p; if(Q-front=Q-rear)return 0; p=Q-front-next; *e=p-data; Q-front-next=p-next; if(Q-rear=p)Q-rear=Q-front; free(p); return 1; int OutputQueue(LinkQueue Q) QueuePtr p; if(Q.front=Q.rear)return
13、0; p=Q.front-next; while(p) printf(%d ,p-data); p=p-next; printf(n); return 1; void main() int i,n; int m; LinkQueue Lq; printf(构造一个空的链接队列); InitQueue(&Lq); printf(n请输入队列的元素个数:); scanf(%d,&n); for(i=1;i=n;i+) EnQueue(&Lq,i); printf(队列中的元素为:); OutputQueue(Lq); DeQueue(&Lq,&m); printf(删除队列中的第一个元素n此时队列
14、中的元素为:); OutputQueue(Lq); （2）环形队列 #include #include #define MAXQSIZE 100 typedef struct int *base; int front; int rear; SqQueue; void InitQueue(SqQueue &Q) Q.base=(int *)malloc(MAXQSIZE*sizeof(int); if(!Q.base)exit(1); Q.front=Q.rear=0; int EnQueue(SqQueue *Q,int e) if(Q-rear+1)%MAXQSIZE=Q-front)ret
15、urn 1; Q-baseQ-rear=e; Q-rear=(Q-rear+1)%MAXQSIZE; return 0; int DeQueue(SqQueue *Q,int *e) if(Q-front=Q-rear)return 1; *e=Q-baseQ-front; Q-front=(Q-front+1)%MAXQSIZE; return 0; void outPutQMeue(SqQueue *Q) int i; for(i=Q-front;irear;i+) printf(%d ,Q-basei); printf(n); void main() SqQueue sq; int n,i,m; printf(构造空的环型队列n); InitQueue(sq); printf(请输入队列的长度:); scanf(%d,&n); for(i=1;i=n;i+) EnQueue(&sq,i); printf(队列的元素为:); outPutQMeue(&sq); DeQueue(&sq,&m); printf(队列中的第一个元素为:%d,m); printf(n删除对头元素,输出队列元素:); outPutQMeue(&sq); （注：可编辑下载，若有不当之处，请指正，谢谢!）