数据结构与算法实验――利用栈逆置队列元素

利用栈逆置队列元素实验报告班级：通信1204班学号：0909123001姓名：谢崇赟利用栈逆置队列元素实验报告通信1204班谢崇赟实验名称利用堆栈将队列中的元素逆置实验目的1．会定义顺序栈和链栈的结点类型。2．掌握栈的插入和删除结点在操作上的特点。3．熟悉对栈的一些基本操作和具体的函数定义。4．会定义顺序队列和链队列的结点类型。实验内容编制一个能实现“利用堆栈将队列中的元素逆置”的程序。问题描述该程序的功能是实现用堆栈将队列中的元素逆置。该程序包括定义的栈结构类型、队列结构类型以及对每一种栈、每一种队列操作的具体的函数定义和主函数。问题分析该实验是基于堆栈和队列知识的基本功能实现。但相较于简单的顺序栈和队列的定义及操作来说，该实验需要进行一定的算法设计，更加考验实习者的实践应用能力。为了程序的可观性，我选用了栈和队列的基本定义和操作函数（栈和队列的定义、出栈和入栈函数、出队和入队函数）进行程序设计。首先，我建立了一个初始队列，将队列的元素逐个出队并逐个压入预先定义好的栈中，然后再定义一个新队列，将栈中的元素逐个出栈并逐个插入新队列中，最后将初始队列和栈释放空间，至此，程序就可以完成了。实验步骤1．需求分析本演示程序用VC++编写，完成栈的初始化、入栈、出栈，队列的初始化、入队、出队等功能。①输入的形式和输入值的范围：插入元素时需要输入插入的位置和元素的值；删除元素时输入删除元素的位置。在所有输入中，元素的值都是整数②输出的形式：在所有三种操作中都显示操作是否正确以及操作后栈的内容。其中删除操作后显示删除的元素的值，查找操作后显示要查找元素的位置。③程序所能达到的功能：栈的初始化、入栈、出栈、取栈顶元素、队列的初始化、取队头元素、入队、出队。④测试数据：建立初始队列为1，2，3，4，5。2．概要设计1、为了实现上述程序功能，需要定义单链表的抽象数据类型：typedefstruct/*定义队列结构体类型*/{DataTypedata[MAXSIZE];intfront,rear;}Sequeue;/*定义DataType为int类型*/typedefintDataType;/*栈的结点类型*/#defineMAXSIZE100typedefstruct{DataTypedata[MAXSIZE];inttop;}Seqstack;/*入队*/Sequeue*Enqueue(Sequeue*sq,intn)/*显示元素*/voidDisplay(Sequeue*s,intn)/*取队列的头元素*/DataTypeFront(Sequeue*s)/*入栈：把队列内容入栈*/Seqstack*Push(Seqstack*p,Sequeue*s,intn)/*出栈*/DataTypePop(Seqstack*q)2、本程序包含5个函数：（1）主函数：main()（2）入栈函数：Seqstack*Push(Seqstack*p,Sequeue*s,intn)（3）出栈函数：DataTypePop(Seqstack*q)（4）取队头元素操作:DataTypeFront(Sequeue*s)（5）入队列操作:Sequeue*Enqueue(Sequeue*sq,intn)函数说明#includestdio.h#includestdlib.h#defineMAXSIZE100typedefintDataType;/*队列结构*/typedefstruct{DataTypedata[MAXSIZE];intfront,rear;}Sequeue;/*栈结构*/typedefstruct{DataTypedata[MAXSIZE];inttop;}Seqstack;/*入队*/Sequeue*Enqueue(Sequeue*sq,intn){intx,i=1;printf(请输入队列中的元素:\t);while(i=n){scanf(%d,&x);sq-rear=(sq-rear+1)%MAXSIZE;sq-data[sq-rear]=x;i++;}returnsq;}/*显示元素*/voidDisplay(Sequeue*s,intn)/*显示时不要移动做出队处理*/{inti=1;intrecord=s-front;while(i=n){record=(record+1)%MAXSIZE;printf(%4d,s-data[record]);i++;}}/*取队列的头元素*/DataTypeFront(Sequeue*s){intx;x=s-data[(s-front+1)%MAXSIZE];s-front=(s-front+1)%MAXSIZE;returnx;}/*入栈：把队列内容入栈*/Seqstack*Push(Seqstack*p,Sequeue*s,intn)/*这里要把队列指针传入*/{inta,i=1;while(i=n){a=Front(s);p-top++;p-data[p-top]=a;i++;}returnp;}/*出栈*/DataTypePop(Seqstack*q){inta;a=q-data[q-top];q-top--;returna;}intmain(void){intn,b,i=1;Sequeue*sq,*r;Seqstack*p,*q;printf(*********************************************\n);printf(**\n);printf(*利用堆栈逆置队列元素*\n);printf(**\n);printf(*********************************************\n);printf(请输入队列的长度n:\t);scanf(%d,&n);sq=(Sequeue*)malloc(sizeof(Sequeue));/*申请一个空间,队列*/sq-front=sq-rear=0;/*初始化*/sq=Enqueue(sq,n);printf(逆置前的队列为:\t);Display(sq,n);p=(Seqstack*)malloc(sizeof(Seqstack));/*申请一个空间,栈*/p-top=0;/*初始化*/r=(Sequeue*)malloc(sizeof(Sequeue));/*申请一个空间,队列*/r-front=r-rear=0;/*初始化*/q=Push(p,sq,n);r-front=MAXSIZE-1;r-rear=MAXSIZE-1;while(i=n){b=Pop(q);r-rear=(r-rear+1)%MAXSIZE;r-data[r-rear]=b;i++;}printf(\n逆置后的队列为:\t);Display(r,n);free(sq);/*释放*/free(p);/*释放*/printf(\n);return0;}程序流程图调试报告因本次实验较为基础，加之平时知识掌握良好，除了在设计程序时花了一定的时间，但执行在程序过程中没有出现明显问题。使用说明心得体会本次实验相对而言比较简易，无需设计复杂算法。过程中涉及的入栈函数、出栈函数、取队头元素操作、入队列操作都是书本上学的，大部分程序仅用顺序语句即可实现，最复杂的也不过是运用了while循环语句，但老实说，循环语句也着实毫无必要，只需再添一个完整的函数以连接出栈和入队操作即可，那反而更简明。我想，在以后的编程中我会更加的出色，能够很快的完成作业!我永远坚信的一句话“长风破浪会有时，直挂云帆济沧海”。