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

《数据结构与算法实验――利用栈逆置队列元素.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、班级：通信1204班学号：姓名：谢崇赟利用栈逆置队列元素实验报告利用栈逆置队列元素实验报告通信1204班谢崇赟实验名称利用堆栈将队列中的元素逆置实验目的1．会定义顺序栈和链栈的结点类型。2．掌握栈的插入和删除结点在操作上的特点。3．熟悉对栈的一些基本操作和具体的函数定义。4．会定义顺序队列和链队列的结点类型。实验内容编制一个能实现“利用堆栈将队列中的元素逆置”的程序。问题描述该程序的功能是实现用堆栈将队列中的元素逆置。该程序包括定义的栈结构类型、队列结构类型以及对每一种栈、每一种队列操作的具体的函数定义和主函数。问题分析该实验是基于堆栈和队列知

2、识的基本功能实现。但相较于简单的顺序栈和队列的定义及操作来说，该实验需要进行一定的算法设计，更加考验实习者的实践应用能力。为了程序的可观性，我选用了栈和队列的基本定义和操作函数（栈和队列的定义、出栈和入栈函数、出队和入队函数）进行程序设计。首先，我建立了一个初始队列，将队列的元素逐个出队并逐个压入预先定义好的栈中，然后再定义一个新队列，将栈中的元素逐个出栈并逐个插入新队列中，最后将初始队列和栈释放空间，至此，程序就可以完成了。实验步骤1．需求分析   本演示程序用VC++编写，完成栈的初始化、入栈、出栈，队列的初始化、入队、出队等功能。 ① 输

3、入的形式和输入值的范围：插入元素时需要输入插入的位置和元素的值；删除元素时输入删除元素的位置。在所有输入中，元素的值都是整数 ② 输出的形式：在所有三种操作中都显示操作是否正确以及操作后栈的内容。其中删除操作后显示删除的元素的值，查找操作后显示要查找元素的位置。 ③ 程序所能达到的功能：栈的初始化、入栈、出栈、取栈顶元素、队列的初始化、取队头元素、入队、出队。 ④ 测试数 据：  建立初始队列为1，2，3，4，5 。 2．概要设计  1、 为了实现上述程序功能，需要定义单链表的抽象数据类型： typedefstruct/*定义队列结构体类型*/

4、{DataTypedata[MAXSIZE];intfront,rear;}Sequeue;/* 定义DataType为int类型 */typedef int DataType; /*栈的结点类型*/#define MAXSIZE 100  typedefstruct{DataTypedata[MAXSIZE];inttop;}Seqstack;/*入队*/Sequeue*Enqueue(Sequeue*sq,intn)   /*显示元素*/voidDisplay(Sequeue*s,intn)/*取队列的头元素*/DataTypeFront(

5、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*E

6、nqueue(Sequeue*sq,intn)            函数说明#include#include#defineMAXSIZE100typedefintDataType;/*队列结构*/typedefstruct{DataTypedata[MAXSIZE];intfront,rear;}Sequeue;/*栈结构*/typedefstruct{DataTypedata[MAXSIZE];inttop;}Seqstack;/*入队*/Sequeue*Enqueue(Sequeue*sq,intn)

7、{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++

8、;}}/*取队列的头元素*/DataTypeFront(Sequeue*s){intx;x=s->data[(s->front+1)%MAXSIZE]