第五章堆叠与伫列.pptVIP

第五章 堆疊與佇列 使用陣列結構建立堆疊 使用鏈結串列建立堆疊 運算式表示法的種類 中序、前序和後序運算式的計算 中序運算式轉成後序運算式 使用堆疊做回溯控制 佇列的應用 使用陣列結構建立佇列 環狀佇列 使用鏈結串列建立佇列 雙佇列 使用陣列結構建立堆疊 「堆疊」(Stacks)屬於一種抽象的資料結構，可以使用多種方式來設計，這種資料結構擁有兩種特性，如下所示： 只能從堆疊的頂端存取資料。 資料是以後出先進(Last Out, First In)的原則進行資料的存取。 使用陣列結構建立堆疊 - 宣告 使用陣列來儲存堆疊資料，如下所示： int stack[MAXSTACK]; 宣告一個變數指向堆疊頂端的陣列索引，如下所示： int top=-1; 使用陣列結構建立堆疊 - push() 函數push()的操作分為二個步驟，如下所示： Step 1：將堆疊頂端的指標加壹。 Step 2：將欲存放的資料存入指標所指的陣列元素內。 使用陣列結構建立堆疊 - pop() 函數pop()的操作分為二個步驟，如下所示： Step 1：取出目前堆疊指標所指的陣列內容。 Step 2：將堆疊指標的內容減一，即指向下一個堆疊元素。 使用鏈結串列建立堆疊 堆疊串列內的結構宣告，如下所示： struct stack_node{ int data; struct stack_node *next;};typedef struct stack_node stack_list;typedef stack_list *link; 一個指標指向堆疊串列頂端的結構指標，其宣告方式如下所示： link stack=NULL; 使用鏈結串列建立堆疊 - push() 函數push()的操作可以分為三個步驟，如下所示： Step 1：建立一個新節點後，存入欲存放的資料。 Step 2：將新節點的指標指向原來堆疊指標所指的節點。 Step 3：新節點指標成為堆疊頂端的指標。 使用鏈結串列建立堆疊 - pop() 函數pop()的操作可以分為三個步驟，如下所示： Step 1：將堆疊指標指向下一個節點。 Step 2：取出原來堆疊指標所指節點的內容。 Step 3：釋回原來堆疊指標所指節點的記憶體。 運算式表示法的種類 「中序表示法」(Infix)： A+B A*B+C 「前序表示法」(Prefix)： +AB +*ABC 「後序表示法」(Postfix)： AB+ AB*C+ 運算式表示法的種類 - 優先順序 運算式表示法的種類 - 轉換 A*(B+C) 將其轉換成前序和後序表示法的步驟，如下表所示： 中序運算式的計算 - 步驟 Step 1：建立運算子和運算元堆疊，而且清除其內容。 Step 2：當運算式內尚有未讀取的運算元、運算子時，如下所示： (1) 讀取運算元或運算子。 (2) 如果讀取的是運算子，則： 1) 如果運算子堆疊是空的，存入運算子堆疊，否則和運算子堆疊頂端的運算子比較優先順序，如果比較低，則： a. 從運算子堆疊取出一個運算子。 b. 從運算元堆疊取出所需的運算元。 c. 計算其值後存回運算元堆疊。 2) 存入運算子至運算子堆疊。 3) 讀取的是運算元，就直接存入運算元堆疊。 Step 3：當運算子堆疊不是空的。 (1) 從運算子堆疊取出一個運算子。 (2) 從運算元堆疊取出所需的運算元。 (3) 計算其值後，存回運算元堆疊。 Step 4：取出運算元堆疊的內容就是最後的計算結果。 前序運算式的計算 處理運算式讀取的操作是將前序運算式整個存入堆疊後，再從堆疊內取出每個字元。讀入運算式迴路的步驟，如下所示： Step 1：如果是運算元存入運算元堆疊。 Step 2：如果是運算子就從運算元堆疊取出所需的運算元，接著計算運算元和讀入運算子的結果後存回運算元堆疊。 等到整個運算式讀取完畢，運算式的結果也就馬上計算出來。 後序運算式的計算 後序運算式的計算並不需要全部推入堆疊，只要從左至右讀取運算式，其完整的步驟如下所示： Step 1：使用迴路從左至右讀入後序運算式。 (1) 如果讀入的是運算子立刻從運算元堆疊取出所需的運算元，接著計算上述運算元和運算子的值，最後將值存回運算元堆疊。 (2) 如果讀入的是運算元就直接存入運算元堆疊。 中序運算式轉成後序運算式 後序運算式是直接從中序運算式轉換而成，兩個運算式的運算元排列順序相同，只有運算子的排列不同 a*b+c*(d-e)/f (中序運算式) ab*cde-*f/+ (後序運算式) 運算元處理不需要運算元堆疊，在讀入運算元後只需馬上輸出。 運算子的處理和中序運算式的計算相同。 使用堆疊做回溯控制 「回溯」(Backtracking)屬於人工