[ToC]

學習路線

Ch1Algorithm, Recursion and Performance Analysis(space + Time)

Ch3 Stack & Queue

Ch5 Tree And Binary Tree

Ch9 Advanced Trees

Ch7 Search and Sorting

CH8 Hasing

Ch6 Graph

Ch2/Ch4 Array&Linked List

Ch1 Algorith, Recursion and Performance Analysis

Algo定義(5個Criteria)

Recursion(遞迴)☆☆☆☆☆

定義

種類

與 Non-Recursion比較考型及來源

效能分析

Space(較少考)

Time(較常考)☆☆☆☆☆

Algorithm(演算法)

• 定義：為了解決特定問題之有限個敘述／步驟／指令所構成之集合，且必須滿足下列５個Criteria：

1. Input：輸入的資料量>=0個即可
2. Output：至少要有>=1個輸出量
3. Definiteness(明確性)：每個敘述／步驟／指令必須是Clear且unambiauous(不可混淆不清)。3之要求在於Algo之寫作格式無一致標準之規範
4. Finiteness(有限性)：必須在執行／追蹤有限個步驟後，必能夠終止
5. Effectiveness(有效性)：人可以用紙和筆追蹤／執行每一個步驟，即每一個Step is baisc enough to be carried。當log完成，你如何確定它是正確的

Recurtion(遞迴)

• 定義：(以Direct Recursion為例)，Algo/program中含有==self-calling(自我呼叫)==敘述存在者，稱之遞迴

• 種類：

  1. Direct：直接遞迴
  2. Indirect：間接遞迴
  3. Tail：尾端遞迴

• 分述如下

  1. 直接遞迴：方法中直接呼叫自己

     1 2 3 4 5 6 7

     function A(){ // do something if(...) then A(); //重複自己 else{ // do something } }

  2. 間接遞迴：多個Module之間彼此形成Calling Cycle，

     1 2 3 4 5 6 7 8 9 10 11

     function A(){ //something Call B(); //相互呼叫 //something } function B(){ //something Call A(); //相互呼叫 //something }

  3. 尾端遞迴：是Direct Recustion 之一種，recursive call發生在程式即將結束之前一行

     1 2 3 4

     function A(){ //do something if(xxx){} then A() //程式的最後一行 優點是Complier或工程師方便改寫成非遞迴的形式(降低時間複雜度 }

任何problem之解決，必定存在兩種形式之Algo

1. 遞迴
2. 非遞迴(Interation)

eq. 求n! 求費氏數列

比較圖如下

• 補充

在complier或程式語言的課程裡面，會討論如何處理recursion?

1. 當遇到Recursive call的時候，

   1. 必須先保存當時執行狀況，push這些東西

   1. 參數值
   2. 區域/占存 變數值
   3. 返回位址(return address)

   到System stack

   2. Jump to 程式開端執行

2. 若遇到程式結束(END)敘述時遞迴條件不符合，繼續往下執行，遇到程式的END，要判斷是某一次的遞迴結束，還是整個都結束了。判斷的依據是查看Stack區是否為空，若為空則代表只是一次的遞迴結束，若Stack為空，則代表整個程式結束

   1 2 3 4 5

   if (stack is empty) then 整個結束 else{ pop stack; //取出當時保存的參數或區域變數以及返回位置(return address) then go to "return address"執行 //所謂的return address(返回位址，就是指遞迴結束完後，下一個會執行的程式碼) }

   例：

   1 2 3 4 5 6 7 8 9 10

   function A(int a){ int x = 0; int y=0; a++; if(xxx) then A(a); //recursive call else{ //do something } x=x+1; (這就是返回位址 (1:) }

考型及來源

考型：

1. 給一個Probleam，寫下Recursive algo/code
2. 給Recursive algo/code，要我們追蹤結果 etc…

來源：

1. 數學類：階層
2. 往後章節(二元樹的追蹤、圖形的追蹤、排序的追蹤…)
3. 其他

1. Tower fo Hanoi
2. permutation printing

數學類

1. 寫下一個非遞迴的求階層方法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

int fac(int n){
    if(n==0){
        return 1;
    }else // n>0{
        int S=1;
    	int i ;
    	for(i=1;i<=n;i++){
            S=S*i;
            return S;
        }
    }   
}

2. 寫下一個用遞迴處理的求階程式

   ==關鍵點：記下數學遞迴定義式==

   

   1 2 3 4 5 6 7

   int fac(int n){ if(n==0){ return 1; }else{ return n * fac(n-1) ; } }

3. 以2的Code為題目

   1. 求Fac(3)

      

   2. 共呼叫Fac函數?次，含Fac(3)這次這影響到了時間複雜度，以及會調用幾次pop

      4次，Fac(n)共呼叫幾次=n+1次

4. write a recursive algo for sum(n)= 1+2+…+n, and sum(0)=0;

   

   1 2 3 4 5 6 7

   int sum(int n){ if(n==0){ return 0; }else{ return n+sum(n-1); } }

5. Fibonacci Number(費氏數列)

   

   n	0	1	2	3	4	5	6	7	8	9	10	11	12	13
   Fn	0	1	1	2	3	5	8	13	21	34	55	89	144	233

   Q：F98 = ? + ? = ? - ? = ? - ?

   1. F97+F96;
   2. F99-F97;
   3. F100-F99;

   Q：不超過500之費氏數列

   ​ A. F14 = 377

6. Write a recursive algo/code for Fibonacci

   1. 遞迴解法

   1 2 3 4 5

   int Fib(int n){ if(n==0){ return 0;} if(n==1){return 1;} return Fib(n-1)+Fib(n-2); }

   2. 非遞迴解法

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

   int Fib(int n){ if (n==0){ return 0 }else if(n==1){ return 1 }else{ int a =0; int b =1; int c ; int i ; for(i=2;i<n;i++){ c= a + b; a =b ; b = c ; } return c; } }

   Fo	F1	F2	F3	…
   a=0	b=1	c=a+b a=b b=c	c=a+b a=b b=c	…

7. 依(1)之code，(i)求出Fib(5)之值(ii)呼叫次數?次(iii)Fib(10)的呼叫次數呢?

   1 2 3 4 5

   int Fib(int n){ if(n==0){ return 0;} if(n==1){return 1;} return Fib(n-1)+Fib(n-2); }

   ans .

   (i) 5

   (ii)

   (iii)

   4. 令T_(n)代表求Fin(n)時之呼叫次數，即T(0)=T(1)=1次，(i)寫出T(n)之Recursive definition(ii)Based on (i)，求出T(10)之值

      ans . (i) T(n) = T(n-1)+T(n-2)+1 且 T(0) =T(1) = 1;

      ​ (ii)

      0	1	2	3	4	5	6	7	8	9	10
      1	1	3	5	9	15	25	41	67	109	177

   5. 求Fib(5)時，則Fib(0),Fib(1),Fib(2),Fib(3),Fib(4),Fib(5),分別被呼叫?次

      Fib(n)	0	1	2	3	4	5
      呼叫幾次	3	5	3	2	1	1

      5只會自己生自己，4只會由5產生，3會由4跟5產生(1+1)，2則是由3跟4產生(2+1)，1會由2跟3產生(3+5)，但0只會由2產生，不會由0產生。

   6. 接續上題，那Fib(10)呢?

      Fin(n)	0	1	2	3	4	5	6	7	8	9	10
      呼叫幾次	34	55	34	21	13	8	5	3	2	1	1

   7. 令T(n)代表求Fib(n)時之加法次數

      (i)求出T(n)之recursive definition

      (ii)求T(5)之值 based on(i)

      ans

      (i) T(n)=T(n-1)+T(n-2)+1，且T(0)=0,T(1)=0

      Fib(n)	0	1	2	3	4	5	6	7	8
      呼叫幾次	0	0	1	2	4	7	12	20	33

   8. code如下，求F(5)之值

      1 2 3 4

      int Fib(int n){ if(n==0 || n==1){return 1} return F(n-1)+F(n-2) }

      Fib(n)	0	1	2	3	4	5
      值	1	1	2	3	5	8

   9. code如下

      1 2 3 4 5

      int Fib(int n){ if(n<1){return 0} if(n<3){return 1} return Fib(n-1)+Fin(n-2) }

      (i)求Fib(5)之值

      Fib(n)	0	1	2	3	4	5
      值	0	1	1	2	3	5

      (ii)呼叫Fib函數?次(含Fib(5))

      

   10. Binomical coe(二項式係數)

   ​

   $$ {C_m}^n =(\underset{m}{\overset{n}{{}}})=\frac{n!}{m!(n-m)!} $$

​

$$ (i)write a recursive algo / code 求 (\underset{m}{\overset{n}{{}}})之值 $$

ans. 關鍵，==必背==

$$ (\underset{m}{\overset{n}{{}}})=
\begin{cases} & 1, \text{ if } (n = m \text{ or } m = 0) \
& (\underset{m}{\overset{n-1}{{}}})+(\underset{m-1}{\overset{n-1}{{}}}) \end{cases} $$

1
2
3
4
5
6

int Bin(int n , int m){
if(n==m || m==0){return 1}
else{
return Bin(n-1,m)+Bin(n-1,m-1)
}
}

(ii) based on (i) code 求Bin(5,3)之值及呼叫次數

ans 10 ,19次

Note ：計算時有些撇步

$$ (\underset{3}{\overset{5}{{}}}) = \frac{5\times4\times3}{1\times2\times3}=10 $$

$$ (\underset{4}{\overset{8}{{}}}) = \frac{8\times7\times6\times5}{1\times2\times3\times4}=70 $$

12. GCD(A,B) 求A,B兩數之最大公因數，寫出recursive algo/code

==☆☆☆☆☆☆☆☆☆要背☆☆☆☆☆☆☆☆☆☆☆☆==

$$ GCD(A,B)=\ \begin{cases} & B, \text{ if } (A modsB)=0 \
&GCD(B,AmodsB), other wise \end{cases} $$

1
2
3
4

int GCD(int A,int B){
if (A%B==0) {return B}
else return GCD(B,A%B)
}

依上述code，試求(1)求GCD(18,33)之值(2)呼叫GCD?次

13. Ackerman’s Function 一坨大便，幹破你娘

$$ A(m,n) = \begin{cases} n+1, & \text{if } m=0\
A(m-1,1), & \text{if } n=0\
A(m-1,A(m,n-1)), & \text{otherwise} \end{cases} $$

(i) A(2,2)=?

ans.

A(2, 2) =7

(ii) A(10,10) ans.

A(10, 10) = A(9, A(10, 9)) = A(9, A(9, A(10, 8))) = A(9, A(9, A(9, A(10, 7)))) = A(9, A(9, A(9, A(9, A(10, 6))))) = A(9, A(9, A(9, A(9, A(9, A(10, 5)))))) = A(9, A(9, A(9, A(9, A(9, A(9, A(10, 4))))))) = A(9, A(9, A(9, A(9, A(9, A(9, A(9, A(10, 3)))))))) = A(9, A(9, A(9, A(9, A(9, A(9, A(9, A(9, A(10, 2))))))))) = A(9, A(9, A(9, A(9, A(9, A(9, A(9, A(9, A(9, A(10, 1)))))))))) = A(9, A(9, A(9, A(9, A(9, A(9, A(9, A(9, A(9, A(9, 1)))))))))) ≈ 2.1216 x 10^19728

(iii)A(1,3)

A(1, 3) = A(0, A(1, 2)) = A(0, A(0, A(1, 1))) = A(0, A(0, A(0, A(1, 0)))) = A(0, A(0, A(0, A(0, 1)))) = A(0, A(0, A(0, 1))) = A(0, A(0, 2)) = A(0, 3) = 4

常考排行

A(2,2) = 7

A(2,1) = 5

A(1,2) = 4

A(2,3)= 9

14. 求xⁿ，其中x,n是integer，且n ≧ 0 , write a recursive algo/ code

ans

$$ x^n= \begin{cases} 1&\text {if}(n==0) \ x \times x^{n-1}&\text {if} (n>0) \end{cases} $$

1
2
3
4
5
6

int exp(int x,int n){
if (n==0){return 1}
else{
return Exp(x,n-1)*x
}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

int foo(int x, int n){
    if(n%2==0){
        f=1;
    }else{
        f=x
    }
    if(n<2){
        return f;
    }
    return f*foo(x*x, n/2);
}

(i) 求foo(2,5)值

​

(ii)求foo(x,n)之功能

​ 求xⁿ

(iii)求foo(x,n)之Time Complexity

​ O(log_n)

河內塔(Towers of Hanai)

程式如下：

Hanoi(n,x,y,z);

n：盤數

x：來源

y：占存地

z：目的地

Step1 Hanoi(n-1,A,C,B);

Step2 Hanoi(1,A,B,C);

Step3 Hanoi(n-1,B,A,C);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

void Hanoi(int n,char A,Char B, Char C){
    if(n==1){
        printf("move disk %d from %c to %c \n",n,A,C);
    }else //n>1{
        Hanoi(n-1,A,C,B);
        printf("move disk %d from %c \n",n,A,C);
    	Hanoi(n-1,B,A,C);
    	
}
}

Permutation列印

將[a,b,c]以不同的排列組合印出來

如

abc

acb

bac

bca

cba

cab

有3!=6種寫法

以遞迴的概念來理解

原始碼的部分

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

void perm(char list[], int i, int n){
    //產生list[i]~list[n]之排列組合
    //i≦n
    if(i==n){ //代表遞迴中止
        for(j=1;j<=n;j++){
            printf(list[j]); // for each完後印出當時list的內容
        }
    }else{
        for(j=i;j<=n;j++){
            swap(list[i],list[j]); // list[j]做頭
            perm(list,i+1,n); //接(i+1)~(n)之perm
            swap(list[i],list[j]) // 還原成原本List的內容
        }
    }
}

實際演練

1
2
3
4

void main(){
    char list[3] = {a,b,c};
    Perm(list,1,3);
}

Performance Analysis(效能分析)

Algo/code之效能分析，主要分析兩點

1. Space
2. Time

Space(空間)需求分析

定義：令SP(P)代表Algo/Code P 之空間需求，則SP(P)= Fixed Space requirement + Variable Space Requirement

固定(Fixed)空間需求= Instruction (or Code) Space 意即你寫了幾行的程式+變數+常數空間 =C(mean Constant)

變動(Varialbe)空間需求=

主要有兩個來源

1. 若參數為結構型態(Array, Struct)且採用Call-By-Value參數傳遞方式(若是用Call-By-Address則也不是變動空間，因為只收一個Address的起始位址而已)
2. 遞迴(recursion)所需之stack space (堆疊空間)

因此主要的分析是在變動空間需求這邊

SP(P)= C + SP(i)

範例

求SP(i)=?

1
2
3
4
5
6
7
8

rsum(floot list[], int n){
    if(n!=0){
        return rsum(list,n-1)+list[n-1]
    }
    return list[0]
}
// 此外，假設 floot 佔4 bytes, int佔2bytes pointr(address)佔2bytes, List[]採用Call-by-address傳遞

Ans.SP(i)= Stack Space for recursion

如何計算?

• 每發生一次遞迴的呼叫(recusive call)，我們需要將

  • 參數值 list[] 佔2byte,因為是call by address。n 佔2bytes

  • 區域變數值無

  • Return Address一定有，題目說是2Byte

    Push 6 byte per recursive call

    又共發生n次recursive call(不含rsum(list,n))

因此Sp(i)= 6n bytes

Time(時間)需求分析

定義：令T(P)代表Algo,code P之時間需求，則T(P)=Development time(開發時間) + Execution Time

只注重/討論 Execution Time分析in DS/Algo課程

Execution Time之評量有兩個方法

1. Measurement(實際量度)
2. Analysis(分析、預估)\

本課程是採用Analysis方式，Analysis是以Algo/Code的指令執行總次數，作為分析Time之基礎

範例1. 不考慮指令之難易度

eq. 整數除法 a/b，浮點數除法 a/b視為一樣

原始code如下：

1
2
3
4

for(i=1i≦n;i++){
    a = a + b;
}
return a;

Then, 宣告一個Global變數，Count=0，在適當處加入Count++之敘述

1
2
3
4
5
6
7
8

for(i=1i≦n;i++){
    count++; //用來統計for做幾次
    a = a + b;
    count++ //統計 a=a+b做幾次
}
count ++;// for最後失敗的那一次，跳出for迴圈，實際上還是有做，因此要補上
conut++; //用來統計下面的return
return a;

T(P)= 指令執行次數之統計= 2n+1+1(每行被執行了幾次)=2n+2次

範例2. 考慮指令之難易程度

利用S/E (Steps per Execution每執行一次要花幾步，開心要怎麼定就怎麼定)區別指令難易程度 S/E高，代表較難

研究所的Time分析考型

1. 計算某行指令執行次數

2. Asymptotic漸進式 Notations符號定義、大小、定理

   (O,Ω,θ,o,w)

3. Recursive time function遞迴時間函數計算/求解 (eq. Honai Tower:T(n)+2*T(n-1)+1)

4. 給一遞迴演算法Recursive algo/code寫出Time Function求解

[006]

[複習] 數學公式

1. 等差數列

   公式：(首項＋尾項) * 項數 / 2

2. 等比數列

   公式：((最高項)^exp+1- (最低項))/公比-1

   範例：r⁰+r¹+r²+…+rⁿ = (rⁿ⁺¹-1) / r-1 = (rⁿ⁺¹ -r⁰)/(r-1)

3. 平方和公式：

   公式：(n(n+1)(2n+1))/6

   範例：1²+2²+3²+…+n²

4. Σ i^d 約莫是 n^d+1的多項式，d ≧之 int

5. Σ 1/i = log n (底數為2) (調和數列)

6. 排列組合 C幾取幾之計算

7. n!之相關式子

   1. n! = 1* 2 * … n ≦ n * n * n =nⁿ
   2. n! ≧ (n/2) ^n/2 (離散)
   3. Striling’s 公式
   4. n ! ≒ n ^n+(1/2) * e^-n, e 為自然對數之底

8. Σ i x 2 ⁱ 解法為

   令S= Σ i x 2 ⁱ，因此S= 1x2 +2x2 ² + 3x3³+…nx2ⁿ，兩邊同x2，為

   2S = 1x2² +2x2 ³ + 3x3⁴+…nx2ⁿ⁺¹

   然後兩邊相減，得出 S = -2¹-2²-2³-…-2ⁿ + n* 2 ⁿ⁺¹=經過很多推導之後=n*2ⁿ⁺¹-2ⁿ⁺¹+2

   

   Note：其他相似型也是如此求法

   

9. 對數系列(底數預設為2)

   

   

   

   

   

給Code，求某行指令執行次數或Big-Oh

例１

1
2
3
4
5
6

for i = 1 to n do
	for j = 1 to n do
		x++;

求x ++ 執行次數
ans :　ｎ＊ｎ次

例２

1
2
3
4
5
6
7

for i = 1 to n do
	for j = 1 to i do
		x++;

求x ++ 執行次數
ans :　(1+n)*n/2次

針對i++, i–之 Loop，可用級數求解

1
2
3
4
5
6

for i = 1 to n do
	for j = i to n do
		x++;

求x ++ 執行次數
ans :　n+(n-1)+(n-2)...+1 = (n+1)n/2

​

太基本，直接跳過

[007]

例題一

1
2
3
4
5

for i = 1 to n do
	for j = 1 to n*n
		if(j%i ==0) then
			for k = 1 to j do
				x++

若i=4時，x會加 4+8+12+16次，也就是4(1+2+3+4)，若i是n時，x會加

n(1+2+..+n)次 = n((1+n)*n)/2

Asymptotic Notations

漸進式符號

目的：表示時間函數之成長速率(Growth rate)之等級

符號種類：

1. Big-Oh：O
2. Omega：Ω
3. Theta：θ
4. Little-Oh：o
5. Little-Omega：ω

Big-Oh

小於等於

定義：F(n)= O(g(n)) iff(若且為若) exitst two postitive constatnts C and N0 such that f(n)≦ C* g(n)，對所有n≧N0

Note：Big-Oh代表理論之上限值(upper-Bound)

例：f(n)=5n²+8n-3，則f(n) = O(n²)

proof：可找到兩個正常數，C=6,N0=8，使得5n²+8n-3≦C*n²，所以f(n) = O(n²)

解法如下，通常會先取最大次項的項數，將他+1

例：f(n) = 3n²+8，則f(n)=O(n)是錯的

例：log(n!) = O (nLogn) ☆☆☆☆

ans

例

例：

1
2
3

for (i=1;i<=n;i++)
	for(j=1; j<=i; j*=2)
		x++;

求此Code之Time=O(?)

比較Growth rate等級之大小

例１：基本型

Growth rate：小 —> 大

例2：複雜型，請參閱課本

[007 1:24:00]

[008]

例題：

例題：

例三

Omega Ω

大於等於

定義：f(n)=Ω(g(n) iff exists two positive constants C and no. such that f(n)≧ c.g(n)，對所有大於N0的n而言

Note：Ω視為理論之下限值(low-bound)

例題：

例題

Theta θ

定義：f(n)= θ (g(n)) iff exists three positive constrants C1, C2, and N0, such that，C1*g(n) ≦ f(n) ≦C2*g(n)，對所有大於n0的n而言。

Note：

1. θ is more precise than O and Ω
2. f(n) = θ (n)
3. f(n) = O(g(n)) and f(n) = Ω(g(n))

例：

例：

Little-Oh：o

哲學意義在於絕對小於

o 就像小於

定義：f(n) = o (g(n)) iff 對於所有的C，存在n0，且C為正常數，使得f(n) ≦ C*g(n)，對於所有的n0皆大於n

大部分都考是非題

例：

Little-Omega：ω

哲學意義在於絕對大於

w 就像大於

定義：f(n) = ω (g(n)) iff 對於所有的C，存在n0，且C為正常數，使得f(n) > C*g(n)，對於所有的n0皆大於n

相關性質/關係

1. 反身性(Reflexive)：自己與自己之間的關係

   • f(n)=O(f(n))。f(n)≦1*f(n), ∀ n≧n0
   • f(n)=Ω(f(n))。
   • f(n)=θ(f(n))。

   這三者皆滿足反身性

   • f(n)=o(f(n)) 不成立，自己絕對不小於自己
   • f(n)=ω(f(n)) 不成立，自己也不大於自己

   這兩者不滿足反身性

2. 遞移性(Transitive)：若a R b, b R c, 則 a R c 也成立

   O, Ω. θ ,o, ω皆滿足遞移性

   • f(n)=O(g(n))且g(n)=O(h(n))，則f(n)=O(h(n))

3. 對稱性(Symmetric)：若aＲb成立，則bＲa也成立

   • 只有θ滿足這個性質(==)，其他均不滿足。
   • 即f(n)=θ(g(n))成立，則g(n)=θ(f(n))也會成立

4. 反對稱性(Asymmetric)：

   • 若f(n)=O(g(n))，則g(n)=Ω(f(n))為True

     f(n)≦c*g(n) => g(n)≧1/c*f(n)

   • 若f(n)=o(g(n))，則g(n)=ω(f(n))為True

綜合練習

[009 00:40:00]

例題一：

例題二：下列哪些是polynomial-Bounded(≦多項式時間等級)?

例題３

[010]

Recursive Time Function求解

1. 展開代入法
2. Master Theory
3. Extended Master Theory
4. Recursive Tree
5. [離散]特徵方程組
6. 猜測、近似法則

展開代入法

做苦工，通常沒問題，但缺點就是麻煩

例一：Tower Of Hanoi

1
2

T(n)= 2*T(n-1)+1, T(1)=1
求T(n)=? O=? 

Ans ：

例題二

例題三

例題四

例題五

例題六：陷阱題

例題七：好難，不懂

例題八

[010 1:30:00]

Master Theory

1. 若T(n)=a*T(n/b)+f(n),其中a≧1之constant，b是>1之constant，f(n)是positive-growth function，則可以使用此定理求出T(n)=θ(?)

2. 使用方式

   1. 先求出

   2. 與f(n)比較growth rate大小

Case1

Case2

Case3

例一：　

例二：

例三：

綜合練習：

Master Theory 之例外狀況

若遇到這種情況，則用Extended Master Theory

[011] 00:30:00

Extended Master Theory

以上面那一題為例，重新再解一次

例題一

例題二

綜合練習

更特殊之例外

[011 01:30:00]

Recursive Tree(遞迴樹)求解

就是結構化的展開帶入法啦

太抽象了。之後再來看

[012]

特徵方程

太抽象了。之後再來看

近似值

太抽象了。之後再來看

[013]

Ch3 Stack 與 Queue

Stack Def 、應用、製作

Stack Permutations

Infix, Postfix, Perfix 轉換與計算 ☆☆☆☆☆

Complier Parsing Using stack例子 ☆☆☆

Queue 定義、應用、“製作”、種類

Stack與Queue相互製作 ☆☆☆

Stack (堆疊)

定義：Stack 具有LIFO之性質，其Insert元素動作叫做PUSH，DELETE元素之動作叫做POP，且PUSH、POP動作發生在同一端，稱為TOP(頂端)

就像品客洋芋片罐一樣

例：對空Stack執行

PushA

PushB

PushC

POP

PushD

POP

POP

PushE

後，Stack內容為何?

AE

應用

• re-entrant routine

​ = pure code

​ = 可重複進入執行之程式

​ = 用在Utility program

• 走迷宮

• Palindrome(迴文)

  = 由左而右 Reading 等於由右而左

  = 若將一文字依序Push到Stack，再一一Pop輸出，等於加到Queue再一一刪除輸出，這一字串有什麼特性？Palindrome

Stack之製作

一個Stack之ADT(abstract data type)應提供下列Operations供外界呼叫/使用

Create,push,pop,isEmpty,isFull，有時候還會多一個TOP(只傳回TOP元素，但不刪除)

1. 利用Arrray製作Stack

   宣告

   1. S : Array [1..n] of items 或 [0 .. (n-1)]

   2. Top：Int = 0 ; 也有可能是-1 取決於你的Index怎麼訂

      1 2 3 4 5 6 7 8 9

      push (S, Item){ if(top==n)then return "S is Full"; else { top = top+1; S[top] = item; } }

      1 2 3 4 5 6 7 8 9 10

      pop(s){ if(top==0)then{ return "s is empty" } else { item = s[top]; top = top-1; return item; } }

2. 利用Link List製作Stack

   宣告

   1. Note Structure如下

      

      若以C語言來看

      1 2 3 4

      struct Node{ int Data; Struct Node *Next; }

   2. top : pointer = null;

      1 2 3 4 5 6

      Push(S,Item){ new(t); //向系統要求配置一個Node空間，讓t指標指向它 t -> Data = item; t -> Next = Top; Top = t; }

      1 2 3 4 5 6 7 8 9 10 11 12

      Pop(s){ if(top ==null){ return "S is empty" } else { t = top; item = top - > Data; Top = Top -> Next ; release(t); //回收T所指的Node Space return item; } }

Stack Permutation

定義：給予N個Data，規定須依序push入Stack，但在過程中，可執行任意合法的POP輸出資料，則所有Data之輸出排列組合，稱之

n個Data之Stack permutation數目 =

與下列問題同義：

1. n個node可形成的不同Binary Tree結構(ch5)
2. n個"(“與n個”)“的合法配對數目
3. (n+1)個Matrix相乘之可能乘法配對順序數目
4. 軌道問題

[014]

Infix,Postfix,Prefix 之轉換 (本章最常考)

先介紹這3個式子

1. Infix中序置式

   格式：Operand1 Operator Operand2 運算元 運算子 運算元

   eg. a+b, a*b, (a-b)/c

   缺點：對Compiler 處理Infix計算十分不方便，因為必須考慮Operator之間的優先權及結合性，故可能導致來回多次的掃描式子，才可求出結果，用白話文來講就是先乘除後加減的特性導致Compiler不方便

   eg: a+b*c^d ….

2. Postfix(後序式)

   格式：Operand1 operand 2 Operator

   ag ab+, ab*, ab>

   優點：Compilter處理Postfix計算，只須由左而右Scan一次

3. Perfix(前序式)

   格式：格式：OperatorOperand1 operand 2

   eg. +ab, *ab, /ab

   優點：同Postfix，但由右而左Scan

   缺點：中序轉前序須兩個Stack支持，但中序轉後序須1個Stack即可

Infix轉Postfix/Prefix計算題型

作法：使用括號法

以Infix轉PostFix為例

Steps

1. 對Infix加上完整的括號配對
2. Operator取代最近的右括號
3. 刪左括號，其他由左而右寫出即得Postfix

一般而言，Operator之優先權等參考下表

題目若有規定，則以題目為主

例一：Infix轉Postfix

1. a+b*c-d/e*f

   Ans. a+(b*c)-((d/e)*f))

   abc*+de/f*-

2. a*(b-c/d)^e*(f/g+h)

   Ans：abcd/-e&*fg&/f+*

   

3. (a+(b-c))^d^e*((f-g)/h)

   Ans: abc-+de^^fg-h/*

4. ~A and (B>C or D<E) or(~F)

   Ans: A~BC>DE<or And F~ or

例二：Infix 轉 Prefix

1. a*((b/c)-d)+e*f/g

   Ans: +*a-/bcd/*efg

2. a*(b-(c+d))/(e*f)^g

   Ans：/*a-b+cd^*efg

3. a+((b-c)/d)-e*f

   Ans：-+a/-bcd*ef

4. A or ((~B and C>D) and E>F)

   Ans. Or A and and ~ B > CD > EF

規定：優先權：括號＞＋＞÷＞－＞╳。＋，÷，－為右結合。×為左結合

1. (a*b)-c/d/e+f+g
2. (a/b/c)+d+(e*f*g)

Ans. (a*b)-c/d/e+f+g

Ans. +/a/bc+d**efg

例三：Postfix轉Infix

• 找出Postfix 樣板

op1 op2 operator

• 改為Infix (op1 operator op2)
• 刪除不必要之括號

1. AB+C*DE-FG+^-

   Ans. (A+B)*C-(D-E)^(F+G)

2. ab/c-de*+ac*-

   Ans. ((()))

[014 50:00:00]

先跳過，太複雜了，之後來看

[015]

先跳過，太複雜了，之後來看

[016]

Queue(佇列)☆☆☆

定義：具有FIFO(First-In-First-Out)先進先出。性質之有序串列

• Insert(enqueue)元素在rear(尾端)
• Delete(dequeue)元素在front(前端)

所以是發生在不同端

例：針對Empty Queue實施

enqueue(a)

enqueue(b)

enqueue(c)

dequeue

dequeue

enqueue(d)

enqueue(e)

dequeue

後，Queue內容為何?

Ans

d,e

應用：

1. 作業系統裡頭各式各樣的Queue eg: ready queue, waiting queue, i/o-device queue etc
2. Buffer(緩衝區)也採FIFO Queue 
3. 佇列理論：Simulation(模擬) System Performnace 評估
4. 圖形的BFS(Breadth First Seatch)
5. Binary Tree的Level-order Traversal
6. 日常生活的排隊行為

Queue 的製作

1. Queue 此一ADT必須提供下列運作供外界使用以及呼叫

   Create, Enqueue, Dequeue,InFull, Isempty 

2. 1. 利用Array製作
      1. Linear Array
      2. Circular Array(最多可利用(n-1)格 Space)
      3. Circular Array(最多可利用n格space)

Linear Array

缺點：若Rear ==n成立，並不一定代表Queue真的滿，若此時Front>0，代表仍有Front 個Space可用，但卻無法加入東西，代表有空間閒置、浪費

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class LinearStack {

    Integer[] array = new Integer[]{10};
    /**
     * 佇列前端
     */
    int front = 0;
    /**
     * 佇列尾端
     */
    int rear = 0;

    public void Enqueue(Integer[] array, Integer item) {
        if (rear == 10) { //問題點
            System.out.println("Queue已滿");
        } else {
            rear = rear + 1;
            array[rear] = item;
        }
    }

    public Integer Dequeue(Integer[] array) {
        if (rear == front) {
            System.out.println("Queue為空");
            return null;
        } else {
            front = front + 1;
            Integer integer = array[front];
            array[front] = 0;
            return integer;
        }
    }
}

分析：

• 解法一：一個直覺的做法當Rear==n，且front>0時，表示有front個空格所以可將[front+1]~[rear]這些元素往左移Front格，並設Rear=Rear-Front,Front=0; then 再作Enqueue。但缺點：導致Enqueue 平均Time從O(1)變成O(n)
• 解法二：利用Circular Array來作Queue

Circular Array(n-1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class CircularLinearStack {

    int queueSize = 10;
    Integer[] array = new Integer[]{queueSize};
    /**
     * 佇列前端
     */
    int front = 0;
    /**
     * 佇列尾端
     */
    int rear = 0;

    public void Enqueue(Integer[] array, Integer item) {
        rear = (rear + 1) % queueSize;
        if (front == rear) {
            System.out.println("Queue已滿");
            rear = (rear - 1) % queueSize;
        } else {
            array[rear] = item;
        }
    }

    public Integer Dequeue(Integer[] array) {
        if (front == rear) {
            System.out.println("Queue為空");
            return null;
        } else {
            front = (front + 1) % queueSize;
            Integer integer = array[front];
            array[front] = 0;
            return integer;
        }
    }
}

分析：

1. 最多只能利用(n-1)格Space即front 所指之格不用

   

2. 若硬用此格(Front)，則當front==rear成立時，無法區分Queue為空或Queue為滿。eg. 明明滿了，但卻無法刪除

3. 判斷Queue空，及Queue滿之條件式一樣

4. Enqueue 及 Dequeue 之 Time為O(1)

Circular Array (n)

宣告：多加一個tag:boolean 變數，初值為false

目的：協助rear, front判斷Queue空orQueue滿，當rear==front成立時

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

class CircularLinearStackBetter {


    int queueSize = 10;
    Integer[] array = new Integer[]{queueSize};
    /**
     * 佇列前端
     */
    int front = 0;
    /**
     * 佇列尾端
     */
    int rear = 0;

    /**
     * 
     */
    boolean tag = false;


    public void Enqueue(Integer[] array, Integer item) {
        if (front == rear & tag == true) {
            System.out.println("Queue已滿");
        } else {
            rear = (rear + 1) % queueSize;
            array[rear] = item;
            if (front == rear) {
                tag = true;
            }
        }
    }

    public Integer Dequeue(Integer[] array) {
        if (front == rear & tag == false) {
            System.out.println("Queue為空");
            return null;
        } else {
            front = (front + 1) % queueSize;
            Integer integer = array[front];
            array[front] = 0;
            if (front == rear) {
                tag = false;
            }
            return integer;
        }
    }

}

分析：

1. 最多可利用n格space
2. Enqueue及Dequeue之Time皆為O(1);
3. 與法二相比，此法Enqueue及Dequeue之時間會變長，因為每個運作中皆多了一條if額外測試，看tag值是否要改變

LinkedList作Queue

使用Single Link List

單向鏈結串列

[017 00:55:00]

跟Pointer有關，先跳過

Queue的種類

1. FIFO Queue （標準、內定、預設）

2. Priority Ｑueue(優先權佇列)

   Def: 不見得是FIFO order 而是刪除時是Delete-MAX或Delete-Min value元素

   eg. OS中運用頗多(CPU Schedule)

   製作Priority Queue 合適之Data structure- Heap

3. Double-ended Queue(雙邊佇列)

   Def: 此佇列之兩端(front, rear)皆可插入及刪除

   

4. Double-ended Priority Queue(雙邊優先權佇列)

   Def: 此Queue支持3個主要運作

   1. Insert
   2. Delete-Min
   3. Delete-MAx

   製作此Queue之最合適Data Structure有

   1. Min-Max Heap
   2. Deop
   3. SMMH

   高等樹會碰到

練習題：用Circular Array(法二)製作Queue，如何球出Queue中元素個數，使用Rear, front, n?

Ans. (Rear-Front+n)%n

Stack與Queue之相互製作

1. 利用stack製作(模擬)Queue兩個Stack✩✩✩✩✩

   1 2 3 4

   Enqueue(queue,item){ if(isFull(stack1)) then return "Queue已滿" else push(stack1,item) }

   1 2 3 4 5 6 7 8 9 10 11 12

   Dequeue(queue){ //由於Stack無法讓你Dequeue最底下的element出去，因此要借助第二個Stack來實現這件事情 if(IsEmpty(stack2))then if(IsEmpty(stack1)) then return "Queue空" else{ while(!IsEmpty(stack1))do{ x= pop(stack1); push(stack2,x); } } item = pop(stack2) return item; }

   

   Time分析：

   • 大部分case(T!=空) -> Time: O(1)
   • 少部分case(S!=空,T=空) -> Time:O(n)

   —> amortized cose:O(1)

2. 利用Queue製作Stack(假設是用Circular Array(法二)作的)

   1 2 3 4

   Push(stack, item){ if(isFull(queue)) then return "Stack滿" else Enqueue(queue) }

   1 2 3 4 5 6 7 8 9 10 11 12 13

   Pop(stack){ if (isEmpty(queue)) then return "Stack為空" else{ n = (rear-front+n) %n //求出元素個數 for(i=1 to (n-1)) do { x= dequeue(queue) enqueue(queue,x) } item = dequeue(queue) return item } }

Ch5 Tree And Binary Tree

Tree Def 相關術語

Tree的表示方法(4種)

Binary Tree之Def，與Tree不同比較

​