課程名稱數(shù)據(jù)結(jié)構(gòu)07

1、課程名稱 數(shù)據(jù)結(jié)構(gòu)07 授課題目鏈?zhǔn)骄€性結(jié)構(gòu) 環(huán)行鏈表授課日期2003 年 10 月 8 日授課班級(jí)生物醫(yī)學(xué)工程授課時(shí)數(shù)4授課方式理論課授課重點(diǎn)、難點(diǎn)1. 掌握鏈?zhǔn)奖淼亩x與特點(diǎn)2. 掌握鏈?zhǔn)綏５牟僮饕c(diǎn)3. 掌握鏈?zhǔn)疥?duì)列的操作要點(diǎn)4. 掌握向前鏈表的幾種常用操作5. 掌握環(huán)行鏈表的操作要點(diǎn)授課內(nèi)容、教具與時(shí)間分配授課內(nèi)容、教具與時(shí)間分配2.2 幾種鏈接表2.2.0 鏈接式線性表一、 定義：如果線性表中邏輯上相鄰的元素在計(jì)算機(jī)中物理存儲(chǔ)位置不一定相鄰，而是用指針相鏈接的結(jié)點(diǎn)序列，這種線性表稱為鏈接式線性表。 優(yōu)點(diǎn)：1. 當(dāng)進(jìn)行插入或刪除操作時(shí)，避免了大量元素的移動(dòng)。 2. 若事先不容易估計(jì)表長(zhǎng)

2、時(shí)，鏈接式線性表可節(jié)省內(nèi)存。 二、鏈接式線性表的結(jié)點(diǎn)成員 struct node xxxx info link 數(shù)據(jù)域 鏈域 char info; 三、申請(qǐng)結(jié)點(diǎn)和釋放結(jié)點(diǎn) struct node *link; typedef struct node NODE; NODE *ptr;ptr=(NODE *)mallc(sizeof(NODE);/*ptr=NULL 表示棧滿，即內(nèi)存用完，很少發(fā)生*/free(ptr); /*調(diào)用 I/O 庫(kù)函數(shù) free ，ptr 是指向待釋放結(jié)點(diǎn)的指針*/四、主要操作：不同的結(jié)構(gòu)有不同的操作2.2.1 鏈接式棧 p38 top一、 圖解 實(shí)際上就是 p17 的

3、單向鏈表，僅畫法不同。 當(dāng) top=NULL，稱為?？?。初值 top=NULL。 棧頂指針 二、入棧操作：1. 申請(qǐng)結(jié)點(diǎn) ptr=(NODE *)malloc(sizeof(NODE) 初值為 （圖解） 2. 數(shù)據(jù)域賦值 ptr->info=arg 3. 結(jié)點(diǎn)鏈入棧 ptr->link=top : 4. 提升棧頂指針 top=ptr :三、出棧操作：1. 保留原棧頂指針 ptr=top : （圖解） 2. 下降棧頂指針 top=ptr->link 3. 提取原棧頂數(shù)據(jù) var=ptr->info 4. 釋放結(jié)點(diǎn) free(ptr) 四、對(duì)p.38 lstack.c 的說(shuō)

4、明 1. #include "llist" 編譯預(yù)處理。 2. main() 中有二個(gè)循環(huán)語(yǔ)句 入棧：當(dāng)遇到 'n' ，循環(huán)終止?？刹豢紤]棧滿，即內(nèi)存用完。 出棧：當(dāng)棧空，top=NULL ，循環(huán)終止。3. 定義外部指針變量 top ，供 push(arg) 和 pop() 共享。 NODE *top=NULL; /*賦初值*/4. 入棧函數(shù) push(arg) 執(zhí)行入棧操作。5. 出棧函數(shù) pop() 執(zhí)行出棧操作。6. 執(zhí)行 輸入：abcde 輸出：edcba 。2.2.2 鏈接式排隊(duì)(隊(duì)列） p39一、定義 隊(duì)首 隊(duì)尾 同 p30二、主要操作：入隊(duì)、出

5、隊(duì)和判斷隊(duì)列空。三、實(shí)現(xiàn)方法： 1. 鏈接式排隊(duì) 圖解 front rear 隊(duì)首指針 front 指向隊(duì)首 (順序式隊(duì)列有隊(duì)首標(biāo)志,是指向隊(duì)首前的一個(gè)位置) 隊(duì)尾指針 rear 指向隊(duì)尾2. 隊(duì)列空 front=rear=NULL 不需要判別隊(duì)列滿四、隊(duì)列的基本操作1. 入隊(duì)函數(shù)：insert(arg)2. 出隊(duì)函數(shù)：delete()五、鏈接式隊(duì)列程序 lqueue.c (40) 的說(shuō)明1. #include "llist.h" 編譯預(yù)處理。2. 主程序中包含二個(gè)循環(huán)語(yǔ)句： 入隊(duì)：輸入一行字符，鏈成隊(duì)列，遇 'n' 停止循環(huán)。可不考慮隊(duì)列滿。 出隊(duì)：顯示出

6、隊(duì)字符。遇隊(duì)列空，停止循環(huán)。3. 定義隊(duì)首、隊(duì)尾指針，供 insert 和 delete 共享。 NODE *front=NULL,*rear=NULL； /*隊(duì)首、隊(duì)尾指針賦初值*/4. 入隊(duì)函數(shù) insert 圖解：鏈入新數(shù)據(jù)(1) 申請(qǐng)結(jié)點(diǎn) ptr=(NODE *)malloc(sizeof(NODE)(2) 結(jié)點(diǎn)數(shù)據(jù)域賦值 prt->info=arg(3) 結(jié)點(diǎn)鏈域賦值 ptr->link=NULL(4) 將新申請(qǐng)的結(jié)點(diǎn)鏈入。根據(jù)隊(duì)列是否空，用二種不同的鏈入方法。 if (front=NULL) front=ptr; /*若隊(duì)列空*/ else rear->link=

7、ptr; /*隊(duì)列不空，鏈入隊(duì)尾*/(5) 修改隊(duì)尾指針 rear=ptr; /*隊(duì)列空或不空*/5. 出隊(duì)函數(shù) delete 圖解：輸出隊(duì)首結(jié)點(diǎn)的數(shù)據(jù)(1) 若是空隊(duì)列，返回 '0'。(2) 保存隊(duì)首指針 ptr=front 。(3) 移動(dòng)隊(duì)首指針，指向下一個(gè)結(jié)點(diǎn) front=ptr->link 。(4) 數(shù)據(jù)出隊(duì) var=ptr->info 。(5) 釋放結(jié)點(diǎn) free(ptr) 。(6) 如果刪除了最后一個(gè)結(jié)點(diǎn),成為空隊(duì)列，隊(duì)首指針front=ptr->link為 NULL，隊(duì)尾指針也應(yīng)為NULL 。 if (front=NULL) rear=NULL;

8、(7) 返回出隊(duì)數(shù)據(jù) 。6. 執(zhí)行 輸入：abcde 輸出：abcde 。 2.2.3 向前鏈表 p41 一、定義 p41 圖解 頭指針 頭結(jié)點(diǎn) 第一個(gè)結(jié)點(diǎn) head 數(shù)據(jù)域閑置 鏈域存放指針，表空鏈域?yàn)镹ULL二、基本操作有五種： 添加、查找、插入、刪除和遍歷 。三、對(duì)向前鏈表程序 list.c (p41) 的說(shuō)明1. #include "llist.h" 編譯預(yù)處理 。2. NODE *search() ； /* 是在主函數(shù) main 之外說(shuō)明 */3. 用開關(guān)語(yǔ)句選擇各種操作 。4. 生成鏈表函數(shù) init() 圖解 鍵盤輸入：abcde e b a 輸出顯示：edc

9、ba head5. 添加函數(shù) append() 圖解 arg 添加在頭結(jié)點(diǎn)之后6. 查找函數(shù) search() 因?yàn)橛蟹祷刂?，調(diào)用前要說(shuō)明。 查找成功，返回結(jié)點(diǎn)指針。不成功，返回 NULL 。7. 插入函數(shù) insert(argf,argr) 圖解 調(diào)用 search ，查找數(shù)據(jù)域?yàn)?argf 的結(jié)點(diǎn)，在其后插入 argr 。 插入成功，返回 0 。不成功，返回 -1 。8. 刪除函數(shù) delete(arg) 圖解 定義二個(gè)指針 NODE *ptr1,*ptr2； ptr1 和 ptr2 同步向前掃描每個(gè)結(jié)點(diǎn) ptr2=ptr1； ptr1=ptr1->link； 如找到 ptr1-&g

10、t;info=arg；則刪除該結(jié)點(diǎn) ptr2->link=ptr1->link； 并釋放該結(jié)點(diǎn) free(ptr1)； 刪除成功，返回 0 。 找不到 arg ，刪除失敗，返回 -1 。9. 遍歷函數(shù) travel 輸入：abcde 輸出：edcba2.3 環(huán)形鏈表 p44 圖解 生成：如果使向前鏈表最后一個(gè)結(jié)點(diǎn)的鏈指向表頭結(jié)點(diǎn)，便可得到一個(gè)環(huán)形鏈表。 特點(diǎn)：在環(huán)形鏈表中，可以把表頭結(jié)點(diǎn)作為普通結(jié)點(diǎn)存放數(shù)據(jù)。 標(biāo)識(shí)：用指針 rignt 指向環(huán)形鏈表的右端，標(biāo)識(shí)這個(gè)環(huán)形鏈表。right->link 所指的結(jié)點(diǎn)是右端。 當(dāng) right=NULL ，鏈表空。 2.3.1 關(guān)于環(huán)形鏈

11、表的操作一、程序 circular.c 有五種基本操作。right 的初值為 0 。 左端添加函數(shù) appendl 右端添加函數(shù) appendr 左端刪除函數(shù) delete 鏈反向函數(shù) reverse 遍歷函數(shù) travel 二、對(duì)環(huán)形鏈表程序p.45 circular.c 的說(shuō)明1. 主函數(shù) main 調(diào)用 init ，生成環(huán)形鏈表 開關(guān)語(yǔ)句選擇各種操作2. 定義指針 right 為外部變量。3. 生成環(huán)形鏈表函數(shù) init 調(diào)用 appendr 右端輸入： abcde 調(diào)用 travel 左端輸出： abcde 先進(jìn)先出4. 右端添加函數(shù) appendr 調(diào)用 appendl， 左端添加；

12、 然后改變 right 指向，相當(dāng)于右端添加。(圖解)5. 左端添加函數(shù) appendl 申請(qǐng)結(jié)點(diǎn)， 數(shù)據(jù)域賦值。 原先是空表，左端添加后自成循環(huán)； 原先不是空表，結(jié)點(diǎn)入鏈。(圖解)6. 左端刪除函數(shù) deletel 原先是空表，return('0')。 原先不是空表，提取左端結(jié)點(diǎn)的指針和數(shù)據(jù)域值。 如果有二個(gè)及以上結(jié)點(diǎn)，用 right->link=ptr->link，刪除左結(jié)點(diǎn)。 如果原先只有一個(gè)結(jié)點(diǎn)，用 right=NULL 刪除后成為空鏈表。(圖解) 釋放被刪結(jié)點(diǎn) 返回被刪結(jié)點(diǎn)數(shù)據(jù)7. 鏈表反向函數(shù) reverse 原先是空表，不做反向操作 輔助指針初始定位

13、ptr1=right ，ptr2=right->link。 do 保留指針 ptr=ptr2->link; 反向 ptr2->link=ptr1; 向前移動(dòng)一個(gè)結(jié)點(diǎn) ptr1=ptr2;ptr2=ptr; ptr2 指向的最后一個(gè)結(jié)點(diǎn)反向后，再同步移到下一個(gè)結(jié)點(diǎn)， 使 ptr1=right ，停止循環(huán)。8. 遍歷函數(shù) travel 空表不操作 非空表，從左結(jié)點(diǎn)開始，逐個(gè)輸出結(jié)點(diǎn)數(shù)據(jù)域值。授課內(nèi)容、教具與時(shí)間分配小結(jié)、復(fù)習(xí)、思考題、參考書思考題：1、鍵入鏈接式排隊(duì)程序 p40 lqueue.c ，執(zhí)行之。2、復(fù)制向前鏈表程序 p41 list.c ，執(zhí)行之。3、編寫函數(shù) insertah 使之能在向前鏈表已知結(jié)點(diǎn)之前插入新結(jié)點(diǎn)，把 insertah 加入 ，執(zhí)行之。4、