以動態記憶體配置鏈結串列.pptVIP

第十四章動態記憶體配置與鏈結串列 認識動態記憶體配置 認識鏈結串列 了解循序串列與鏈結串列的優缺點 以C語言實作鏈結串列 記憶體配置的方式 記憶體配置： 靜態配置： 在編譯時期（compile-time），編譯器便會配置記憶空間給變數 缺點為記憶體使用較無彈性，可能會配置過多或過少 動態配置： 在程式執行時期（run-time），才向系統要求記憶空間 可以有效的配置記憶體 動態記憶體配置 C 是利用malloc() 函數進行動態記憶體的配置 設定與取得記憶體的內容 第 k 個記憶空間的內容可藉由*(ptr+k-1)來取得 歸還記憶空間 把它動態記憶體歸還給系統時，可用free() 函數 動態記憶體實例 一 動態記憶體實例 二 (1/2) 以 malloc() 配置記憶空間給結構變數 動態記憶體實例 二 (2/2) 串列 (List) 有次序的資料可組成一個串列（list） 串列可分為循序串列與鏈結串列 循序串列 ：存放串列的記憶體是循序的（即有先後次序） 優點：存取方便 缺點：增加或刪除節點較麻煩，易造成記憶空間不足或浪費 鏈結串列 ：以指標將存放串列的記憶體鏈結起來 優點：記憶點配置較有彈性 缺點：搜尋某個元素時，可能會較為耗時 以陣列實作鏈結串列 以陣列實作鏈結串列，資料的移動會較為頻繁 鏈結串列的表示法 (1/2) 節點包含有兩個成員 第一個成員是該節點所儲存的資料 第二個成員是一個指標，它指向了下一個節點的位址 鏈結串列的表示法 (2/2) 鏈結串列是由許多節點鏈結而成 每一個節點均有一個指標指向下一個節點 鏈結串列可由下圖來表示 以結構來表示鏈結串列 以結構表示鏈結串列： 每一個節點有兩個成員 第一個成員用來存放資料 (data) 第二個成員用來存儲指向下一個節點的指標 (next) 鏈結串列的實作範例 (1/3) 下面的範例建立了如下圖的鏈結串列： 鏈結串列的實作範例 (2/3) 鏈結串列的實作範例 (3/3) prog14_3 的執行結果 以動態記憶體配置鏈結串列 (1/3) 以動態記憶體配置鏈結串列的範例 以動態記憶體配置鏈結串列 (2/3) 以動態記憶體配置鏈結串列 (3/3) 鏈結串列的基本操作 (1/4) 鏈結串列相關運算的標頭檔 鏈結串列的基本操作 (2/4) 以陣列arr的元素建立鏈結串列： 鏈結串列的基本操作 (3/4) 串列資料列印函數： 鏈結串列的基本操作 (4/4) 記憶體空間釋放函數： 鏈結串列的實例 以陣列 {14,27,32,46} 建立鏈結串列： 節點的搜尋 要插入一個節點，必須先知道節點的位址 searchNode() 函數可用來找尋節點的位址 節點的插入 insertNode可在節點之後插入一個新的節點 實例應用：節點搜尋與插入 節點搜尋與插入的範例： 節點的刪除 (1/2) 在刪除節點時，會有下列三種情況發生： 如果串列為空串列時，則不必進行刪除的動作 如果刪除的是第一個節點 － 把指標first指向下一個節點，然後刪除第一個節點： 節點的刪除 (2/2) 刪除節點的第三種情況： 刪除第一個節點以外的其它節點 － 將指標指向要刪除之節點的下一個節點，然後釋放記憶空間 節點的刪除－deleteNode() 函數 刪除節點的範例 (1/2) 刪除節點的範例： 刪除節點的範例 (2/2) * * 14.1 動態記憶體配置 指標變數=(指標變數所指向的型態 *) malloc(所需的記憶空間) malloc() 的語法 將malloc() 所傳回的位址強制轉換成指標變數所指向的型態 int *ptr; /* 宣告指向整數的指標ptr */ ptr=(int *) malloc(12); /* 較不好的寫法 */ ptr=(int *) malloc(3*sizeof(int)); /* 較好的寫法 */ 配置可存放3個整數的記憶空間： 14.1 動態記憶體配置 int *ptr; ptr=(int *) malloc(3*sizeof(int)); *ptr=12; /* 將ptr所指向的第1個記憶空間設值為12 */; *(ptr+1)=35; /* 將第2個記憶空間設值為35 */ *(ptr+2)=140; /* 將第3個記憶空間設值為140 */ 14.1 動態記憶體配置 free(指標變數); /* 釋放由指標變數所指向的記憶空間 */ free() 的語法 記憶體洩漏（memory leakage） 沒有用free() 歸還記憶空間 記憶空間分割失敗（segmentation fault）