Presentation is loading. Please wait.

Presentation is loading. Please wait.

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

Similar presentations


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萬元


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

Similar presentations


Ads by Google