单向链结串列的走访课件.pptVIP

第4章鏈結串列（LinkedLists）??????4-6鏈結串列的應用表示法

4-1動態記憶體配置-明?動態記憶體配置執行階段，才向作業系統要求配置所需的記憶體空間，用程式所需的?在stdlib函式提供兩個函數：malloc()和free()，可以配置和釋放程式所需的記憶體空間

4-1動態記憶體配置-malloc()malloc()函數：配置記憶體空間?malloc()函數向作業系統取得一塊可用的記憶體空間數的語fp=(資料型態*)malloc(sizeof(資料型態));通用型指標，所以將函數傳回的指標轉換成指定資料型態的指標子可以計?算資料型態的大點數變數的記憶空間，fp=(float*)malloc(sizeof(float));structtest*score;score=(structtest*)malloc(num*sizeof(structtest));

4-1動態記憶體配置-free()free()函數：釋放配置的記憶體空間?指標fp是一個指向malloc()函數傳回的浮點數記憶體空間的指標釋放這塊記憶體，free(fp);?上述程式碼的指標指標，也可以是m它資料型態指標、

4-2鏈結串列的基礎-明?有序串列OrderedList線性串列LinearList是一種元素間擁有順序的集合(a0,a1,a2,…,an)，ai，0=i=n列，如果是空的線性串列表示串列中沒有任何元素是使用()空括號表示?

4-2鏈結串列的基礎-範例範例?(Jan,Feb,March,…,Oct,Nov,Dec)(Mon,Tue,Wed,Thu,Fri,Sat,Sun)7,8,9,,Q,K)。–樓層：(B2,B1,1,–生肖：(鼠,牛,虎

4-2鏈結串列的基礎-運算?線性串列的相關運算–length()素。–get()右到左走訪線性–search()除元素。–delete()–insert()：在線性串

4-2鏈結串列的基礎-使用陣列實作線性串列

4-2鏈結串列的基礎-使用陣列實作線性串列(問題)?複雜的新增與刪除運算新增或刪除資料需要搬移大量元素滿足同新增江星都需要依將江小魚插入，同所有元需要?浪費記憶體空間：因位，所以需要宣告一個很大的結構陣列來儲存名單，如果最後只使用到幾個元素，就會造成大量記憶體空間的閒置

4-2鏈結串列的基礎-使用鏈結串列實作線性串列?鏈結串列LinkedLists如同火車掛車廂以線性方式將車廂連結起來，每個車廂是鏈結串列的節點（Nodes），儲存線性串列的資料，車廂和車廂之間的鏈結，就是節點間的鏈結（Link）。下圖所示

4-2鏈結串列的基礎-使用鏈結串列實作線性串列(實作)宣告一個結構作為節來鏈結其它節點點所?點含指標即可解決結構陣列實作上浪費記憶體的問題郵寄名單，筆者名單的資料，?郵鏈結串

4-3單向鏈結串列???點

4-3單向鏈結串列-明?單向鏈結串列節點指標指向同一個方向從前一個節點指向下一個節點，然後最後1個節點指向NULL所以稱為單向：

4-3單向鏈結串列-標頭檔01:/*程式範例:Ch4-3.h*/02:structNode{03:intdata;/*Node節點結構*//*結構變數宣告*/04:structNode*next;/*指向下一個節點*/05:};06:typedefstructNodeLNode;/*串列節點的新型態*/07:typedefLNode*List;08:Listfirst=NULL;/*串列的新型態*//*串列的開頭指標*/09:/*抽象資料型態的操作函數宣告*/10:externvoidcreatList(intlen,int*array);11:externintisListEmpty();12:externvoidprintList();13:externListsearchNode(intd);14:externintdeleteNode(Listptr);15:externvoidinsertNode(Listptr,intd);

4-3-1建立和走訪單向鏈結串列-建立()建立單向鏈結串列?createList()函數使用for迴圈將取得的陣列建立成串列節點圈，就在所示：for(i=0;ilen;i++){newnode=