棧的表示及棧的應(yīng)用

1、實驗二：棧的表示及棧的應(yīng)用【實驗?zāi)康摹浚?）掌握棧的順序存儲結(jié)構(gòu)及其基本操作的實現(xiàn)。（2）掌握棧后進先出的特點，并利用其特性在解決實際問題中的應(yīng)用。（3）掌握用遞歸算法來解決一些問題?！緦嶒瀮?nèi)容】編寫程序，對于輸入的任意一個非負十進制整數(shù)，輸出與其等值的八進 制數(shù)（課本P48）O編寫遞歸程序，實現(xiàn)以下函數(shù)的求解（課本P54）of n,n = 0,1Fib（n） = （Fib（n -1） + Fib （it - 2）, n 1編寫程序，實現(xiàn)Hanoi塔問題（課本P55-P58）。【實驗步驟】1 .打開VC十十。建立工程：點File-New,選Project標(biāo)簽，在列表中選 Win32 Conso

2、le Application,再在右邊的框里為工程起好名字，選好路徑，點OK-flmsho至 此工程建立完畢。創(chuàng)建源文件或頭文件：點File-New,選File標(biāo)簽，在列表里選C+ Somce Fileo給文件起好名字，選好路徑，點OK。至此一個源文件就被添加到了你 剛創(chuàng)建的工程之中。寫好代碼編譯一鏈接一調(diào)試【主要代碼】進制轉(zhuǎn)換#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)(/構(gòu)造一個空棧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(”請入一個數(shù)字：”)； scanff%d”,&M);printfC需要轉(zhuǎn)換為幾進制：”)

6、； scanff%d”,&M);while(N)fPush(S,N % M);N=N/M;pnntf(M其對應(yīng)的%d進制數(shù)是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，）；