第7次課--鏈表的概念、鏈表的建立和輸出

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

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

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

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

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

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

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

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

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

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

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

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

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

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