数据结构--04队列的基本操作

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)return 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() sqqueu