資料結構與C++程式設計進階 資料結構概論 講師：林業峻 CSIE, NTU 6/ 7, 2010.

Presentation on theme: "資料結構與C++程式設計進階 資料結構概論 講師：林業峻 CSIE, NTU 6/ 7, 2010."— Presentation transcript:

1 資料結構與C++程式設計進階 資料結構概論 講師：林業峻 CSIE, NTU 6/ 7, 2010

2 課程大綱 基礎複習 程式語言 資料內容與位置 指標與動態記憶體配置 結構 資料結構與演算法 陣列與串列 常見的資料結構與應用

3 程式設計 程式語言? 語法介於人與電腦之間，用來命令電腦 做事的一種語言! 寫程式的主要兩個動作： 人類: 中文, 英文, …
電腦: … 寫程式的主要兩個動作： 宣告資料儲存空間 & 操作資料 控制 (邏輯), 運算 (數學) 儲存資料

4 資料內容與位置 資料儲存的單位 資料的存取 儲存空間的產生 用來宣告一塊空間，儲存資料內容的單位：變數
用來宣告一塊空間，儲存資料位置的單位：指標 儲存很多相同型態的資料：陣列 儲存很多不同型態的資料：結構 (或C++的類別) 資料的存取 直接存取：變數、陣列、結構 (或C++的類別) 間接存取：指標 儲存空間的產生 靜態：程式一開始就產生 (宣告)　 動態：程式執行中跟系統要求而產生 使用指標取得動態記憶體配置之位置 儲存資料

5 練習 使用鍵盤輸入五個整數，印出平均於螢幕。 思考： 你用了什麼資料儲存單位？你用了什麼方式操作它們？為什麼你這 樣做？

6 指標的概念 用途：儲存另一個資料的位置，然後間接操作它 你要的資料在0x1000位置! int * 不知道名稱： 透過指標!
位置：(不重要) 名稱：p 間接找到資料並使用 int 70 資料內容 名稱：a 位置：0x1000 有名稱可用：直接用a 我要使用70那個整數…

7 指標的重要應用 動態記憶體配置： 當程式執行到一半，發現它需要一塊記憶體空間來存放資料, 才向系統索取一塊記憶體空間。
當程式執行到一半，發現它需要一塊記憶體空間來存放資料, 才向系統索取一塊記憶體空間。 當此記憶體空間用不到時，也可隨時將之釋放供其它程式使 用。 使用指標做記憶體配置： p = (int*)malloc(sizeof(int)*3); 位置：0x3000 系統：0x3000這位置有你要的! 名稱：(無) int [0] [1] [2] 不能直接用,只好間接用 0x3000 int * 名稱：p 位置：(不重要) 我突然需要使用三個整數當陣列用!

8 動態記憶體配置 描述指令之意義

9 練習 使用鍵盤輸入N個整數，印出平均於螢幕。(N為 正整數，由執行程式的人自訂)
思考： 你用了什麼資料儲存單位？你用了什麼方式操作它們？為什麼你這 樣做？

10 結構 通常一個簡單之變數或陣列不足以用來儲存複雜 之記錄。
結構允許使用者宣告資料實體將不同形式之元素 儲存一起。是一種由使用者自訂之資料型態。 struct 結構名稱標籤 { 資料型態 資料變數元素1; 資料型態 資料變數元素2; ‧‧‧‧‧‧‧‧ }; 

11 結構陣列 將結構宣告成陣列 缺點 Person Person Person Person Person Name Height Weight
#include<stdio.h> struct _Person { char Name[64]; int Height; int Weight; }; typedef struct _Person Person; int main() Person p[5]; return 0; } 將結構宣告成陣列 常用來管理大量資料 缺點 刪除與插入造成資料移動頻繁 浪費不必要之記憶體 陣列長度為常數, 可能會不夠用 Person Person Person Person Person Name Height Weight p [0] [1] [2] [3] [4]

12 練習 寫一個可以管理使用者(人數上限5人)的姓名、身 高、體重資料之程式，功能如下： (1) 新增一位使用者資料
練習  寫一個可以管理使用者(人數上限5人)的姓名、身 高、體重資料之程式，功能如下： (1) 新增一位使用者資料 (2) 查詢某位使用者資料 (輸入編號) (3) 修改某位使用者資料 (輸入編號) (4) 列出所有使用者資料 思考： 你用了什麼資料儲存單位？你用了什麼方式操作它們？為什 麼你這樣做？ 思考2： 你所使用的方式，如果要做插入或刪除資料會有效率嗎？

13 課程大綱 基礎複習 程式語言 資料內容與位置 指標與動態記憶體配置 結構 資料結構與演算法 陣列與串列 常見的資料結構與應用

14 資料結構與演算法 資料儲存方式資料結構 程式行為演算法 你所選用的資料儲存方式將影響你程式的複雜度與效率！ 資料如何擺放 空間夠不夠用
資料結構與演算法  資料儲存方式資料結構 資料如何擺放 空間夠不夠用 會不會浪費空間 程式行為演算法 資料如何儲存、搜尋、刪除 執行速度 你所選用的資料儲存方式將影響你程式的複雜度與效率！

15 資料結構 了解資料結構的三個重點 應用：這個結構可以用在什麼地方 結構：這個結構用什麼方式來描述 程式：這個結構如何用程式來操作

16 思考 你想設計一個通訊錄程式, 用來紀錄不同人的資料( 姓名, 身高, 體重), 資料該如何儲存?程式該如何設 計?
思考 你想設計一個通訊錄程式, 用來紀錄不同人的資料( 姓名, 身高, 體重), 資料該如何儲存?程式該如何設 計? 結構陣列? (資料可能浪費或不夠用) 結構指標+動態記憶體配置? (請輸入你的好友個數???) 串列!?

17 課程大綱 基礎複習 程式語言 資料內容與位置 指標與動態記憶體配置 結構 資料結構與演算法 陣列與串列 常見的資料結構與應用

18 串列的使用 結構中帶有一個用來指向下一個資料的指標 用途： 與陣列做比較： Person Person Person t3 t3 p [0]
(1) 不知道資料個數時 (2) 資料常需要隨時插入或刪除, 為了效率考量時 與陣列做比較： 結構陣列 (靜態配置) 鏈結串列 (動態配置) Person Person Person t3 t3 p [0] [1] [2] *Person Person Person Person NULL (空指標) p (節點1) (節點2) (節點3)

19 練習 觀察並試著解釋以下程式中指標的操作 #include<stdio.h> struct _Person {
char Name[64]; int Height; int Weight; }; typedef struct _Person Person; int main() Person p = {"Joe", 180, 80}; Person *p1, *p2; p1 = &p; p2 = p1; p1->Height = 190; p2->Weight = 90; printf("Name: %s\n", p.Name); printf("Height: %d\n", p.Height); printf("Weight: %d\n", p.Weight); return 0; }

20 練習 使用串列輸入三個使用者的姓名、身高、體重資 料並印出 (chap01_ex1.c) *Person Person Person
struct _Person { char Name[64]; int Height; int Weight; struct _Person *next; }; typedef struct _Person Person; *Person Person Person Person NULL (空指標) next next next p (節點1) (節點2) (節點3)

21 課程大綱 基礎複習 程式語言 資料內容與位置 指標與動態記憶體配置 結構 資料結構與演算法 陣列與串列 常見的資料結構與應用

22 本課程將介紹的資料結構 為了解決各式各樣的問題，你會使用不同的資料 結構來處理，以增加效能減少複雜度 常見的資料結構 演算法
鏈結串列(Linked List) 堆疊(Stack) 佇列(Queue) 樹狀結構(Tree) 圖形結構(Graph) 演算法 新增 (Insert) 刪除 (Delete) 搜尋 (Search) 排序 (Sort) A B C D E F Example: 樹狀結構 A C B D F E

23 單向鏈結串列 … 用途： 單向鏈結串列之結構如下圖所示 head 鏈結起點 鏈結終點 (1) 不知道資料個數時
(2) 資料常需要隨時插入或刪除, 為了效率考量時 單向鏈結串列之結構如下圖所示 head：指向串列前端之指標 head … NULL 鏈結起點 鏈結終點

24 鏈結串列－通訊錄程式實作 … 我們可以使用鏈結串列來實作個有效率且能有效 利用記憶體空間之通訊錄程式 head 鏈結起點 鏈結終點
Andy 0919.. Joe 0958.. Mary 0937.. … NULL 鏈結起點 鏈結終點

25 堆疊與佇列 堆疊(Stack) 佇列(Queue) 用途：後進先出(LIFO)之資料特性 例子：發撲克牌、走迷宮
用途：先進先出(FIFO)之資料特性 例子：排隊問題、資源使用順序控制

26 堆疊－自動走迷宮程式 使用堆疊結構實作走迷宮問題 走法: 每次都把目前位置存到堆疊, 然後走下一步 下一步順序: 上,下,左,右
無路可走: 從堆疊中取出上一位置, 看看有沒路走 1 1 1 1 1 1 1 1 1 1 出口 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 入口 1 1 1 1 1 1 1 1 1 1

27 佇列－排隊與插隊問題 優先佇列 (Priority Queues)
許多排隊場合不一定是先到先贏, 例如: 搭飛機時排隊進飛機 艙, 會先請頭等艙先進入, 在依會員等集進入, 這時的排隊應該 有優先順序問題 下圖會員分三等級(A,B,C級), A級優先權較高, B第 二, C最低, 如何完成這個特殊的排隊問題？

28 樹狀結構 「樹」（Tree） 用途：資料大量且常需要做搜索時
是一種模擬現實生活中樹幹和樹枝的資料結構，屬於一種階 層架構的非線性資料結構，例如：家族族譜, 決策模型 用途：資料大量且常需要做搜索時

29 樹狀結構：二元搜尋樹 如何利用樹狀結構實作一個快速的搜尋法?
以下的數都只有左右兩個分支, 左分支的數字一定 比右分支大, 在一堆數字當中, 如果你要找20這個 數字, 該如何找? 為什麼比較快呢? 試著跟一般陣列或鏈結串列比較 10 5 20 1 5 8 10 15 20 30 1 8 15 30

30 圖形結構 「圖形」(Graph) 是由有限的「頂點」(Vertex)和 邊線所組成。通常使用小圓圈代表頂點，頂點之 間的連線代表「邊線」(Edge) 用途： (1) 資料間關係較為複雜時 (2) 找各種最佳問題之解答 例子： 車站系統實作 最短路徑問題 最低成本問題

31 圖形結構－最短路徑問題 計算圖形內某一個頂點到另一個圖形間的「最短 路徑」(Shortest Paths)。 共195km

32 圖形結構－最低成本問題 有五個村莊, 之間沒有任何道路, 如果你想造一些 路, 讓一個村裝有辦法到任一個村莊, 如何打造「 最低成本」(Minimum Cost)的路呢? 8萬 2萬 6萬 5萬 3萬 10萬 4萬 15萬

33 圖形結構－最低成本問題 使用最小成本擴張樹(Minimum-cost Spanning Trees)來解此問題, 得到如下結果： 2萬 6萬
5萬 3萬 共16萬元