数据结构实验报告2栈、队列、递归程序设计.doc

计算机科学与技术（本科）数据结构实验报告日期： 学号： 姓名： 实验名称：实验报告二栈、队列、递归程序设计 实验目的与要求：2.1栈和队列的基本操作（1） 正确理解栈的先进后出的操作特点，建立初始栈，通过相关操作显示栈底元素。（2） 程序中要体现出建栈过程和取出栈底元素后恢复栈的入栈过程，按堆栈的操作规则打印结果栈中的元素2.2递归程序设计（1）要求从低位到高位逐次输出各位数字。（2）要求从高位到低位逐次输出各位数字。实验步骤：(请写出算法设计、程序编码、调试过程及运行结果)2.1栈和队列的基本操作/数据结构实验2.1栈和队列的基本操作/调试环境： Visual C+ 6.0/-库文件的预设和定义#include #include #define MaxSize 100typedef char ElemType;typedef struct ElemType dataMaxSize;int top;/栈顶指针 SeqStack;/定义栈typedef struct ElemType elemMaxSize;int front,rear;/队首和队尾指针 SqQueue;/定义队列/-初始栈函数void InitStack(SeqStack *&s)s=(SeqStack *)malloc(sizeof(SeqStack);s-top=-1;/-进栈函数int Push(SeqStack *&s,ElemType e)if (s-top=MaxSize-1)return 0;s-top+;s-datas-top=e;return 1;/-显示栈函数void DispStack(SeqStack *s)int i;for (i=s-top;i=0;i-)printf(%c ,s-datai);printf(n);/-显示栈底元素void DispBottomStack(SeqStack *s)printf(%c ,s-data0);/先进后出,栈底元素为第一个元素,即data0printf(n);/-判空栈函数int StackEmpty(SeqStack *s)return(s-top=-1);/-出栈函数int Pop(SeqStack *&s,ElemType &e)if (s-top=-1)return 0;e=s-datas-top;s-top-;return 1;/-初始队列函数void InitQueue(SqQueue *&q)q=(SqQueue *)malloc (sizeof(SqQueue);q-front=q-rear=0;/-入队列函数int InQueue(SqQueue *&q,ElemType e)if (q-rear+1)%MaxSize=q-front) /队满return 0;q-rear=(q-rear+1)%MaxSize;q-elemq-rear=e;return 1;/-出队列函数int OutQueue(SqQueue *&q,ElemType &e)if (q-front=q-rear) /队空return 0;q-front=(q-front+1)%MaxSize;e=q-elemq-front;return 1;/-判空队列函数int QueueEmpty(SqQueue *q)return(q-front=q-rear);/-主程序void main()ElemType e;SeqStack *s;printf(1)初始化栈sn);InitStack(s);printf(2)栈为%sn,(StackEmpty(s)?空:非空);printf(3)依次进栈元素a,b,c,d,en);Push(s,a);/入栈元素1Push(s,b);/入栈元素2Push(s,c);/入栈元素3Push(s,d);/入栈元素4Push(s,e);/入栈元素5printf(4)栈为%sn,(StackEmpty(s)?空:非空);printf(5)从栈顶到栈底元素:);DispStack(s);printf(6)栈底元素为:);DispBottomStack(s);printf(7)出栈/入队列序列:);SqQueue *q;InitQueue(q);while (!StackEmpty(s)Pop(s,e);/出栈printf(%c ,e);InQueue(q,e);/入队printf(n);printf(8)栈为%s,(StackEmpty(s)?空:非空);printf(队列为%sn,(QueueEmpty(q)?空:非空);printf(9)出队列/入栈序列:);while (!QueueEmpty(q)OutQueue(q,e);/出队Push(s,e);/入栈printf(%c ,e);printf(n);printf(10)栈为%s,(StackEmpty(s)?空:非空);printf(队列为%sn,(QueueEmpty(q)?空:非空);free(q);/释放队列printf(11)从栈顶到栈底元素:);DispStack(s);free(s);/释放栈2.2递归程序设计/数据结构实验2.2递归程序设计/调试环境： Visual C+ 6.0/-库文件的预设和定义#include#includevoid out(int n,int i)/从高位到低位输出函数int x,y;y=int(pow(10,i);if (n!=0)x=n/y;n=n-x*y;printf(%d ,x);else printf(0 );i-;if(i=0) out(n,i);void out1(int m,int j)/从低位到高位输出函数int x,z;if (m!=0)x=int(m/10);z=m-x*10;m=x;printf(%d ,z);else printf(0 );j-;if(j=0) out1(m,j);void main()int m,n,o,x,i,j;printf(输入需要排列的数字:n);scanf(%d,&o);m=n=o;x=n;i=-1;while(x!=0)x=x/10;i+;/求出i为十进制正整数位数j=i;printf(n);printf(从高位到低位逐次输出各位数字:);out(n,i);printf(n);printf(从低位到高位逐次输出各位数字:);out1(m,j);printf(n);结论和体会：1. 栈和队列是运算受限制的线性表2