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

数据结构--04队列的基本操作数据结构--04队列的基本操作数据结构--04队列的基本操作数据结构--04队列的基本操作编制仅供参考审核批准生效日期地址：电话：传真:邮编:《数据结构》实验报告院系光电与信息工程学院专业电子信息工程姓名学号电话2011级2班2013年4月20日1．实验题目实验4.对列的基本操作2．需求分析（1）编写链接队列的基本操作函数，调用上述函数实现下列操作，操作步骤如下：调用进队函数建立一个队列。读取队列中的第一个元素。从队列中删除元素。输出队列中的所有元素。（2）编写环型队列的基本操作函数。调用上述函数实现下列操作，操作步骤如下:调用进队函数建立一个队列。读取队列中的第一个元素。从队列中删除元素。输出队列中的所有元素。链接队列：①进队操作EnQueue(LinkQueue*Q,QElemTypee)②出队操作，队空DeQueue(LinkQueue*Q,QElemType*e)③输出队列中元素0utputQueue(LinkQueueQ)环型队列：①进队操作，返回1为队满EnQueue(SqQueue*Q,QElemTypee)②出队操作，返回1为队空DeQueue(SqQueue*Q,QElemType*e)③输出队列中元素outPutQMeue(SqQueueQ)输入形式：整型数。3．概要设计（1）链接队列ADTQNode{数据对象：D={ai|ai∈IntegerSet,i=0,1,2,…,n,n≥0}结构关系：R={<ai,ai+1>|ai,ai+1∈D}基本操作：InitQueue(LinkQueue*Q)操作前提：Q是一个未初始化的链接队列操作结果：将Q初始化为一个空的链接队列EnQueue(LinkQueue*Q,QElemTypee)操作前提：链接队列Q已存在操作结果：将元素e插入到链接队列中DeQueue(LinkQueue*Q,QElemType*e)操作前提：链接队列Q已存在操作结果：将链接队列Q中队头元素删除，删除的元素值通过e返回0utputQueue(LinkQueueQ)操作前提：链接队列Q已存在操作结果：将链接队列Q中的元素显示到屏幕上}本程序包含5个函数：主函数main()初始化链接队列函数InitQueue()进队函数EnQueue()出队函数DeQueue()输出队列中元素函数OutputStack()各函数调用关系：主函数main调用其他四个函数主函数的伪码main(){定义变量i，n，m；定义一个LinkQueue变量Lq初始化Lq；输入队列元素的个数；For循环（i=1;i<=n;i++）｛调用EnQueue函数；｝输出队列中元素； 调用DeQueue函数；显示删除的队头元素；显示Lq；｝（2）环形队列ADTSqQueue{数据对象：D={ai|ai∈IntegerSet,i=0,1,2,…,n,n≥0}结构关系：R={<ai,ai+1>|ai,ai+1∈D}基本操作：InitQueue(SqQueue&Q)操作前提：Q是一个未初始化的环型队列操作结果：将Q初始化为一个空的环型队列EnQueue(SqQueue*Q,inte)操作前提：环型队列Q已存在操作结果：将元素e插入到队列中DeQueue(SqQueue*Q,int*e)操作前提：环型队列Q已存在操作结果：将环型队列Q中队头元素删除，删除的元素值通过e返回outPutQMeue(SqQueue*Q)操作前提：环型队列Q已存在操作结果：将环型队列Q中的元素显示到屏幕上}本程序包含5个函数：主函数main()初始化链接队列函数InitQueue()进队函数EnQueue()出队函数DeQueue()输出队列中元素函数OutputStack()各函数调用关系：主函数main调用其他四个函数函数的伪码main（）｛ 定义SqQueue变量sq;定义整型变量n,i,m;构造空的环型队列；输入队列的长度；For循环（i=1;i<=n;i++）｛调用EnQueue函数；｝输出队列元素；删除对头元素；输出队列元素；｝详细设计（1）链接队列类型定义typedefstructQNode{ intdata; structQNode*next;}QNode,*QueuePtr;typedefstruct{ QueuePtrfront; QueuePtrrear;}LinkQueue;基本操作的伪码算法（1）初始化voidInitQueue(LinkQueue*Q){Q->front=Q->rear==申请新结点;Q->front->next=NULL;}（2）进队voidPush(SqStack&S,inte){定义QueuePtr变量p；p=申请新的空间；如果申请失败，结束程序p->data=e;p->next=NULL;如果是第一个元素则{Q->front->next=p;} Q->rear->next=p; Q->rear=p;｝(3)出队intPop(SqStack*S,inte)｛定义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）输出元素intOutputQueue(LinkQueueQ){定义QueuePtr变量p；如果队空则返回0； p=>next;while(p) { printf("%d",p->data); p=p->next; } printf("\n"); 返回1; }（2）环形队列类型定义typedefstruct{ int*base; intfront; intrear;}SqQueue;基本操作的伪码算法（1）初始化voidInitQueue(SqQueue&Q){=申请新的空间；如果申请失败，结束程序；==0;}（2）进队intEnQueue(SqQueue*Q,inte){如果队满了则返回1； Q->base[Q->rear]=e; Q->rear=(Q->rear+1)%MAXQSIZE;返回0；｝出队intDeQueue(SqQueue*Q,int*e)DeQueue(SqQueue*Q,int*e)｛如果队空则返回1；*e=Q->base[Q->front]; Q->front=(Q->front+1)%MAXQSIZE;返回0；}（4）输出元素voidoutPutQMeue(SqQueue*Q){定义整型变量i；For循环（i=Q->front;i<Q->rear;i++){输出Q->base[i]；}换行；}调试分析链接队列：调试是出现错误，经过检查发现在某些地方分号用中文表示，出现空指针问题。环型队列：出现空指针问题，内存不能读取等使用说明（1）链接队列：程序执行过程如下：提示用户输入元素个数；用户按要求输入一个整型数；程序输出构造好的链接队列；调用出队函数，并把剩余元素显示在屏幕上；（2）环型队列：程序执行过程如下：提示用户输入队列元素个数；用户按要求输入一个整型数；程序用输入的整型数构建一个环型队列，并输出队列元素；调用出栈函数，删除栈顶，显示栈中元素；测试结果（1）链接队列构造一个空的链接队列后，屏幕显示：请输入队列的元素个数：输入5后，屏幕显示建立的队列元素：12345调用出队函数后，屏幕显示：2345（2）环形队列建立空队列，程序运行后屏幕显示：输入队列元素的长度输入5后，屏幕显示队列的元素：12345接着屏幕又显示：队列中的第一个元素为：1调用出队函数，然后输入队列中元素：23458.参考文献数据结构（c语言版）9．附录源程序文件如下：（1）链接队列#include<>#include<>typedefstructQNode{ intdata; structQNode*next;}QNode,*QueuePtr;typedefstruct{ QueuePtrfront; QueuePtrrear;}LinkQueue;voidInitQueue(LinkQueue*Q){ Q->front=Q->rear=(QNode*)malloc(sizeof(QNode));Q->front->next=NULL;}voidEnQueue(LinkQueue*Q,inte){ QueuePtrp; p=(QueuePtr)malloc(sizeof(QNode)); if(!p)exit(1); p->data=e; p->next=NULL; if(Q->front->next==NULL) {Q->front->next=p;} Q->rear->next=p; Q->rear=p;}intDeQueue(LinkQueue*Q,int*e){ QueuePtrp; if(Q->front==Q->rear)return0; p=Q->front->next; *e=p->data; Q->front->next=p->next; if(Q->rear==p){Q->rear=Q->front;} free(p); return1;}intOutputQueue(LinkQueueQ){ QueuePtrp; if==return0; p=>next; while(p) { printf("%d",p->data); p=p->next; } printf("\n"); return1;}voidmain(){inti,n;intm; LinkQueueLq; 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此时队列中的元素为:");OutputQueue(Lq);}（2）环形队列#include<>#include<>#defineMAXQSIZE100typedefstruct{ int*base; intfront; intrear;}SqQueue;voidInitQueue(SqQueue&Q){ =(int*)malloc(MAXQSIZE*sizeof(int)); if(!exit(1); ==0;}intEnQueue(SqQueue*Q,inte){ if((Q->rear+1)%MAXQSIZE==Q->front)return1; Q->base[Q->rear]=e; Q->rear=(Q->rear+1)%MAXQSIZE; return0;}int