第4章鏈結串列l(wèi)inkedlists(已修改)
2024-10-27 13:36 本頁面
【正文】 第 4章 鏈結串列（ Linked Lists） ? 41 動態(tài)記憶體配置 ? 42 鏈結串列的基礎 ? 43 單向鏈結串列 ? 44 環(huán)狀鏈結串列 ? 45 雙向鏈結串列 ? 46 鏈結串列的應用 多項式表示法 41 動態(tài)記憶體配置 說明 ? 動態(tài)記憶體配置不同於陣列的靜態(tài)記憶體配置是在編譯階段就配置記憶體空間，動態(tài)記憶體配置是等到執(zhí)行階段，才向作業(yè)系統(tǒng)要求配置所需的記憶體空間，可以讓程式設計者靈活運用程式所需的記憶體空間。 ? 在 C語言 標頭檔的標準函式庫提供兩個函數(shù)： malloc()和 free()，可以配置和釋放程式所需的記憶體空間。 41 動態(tài)記憶體配置 malloc() malloc()函數(shù)：配置記憶體空間 ? C語言的程式碼可以呼叫 malloc()函數(shù)向作業(yè)系統(tǒng)取得一塊可用的記憶體空間，函數(shù)的語法，如下所示： fp = (資料型態(tài) *) malloc(sizeof(資料型態(tài) ))。 ? 上述語法因為函數(shù)傳回 void通用型指標，所以需要加上型態(tài)迫換，將函數(shù)傳回的指標轉換成指定資料型態(tài)的指標， sizeof運算子可以計算指定資料型態(tài)的大小。例如：配置一個浮點數(shù)變數(shù)的記憶空間，如下所示： fp = (float *) malloc(sizeof(float))。 struct test *score。 score=(struct test *) malloc(num*sizeof(struct test))。 41 動態(tài)記憶體配置 free() free()函數(shù)：釋放配置的記憶體空間 ? free()函數(shù)可以釋放 malloc()函數(shù)配置的記憶體空間，例如：指標 fp是一個指向malloc()函數(shù)傳回的浮點數(shù)記憶體空間的指標，呼叫 free()函數(shù)釋放這塊記憶體，如下所示： free(fp)。 ? 上述程式碼的指標 fp可以是 float浮點數(shù)指標，也可以是 malloc()函數(shù)傳回的其它資料型態(tài)指標、陣列或結構指標。 42 鏈結串列的基礎 說明 ? 「有序串列」（ Ordered List）或稱為「線性串列」（ Linear List）是一種元素間擁有順序的集合，如下所示： (a0, a1, a2, … , an)， ai， 0 = i = n ? 上述集合是一個線性串列，如果是空的線性串列，表示串列中沒有任何元素，是使用 ( )空括號表示。 42 鏈結串列的基礎 範例 ? 一些線性串列的範例，如下所示： ?英文的月份： ( Jan, Feb, March, … , Oct, Nov, Dec )。 ?英文的星期： ( Mon, Tue, Wed, Thu, Fri, Sat, Sun )。 ?撲克牌的點數(shù)： ( A, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K )。 ?樓層： ( B2, B1, 1, 2, 3, 4, 5, 6 )。 ?生肖： ( 鼠 , 牛 , 虎 , …… , 狗 , 豬 )。 42 鏈結串列的基礎 運算 ? 線性串列的相關運算，如下所示： ?length()： 取得線性串列的長度。 ?get()： 存取線性串列的第 i個元素。 ?search()： 從左到右，或從右到左走訪線性串列。 ?delete()： 在線性串列第 i個元素刪除元素。 ?insert()： 在線性串列第 i個元素插入元素。 42 鏈結串列的基礎 使用陣列實作線性串列 42 鏈結串列的基礎 使用陣列實作線性串列 (問題 ) ? 複雜的新增與刪除運算： 在新增或刪除名單時，因為陣列儲存的是循序且連續(xù)資料，所以在陣列中需要搬移大量元素，才能滿足同縣巿位在同一區(qū)段。例如：在桃園巿新增江小魚，則王小美、李光明和周星星都需要依序往後搬移 1個元素，才能將江小魚插入，同理，刪除王大毛時，之後的所有元素也需要往前搬移。 ? 浪費記憶體空間： 因為並不知道名單有多少位，所以需要宣告一個很大的結構陣列來儲存名單，如果最後只使用到幾個元素，就會造成大量記憶體空間的閒置。 42 鏈結串列的基礎 使用鏈結串列實作線性串列 ? 「鏈結串列」（ Linked Lists）是一種實作線性串列的資料結構。在現(xiàn)實生活中，鏈結串列如同火車掛車廂以線性方式將車廂連結起來，每個車廂是鏈結串列的節(jié)點（ Nodes），儲存線性串列的資料，車廂和車廂之間的鏈結，就是節(jié)點間的鏈結（ Link）。如下圖所示： 42 鏈結串列的基礎 使用鏈結串列實作線性串列 (實作
教學課件相關推薦
鄂ICP備17016276號-1