【正文】 itStack(struct sNode **HS) { *HS=NULL。 } 如果 定義為 struct sNode*類型的棧頂變量 p作為一個棧頂指針，則初始化程序可變?yōu)椋? Void InitStack(amp。p) { p=NULL。 } 2. 向鏈棧中插入一個元素 void Push(struct sNode** HS, ElemType x) { /*為插入元素獲取動態(tài)結點 */ struct sNode *newp。 newp=malloc(sizeof(struct sNode))。 if(newp==NULL) { printf(內存動態(tài)空間用完，退出運行 !\n)。 exit(1)。 } /*給新分配的結點賦值 */ newpdata=x。 /*向棧頂插入新結點 */ newpnext=*HS。 *HS=newp。 } 3. 從鏈棧中刪除一個元素并返回它 ElemType Pop(struct sNode** HS) { struct sNode* p。 ElemType temp。 /*對于空棧則退出運行 */ if(*HS==NULL) { printf(?？諢o法刪除 !\n)。 exit(1)。 } /*暫存棧頂結點指針 ,并使棧頂指針指向下一結點 */ p=*HS。 *HS=pnext。 /*暫存原棧頂元素以便返回 ,同時回收原棧頂結點 */ temp=pdata。 free(p)。 /*返回原棧頂元素 */ return temp。 } 4. 讀取棧頂元素 ElemType Peek(sNode **HS) //HS為值參或引用形參均可 { if(*HS==NULL) { //無法從空棧中讀取 printf(“?？?，無棧頂結點！ \n”) exit(1)。 } return (*HS)data。 //返回棧頂結點的值 } 棧的簡單應用舉例 例 41 從鍵盤上輸入一批整數，然后按照相反的次序打印出來 根據題意可知，后輸入的整數將先被打印出來，這正好符合棧的后進先出的特點。所以此題很容易用棧來解決。假定采用順序棧，其參考程序 如下： include include typedef int ElemType。 /*定義元素類型為整型 */ struct StackSq { ElemType *stack。 /*存棧元素的動態(tài)數組指針 */ int top。 /*存棧頂元素的下標位置 */ int MaxSize。 /*存 stack數組長度，亦即所能存儲棧的最大長度 */ }。 include順序棧操作 .c /*假定對順序棧各種操作的算法已經存于該程序文件中 */ void main() { struct StackSq a。 int x。 InitStack(amp。a)。 printf(輸入一批整數，直到輸入終止標志 1為止 !\n)。 scanf(%d,amp。x)。 while(x!=1) { Push(amp。a,x)。 scanf(%d,amp。x)。 } while(!EmptyStack(amp。a)) /*棧不為空時依次退棧并輸出 */ printf(%d ,Pop(amp。a))。 printf(\n)。 } ?假定從鍵盤上輸入為： ? 78 63 45 82 91 34 1 ?則輸出為： ? 34 91 82 45 63 78 例 42 堆棧在計算機語言的編譯過程中可用來進行語法檢查。試編寫一個算法，用來檢查一個 C/C++語言程序中的花括號、方括號和圓括號是否配對，若能夠全部配對則返回 1，否則返回 0。 編寫出算法如下： int BracketsCheck(char* fname) /*對由 fname所指字符串為文件名的程序文件進行括號配對檢查 */ { Struct StackSq a。 /*定義一個順序棧 */ char ch。 /*定義一個字符變量 */ FILE *finstr。 /*定義一個文件指針變量，即文件流 */ finstr=fopen(fname,r)。 /*用文件流 finstr打開以 fname所指字符串為文件名的文件 ,并規(guī)定為讀文件方式 */ if(!finstr) { /*沒有找到對應的磁盤文件則退出運行 */ printf(File\39。%s\39。not found!\n,fname)。 exit(1)。 } InitStack(amp。a)。 /*棧 a初始化 */ ch=fgetc(finstr)。 /*從文件中讀取第一個字符到 ch*/ while(ch!=EOF) /*未讀到文件最后的結束標志則循環(huán) */ { printf(%c,ch)。 /*向屏幕輸出被讀出的字符 */ switch (ch) /*對讀到的各種括號分情況處理 */ { case 39。{39。: case 39。[39。: case 39。(39。: Push(amp。a,ch)。 /*出現以上三種左括號則進棧 */ break。 case 39。}39。: if(Peek(amp。a)==39。{39。) Pop(amp。a)。 /*棧頂的左花括號出棧 */ else return 0。 break。 case 39。]39。: if(Peek(amp。a)==39。[39。) Pop(amp。a)。 /*棧頂的左中括號出棧 */ else return 0。 break。 case 39。)39。: if(Peek(amp。a)==39。(39。) Pop(amp。a)。 /*棧頂的左圓括號出棧 */ else return 0。 break。 } ch=fgetc(finstr)。 /*從文件中順序讀取下一個字符到 ch*/ } if(EmptyStack(amp。a)) /*棧最后為空時返回 1否則返回 0*/ return 1。 else return 0。 } 167。 算術表達式的計算 167。 算術表達式的兩種表示 ? 算術表達式是操作數（又叫運算對象）和運算符以及改變運算次序的括號（圓或方括號）所組成。 ? 操作數可以是常量，變量和函數，同時還可以是另一個表達式。 ? 而運算符可以是單目運算符和雙目運算符。單目運算符只需一個操作數，雙目運算符要求兩個操作數，并被放在兩個操作數的中間。 ? 單目運算符有取正，取負，平方、開根等。而雙目運算符有 +、 、 、 247。 等。 ? 雙目運算符出現在兩個操作數中間的這種習慣表示法叫做算術表達式的中綴表示法（如 2+5 6）。這種算術表達式稱為中綴表達式。 ? 中綴表達式的計算必須遵守以下三條規(guī)則： (1) 先計算括號內，后計算括號外； (2) 在無括號或同層括號內，先進行乘除運算，后 進行加減運算，即乘除運算的優(yōu)先級高于加減 運算的優(yōu)先級； (3) 同一優(yōu)先級運算，從左向右依次進行。 ?運算符放在兩個計算對象的后面的算式表示法叫做后綴表示法 ?在利用后綴表示法進行計算時，不存在括號，也不存在優(yōu)先級的差別，計算過程完全按照運算符出現的先后次序來進行，整個計算過程只需前面的一個運算符的掃描排序過程。 ?采用后綴表示的計算表達式，可利用標準的計算程序來實現多種復雜的算術表達式的計算。 例如，對于下列各中綴表達式： (1) 3/5+6 (2) 169*(4+3) (3) 2*(x+y)/(1x) (4) (25+x)*(a*(a+b)+b) 對應的后綴表達式分別為： (1) 3□ 5□ /□ 6□ + (2) 16□ 9□ 4□ 3□ +□ *□ (3) 2□ x□ y□ +□ *□ 1□ x□ □ / (4) 25□ x□ +□ a□ a□ b□ +□ *□ b□ +□ * 后綴表達式求值的算法 算法思想： 1. 利用堆棧對算式從頭到尾進行掃描，來實現對算式的解釋和計算。 2. 算式用一字符串來表示，并用空格來分隔各操作數和運算符 3. 在掃描時，遇到操作數就將其壓入堆棧（如遇到小數點則將整個帶小數點的數字轉換為浮點數后再壓入堆棧），直到遇到運算符 4. 在掃描時，遇到運算符，就將堆棧內的最上面的兩個操作數彈出，并按其掃描到的運算符進行計算。 5. 將計算結果存入一個結果變量中（如 x)，并壓入堆棧，以便作為后面運算的操作數 6. 依次向下掃描每一個字符直到遇到字符串結束符 例子： 假定有一個中綴算術表達式： ((12+34)+(5/2))*2 該表達式用后綴表示法的表示字符串為： char *a=“12 34 + 5 2 / + 2 *”。 使用后綴表達式求值的算法計算后可得到與