C高級(jí)程序應(yīng)用鏈表課件

1、第十章 C高級(jí)程序應(yīng)用鏈表*10.1鏈表的基本概念10.2單向鏈表10.3雙向鏈表10.4應(yīng)用舉例鏈表是具有相同數(shù)據(jù)類(lèi)型的對(duì)象的有序集合。其對(duì)象的類(lèi)型為結(jié)構(gòu)類(lèi)型，鏈表中的對(duì)象一般稱為“結(jié)點(diǎn)”。每個(gè)結(jié)點(diǎn)在內(nèi)存中的存放位置是隨機(jī)的?？梢允沁B續(xù)的，也可以是不連續(xù)的，每一個(gè)結(jié)點(diǎn)對(duì)象通過(guò)其鏈指針成員和集合中的另一個(gè)結(jié)點(diǎn)關(guān)聯(lián)。由此，好像一個(gè)“鏈”一樣將整個(gè)鏈表集合中的所有結(jié)點(diǎn)對(duì)象連起來(lái)，所以稱為“鏈表”。鏈表的實(shí)現(xiàn)涉及到動(dòng)態(tài)內(nèi)存分配和引用自身的結(jié)構(gòu)類(lèi)型。10.1 鏈表的基本概念10.1.1 動(dòng)態(tài)內(nèi)存分配函數(shù)：動(dòng)態(tài)內(nèi)存分配是指在程序運(yùn)行過(guò)程中，根據(jù)需要而分配內(nèi)存空間的方式。在C系統(tǒng)的函數(shù)庫(kù)中提供了動(dòng)態(tài)分配和

2、釋放內(nèi)存空間的函數(shù)，詳見(jiàn)教材P269例10.1在C+編譯系統(tǒng)中則使用C+內(nèi)置的操作符new和delete來(lái)動(dòng)態(tài)分配和釋放內(nèi)存空間。當(dāng)我們使用操作符new在內(nèi)存中動(dòng)態(tài)申請(qǐng)一片存儲(chǔ)空間時(shí)，它實(shí)際上做了兩件事：獲得一塊內(nèi)存空間和返回該片內(nèi)存空間的首地址。new和delete操作符是配對(duì)使用的。詳見(jiàn)教材P27110.1 鏈表的基本概念10.1.2 用于動(dòng)態(tài)內(nèi)存分配的操作符new和delete操作符：例10.2引用自身的結(jié)構(gòu)類(lèi)型 是一種特殊的結(jié)構(gòu)類(lèi)型，即該結(jié)構(gòu)類(lèi)型的成員中包含有指向該結(jié)構(gòu)類(lèi)型自身的指針成員。10.1 鏈表的基本概念10.1.3 引用自身的結(jié)構(gòu)類(lèi)型：struct TeacherNode D

3、atatype data; / 數(shù)據(jù)成員 TeacherNode *next; / 指向結(jié)構(gòu)類(lèi)型自身的指針 ;該結(jié)構(gòu)中定義了兩個(gè)成員，第一個(gè)是數(shù)據(jù)成員data；其類(lèi)型為Datatype（Datatype可以是C支持的任何數(shù)據(jù)類(lèi)型），用來(lái)存放一個(gè)TeacherNode結(jié)構(gòu)類(lèi)型的對(duì)象的基本信息；第二個(gè)是指針成員next，這是指向TeacherNode自身的指針。引用自身的結(jié)構(gòu)類(lèi)型 是一種特殊的結(jié)構(gòu)類(lèi)型，即該結(jié)構(gòu)類(lèi)型的成員中包含有指向該結(jié)構(gòu)類(lèi)型自身的指針成員。10.1 鏈表的基本概念10.1.3 引用自身的結(jié)構(gòu)類(lèi)型（續(xù)）：struct TeacherNode Datatype data; / 數(shù)據(jù)成

4、員 TeacherNode *next; / 指向結(jié)構(gòu)類(lèi)型自身的指針 ;由于每一個(gè)該類(lèi)型的結(jié)構(gòu)變量都可以通過(guò)其next成員找到另一個(gè)該類(lèi)型的結(jié)構(gòu)變量，因此，使用引用自身的結(jié)構(gòu)類(lèi)型，可以將存放在內(nèi)存中隨機(jī)位置的結(jié)構(gòu)變量從邏輯上鏈接起來(lái)，在邏輯上形成一個(gè)有序的集合鏈表。通常把next成員稱為鏈指針。單向鏈表 是由稱為結(jié)點(diǎn)的對(duì)象構(gòu)成的。每個(gè)結(jié)點(diǎn)，除需要存儲(chǔ)數(shù)據(jù)值外還需要存儲(chǔ)一個(gè)直接指向相應(yīng)后繼結(jié)點(diǎn)存放位置的指針信息(即后繼結(jié)點(diǎn)的內(nèi)存存儲(chǔ)地址)。所以，結(jié)點(diǎn)是含有數(shù)據(jù)成員和鏈指針成員的結(jié)構(gòu)類(lèi)型。鏈指針用來(lái)指向后繼結(jié)點(diǎn)(即存放指向結(jié)點(diǎn)的地址)。10.2 單向鏈表10.2.1 單向鏈表的建立：由于訪問(wèn)單向鏈

5、表中的任一結(jié)點(diǎn)都必須是從鏈表的頭開(kāi)始，所以，我們?cè)O(shè)置一個(gè)專(zhuān)門(mén)的指針變量用來(lái)指向鏈表的開(kāi)頭，這個(gè)專(zhuān)門(mén)的指針變量稱為表頭指針（head）。實(shí)際中，為了操作方便，鏈表一般都會(huì)設(shè)一個(gè)頭結(jié)點(diǎn)，將表頭指針head指向這個(gè)頭結(jié)點(diǎn)。頭結(jié)點(diǎn)的的數(shù)據(jù)域是沒(méi)有用處的。頭結(jié)點(diǎn)的后繼所指向的結(jié)點(diǎn)才是鏈表的第一個(gè)結(jié)點(diǎn)。圖10-2-1 單向鏈表結(jié)構(gòu)頭結(jié)點(diǎn)head空表NULLhead頭結(jié)點(diǎn)指針數(shù)據(jù)NULL數(shù)據(jù)指針例10.310.2 單向鏈表10.2.2 單向鏈表中結(jié)點(diǎn)的遍歷：void browseTeacherList(TeacherList teacherList) TeacherNode *p = teacherList

6、-next; / 指向當(dāng)前教師結(jié)點(diǎn)的指針int n = 0; / 教師人數(shù)while(p != NULL) / 循環(huán)后移指針，至p指向最后一個(gè)教師為止 writelnTeacher(p-data); / 輸出當(dāng)前教師信息 p = p-next; / 指針后移 n+; 10.2 單向鏈表10.2.3 單向鏈表中結(jié)點(diǎn)的插入：圖10-2-4在單向鏈表中插入一個(gè)結(jié)點(diǎn)（b）插入后（a）插入前101101101103NULLpqs101101101103NULLpq101102headheadTeacherNode *s = NULL; s = new TeacherNode; s-data = xxxx

7、; s-next = q; p-next = s; 10.2 單向鏈表10.2.4 單向鏈表中結(jié)點(diǎn)的刪除：pre-next = p-next; / 或pre-next=pre-next-next;delete p; / 釋放當(dāng)前結(jié)點(diǎn)指針p所指向的空間圖10-2-5 在單向鏈表中刪除一個(gè)結(jié)點(diǎn)（a）刪除節(jié)點(diǎn)前xxxxxxprexxxxxxNULLpre（b）刪除節(jié)點(diǎn)后xxxxxxxxxxxxNULLppheadhead10.2 單向鏈表10.2.5 由單向鏈表構(gòu)成循環(huán)鏈表：圖10-2-6 單向循環(huán)鏈表datadatadatarear如果將單向鏈表的最后一個(gè)結(jié)點(diǎn)的鏈指針指向單向鏈表的第一個(gè)結(jié)點(diǎn)，就構(gòu)

8、成了一個(gè)單向循環(huán)鏈表，如圖10-2-6所示從循環(huán)鏈表中任意給定結(jié)點(diǎn)出發(fā)，都可以訪問(wèn)到循環(huán)鏈表中的其它結(jié)點(diǎn)。在一個(gè)循環(huán)鏈表中，通常要定義一個(gè)指向尾結(jié)點(diǎn)的指針rear（表尾指針）。指針rear的作用類(lèi)似于單鏈表中的表頭指針head。10.3 雙向鏈表雙向鏈表是指鏈表中的每個(gè)結(jié)點(diǎn)共有兩個(gè)指針域：一個(gè)是向后進(jìn)行鏈接的指針，另一個(gè)是向前進(jìn)行鏈接的指針。這樣，一個(gè)結(jié)點(diǎn)至少有三個(gè)域，即數(shù)據(jù)域（data）、前指針域（prior）和后指針域（next）。圖10-3-1表示了雙向鏈表的結(jié)構(gòu)。圖10-3-1 雙向鏈表headdataNULLenddatadataNULL使用雙向鏈表的主要優(yōu)點(diǎn)是： 能從兩個(gè)方向?qū)︽湵?/p>

9、進(jìn)行操作。不僅簡(jiǎn)化了排序，而且使用戶能從兩個(gè)方向檢索鏈表。 由于可以從正向或反向讀鏈表。當(dāng)其中一個(gè)鏈被破壞時(shí)，可以使用另一個(gè)鏈重建鏈表。10.3 雙向鏈表（續(xù)）雙向鏈表的結(jié)點(diǎn)類(lèi)型：圖10-3-1 雙向鏈表headdataNULLenddatadataNULLstruct TeacherNode TeacherInfo data; / 數(shù)據(jù)域 TeacherNode *next; / 后繼指針 TeacherNode *prior; / 前驅(qū)指針;10.3 雙向鏈表（續(xù)）在雙向鏈表中，將new指向的新結(jié)點(diǎn)插入到雙向鏈表遍歷指針p指向結(jié)點(diǎn)之后。操作過(guò)程如圖10-3-2所示new-next = p-next; new-prior = pp-next-prior = new; p-next = new圖10-3-2 新結(jié)點(diǎn)插入到指定結(jié)點(diǎn)前后的示意圖（a）插入結(jié)點(diǎn)前headdataNULLenddatadataNULL（b）插入結(jié)點(diǎn)后