1、,本次課開(kāi)始學(xué)習(xí)鏈表啦！,教案,主要內(nèi)容,鏈表概述 單鏈表及其基本結(jié)構(gòu) 單向循環(huán)鏈表、雙向鏈表及雙向循環(huán)鏈表 單鏈表的建立和輸出,鏈表概述,鏈表的引入 數(shù)組（靜態(tài)存儲(chǔ)方法）：占用連續(xù)的內(nèi)存區(qū)域。 動(dòng)態(tài)存儲(chǔ)方法：申請(qǐng)分配的內(nèi)存空間之間不一定是連續(xù)的。 鏈表的分類 根據(jù)指針域的不同和結(jié)點(diǎn)構(gòu)造鏈的方法不同，主要有單鏈表、單向循環(huán)鏈表、雙向鏈表和雙向循環(huán)鏈表等。每一種又有帶附加頭結(jié)點(diǎn)結(jié)構(gòu)和不帶附加頭結(jié)點(diǎn)結(jié)

2、構(gòu)兩種。,,通過(guò)鏈表建立聯(lián)系,返回,單鏈表的概念,單鏈表：是用“一根有方向的鏈”把各數(shù)據(jù)元素聯(lián)系起來(lái)的一種數(shù)據(jù)結(jié)構(gòu)。 結(jié)點(diǎn)是單鏈表的基本存儲(chǔ)單元，一個(gè)結(jié)點(diǎn)與一個(gè)數(shù)據(jù)元素相對(duì)應(yīng)。 每個(gè)結(jié)點(diǎn)內(nèi)部都是內(nèi)存中一塊連續(xù)的存儲(chǔ)空間，各個(gè)結(jié)點(diǎn)之間的存儲(chǔ)空間是不一定連續(xù)的。,結(jié)點(diǎn),,單鏈表的基本結(jié)構(gòu)（定義結(jié)點(diǎn)）,結(jié)點(diǎn)定義 定義一個(gè)結(jié)構(gòu)體，用來(lái)保存單鏈表結(jié)點(diǎn)的數(shù)據(jù)，其中含有一個(gè)特殊的成員，該成員定義為指向該結(jié)構(gòu)體本身的指針變量。

3、 結(jié)點(diǎn)示意圖：,,,指針域,數(shù)據(jù)域,單鏈表結(jié)點(diǎn)定義舉例,例如：定義學(xué)生結(jié)點(diǎn),,千萬(wàn)不可少哦,,,數(shù)據(jù)域 data,指針域 link,單鏈表的基本結(jié)構(gòu)（結(jié)點(diǎn)之間建立聯(lián)系）,結(jié)點(diǎn)與結(jié)點(diǎn)之間聯(lián)系的建立 用指針域建立結(jié)點(diǎn)之間的聯(lián)系。 方法是：在第一個(gè)結(jié)點(diǎn)的指針域內(nèi)存入第二個(gè)結(jié)點(diǎn)的首地址，在第二個(gè)結(jié)點(diǎn)的指針域內(nèi)又存放第三個(gè)結(jié)點(diǎn)的首地址，依次類推，直到最后一個(gè)結(jié)點(diǎn)。最后一個(gè)結(jié)點(diǎn)因無(wú)后續(xù)結(jié)點(diǎn)連接，其指針域可賦值為NULL。,單鏈表示

4、意圖,單鏈表（含有附加頭結(jié)點(diǎn)）的示意圖,單鏈表（不含附加頭結(jié)點(diǎn)）的示意圖,思考：① Head的作用？② 兩者的不同？,單鏈表的特點(diǎn)：對(duì)于任意結(jié)點(diǎn)，能方便地找到后繼結(jié)點(diǎn)。,判斷單鏈表是否為空的條件,有附加頭結(jié)點(diǎn)的單鏈表 單鏈表為空的條件：head->next == NULL 無(wú)附加頭結(jié)點(diǎn)的單鏈表 單鏈表為空的條件：head == NULL,單鏈表舉例,【例】建立有兩個(gè)學(xué)生數(shù)據(jù)的單鏈表。 源程序,運(yùn)行程序(

5、7_1),返回,看源程序(7_1),單向循環(huán)鏈表,結(jié)點(diǎn)定義 與單鏈表相同。 結(jié)點(diǎn)之間關(guān)系示意圖 判斷單向循環(huán)鏈表（含有附加頭結(jié)點(diǎn)）為空的條件 head->next == head 特點(diǎn) 從任意一個(gè)結(jié)點(diǎn)出發(fā)，都能找到其余所有結(jié)點(diǎn)。,雙向鏈表,結(jié)點(diǎn)定義 結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)描述struct node{ struct node *prior; 數(shù)據(jù)域定義；

6、struct node *next;};,雙向鏈表,結(jié)點(diǎn)之間關(guān)系示意圖 判斷雙向鏈表（含有附加頭結(jié)點(diǎn)）為空的條件 head->next == NULL 特點(diǎn) 對(duì)于任意結(jié)點(diǎn)，能方便地找到后繼結(jié)點(diǎn)和前驅(qū)結(jié)點(diǎn)。,雙向循環(huán)鏈表,結(jié)點(diǎn)定義 與雙向鏈表相同。 結(jié)點(diǎn)之間關(guān)系示意圖 判斷雙向循環(huán)鏈表（含有附加頭結(jié)點(diǎn)）為空的條件 head->next == head 或

7、head->prior==head 特點(diǎn) 可以很方便地進(jìn)行插入和刪除操作。,返回,回顧,在第5章中，學(xué)習(xí)了用順序存儲(chǔ)方式實(shí)現(xiàn)線性表的各種操作。 除了順序存儲(chǔ)方式外，還可以用鏈接存儲(chǔ)方式實(shí)現(xiàn)線性表。 下面以單鏈表為例進(jìn)行介紹。,單鏈表的建立和輸出,【例7-5】用單鏈表實(shí)現(xiàn)線性表的建立和輸出。假定線性表中每個(gè)數(shù)據(jù)元素只含一個(gè)成員data，并且數(shù)據(jù)類型為整型。 分析（1）因?yàn)榫€性表中每個(gè)數(shù)據(jù)元素只含一個(gè)整型成員data，所

8、以結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)可以定義如下：typedef struct node{ int data; struct node *next;}Node;（2）采用有附加結(jié)點(diǎn)的單鏈表。（3）主函數(shù)中完成鏈表的初始化、建立鏈表、輸出鏈表，最后還要釋放結(jié)點(diǎn)空間。所以共有4個(gè)模塊構(gòu)成。,,,,,主函數(shù)模塊,【例7-5】用單鏈表實(shí)現(xiàn)線性表的建立和輸出。假定線性表中每個(gè)數(shù)據(jù)元素只含一個(gè)成員data，并且數(shù)據(jù)類型為整型。 主函數(shù)流程

9、圖 源程序,運(yùn)行程序(7_2),看源程序(7_2),建立鏈表模塊,【例7-5】用單鏈表實(shí)現(xiàn)線性表的建立和輸出。假定線性表中每個(gè)數(shù)據(jù)元素只含一個(gè)成員data，并且數(shù)據(jù)類型為整型。 分析 建立鏈表就是在程序執(zhí)行過(guò)程中，通過(guò)循環(huán)不斷地開(kāi)辟結(jié)點(diǎn)空間和輸入結(jié)點(diǎn)數(shù)據(jù)，并建立起結(jié)點(diǎn)之間前后相鏈的關(guān)系。（1）為簡(jiǎn)單起見(jiàn)，我們采用總是把新結(jié)點(diǎn)鏈到鏈尾的方法來(lái)建立結(jié)點(diǎn)之間的鏈接關(guān)系。（2）當(dāng)輸入的數(shù)據(jù)為0時(shí)，結(jié)束循環(huán)。,建立鏈表模塊,【例

10、7-5】用單鏈表實(shí)現(xiàn)線性表的建立和輸出。假定線性表中每個(gè)數(shù)據(jù)元素只含一個(gè)成員data，并且數(shù)據(jù)類型為整型。 建立鏈表流程圖 源程序,運(yùn)行程序(7_2),看源程序(7_2),輸出鏈表模塊,【例7-5】用單鏈表實(shí)現(xiàn)線性表的建立和輸出。假定線性表中每個(gè)數(shù)據(jù)元素只含一個(gè)成員data，并且數(shù)據(jù)類型為整型。 分析 對(duì)鏈表結(jié)點(diǎn)的輸出，只需從第一個(gè)結(jié)點(diǎn)開(kāi)始，依次遍歷鏈表，直到最后一個(gè)結(jié)點(diǎn)為止。,輸出鏈表模塊,【例7-5】用單鏈表實(shí)現(xiàn)線性表的

11、建立和輸出。假定線性表中每個(gè)數(shù)據(jù)元素只含一個(gè)成員data，并且數(shù)據(jù)類型為整型。 輸出鏈表流程圖 源程序,運(yùn)行程序(7_2),看源程序(7_2),釋放結(jié)點(diǎn)空間模塊,【例7-5】用單鏈表實(shí)現(xiàn)線性表的建立和輸出。假定線性表中每個(gè)數(shù)據(jù)元素只含一個(gè)成員data，并且數(shù)據(jù)類型為整型。 分析 釋放鏈表的內(nèi)存空間與輸出鏈表類似，只需從附加頭結(jié)點(diǎn)開(kāi)始，依次釋放結(jié)點(diǎn)空間，直到最后一個(gè)結(jié)點(diǎn)為止。,釋放結(jié)點(diǎn)空間模塊,【例7-5】用單鏈表實(shí)現(xiàn)線性

12、表的建立和輸出。假定線性表中每個(gè)數(shù)據(jù)元素只含一個(gè)成員data，并且數(shù)據(jù)類型為整型。 釋放結(jié)點(diǎn)空間流程圖 源程序,運(yùn)行程序(7_2),看源程序(7_2),思考：不用附加頭結(jié)點(diǎn)，任何修改？(7_3),任務(wù)相關(guān)部分,在本章任務(wù)中，要實(shí)現(xiàn)功能“新建學(xué)生數(shù)據(jù)”和“輸出學(xué)生數(shù)據(jù)”，實(shí)際上就是建立鏈表和輸出鏈表，只不過(guò)線性表的每個(gè)元素有多個(gè)成員而已。 結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)可以定義如下：typedef struct student{ in

13、t no; /* 學(xué)號(hào) */ char name[ 20 ]; /* 姓名 */ int score[ 5 ]; /* 學(xué)生各門課程的成績(jī) */

14、int total; /* 總分 */ float average; /* 平均分 */ struct student *next; /* 指向下一個(gè)結(jié)點(diǎn)的指針 */} Student;