課程名稱數據結構07

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

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

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

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

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

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

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

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

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

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

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

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

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