【电大本科数据结构实验报告】栈和队列的基本操作.doc

《【电大本科数据结构实验报告】栈和队列的基本操作.doc》由会员分享，可在线阅读，更多相关《【电大本科数据结构实验报告】栈和队列的基本操作.doc（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实验报告（学科：数据结构）姓名_单位_班级_实验名称：2.1 栈和队列的基本操作【问题描述】编写一个算法，输出指定栈中的栈底元素，并使得原栈中的元素倒置。【基本要求】（1）正确理解栈的先进后出的操作特点，建立初始栈，通过相关操作显示栈底元素。（2）程序中要体现出建栈过程和取出栈底元素后恢复栈的入栈过程，按堆栈的操作规则打印结果栈中的元素。【实验步骤】（1）建立顺序栈SeqStack，存放测试数据；建立队列SeqQueue存放出栈数据；（2）建立InitStack、StackEmpty、StackFull、Pop、Push、GetTop函数用作顺序栈的基本操作；（3）建立InitQueue、QE

2、mpty、Qfull、InQueue、OutQueue、ReadFront函数用作队列的基本操作；（4）建立主函数依次按序对子函数进行操作：InitStack初始化栈Push压入数据InitQueue初始化队列Pop弹出数据InQueue存入队列OutQueue出队列Push压入栈Pop弹出数据free清空栈与队列。在数据的输入与数据的输出时提供必要的提示信息。（5）使用Visual Studio C+ 2005语言环境进行调试，源代码P202-2-1.cpp通过编译生成目标文件P202-2-1.obj，运行可执行文件：实验2-2-1.exe测试通过。【源代码】#include stdio.h

3、#include stdlib.h#define MaxSize 8typedef int ElemType;/*顺序栈的类型定义*/struct SeqStack ElemType dataMaxSize; int top; ;struct SeqStack * s;/*顺序队列的类型定义*/struct SeqQueue ElemType dataMaxSize; int front,rear;struct SeqQueue * sq;/*栈的基本运算*/*初始化栈操作*/void InitStack(struct SeqStack * s) s-top=-1;/*判断栈空操作*/int

4、StackEmpty(struct SeqStack * s) if(s-top=-1) return(1); elsereturn(0);/*判断栈满操作*/int StackFull(struct SeqStack * s) if(s-top=MaxSize-1) return(1); else return(0);/*压栈操作*/void Push(struct SeqStack *s,ElemType x) if(s-top=MaxSize-1) printf(栈满溢出错误!n); exit(1); s-top+; s-datas-top=x;/*弹栈操作*/ElemType Pop(

5、struct SeqStack * s) if(StackEmpty(s) printf(栈下溢错误!n); return(1); s-top-; return s-datas-top+1;/*获取栈顶元素操作*/ElemType GetTop(struct SeqStack * s) if(StackEmpty(s) printf(栈下溢错误!n); exit(1); return s-datas-top;/*队列的基本运算*/*初始化队列*/void InitQueue(struct SeqQueue * sq) sq-front=0; sq-rear=0;/*判队空*/int QEmpt

6、y(struct SeqQueue * sq) if(sq-front=sq-rear) printf(队列已空，不能进行出队操作!n); return(1); /*如果链队为空，则返回*/ else return(0); /*否则返回*/ ; /*判队满*/int Qfull(struct SeqQueue * sq) if(sq-rear=MaxSize) /*判队列是否已满*/ printf(队列已满!n); return(1); /*入队失败，退出函数运行*/ return(0);/*入队列操作*/void InQueue(struct SeqQueue * sq, int x) if

7、(!Qfull(sq) sq-datasq-rear=x; /*数据送给队尾指针所指单元*/ sq-rear+; /*将队尾指针加*/ /*出队列操作*/ElemType OutQueue(struct SeqQueue *sq) if(sq-rear=sq-front) /*判断队列是否为空*/ printf(队列已空，不能进行出队操作!n); return(1); /*出队失败，退出函数运行*/ sq-front+; return sq-datasq-front-1;/*读队头元素*/void ReadFront(struct SeqQueue * sq,int x) if(!QEmpty

8、(sq) sq-front+; /*将头指针加,前移*/ OutQueue(sq); /*出队列操作*/ void main() int n; struct SeqStack *a=(SeqStack *)malloc(sizeof(struct SeqStack); /*分配栈的内存空间，使结构指针a指向栈地址*/ struct SeqQueue *sq=(SeqQueue *)malloc(sizeof(struct SeqQueue); InitStack(a); do printf(输入栈中的数据:); scanf(%d,&n); Push(a,n); /*把数据压入栈中*/ whil

9、e(!StackFull(a); InitQueue(sq); do InQueue(sq,Pop(a); /*弹出栈数据，把数据放进队列中*/ while(!(StackEmpty(a)&Qfull(sq); do Push(a,OutQueue(sq); /*从队列输出数据，把数据压入到栈内*/ while(!(QEmpty(sq)&StackFull(a); do printf(输出栈中的数据:%dn,Pop(a); /*弹出栈中所有数据*/ while(!StackEmpty(a);free(a);free(sq); 【实验数据】【结论】由 于栈的结构特点决定了栈对数据的操作规则。先进后出操作，说明对栈中的数据操作只能每次输出或者压入一个元素进入栈中。通过栈的基本运算函数实现初始化 栈，对栈进行数据入栈或者出栈的操作。运用队列对数据处理的先进先出的操作规则，把栈内的数据取出放入到队列中，实现输出栈底数据，倒置栈内数据的操作。