重點 資料結構之選定會影響演算法 選擇對的資料結構讓您上天堂 程式

第一章 資料結構簡介

大綱 1.1 前言 1.2 演算法 (Algorithm) 1.3 演算法的效率評估 1.4 資料表示法 1.5 C語言重點回顧 1.4.1 常見的幾種進制表示法 1.4.2 整數資料表示 1.4.3 實數表示法1.4.4 文數資料表示法 1.4.4.1 ASCII碼 1.4.4.2 EBCDIC碼 1.5 C語言重點回顧 1.5.1 迴圈控制敘 述 1.5.2 條件判斷結 構 1.6 常見的資料結構 習題

1.1 前言 資料(Data):要讓電腦處理的原始內容 資訊(Information):電腦處理過後所產生的有意義訊息 圖1.1 資料與資訊的關係

1.1 前言 – 續 利用電腦來處理資料有兩種方式： 利用事先設計好的套裝軟體來進行資料處理的動作,使用者所扮演的角色是應用程式使用者 (Application User). 例如微軟的Word，我們就可以透過它來處理文書資料. 要自行撰寫程式來解決給定的問題,使用者所扮演的角色是程式撰寫者 (Programmer).

1.1 前言 – 續 圖1.2 解決問題的流程

1.1 前言 – 續 先了解問題的定義並找出要處理的資料 將解題的程序也就是演算法(Algorithm)找出來並詳細的加以列出 挑選一個合適的程式語言(Programming Language)來撰寫程式，在本書中我們是以C語言來撰寫程式 將寫好的程式透過編譯或直譯的方式來轉換成可執行的機器碼(Executable Machine Code) 如果解題的程序是正確的，則我們所希望獲得的資訊會在機器碼執行後正確地產生

1.1 前言 – 續 資料結構(Data Structure)與整個利用電 腦來處理問題的關係究竟為何? 資料結構是我們將解題程序撰寫成對應程式 的過程中用來表示處理資料的方法 表示相同資料的方法並不是唯一的，但是若 能妥善利用好的資料結構來表示處理的資料， 通常能夠使得程式執行的效率提升或是減少 程式所需的變數儲存空間

Example … 以電腦記錄(&後續處理)班上40位同學的姓名、學號、身高與地址資訊 方法 1: 方法 2: Char name0[10], name2[10], … name39[10] Char ID0[12], ID1[12], … ID39[12] Int Height0, height1, … height39 … 方法 2: Char name[40][10]; Char ID[40][12]; Int height[40];

Example … (續) 方法 3 上述不同資料表示法, 對程式撰寫是否有影響? Struct student_record { char name[10]; char ID[12]; int height; char address[80]; } Struct student_record student[40]; 上述不同資料表示法, 對程式撰寫是否有影響?

1.2 演算法 演算法是為了解決一個給定的問題，經過問 題的分析與了解後所撰寫出來的一系列解題 程序 一個演算法必須滿足下列五個條件： 輸入資料：一個演算法所須之輸入資料可有可無 輸出資料：一個演算法至少必須有一個輸出結果 有限性：亦即須能在有限個步驟之內解決問題 明確性：即每一個步驟必須條理分明，意義清楚 有效性：整個解題程序執行完後必須能夠解決給 定的問題。也就是能夠輸出對應的資訊

1.2 演算法 – 續 描述一個演算法常見的方式有兩種： 虛擬語言(Pseudo Language):是一種用來描述解題程序的語法，並不是屬於真正的程式語言而是一種接近英文語法的描述方式 流程圖(Flow Chart)的繪製:利用事先定義好的一些圖形與流程控制圖示來描述整個問題的解題程序

1.2 演算法 – 續 表1.1 虛擬語言的介紹

1.2 演算法 – 續 範例一 計算梯形的面積，其中梯形的上底、下底與高度是由使用者所輸入。而梯形面積的計算公式為 (上底+下底)*高度/2。

1.2 演算法 – 續 範例一之程式

1.2 演算法 – 續 範例二 讀入三位學生的資料結構成績，並計算其 平均分數。要算出三位學生的平均分數可 先算出成績的總和後除以人數。

1.2 演算法 – 續 範例二之程式

1.2 演算法 – 續 範例三 讀入三個數值A，B，C，並找出其中最大數值。

1.2 演算法 – 續 範例三之程式

1.2 演算法 – 續 範例四 利用數學的描述法，求n階層(n!)之值，可以 寫成：n! = n * (n-1)*… * 1，0! = 1

1.2 演算法 – 續 範例四之程式

資料結構的基礎-圖例 策略或方法是指如何選擇最恰當的資料結構，並且將這些資料轉換成有用的資訊，轉換資料的方法就是「演算法」（Algorithms），如下圖所示： 演算法和資料結構的關係非常的密切，因為程式使用的演算法和資料結構都會影響程式的執行效率，換句話說，演算法加上資料結構就等於程式，如下所示： 「演算法」 + 「資料結構」 = 「程式」

範例 1 : 找出最大數 main() { int largest = 0; if (25 > largest) largest = 25; if (30 > largest) largest = 30; if (18 > largest) largest = 18; if (7 > largest) largest = 7; if (10 > largest) largest = 10; printf("最大數為%d", largest); }

範例 2 : 找出最大數 01:main() 02:{ 03: int i; 04: int list[5] = {25, 30, 18, 7, 10}; 05: int largest = 0; 06: for(i = 0; i < 5; i++) 07: if (list[i] > largest) largest = list[i]; 08: printf("最大數為%d", largest); 09:}

Difference between the above two? How data structure affects your program? Which one is better? Why? Which one would be potentially faster? Why? Let’s review some basics before answering the above questions …

The Von Neumann Model & Memory Access Q1: How fast is your CPU? Q2: How is your DIMM’s access latency? Q3: What conclusion can be drawn from them? Q4: Where does your program stored? Q5: Cache?

CPU vs Memory Speed Clock cycle of a 2GHz CPU 1 / (2 * 109) = 0.5 ns In case 4 clocks per instruction  2 ns How about int sum = i + j; DDR2-800 (clock freq=400MHz) 1 / (400 * 106) = 2.5 ns In case CL = 6  6 * 2.5 ns = 15 ns For a WORD access Cache

From: Pastry, https://www.mobile01.com/topicdetail.php?f=489&t=1162932

1.3 演算法的效率評估 演算法的效率指的是計算根據該演算法 所撰寫的程式在經過編譯後實際執行所 需的時間 有可能因為程式編譯的過程或是電腦設 備的差異使得效率分析會因電腦的軟硬 體不同而有不同的結果

1 .3 演算法的效率評估 – 續 除了實際衡量程式的執行時間外，另外一種效益評估的方式則是透過分析個別程式的複雜度(Complexity) 通常程式的複雜度分析可以分成兩大類： 時間複雜度(Time Complexity) 空間複雜度(Space Complexity)

1 .3 演算法的效率評估 – 續 為了簡化時間複雜度的分析，我們只著重於程式必須執行的指令個數而不去考慮個別指令實際執行所需的時間 範例

1 .3 演算法的效率評估 – 續 理論上我們通常將一個程式P的時間複雜度表示成T(P)的形式，而T(P)記錄了程式的實體特性n的成長速率

1 .3 演算法的效率評估 – 續 常見的時間複雜度函數可能為下列形式： T(P)=c,為一常數多項式 T(P)=a*n+b,其中 a>0,b>0為一個線性多項式 T(P)=a*n2+b*n+c,其中 a>0為一個二次方多項式 T(P)=a*n3+b*n2+c*n+d,其中 a>0為一個三次方多 項式 T(P)=an,其中 a>0為一個指數多項式 T(P)=a*logn+b,其中 a>0為一個對數多項式

1 .3 演算法的效率評估 – 續 當輸入資料的個數n值我們可以得到下列關係 : logn < n < nlogn < n2 < n3 < 2n 表1.2 常見的多項式成長速率比較

1 .3 演算法的效率評估 – 續 一個程式P的空間複雜度(Space Complexity)包含固定的空間需求與變動的空間需求兩個部分 固定的空間需求包含了程式在編譯時期(Compile Time)所產生的空間需求 變動空間需求包含了動態記憶體要求(Dynamic Memory Allocation)所配置的空間，以及遞迴函數執行時所需要用來儲存活動紀錄(Activation Record)的執行時堆疊空間(Run Time Stack)

1 .3 演算法的效率評估 – 續 通常我們會利用S(P)來表示一個程式P所需的空間需求，而S(P)=c+SP(I) SP(I)則表示程式P針對特定的輸入資料集合I (Instance)所需的變動空間需求

1 .4 資料表示法 數位化資料可分成兩類： 常見的數值表示法可以分成兩大類:整數與實數 數值資料 : 可進行加、減、乘、除等算術運算的資料 文數資料 : 不能拿來運算的資料 常見的數值表示法可以分成兩大類:整數與實數 整數與實數最大的差別是在於實數能夠表示包含小數的數值資料

1 .4.1 常見的幾種進制表示法 表1.3 不同進制間的轉換範例

1 .4.2 整數資料表示 – 續 常見的整數表示法有兩類： 利用二進制來表示整數資料的做法中，常見的表示方式有三種 : 1 .4.2 整數資料表示 – 續 常見的整數表示法有兩類： 無正負號之整數(Unsigned Integer) : 只能表示非負的數值，而其能表示的數字 範圍跟儲存空間的大小有關 整數(Integer) : 包含了正整數、零與負整數 利用二進制來表示整數資料的做法中，常見的表示方式有三種 : 符號帶大小(Sign Significant)表示法 1的補數(1’s Complement)表示法 2的補數(2’s Complement)表示法

1 .4.2 整數資料表示 – 續 符號帶大小的表示法: 是利用一個位元來記錄數值的正負號資訊(Sign)，通常表示負整數時其對應的符號位元為1，反之 則為0 1的補數表示法: 將數值之二進制中的0變為1且將1變為0 2的補數表示法: 將此數值對應的1的補數計算出後再將結果加1 就可得到其對應2的補數的結果 電腦內部用來表示一般整數的方法是利用2的補數

1 .4.2 整數資料表示 – 續 表1.4 利用四個位元表示一般的整數

1 .4.2 整數資料表示 – 續 表1.5 整數的種類與能夠表示的數值範圍

1 .4.2 整數資料表示 – 續 範例

1 .4.3 實數表示法 實數的組成包含三個部分：符號位元(Sign Bit)、指數部分(Exponent)與假數部分(Mantissa) 符號位元則是用來表示正負號，而指數部分與假數部分是用來紀錄實數在轉換成二進制科學表示法後的資訊 圖1.3 浮點數值的三個組成部分

1 .4.3 實數表示法 – 續 要表示一個給定的實數時，我們會先將其轉換成對應的二進制表示法，接著再轉換成科學表示法。也就是轉換成 (-1)s x m x 2e的形式 m的數值代表給定的實數的假數部分的數值，將m的小數點後所有其他的數值紀錄到假數的部分即可完成假數部分的處理

1 .4.3 實數表示法 – 續 e的數值代表給定的實數的指數次方的數值，大多數的電腦對於指數數值是以e+2t-1的方式來表示之，其中t代表指數部份的總位元數 為了要利用t 個位元來表示所有可能的狀況通常採用的方式是透過平移原始的指數數值來處理 表1.6 利用八個位元紀錄指數數值之平移處理

圖1.4 IEEE Standard 754之32位元短浮點式表示法 1 .4.3 實數表示法 – 續 實數資料在電腦中有兩種常見的表示法，即短浮點式(Short Floating Point Format)及長浮點式(Long Floating Point Format) 圖1.4 IEEE Standard 754之32位元短浮點式表示法

圖1.4 IEEE Standard 754之64位元常浮點式表示法 1 .4.3 實數表示法 – 續 b0 b1 b62 b63 b51 b52 正/負 指數部分 假數部分 圖1.4 IEEE Standard 754之64位元常浮點式表示法

1 .4. 4 文數資料表示法 文數資料(Alphanumeric Data)是包含文字(Letters)、符號(Symbols )與數字(Digits)的資料，所有不可做算術運算的資料皆屬此類 目前電腦中最常使用的文數資料表示法有兩種: ASCII碼 (American Standard Code for Information Interchange,美國標準資訊交換碼)，目前市面上個人電腦通用的資料表示法 EBCDIC碼(Extended Binary Coded Decimal Interchange Code) ，EBCDIC碼是IBM 、UNIVAC 等一些大型電腦所採用的編碼法

1 .4 .4 .1 ASCII碼 ASCII碼是由美國國家標準局(ANSI)所制定的 早期的ASCII碼由七個位元來表示一個字元(Character) ，總共可以表示128種不同的符號，其中包含大小寫英文字母、阿拉伯數字、標點符號與四則運算符號等鍵盤上常看到的按鍵 剩餘的組合可用來表示一些特殊符號及螢幕與列表機的控制符號 隨著電腦軟硬體的快速發展，七位元的ASCII碼被擴充成八位元的ASCII碼 圖1.7 七位元ASCII之排列方式

1 .4 .4 .1 ASCII碼 – 續 表1.7 七位元ASCII 碼一覽表

1 .4 .4 .1 ASCII碼 – 續 表1.8 部分8-位元的ASCII碼

1 .4 .4 .2 EBCDIC碼 由八個位元來表示一個符號，總共可表示256種不同的字元 表1.9 EBCDIC 碼一覽表

1 .5 C語言重點回顧 1.5.1介紹C語言常見的迴圈控制結構，內容包含回顧 for, while與 do while等迴圈控制結構 1.5.2介紹C語言的條件判斷結構， 內容包含if, if else與switch case等條件判斷結構

1 .5 .1 迴圈控制敘述 for的迴圈控制結構，其對應的C語言語法如下所列：

1 .5 .1 迴圈控制敘述 – 續

1 .5 .1 迴圈控制敘述 – 續 while的迴圈控制結構，其對應的C語言語法如下所列：

1 .5 .1 迴圈控制敘述 – 續

1 .5 .1 迴圈控制敘述 – 續 do while 的迴圈控制結構與前面所介紹的for 與 while 迴圈的最大差別在於前面兩個迴圈控制結構是 do while迴圈控制結構至少會執行一次迴圈內所有指令 do while的迴圈控制結構，其對應的C語言語法如下所列：

1 .5 .1 迴圈控制敘述 – 續

1 .5 .2 條件判斷結構 if的條件判斷結構，其對應的C語言語法如下所列： 1 .5 .2 條件判斷結構 if的條件判斷結構，其對應的C語言語法如下所列： 蜂巢式if (Nested if)的使用，也就是在一個 if 的條件判斷敘述中可以包含另一個 if 的條件判斷敘述

1 .5 .2 條件判斷結構 – 續 if else的條件判斷結構，它與if 條件判斷的差別在於當判斷條件成立或是不成立時都有對應的指令必須要執行，其對應的C語言語法如下所列：

1 .5 .2 條件判斷結構 – 續 if else (Nested if else)條件判斷結構，其對應的C語言語法如下所列：

1 .5 .2 條件判斷結構 – 續 switch case 的條件判斷結構，其對應的C語言語法如下所列：

1 .5 .2 條件判斷結構 – 續 在switch的條件判斷敘述其結果必須是整數資料或是字元資料

1 .5 .2 條件判斷結構 – 續

1 .6 常見的資料結構 陣列(Array) : 電影院中的坐椅、排列整齊的椅子 1 .6 常見的資料結構 陣列(Array) : 電影院中的坐椅、排列整齊的椅子 鏈結串列(Linked List) : 在鐵軌上南來北往的火車，每一部火車將一節一節的車廂從頭到尾串連在一起，而連接各節車廂的連接器就是此鏈結串列的鏈結 堆疊(Stack) : 到西餐廳享用歐式自助餐時，餐盤一個一個依照由下而上的順序整齊的擺置 佇列(Queue) : 中午用餐時間，我們經常會看到學校自助餐前面大排長龍，等待享用午餐的排隊人潮 樹狀結構(Tree Structure) : 電腦內部檔案儲存的結構，或是歷屆學生的家族族譜，羽球比賽的單循環賽程資料等

1 .6 常見的資料結構 – 續 圖形及網路 : 全台灣省的省道與高速公路路線圖、環島鐵路的路線圖、長榮航空公司的全球航線圖 1 .6 常見的資料結構 – 續 圖形及網路 : 全台灣省的省道與高速公路路線圖、環島鐵路的路線圖、長榮航空公司的全球航線圖 排序(Sorting) : 書店中常見的英漢字典，其中的所有英文字均是按照字母的大小次序排列的 赫序函數(Hashing Function) : 利用一種技術將特定的資料例如某一個學生的學號輸入，就可以馬上找出他家裡的電話號碼、地址，… 檔案系統(File System):想要查詢某一位同學的個人資料，我們可以到檔案室中很快地找出某一位同學的學籍資料表來

1 .6 常見的資料結構 – 續 學習資料結構的最主要目的 : 能妥善利用電腦將所有個人手邊的資料有系統地安排，建立資料與資料彼此間的關係，仿照日常生活中人、事、物常見的各式各樣結構，將所有的資料做最適當的安排、儲存，以方便資料的更新及存取

1 .6 常見的資料結構 – 續 資料結構的應用主要包含下列幾個重要主題： 有效地儲存給定的各種不同資料 1 .6 常見的資料結構 – 續 資料結構的應用主要包含下列幾個重要主題： 有效地儲存給定的各種不同資料 不同的資料結構表示法和其相關演算法的探討 改進現存演算法的效率，使程式的執行速度趨於更快 利用合適的使用者介面來建構資料存取方法、資料儲存之結構和資料儲存之媒體 資料處理之各種技巧，比如：排序、搜尋、合併、更新、分配等演算法探討 利用結構化程式設計的概念來提升軟體開發之生產力

1 .6 常見的資料結構 – 續 用來挑選資料結構的條件： 給定的資料量是相當大或是很小 1 .6 常見的資料結構 – 續 用來挑選資料結構的條件： 給定的資料量是相當大或是很小 資料是否需要常常增刪或更新，也就判斷資料是靜態的或是動態的？ 資料在實際應用上被擷取次數之頻率 可用以儲存資料的記憶體容量有多大 實際應用時可以接受的資料擷取時間 使用某種資料結構是否很容易編寫對應程式碼