栈的表示与实现及栈的应用实验报告.doc

《栈的表示与实现及栈的应用实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、实验二：栈的表示与实现及栈的应用【实验目的】（1）掌握栈的顺序存储结构及其基本操作的实现。（2）掌握栈后进先出的特点，并利用其特性在解决实际问题中的应用。（3）掌握用递归算法来解决一些问题。【实验内容】1.编写程序，对于输入的任意一个非负十进制整数，输出与其等值的八进制数。2.编写递归程序，实现N！的求解。3.编写递归程序，实现以下函数的求解。4.编写程序，实现Hanoi塔问题。【实验步骤】1.打开VC++。2.建立工程：点File->New，选Project标签，在列表中选Win32ConsoleAppli

2、cation，再在右边的框里为工程起好名字，选好路径，点OK->finish。至此工程建立完毕。3.创建源文件或头文件：点File->New，选File标签，在列表里选C++SourceFile。给文件起好名字，选好路径，点OK。至此一个源文件就被添加到了你刚创建的工程之中。4．写好代码5．编译－＞链接－＞调试1、#include#include#include#defineOK1#defineERROR0#defineOVERFLOW-2typede

3、fintStatus;typedefintSElemType;#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;StatusInitStack(SqStack&S){S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base)returnOVERFLOW

4、;S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}//InitStackStatusPush(SqStack&S,SElemTypee){if(S.top-S.base>=S.stacksize){S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksiz

5、e;S.stacksize+=STACKINCREMENT;}*S.top++=e;returnOK;}//PUSHStatusPop(SqStack&S,SElemType&e){if(S.top==S.base)returnERROR;e=*--S.top;returnOK;}//PopStatusStackEmpty(SqStackS){if(S.top==S.base)returnOK;elsereturnERROR;}//StackEmptyvoidconversion(){intN;inte;Sq

6、StackS;InitStack(S);printf("输入要转换的数据：");scanf("%d",&N);while(N){Push(S,N%8);N=N/8;}printf("其对应的八进制数是：");while(!StackEmpty(S)){Pop(S,e);printf("%d",e);}}voidmain(){conversion();}2、#includeIntfact(intn){If(n==1)return1;elsereturnn*fact(n-1);}voidma

7、in(){Intn;printf(“输入一个数n:”);scanf(“%d”,&n);printf("fact(%d)=%d",n,fact(n));}3、#includeintfib(intn){if(n>1)returnfib(n-1)+fib(n-2);elsereturnn;}voidmain(){intn;printf("输入一个数n:");scanf("%d",&n);printf("fib(%d)=%d",n,fib(n));}4、#include

8、voidmove(charx,intn,charz){printf("将%d号盘从%c柱移到%c柱",n,x,z);}voidhanoi(intn,charx,chary,charz){if(n==1)move(x,1,z);else{hanoi(n-1,x,z,y);move(x,n,z);hanoi(n-1,y,x,z);}}voidmain(){intn;scanf("%d",&n);ha