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

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

2、時，鏈接式線性表可節(jié)省內(nèi)存。 二、鏈接式線性表的結(jié)點成員 struct node xxxx info link 數(shù)據(jù)域 鏈域 char info; 三、申請結(jié)點和釋放結(jié)點 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 庫函數(shù) free ，ptr 是指向待釋放結(jié)點的指針*/四、主要操作：不同的結(jié)構(gòu)有不同的操作2.2.1 鏈接式棧 p38 top一、 圖解 實際上就是 p17 的

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

4、明 1. #include "llist" 編譯預(yù)處理。 2. main() 中有二個循環(huán)語句 入棧：當遇到 'n' ，循環(huán)終止?？刹豢紤]棧滿，即內(nèi)存用完。 出棧：當棧空，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 鏈接式排隊(隊列） p39一、定義 隊首 隊尾 同 p30二、主要操作：入隊、出

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

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

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

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

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

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

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

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

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