|
一共包括六個程序，分別是： l > 數(shù)制轉換， l > 括號匹配的檢驗， l > 行編輯程序問題， l > 迷宮求解， l > 表達式求值， l > 漢諾塔遞歸實現(xiàn)
這些棧的應用都是嚴蔚敏的數(shù)據(jù)結構那本書中的例子，但是那本書中的例子大都是用偽代碼的形式寫的，不是很容易理解和實現(xiàn)，對初學者造成了不小的困擾，在這里我們將其詳盡的實現(xiàn)出來，以便初學者調試和運行，并從中有所收獲。 上述的六個程序，每個程序的實現(xiàn)在一個文件中，每個程序都由C語言編寫，只是借用C++中的兩個東西，一是注釋符‘//’，一是引用符‘&’。每個程序可以在C++兼容的編譯器上直接運行，經(jīng)過測試，運行情況良好，有什么問題，歡迎留言交流。 文件一：數(shù)制轉換 /********************** 聲明部分 **********************/#include#include#define STACK_INIT_SIZE 10 //定義最初申請的內(nèi)存的大小#define STACK_INCREMENT 2 //每一次申請內(nèi)存不足的時候擴展的大小#define OVERFLOW 0#define FALSE 0#define TRUE 1#define ERROR 0#define INFEASIBLE 0#define OK 1typedef int SElemType;typedef int Status;int Length;/********************** 結構類型部分 **********************/typedef struct SqStack{ SElemType *base; // 棧底指針 SElemType *top; // 棧頂指針 int stacksize;}SqStack; // 順序棧/********************** 基本操作函數(shù)部分 **********************//********************** 構造一個空棧S **********************/Status InitStack(SqStack &S){ // 構造一個空棧S if (!(S.base = (SElemType *) malloc(STACK_INIT_SIZE * sizeof (SElemType)))) exit(OVERFLOW); // 存儲分配失敗 S.top = S.base; S.stacksize = STACK_INIT_SIZE; //初始棧容量 return OK;}/********************** 輸入棧元素 **********************/Status Push(SqStack &S, SElemType e){ if (S.top - S.base >= S.stacksize) // 棧滿，追加存儲空間 { //可能會改變棧底地址，新棧底指針S.base S.base = (SElemType *) realloc(S.base, //原棧底指針 (S.stacksize + STACK_INCREMENT) * sizeof (SElemType)); //新大小 if (!S.base) exit(OVERFLOW); // 存儲分配失敗 //給SqStack結構對象S的3個成員賦值 S.top = S.base + S.stacksize; S.stacksize += STACK_INCREMENT; } *S.top++ = e; //先把e壓入棧頂，S.top再增1指向棧頂元素e的下一個位置 return OK;}/********************** 輸出棧元素 **********************/void OutList(SqStack S){ S.top=S.base; // 從棧底開始輸出 for(int i=0;i=0） = '); scanf('%u', &n); // 輸入非負十進制整數(shù)n printf('\n請輸入需要轉換到的進制： '); scanf('%u', &m); // 輸入非負十進制整數(shù)n printf('十進制數(shù)%u的八進制數(shù)是', n); while (n) // 只要n不等于0就循環(huán) //從n為用戶輸入的十進制數(shù)開始，一直到n等于0為止 { Push(s, n % m); // n除以8的余數(shù)(8進制的低位)入棧 //把n除以8的余數(shù)壓入棧s //先壓入的余數(shù)是八進制的低位，后壓入的余數(shù)是八進制的高位 n = n / m; //令n等于n整除以8的商，進入下輪循環(huán) } //循環(huán)結束時，n等于0 while (!StackEmpty(s)) // 只要棧s沒彈空就不斷循環(huán)， //直到彈出棧底元素棧s為空為止 { Pop(s, e); // 彈出棧頂元素且賦值給e //依次彈出棧s的棧頂元素交給e帶回 //先彈出的是八進制的高位，后彈出的是八進制的低位 printf('%d', e); // 依次輸出e } //循環(huán)結束時，棧s為空 printf('\n');}/********************** 主函數(shù)部分 **********************/int main(){ /********************** 函數(shù)聲明區(qū) **********************/ Status InitStack(SqStack &S); Status Push(SqStack &S, SElemType e); void OutList(SqStack S); /********************** 函數(shù)執(zhí)行區(qū) **********************/ conversion(); return 0;}
文件二：括號匹配的檢驗 /********************** 聲明部分 **********************/#include //輸入輸出函數(shù)頭文件#include //內(nèi)存申請函數(shù)頭文件#define OVERFLOW false //異常拋出返回值#define FALSE false //異常拋出返回值#define TRUE true //異常拋出返回值#define ERROR false //異常拋出返回值#define INFEASIBLE false //異常拋出返回值#define OK true //程序正確執(zhí)行拋出返回值typedef bool Status; //別名聲明#define STACK_INIT_SIZE 100 // 存儲空間初始分配量#define STACKINCREMENT 2 // 存儲空間分配增量 typedef char SElemType;/********************** 結構類型部分 **********************/typedef struct SqStack{ //棧的數(shù)據(jù)元素類型在應用程序中定義typedef int SElemType; SElemType *base; // 棧底指針 //在棧構造之前和銷毀之后，base為NULL SElemType *top; // 棧頂指針 //初值指向棧底，top = base可做?？諛擞? //插入新棧頂元素時，top增1；刪除棧頂元素時，top減1 //非空棧的top始終在棧頂元素的下一個位置上 int stacksize; // 當前已分配的存儲空間，以元素為單位 //棧當前可使用的最大容量 int len;}SqStack;// 順序棧/********************** 構造一個空棧S **********************/Status InitStack(SqStack &S){ // 構造一個空棧S //棧底指針S.base指向新分配的STACK_INIT_SIZE個SElemType大小的空間 if (!(S.base = (SElemType *) malloc(STACK_INIT_SIZE * sizeof (SElemType)))) exit(OVERFLOW); // 存儲分配失敗 //必須給SqStack結構對象S的3個成員賦值 S.top = S.base; //空棧的棧頂指針S.top = 棧底指針S.base S.stacksize = STACK_INIT_SIZE; //初始棧容量 S.len = 0; return OK;}/********************** 返回棧頂元素 **********************/Status GetTop(SqStack S, SElemType &e){ // 若棧不空，則用e返回S的棧頂元素，并返回OK；否則返回ERROR if (S.top > S.base) { e = *(S.top - 1); //因為S.top指向棧頂元素的下一個位置， //所以棧頂元素就是e = *(S.top - 1) return OK; } else return ERROR;}/********************** 插入新的棧頂元素 **********************/Status Push(SqStack &S, SElemType e){ // 插入元素e為新的棧頂元素 if (S.top - S.base >= S.stacksize) // 棧滿，追加存儲空間 //如果棧長度大于棧容量 { //可能會改變棧底地址，新棧底指針S.base S.base = (SElemType *) realloc(S.base, //原棧底指針 (S.stacksize + STACKINCREMENT) * sizeof (SElemType)); //新大小 if (!S.base) exit(OVERFLOW); // 存儲分配失敗 //給SqStack結構對象S的3個成員賦值 S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; } *(S.top)++ = e; //先把e壓入棧頂，S.top再增1指向棧頂元素e的下一個位置 S.len++; return OK;}/********************** 刪除棧頂元素 **********************/Status Pop(SqStack &S, SElemType &e){ // 若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR if (S.top == S.base) //如果空棧，報錯 return ERROR; e = *--S.top; //S.top先減1指向棧頂元素，再取值，交給e帶回 S.len--; return OK;}Status IsEmpty(SqStack &S){ // 若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR if (S.top == S.base) //如果空棧，報錯 return TRUE; return FALSE;}void BraceMatch(){ char e,a[20]; int i=0; int flag=1; SqStack S; InitStack(S); printf('input the braces (<=20) and press '#' to show the end:\n'); //輸入字符 do{ scanf('%c',&e); a[i]=e; i++; }while(e!='#'); printf('%s\n',a); i=0; e=a[0]; while(e!='#'&& flag) { switch(e) {case '(': Push(S,e); break; case '[': Push(S,e); break; case '{': Push(S,e); break; case ')': if(!IsEmpty(S)) { Pop(S,e); if(e!='(')flag=0; } else flag=0; break; case ']': if(!IsEmpty(S)) { Pop(S,e); if(e!='[') flag=0; } else flag=0; break; case '}': if(!IsEmpty(S)) { Pop(S,e); if(e!='{') flag=0; } else flag=0; break; } i++; e=a[i]; printf('The length of the stack is %d\n',S.len); } if(!IsEmpty(S)) flag=0; if(flag)printf('MATCH!\n'); else printf('MIS MATCH!\n'); }int main(){ BraceMatch(); return 0;}
文件三：行編輯程序問題 /********************** 聲明部分 **********************/#include #include#define STACK_INIT_SIZE 10 //定義最初申請的內(nèi)存的大小#define STACK_INCREMENT 2 //每一次申請內(nèi)存不足的時候擴展的大小#define OVERFLOW false //異常拋出返回值#define FALSE false //異常拋出返回值#define TRUE true //異常拋出返回值#define ERROR false //異常拋出返回值#define INFEASIBLE false //異常拋出返回值#define OK true //程序正確執(zhí)行拋出返回值typedef int SElemType; //別名聲明，其實int可以用任意的名字代入typedef bool Status; //別名聲明/********************** 結構類型部分 **********************/struct SqStack{ SElemType *base; // 棧底指針 //在棧構造之前和銷毀之后，base為NULL SElemType *top; // 棧頂指針 //初值指向棧底，top = base可做?？諛擞? //插入新棧頂元素時，top增1；刪除棧頂元素時，top減1 //非空棧的top始終在棧頂元素的下一個位置上 int stacksize; // 當前已分配的存儲空間，以元素為單位}; // 順序棧/********************** 構造一個空棧S **********************/Status InitStack(SqStack &S){ // 構造一個空棧S //棧底指針S.base指向新分配的STACK_INIT_SIZE個SElemType大小的空間 if (!(S.base = (SElemType *) malloc(STACK_INIT_SIZE * sizeof (SElemType)))) exit(OVERFLOW); // 存儲分配失敗 //必須給SqStack結構對象S的3個成員賦值 S.top = S.base; //空棧的棧頂指針S.top = 棧底指針S.base S.stacksize = STACK_INIT_SIZE; //初始棧容量 return OK;}/********************** 把S置為空棧 **********************/Status ClearStack(SqStack &S){ // 把S置為空棧 S.top = S.base; //空棧的棧頂指針S.top = 棧底指針S.base return OK;}/********************** 銷毀棧S **********************/Status DestroyStack(SqStack &S){ // 銷毀棧S，S不再存在 ClearStack(S); free(S.base); //釋放棧底指針S.base //必須給SqStack結構對象S的3個成員賦值 S.base = NULL; S.top = NULL; S.stacksize = 0; return OK;}/********************** 插入新的棧頂元素 **********************/Status Push(SqStack &S, char e){ // 插入元素e為新的棧頂元素 if (S.top - S.base >= S.stacksize) // 棧滿，追加存儲空間 //如果棧長度大于棧容量 { //可能會改變棧底地址，新棧底指針S.base S.base = (SElemType *) realloc(S.base, //原棧底指針 (S.stacksize + STACK_INCREMENT) * sizeof (SElemType)); //新大小 if (!S.base) exit(OVERFLOW); // 存儲分配失敗 //給SqStack結構對象S的3個成員賦值 S.top = S.base + S.stacksize; S.stacksize += STACK_INCREMENT; } *(S.top)++ = e; //先把e壓入棧頂，S.top再增1指向棧頂元素e的下一個位置 return OK;}/********************** 輸出棧元素 **********************/int Length=0;void OutList(SqStack S){ S.top=S.base; // 從棧底開始輸出 for(int i=0;i
文件四：迷宮求解 /********************** 聲明部分 **********************/#include //輸入輸出函數(shù)頭文件#include //內(nèi)存申請函數(shù)頭文件#define STACK_INIT_SIZE 10 //定義最初申請的內(nèi)存的大小#define STACK_INCREMENT 2 //每一次申請內(nèi)存不足的時候擴展的大小#define OVERFLOW false //異常拋出返回值#define FALSE false //異常拋出返回值#define TRUE true //異常拋出返回值#define ERROR false //異常拋出返回值#define INFEASIBLE false //異常拋出返回值#define OK true //程序正確執(zhí)行拋出返回值typedef bool Status; //別名聲明#define STACK_INIT_SIZE 10 // 存儲空間初始分配量#define STACKINCREMENT 2 // 存儲空間分配增量/* typedef int ElemType; */typedef struct{ int r; int c;}PosType;typedef struct{ int ord; /* 通道塊在路徑上的序號 */ PosType seat; /* 通道塊在迷宮中的“坐標位置” */ int di; /* 從此通道塊走向下一個通道塊的“方向” */}SElemType;typedef struct{ char arr[10][10];}MazeType;/********************** 結構類型部分 **********************/typedef struct SqStack{ //棧的數(shù)據(jù)元素類型在應用程序中定義typedef int SElemType; SElemType *base; // 棧底指針 //在棧構造之前和銷毀之后，base為NULL SElemType *top; // 棧頂指針 //初值指向棧底，top = base可做?？諛擞? //插入新棧頂元素時，top增1；刪除棧頂元素時，top減1 //非空棧的top始終在棧頂元素的下一個位置上 int stacksize; // 當前已分配的存儲空間，以元素為單位 //棧當前可使用的最大容量}SqStack;// 順序棧/********************** 構造一個空棧S **********************/Status InitStack(SqStack &S){ // 構造一個空棧S //棧底指針S.base指向新分配的STACK_INIT_SIZE個SElemType大小的空間 if (!(S.base = (SElemType *) malloc(STACK_INIT_SIZE * sizeof (SElemType)))) exit(OVERFLOW); // 存儲分配失敗 //必須給SqStack結構對象S的3個成員賦值 S.top = S.base; //空棧的棧頂指針S.top = 棧底指針S.base S.stacksize = STACK_INIT_SIZE; //初始棧容量 return OK;}/********************** 返回棧頂元素 **********************/Status GetTop(SqStack S, SElemType &e){ // 若棧不空，則用e返回S的棧頂元素，并返回OK；否則返回ERROR if (S.top > S.base) { e = *(S.top - 1); //因為S.top指向棧頂元素的下一個位置， //所以棧頂元素就是e = *(S.top - 1) return OK; } else return ERROR;}/********************** 插入新的棧頂元素 **********************/Status Push(SqStack &S, SElemType e){ // 插入元素e為新的棧頂元素 if (S.top - S.base >= S.stacksize) // 棧滿，追加存儲空間 //如果棧長度大于棧容量 { //可能會改變棧底地址，新棧底指針S.base S.base = (SElemType *) realloc(S.base, //原棧底指針 (S.stacksize + STACKINCREMENT) * sizeof (SElemType)); //新大小 if (!S.base) exit(OVERFLOW); // 存儲分配失敗 //給SqStack結構對象S的3個成員賦值 S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; } *(S.top)++ = e; //先把e壓入棧頂，S.top再增1指向棧頂元素e的下一個位置 return OK;}/********************** 刪除棧頂元素 **********************/Status Pop(SqStack &S, SElemType &e){ // 若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR if (S.top == S.base) //如果空棧，報錯 return ERROR; e = *--S.top; //S.top先減1指向棧頂元素，再取值，交給e帶回 return OK;}Status IsEmpty(SqStack &S){ // 若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR if (S.top == S.base) //如果空棧，報錯 return TRUE; return FALSE;}int pass(MazeType MyMaze, PosType CurPos);void footPrint(MazeType &MyMaze, PosType CurPos);void markPrint(MazeType &MyMaze, PosType CurPos);PosType nextPos(PosType CurPos, int Dir);int pass( MazeType MyMaze,PosType CurPos){ if (MyMaze.arr[CurPos.r][CurPos.c]==' ') return 1; // 如果當前位置是可以通過，返回1 else return 0; // 其它情況返回0}void footPrint(MazeType &MyMaze,PosType CurPos){ MyMaze.arr[CurPos.r][CurPos.c]='*';}void markPrint(MazeType &MyMaze,PosType CurPos) { MyMaze.arr[CurPos.r][CurPos.c]='!';}PosType nextPos(PosType CurPos, int Dir) { PosType ReturnPos; switch (Dir) { case 1: ReturnPos.r=CurPos.r; ReturnPos.c=CurPos.c+1; break; case 2: ReturnPos.r=CurPos.r+1; ReturnPos.c=CurPos.c; break; case 3: ReturnPos.r=CurPos.r; ReturnPos.c=CurPos.c-1; break; case 4: ReturnPos.r=CurPos.r-1; ReturnPos.c=CurPos.c; break; } return ReturnPos;}/* 迷宮函數(shù) *//* 判斷是否存在一條從開口到結尾的路徑 */int mazePath(MazeType &maze, PosType start, PosType end){ SqStack s; InitStack(s); PosType curpos = start; // 設定'當前位置'為'入口位置' SElemType e; int curstep = 1; // 探索第一步 do { if (pass(maze,curpos)) { // 當前位置可通過，即是未曾走到過的通道塊 footPrint(maze,curpos); // 留下足跡 e.di =1; e.ord = curstep; e.seat= curpos; Push(s,e); // 加入路徑 if (curpos.r == end.r && curpos.c==end.c) return TRUE; // 到達終點（出口） curpos = nextPos(curpos, 1); // 下一位置是當前位置的東鄰 curstep++; // 探索下一步 } else { // 當前位置不能通過 if (!IsEmpty(s)) { Pop(s,e); while (e.di==4 && !IsEmpty(s)) { markPrint(maze,e.seat); Pop(s,e); // 留下不能通過的標記，并退回一步 } // while if (e.di<4) { e.di++; Push(s, e); // 換下一個方向探索 curpos = nextPos(e.seat, e.di); // 當前位置設為新方向的相鄰塊 } // if } // if } // else } while (!IsEmpty(s) ); return FALSE;} // MazePathint main(){ //printf('Hello world!'); MazeType maze; maze.arr = { {'0','0','0','0','0','0','0','0','0','0'}, {'0',' ',' ','0',' ',' ',' ','0',' ','0'}, {'0',' ',' ','0',' ',' ',' ','0',' ','0'}, {'0',' ',' ',' ',' ','0','0',' ',' ','0'}, {'0',' ','0','0','0',' ',' ',' ',' ','0'}, {'0',' ',' ',' ','0',' ',' ',' ',' ','0'}, {'0',' ','0',' ',' ',' ','0',' ',' ','0'}, {'0',' ','0','0','0',' ','0','0',' ','0'}, {'0','0',' ',' ',' ',' ',' ',' ',' ','0'}, {'0','0','0','0','0','0','0','0','0','0'} }; PosType start = {1,1}; PosType end = {8,8}; if(mazePath(maze,start,end)) printf('You can go through the maze~~\n'); else printf('there is no path~~\n'); return 0;}
文件五：表達式求值 /********************** 聲明部分 **********************/#include //輸入輸出函數(shù)頭文件#include //內(nèi)存申請函數(shù)頭文件#define STACK_INIT_SIZE 10 //定義最初申請的內(nèi)存的大小#define STACK_INCREMENT 2 //每一次申請內(nèi)存不足的時候擴展的大小#define OVERFLOW false //異常拋出返回值#define FALSE false //異常拋出返回值#define TRUE true //異常拋出返回值#define ERROR false //異常拋出返回值#define INFEASIBLE false //異常拋出返回值#define OK true //程序正確執(zhí)行拋出返回值typedef int SElemType; //別名聲明，其實int可以用任意的名字代入typedef bool Status; //別名聲明#define STACK_INIT_SIZE 10 // 存儲空間初始分配量#define STACKINCREMENT 2 // 存儲空間分配增量/********************** 結構類型部分 **********************/struct SqStack{ //棧的數(shù)據(jù)元素類型在應用程序中定義typedef int SElemType; SElemType *base; // 棧底指針 //在棧構造之前和銷毀之后，base為NULL SElemType *top; // 棧頂指針 //初值指向棧底，top = base可做?？諛擞? //插入新棧頂元素時，top增1；刪除棧頂元素時，top減1 //非空棧的top始終在棧頂元素的下一個位置上 int stacksize; // 當前已分配的存儲空間，以元素為單位 //棧當前可使用的最大容量}; // 順序棧/********************** 構造一個空棧S **********************/Status InitStack(SqStack &S){ // 構造一個空棧S //棧底指針S.base指向新分配的STACK_INIT_SIZE個SElemType大小的空間 if (!(S.base = (SElemType *) malloc(STACK_INIT_SIZE * sizeof (SElemType)))) exit(OVERFLOW); // 存儲分配失敗 //必須給SqStack結構對象S的3個成員賦值 S.top = S.base; //空棧的棧頂指針S.top = 棧底指針S.base S.stacksize = STACK_INIT_SIZE; //初始棧容量 return OK;}/********************** 返回棧頂元素 **********************/Status GetTop(SqStack S, SElemType &e){ // 若棧不空，則用e返回S的棧頂元素，并返回OK；否則返回ERROR if (S.top > S.base) { e = *(S.top - 1); //因為S.top指向棧頂元素的下一個位置， //所以棧頂元素就是e = *(S.top - 1) return OK; } else return ERROR;}/********************** 插入新的棧頂元素 **********************/Status Push(SqStack &S, SElemType e){ // 插入元素e為新的棧頂元素 if (S.top - S.base >= S.stacksize) // 棧滿，追加存儲空間 //如果棧長度大于棧容量 { //可能會改變棧底地址，新棧底指針S.base S.base = (SElemType *) realloc(S.base, //原棧底指針 (S.stacksize + STACKINCREMENT) * sizeof (SElemType)); //新大小 if (!S.base) exit(OVERFLOW); // 存儲分配失敗 //給SqStack結構對象S的3個成員賦值 S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; } *(S.top)++ = e; //先把e壓入棧頂，S.top再增1指向棧頂元素e的下一個位置 return OK;}/********************** 刪除棧頂元素 **********************/Status Pop(SqStack &S, SElemType &e){ // 若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR if (S.top == S.base) //如果空棧，報錯 return ERROR; e = *--S.top; //S.top先減1指向棧頂元素，再取值，交給e帶回 return OK;}/********************** 判斷兩符號的優(yōu)先關系 **********************/SElemType Precede(SElemType t1, SElemType t2){ SElemType f; //棧元素f，準備存放<、=、>供函數(shù)返回值使用 switch (t2) { case '+': case '-': if (t1 == '(' || t1 == '#') //(、# < +、- f = '<'; else //其余 > +、- f = '>'; break; case '*': case '/': if (t1 == '*' || t1 == '/' || t1 == ')') //*、/、) > *、/ f = '>'; else //其余 < *、/ f = '<'; break; case '(': if (t1 == ')') //)后面不能緊跟(，緊跟報錯 { printf('ERROR1\n'); exit(ERROR); } else //其余 < ( f = '<'; break; case ')': switch (t1) { case '(': f = '='; //( = ) break; case '#': //#后面不能緊跟)，緊跟報錯 printf('ERROR2\n'); exit(ERROR); default: //其余 > ) f = '>'; } break; case '#': switch (t1) { case '#': f = '='; //# = # break; case '(': //(后面不能緊跟#，緊跟報錯 printf('ERROR3\n'); exit(ERROR); default: //其余 > # f = '>'; } } return f;}/********************** 判斷是否為運算符 **********************/Status In(SElemType c){ // 判斷c是否為運算符 switch (c) { case'+': case'-': case'*': case'/': case'(': case')': case'#': return TRUE; default: return FALSE; }}/********************** 計算函數(shù) **********************/SElemType Operate(SElemType a, SElemType theta, SElemType b) //棧元素a、theta、b{ // 二元運算c = a theta b SElemType c; //棧元素c，準備存放運算結果，供函數(shù)返回值使用 a = a - 48; b = b - 48; switch (theta) { case '+': c = a + b + 48; //運算完畢后再把數(shù)字轉換成字符 break; case '-': c = a - b + 48; break; case '*': c = a * b + 48; break; case '/': c = a / b + 48; } return c; //返回運算結果}/********************** 主算法函數(shù) **********************/SElemType EvaluateExpression() // 算法3.4{ // 算術表達式求值的算符優(yōu)先算法。設OPTR和OPND分別為運算符棧和運算數(shù)棧 SqStack OPTR, OPND; //順序棧OPTR、OPND SElemType a, b, c, x, theta; //棧元素a、b、c、x、theta InitStack(OPTR); //構造空棧OPTR，準備裝運算符 Push(OPTR, '#'); //棧OPTR的棧底元素是# InitStack(OPND); //構造空棧OPND，準備裝操作數(shù) //初始化循環(huán)變量 c = getchar(); //輸入字符c GetTop(OPTR, x); //取OPTR的棧頂元素交給x //只要棧頂元素x、或輸入字符c不為#，就循環(huán) while (c != '#' || x != '#') { if (In(c)) // 如果c是7種運算符之一，In(c)返回TRUE switch (Precede(x, c)) //比較棧頂元素x、輸入字符c的優(yōu)先權 { case '<': // 如果棧頂元素x優(yōu)先權低于輸入字符c Push(OPTR, c); //輸入字符c入運算符棧OPTR c = getchar(); //接收下個字符，準備下輪循環(huán) //接收不到就用原來在c中的值參加下輪和x的比較 break; case '=': // 如果棧頂元素x優(yōu)先權等于輸入字符c Pop(OPTR, x); //棧OPTR的棧頂元素出棧，賦給棧頂元素x //消括號(、)，只有(和)、#和#的優(yōu)先權相等； //但是#不用這消，而是用while循環(huán)的判斷條件消 //(的優(yōu)先權最高，)的優(yōu)先權最低， //如果(在棧頂、)在輸入，則( = )； //如果)在棧頂、(在輸入，則報錯 c = getchar(); //接收下個字符，準備下輪循環(huán) //接收不到就用原來在c中的值參加下輪和x的比較 break; case '>': // 如果棧頂元素x優(yōu)先權高于輸入字符c Pop(OPTR, theta); // 棧頂元素x出運算符棧OPTR，賦給theta Pop(OPND, b); //操作數(shù)出操作數(shù)棧OPND，賦給b Pop(OPND, a); //操作數(shù)出操作數(shù)棧OPND，賦給a Push(OPND, Operate(a, theta, b)); //運算結果Operate(a, theta, b)入操作數(shù)棧OPND break; } else if (c >= '0' && c <= '9') // 如果c在0到9之間，是操作數(shù) { Push(OPND, c); //操作數(shù)c入操作數(shù)棧OPND c = getchar(); //接收下個字符，準備下輪循環(huán) } else // 如果c既不是7種運算符也不是0到9的操作數(shù)，那么c是非法字符，報錯 { printf('ERROR4\n'); exit(ERROR); } GetTop(OPTR, x); //只要運算符棧OPTR的棧頂元素x或當前讀入字符c不為#， //就不斷地取運算符棧OPTR的棧頂元素賦給x } //循環(huán)結束時，操作數(shù)棧OPND的棧頂元素是運算結果 GetTop(OPND, x); //取操作數(shù)棧OPND的棧頂元素（運算結果）賦給x return x; //返回運算結果}int main(){ printf('請輸入算術表達式（中間值及最終結果要在0～9之間），并以#結束\n'); printf('%c\n', EvaluateExpression()); //算術表達式求值 return 0;}
文件六：漢諾塔遞歸實現(xiàn) /*********** 漢諾塔 *********/#include int c = 0; // 全局變量，搬動次數(shù)//x源塔，第n個圓盤（編號n），z目標塔void move(char x, int n, char z){ // 將編號為n的圓盤從塔座x搬到塔座z printf('第%i步: 將%i號盤從%c移到%c\n', ++c, n, x, z);}//n個圓盤（編號從1到n），x源塔，y輔助塔，z目標塔void hanoi(int n, char x, char y, char z){ // 將塔座x上按直徑由小到大且自上而下編號為1至n的n個圓盤 // 按規(guī)則搬到塔座z上，y作輔助塔 if (n == 1) move(x, 1, z); // 將編號為1的圓盤從塔座x搬到塔座z else { hanoi(n - 1, x, z, y); // 將塔座x上編號為1至n - 1的圓盤搬到塔座y，z作輔助塔 move(x, n, z); // 將編號為n的圓盤從塔座x搬到塔座z hanoi(n - 1, y, x, z); // 將塔座y上編號為1至n - 1的圓盤搬到塔座z，x作輔助塔 }}int main(){ int n; printf('3個塔座為a、b、c，圓盤最初在a座，借助b座移到c座。請輸入圓盤數(shù)：'); scanf('%d', &n); hanoi(n, 'a', 'b', 'c'); // 將塔座a上編號為1至n的n個圓盤搬到塔座c上，b作輔助塔 return 0;}
|
