1. 堆疊

1. 堆疊的定義：限定在表尾進行插入和洗掉操作的線性表
2. 空堆疊：不換任何元素的堆疊
3. 堆疊頂 top ：允許插入洗掉的一端
4. 堆疊的操作(連續設計)
   1. 置空堆疊 make_null_stack()

   #define maxn 1000    // max number of stack frames
   typedef struct{
    datatype elements[maxn];
    int top;
   } Stack;
   
   void make_null_stack(Stack& stack){
    stack.top = -1;
   }
   

   2. 判斷堆疊是否為空 empty()

   bool empty(Stack& stack){
    return stack.top == -1;
   }
   

   3. 入堆疊 push()

   void push(Stack& stack , datatype element){
    if(stack.top == maxn - 1) 
        cout << "Overflow!" << endl;
    else stack[++top] = element;
   }
   

   4. 出堆疊 pop()

   void pop(Stack& stack){
    if(empty(stack)) 
        cout << "Stack is NULL" << endl;
    else --stack.top;
   }
   

   5. 獲得堆疊頂元素 peek()

   datatype peek(Stack& stack){
    return (empty(stack)) ? NULL : stack[top];
   }
   

5. 堆疊的操作（單鏈表）：當多個堆疊共享空間時，連續存盤已經無法滿足空間需要
   1. 置空堆疊 make_null_stack()

   typedef struct Node{
    datatype data;
    Node* next;
    Node(datatype data):Node(data , nullptr){};
   }Stack;
   
   Stack make_null_stack(){
    Stack top = new Node(0 , nullptr);
    return top;
   }
   

   2. 判斷堆疊是否為空 empty()

   bool empty(Stack& top){
    return top -> next == nullptr;
   }
   

   3. 入堆疊 push()

   void push(Stack& top , datatype element){
    Stack s = new Node(element);
    s->next = top -> next;
    top -> next = s;
   }
   

   4. 出堆疊 pop()

   void pop(Stack& top){
    if(empty(top)) 
        cout << "Stack is NULL" << endl;
    else {
        Stack s ;
        s = top -> next;
        top -> next = s -> next;
        delete s;
    }
   }
   

   5. 獲得堆疊頂元素 peek()

   datatype peek(Stack& top){
    return (empty(top)) ? NULL : top->next->data;
   }
   

2. 堆疊的應用

1. 進制轉換:十進制轉 base 進制

   classDiagram direction RL Stack <|-- 豎式除法 class 豎式除法{ 8 | 159 ---7 8 | 19 ---3 8 | 12 ---2 0 } class Stack{ 2 3 7 }

   void convertion(int number , int base){
    stack<int> stk;
    while(number){
        stk.push(stk , number % base);
        number /= base;
    }
    while(!empty(stk)){
        int ele = stk.peek();
        cout << ele;
        stk.pop();
    }
   }
   

2. 運算式處理

   1. 運算式形式 (a + b) * (a - b)

      1. 前綴運算式：*+ab-ab （波蘭運算式）
      2. 中綴運算式：(a + b) * (a - b)
      3. 后綴運算式：ab+ab-*（逆波蘭運算式）

   2. 中綴運算式求值

      1. 規則：\(\theta 1\) 在 \(\theta 2\) 的前面

      \(\theta1/\theta2\)	+	-	*	/	(	)	#
      +	>	>	<	<	<	>	>
      -	>	>	<	<	<	>	>
      *	>	>	>	>	<	>	>
      /	>	>	>	>	<	>	>
      (	<	<	<	<	<	=
      )	>	>	>	>		>	>
      #	<	<	<	<	<		=

      2. 操作
         1. 運算元堆疊置空，運算子堆疊壓入 # (終止符)
         2. 依次讀入運算式的每個單詞
         3. 如果是運算元，壓入運算元堆疊
         4. 如果是運算子，將運算子堆疊頂元素 \(\theta1\) 與讀入的運算子 \(\theta2\) 進行優先級比較
            1. 如果堆疊頂元素優先級低 ， 將 \(\theta2\) 壓入運算子堆疊
            2. 如果優先級相等 ， 彈出 pop() 運算子堆疊
            3. 如果堆疊頂元素優先級高 ， 彈出兩個運算元，一個運算子，進行計算，并將計算結果壓入運算元堆疊，重復第4步
         5. 全部處理完畢，operator_stack.top() == '#'

   3. 中綴轉為后綴運算式（后綴運算式更利于計算機計算）

      1. 運算元堆疊置空，運算子堆疊壓入 # (終止符)
      2. 依次讀入運算式的每個單詞
      3. 如果是運算元，直接輸出
      4. 如果是運算子，將運算子堆疊頂元素 \(\theta1\) 與讀入的運算子 \(\theta2\) 進行優先級比較
         1. 如果堆疊頂元素優先級低 ， 將 \(\theta2\) 壓入運算子堆疊
         2. 如果優先級相等 ， 彈出 pop() 運算子堆疊
         3. 如果堆疊頂元素優先級高 ， 彈出 pop() 運算子堆疊頂元素并且輸出，重復第4步
      5. 全部處理完畢，operator_stack.top() == '#'

3. 遞回 \(Recursion\)

1. 遞回基本思想

1. 遞回呼叫的定義：子程式（或函式）直接呼叫自己或者一系列呼叫陳述句間接呼叫自己，是一種描述問題和解決問題的基本方法
2. 基本思想：將大問題化為重復的小問題，直至每個小問題都可以得到直接解決
3. 演算法
   1. 遞回基：最小子問題
   2. 遞回步：通過較為簡單的函式值定義一般情況下的函式值
4. 適用問題：問題具有某種可借用的類同自身的子問題的描述的性質
5. 分類：
   • 單路遞回：一個遞回程序只有一個遞回入口
   • 多路遞回：一個遞回程序有多個出口
   • 間接遞回：函式可以通過其他函式間接呼叫自己
   • 迭代遞回：每次遞回呼叫都包含一次回圈遞回

2. 遞回演算法實體

1. 排列問題
   1. 有 \(n\) 個元素，編號為 \(1,2,\cdots,n\)，用一個具有 \(n\) 個元素的陣列 A 來存放所生成的排列，然后輸出它們
   2. 分析：
      1. 遞回基：\(k = 1\) ， 只有一個元素，顯然構成排列
      2. 遞回步：\(k > 1\) ， 如果可由演算法 perm(A,k-1,n) 完成陣列后面k-1個元素的排列，為完成陣列后面k個元素的排列perm(A,k,n)，逐一對陣列第n-k元素與陣列中第n-k ~ n 元素進行互換，每互換一次，就執行一次perm(A,k-1,n)操作，產生一個排列
   3. 演算法

   void perm(vector<int> arr , int k , int n){
       if(k == 1) {    //遞回基
           for(int i = 0 ; i < n ; ++i) cout << arr[i] << ' ';
       }
       else {
           for(int i = n - k ; i < n ; ++i){
               swap(arr[i] , arr[n - k]);
               perm(arr , k - 1 , n);  //遞回步
               swap(arr[i] , arr[n - k])
           }
       }
   }
   

2. \(Hanoi\)漢諾塔問題
   1. 設A,B,C是3個塔座，開始時，在塔座A上有一疊共n個圓盤，這些圓盤自下而上，由大到小地疊在一起，各圓盤從小到大編號為1,2,...,n,現要求將塔座A上的這一疊圓盤移到塔座B上，并仍按同樣順序疊置，在移動圓盤時應遵守以下移動規則：
      1. 每次只能移動1個圓盤；
      2. 任何時刻都不允許將較大的圓盤壓在較小的圓盤之上；
      3. 在滿足移動規則1和2的前提下，可將圓盤移至A,B,C中任一塔座上
   2. 分析：
      1. 把 n-1 個盤子移到 B 上（通過C移到從A移到B）
      2. 把第 n 個盤子移到 C 上
      3. 把 n-1 個盤子移到 C 上 （通過A移到從B移到C）
   3. 演算法

      void move(char pillar_1, int index, char pillar_2){
         cout << "move plate " << index << 
         " from " << pillar_1 << " to " << pillar_2 << endl;
      }
      
      void hanoi(int n, char a, char b, char c){
         if(n == 1) move(a, 1, c);   //將編號1的盤子從a移到c
         else {
            hanoi(n - 1, a, c, b);  //通過c移到從a移到b
            move(a, n, c);
            hanoi(n - 1, b, a, c);  //通過a移到從b移到c
         }
      }
      

3. 函式遞回呼叫的內部執行程序

1. 運行開始時，首先為遞回呼叫一個作業 堆疊 ，其結構包括值參，區域變數與回傳地址
2. 每次執行遞回呼叫之前，將遞回函式的值參和區域變數的當前值以及呼叫后的回傳地址壓入堆疊中
3. 每次遞回呼叫結束之后，將堆疊頂元素彈出堆疊，是相應的值參和區域變數恢復為呼叫前的值，然后轉向送回回傳地址指定的位置繼續執行

標籤：其他

上一篇：分布式存盤系統之Ceph集群RBD基礎使用

下一篇：ABC 271 F - XOR on Grid Path（搜索 meet in the mid）