数据结构实验报告2

实验报告（二）分校名称 学号姓名实验日期2010-11-11专业名称计算机科学与技术课程名称数据结构批改教师主持教师实验成绩校外评阅教师实验名称栈、队列、递归程序设计使用主要设备PC，VC++6.0实验要求正确理解栈的现金后出的操作特点，建立初始栈，通过操作显示栈底元素程序中要体现出建栈的过程和取出栈底元素后恢复栈的入栈过程，按堆栈的操作规定打印结果栈的元素比较体重二种不同的递归程序设计和执行过程的差别正确理解递归程序的执行过程显示计算结果实验报告内容：调试中碰到的问题及解决方法调试成功的程序清单实验结论2.1栈和队列的基本操作编写一个算法，输出指定栈中的栈底元素，并使得原栈中的元素倒置。（1）正确理解栈的先进后出的操作特点,建立初始栈，通过相关操作显示栈底元素。（2）程序中要体现出建栈过程和取出栈底元素后恢复栈的入栈过程，按堆栈的操作规则打印结果栈中的元素。设计程序代码如下://数据结构实验2.1栈和队列的基本操作//调试环境：VisualC++6.0//-----库文件的预设和定义#include<stdio.h>#include<malloc.h>#defineMaxSize100typedefcharElemType;typedefstruct{ ElemTypedata[MaxSize]; inttop; //栈顶指针}SeqStack;//定义栈typedefstruct{ ElemTypeelem[MaxSize]; intfront,rear; //队首和队尾指针}SqQueue;//定义队列//---初始栈函数voidInitStack(SeqStack*&s){ s=(SeqStack*)malloc(sizeof(SeqStack)); s->top=-1;}//----进栈函数intPush(SeqStack*&s,ElemTypee){ if(s->top==MaxSize-1) return0; s->top++; s->data[s->top]=e; return1;}//---显示栈函数voidDispStack(SeqStack*s){ inti; for(i=s->top;i>=0;i--) printf("%c",s->data[i]); printf("\n");}//---显示栈底元素voidDispBottomStack(SeqStack*s){ printf("%c",s->data[0]);//先进后出,栈底元素为第一个元素,即data[0] printf("\n");}//---判空栈函数intStackEmpty(SeqStack*s){ return(s->top==-1);}//---出栈函数intPop(SeqStack*&s,ElemType&e){ if(s->top==-1) return0; e=s->data[s->top]; s->top--; return1;}//---初始队列函数voidInitQueue(SqQueue*&q){ q=(SqQueue*)malloc(sizeof(SqQueue)); q->front=q->rear=0;}//---入队列函数intInQueue(SqQueue*&q,ElemTypee){ if((q->rear+1)%MaxSize==q->front)//队满 return0; q->rear=(q->rear+1)%MaxSize; q->elem[q->rear]=e; return1;}//---出队列函数intOutQueue(SqQueue*&q,ElemType&e){ if(q->front==q->rear)//队空 return0; q->front=(q->front+1)%MaxSize; e=q->elem[q->front]; return1;}//---判空队列函数intQueueEmpty(SqQueue*q){ return(q->front==q->rear);}//-----主程序voidmain(){ ElemTypee; SeqStack*s; printf("(1)初始化栈s\n"); InitStack(s); printf("(2)栈为%s\n",(StackEmpty(s)?"空":"非空")); printf("(3)依次进栈元素a,b,c,d,e\n"); Push(s,'a');//入栈元素1 Push(s,'b');//入栈元素2 Push(s,'c');//入栈元素3 Push(s,'d');//入栈元素4 Push(s,'e');//入栈元素5 printf("(4)栈为%s\n",(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("队列为%s\n",(QueueEmpty(q)?"空":"非空")); printf("(9)出队列/入栈序列:"); while(!QueueEmpty(q)) { OutQueue(q,e);//出队 Push(s,e);//入栈 printf("%c",e); } printf("\n"); printf("(10)栈为%s,",(StackEmpty(s)?"空":"非空")); printf("队列为%s\n",(QueueEmpty(q)?"空":"非空")); free(q);//释放队列 printf("(11)从栈顶到栈底元素:");DispStack(s); free(s);//释放栈 }程序运行结果如下:2.2递归程序设计给定一个5位的十进制正整数，用递归法分别编制程序：（1）要求从低位到高位逐次输出各位数字。（2）要求从高位到低位逐次输出各位数字。程序代码如下://数据结构实验2.2递归程序设计//调试环境：VisualC++6.0//-----库文件的预设和定义#include<stdio.h>#include<math.h>voidout(intn,inti)//从高位到低位输出函数{intx,y;y=int(pow(10,i));if(n!=0){x=n/y;n=n-x*y;printf("%d",x);}elseprintf("0");i--;if(i>=0)out(n,i);}voidout1(intm,intj)//从低位到高位输出函数{intx,z;if(m!=0){x=int(m/10);z=m-x*10;m=x;printf("%d",z);}elseprintf("0");j--;if(j>=0)out1(m,j);}voidmain(){intm,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("从低位到高位逐次输出各位数字:");out