栈的表示及栈的应用

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

2、le Application,再在右边的框里为工程起好名字，选好路径，点OK-flmsho至 此工程建立完毕。创建源文件或头文件：点File-New,选File标签，在列表里选C+ Somce Fileo给文件起好名字，选好路径，点OK。至此一个源文件就被添加到了你 刚创建的工程之中。写好代码编译一链接一调试【主要代码】进制转换#iiiclude #iiiclude define OK 1#define ERROR 0#define OVERFLOW .2 typedef int Status;typedef int SElemType;#define STACK_INIT_SIZE100#d

3、efine STACKINCREMENT10 typedef stmct (SElemType*base;SElemType*top;int stacksize;)SqStack;Status IiiitStack(SqStack &S)(/构造一个空栈S.base=(SElemType *)nialloc (STACK_INIT_SIZE*sizeof(SElemType);if(?S.base) exit (OVERFLOW);/存储分配失败S.top=S.base;S.stacksize=STACK INIT SIZE;leturn OK;/IiiitStackStatus Push(S

4、qStack &S, SElemType e)(插入元素e为新的栈顶元素if (S. top-S. base=S. stacksize)栈满，追加存储空间Sbase=(SElemType*)iealloc(S.base,(S.stacksize-rSTACKINCREMENT)* sizeof(SElemType);if (IS.base) exit(OVERFLOW);/存储分配失败S .top=S. base+ S. stacksize;S.stacksize+=STACKINCREMENT;)*S.top+=e;return OK; /PUSHStatus Pop(SqStack &S,

5、 SElemType &e)若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERRORif(S.top=S.base)return ERROR;e=*-S.top;return OK; /PopStatus StackEmpty(SqStack S)若栈不空，返回ERROR.否则返回OKif (S.top=S.base)return OK;return ERROR; /StackEmptyvoid main()(int N,e,M;SqStack S;IiutStack(S);printf(”请入一个数字：”)； scanff%d”,&M);printfC需要转换为几进制：”)

6、； scanff%d”,&M);while(N)fPush(S,N % M);N=N/M;pnntf(M其对应的%d进制数是M);while(? StackEnipty(S)(Pop(S,e);prinrff%d”,e);pnntfCW);递归程序#include long Fibonacci(iiit n);int n;long L;printf(”请输入n的值：， scanff%d”.&n);L=Fibonacci(n);printf(,Fibonacci(%d)=%ldnn,L);long Fibonacci(iiit n)long t=l;if(n=l|n=0)t=t*n;t=Fibonacci(n-l)+Fibonacci(n-2);return t;汉诺塔#iiicludevoid move(char a.iiit n.char b)printf(将编号为d的盘从移到c nM,n,a,b);void haiioi(mt n,char x.char y,char z)if(n=l)move(x,l,z);elsehanoi(n-l,x,z,y);move(x,n,z);hanoi(n-l,y,x,z);void main（）int n;pnntf（iW输入 n 的值:”）；scanff%d”.&n）;hanoi（na；b、c，）；