數(shù)據(jù)結(jié)構(gòu)-鏈表

1、第二章 線性表 （一）講授內(nèi)容：（一）講授內(nèi)容： 1、線性表的類型定義。 2、線性表的順序表示和實(shí)現(xiàn)。 3、線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)。 4、一元多項式的表示及相加。 (二二) 教學(xué)要求：教學(xué)要求： 1、了解線性表的邏輯結(jié)構(gòu)特性（數(shù)據(jù)元素之間存在著線性關(guān)系）， 在計算機(jī)中表示線性表數(shù)據(jù)元素關(guān)系的兩種方法：順序存儲結(jié)構(gòu) 和鏈?zhǔn)酱鎯Y(jié)構(gòu)，以及由兩種關(guān)系表示得到的順序表、鏈表。 2、熟練掌握這兩種存儲結(jié)構(gòu)的描述方法。 3、熟練掌握線性表在順序存儲結(jié)構(gòu)上的各種基本操作：查找、插 入和刪除的算法。 4、熟練掌握在各種鏈表結(jié)構(gòu)中實(shí)現(xiàn)線性表操作的基本方法，能在 實(shí)際應(yīng)用中選用適當(dāng)?shù)逆湵斫Y(jié)構(gòu)。了解靜態(tài)鏈表的定義及

2、實(shí)現(xiàn)方 法。 5、能夠從時間和空間復(fù)雜度的角度綜合比較線性表兩種存儲結(jié)構(gòu) 的不同特點(diǎn)、各種操作的算法復(fù)雜度分析及其適用場合。 （三）教學(xué)重難點(diǎn)：（三）教學(xué)重難點(diǎn)： 教學(xué)重點(diǎn)：教學(xué)重點(diǎn)： 線性表的基本概念、順序表 的實(shí)現(xiàn)及應(yīng)用；單鏈表、循環(huán)鏈表以及 雙向鏈表的定義、實(shí)現(xiàn)及應(yīng)用。 教學(xué)難點(diǎn)：教學(xué)難點(diǎn)： 實(shí)現(xiàn)鏈表刪除與插入操作時 指針的變化以及特殊情況處理。 學(xué)時分配：學(xué)時分配：本章共講授12學(xué)時。 線性結(jié)構(gòu)的特點(diǎn) 在數(shù)據(jù)元素的非空有限集中 存在唯一的一個被稱作“第一個第一個”的數(shù)據(jù)元素 存在唯一的一個被稱作“最后一個最后一個”的數(shù)據(jù)元素 除第一個外，集合中的每個數(shù)據(jù)元素均只有一個前驅(qū)前驅(qū) 除最后一

3、個外，集合中的每個數(shù)據(jù)元素均只有一個后繼后繼 2.1 線性表的類型定義 線性表(Linear List) ：由n(n0)個數(shù)據(jù)元素組成的有限 序列，這里的數(shù)據(jù)元素只是一個抽象的符號，其具體 含義在不同的情況下可以不同：數(shù)據(jù)元素可以是原子 類型，也可以是結(jié)構(gòu)類型。 線性表舉例 例 英文字母表（A,B,C,.Z)是一個線性表 例 計算機(jī)擁有量（6，17，28，50，92，188） 復(fù)雜線性表中的一個數(shù)據(jù)元素可由若干數(shù)據(jù)項數(shù)據(jù)項組成（結(jié)構(gòu)類型）， 此時又把數(shù)據(jù)元素稱作記錄記錄，把含有大量記錄的線性表稱作文件文件。 例 學(xué)號姓名年齡 001張三18 002李四19 數(shù)據(jù)元素 文件文件 數(shù)據(jù)項數(shù)據(jù)項 線

4、性表特征 線性表中的元素具有相同屬性， 相鄰元素之間存在序偶關(guān)系，1i0時通 常表示成下列形式： ),.,.,( 121nii aaaaaL 線性表的ADT 講解：P19 注意：數(shù)據(jù)結(jié)構(gòu)的基本運(yùn)算，不是它的全部運(yùn) 算。每一個基本運(yùn)算在實(shí)現(xiàn)時可根據(jù)不同的存 儲結(jié)構(gòu)派生出一系列相關(guān)的運(yùn)算來。 例：線性表的查找在鏈?zhǔn)酱鎯Y(jié)構(gòu)中還會有按 序號查找 例：插入運(yùn)算，可以是將新元素插入到適當(dāng) 位置上 建議：掌握了某一數(shù)據(jù)結(jié)構(gòu)上的基本運(yùn)算后， 其它的運(yùn)算可以通過基本運(yùn)算來實(shí)現(xiàn)，也可以 直接去實(shí)現(xiàn)。 線性表的高級操作 合并 分拆 復(fù)制 P20 例子2.1 線性表的合并 利用兩個線性表LA和LB分別表示兩個集合A

5、和 B，現(xiàn)要求一個新的集合A=AB。 集合的合并運(yùn)算說明： 1、 LB中與LA中相同的元素不予合并。 2 、不另建新線性表，只需擴(kuò)大表LA，將LB中需要并入的元素插入 到LA中。 3 、LB中需要并入的元素作為LA的尾元素插入。 算法2.1 void union(List Lb_len=ListLength(Lb);/求線形表的長度 for(i=1; i =lb_len; i +) GetElem(Lb， i ，e);/取Lb中第 i個數(shù)據(jù)元素賦給e if(!LocateElem(La,e,equal) ListInsert(La，+La-len，e); / La中不存在和e相同的元素，則插入

6、之 并集運(yùn)算算法時間復(fù)雜度分析 查找一個元素LB（i）是否在表LA中，需要掃 描 整 個 表 L A ， 即 進(jìn) 行 比 較 的 時 間 為 O(ListLenth(LA)；每插入一個元素所需時間為 常數(shù)時間O(1)；共調(diào)用ListLenth(LB)次元素查 找過程，插入元素的個數(shù)不會大于LB的長度 ListLenth(LB) ，所需查找時間的復(fù)雜度為 O(ListLenth(LA) * ListLenth(LB)。 例子2.2 線性表的歸并 例2-2 巳知線性表LA和線性表LB中的數(shù)據(jù)元 素按值非遞減有序排列，現(xiàn)要求將LA和LB歸 并為一個新的線性表LC，且LC中的元素仍按 值非遞減有序排列

7、。 例子2.2 線性表的歸并 算法的思想： 從上述問題要求可知，LC中的數(shù)據(jù)元素或是LA中的數(shù)據(jù)元素，或是 LB中的數(shù)據(jù)元素，則只要先設(shè)LC為空表，然后將LA或LB中的元素逐個 插入到LC即可。 為了使得LC中的元素按值非遞減有序排列，可分別設(shè)兩個指針i和j分 別指向LA和LB中的某個元素，若設(shè)i當(dāng)前所指的元素為a，j當(dāng)前所指的元 素為b，則當(dāng)前應(yīng)插入到LC中的元素c為: 顯然，指針i和j的初值均為1，在所指元素插入到LC之后，在LA或LB 中順序后移。 bawhenb bawhena c 例2.2 線性表的歸并 例如，設(shè) LA=（3，5，8，11） LB=（2，6，8，9，11，15，20）

8、 則 LC=（2，3，5，6，8，8，9，11，15， 20） 算法2.2 void Merge List( List La, List Lb, List i = j = 1; k = 0; La_len = ListLength( La ); Lb_len = ListLength( Lb ); while( ( i= La_len ) GetElem( Lb, j, bj ); if ( ai = bj ) ListInsert(Lc, +k, ai); +i; else ListInsert(Lc, +k, bj); +j; /當(dāng)其中一個線形表的數(shù)據(jù)元素均已插入到線形表Lc中后，只要將另外一個線形 表中的剩余元素依次插入即可。 while ( i= la_len ) GetElem( La, I+, ai ); ListInsert( Lc, +k, ai ); while ( j= lb_len ) GetElem( La, j+, bj); ListInsert( Lc, +k, ai ); / Merge List 歸并算法時間復(fù)雜度分析 歸并算法的時間復(fù)雜度為： O(ListLenth(A)+ListLenth(B)。 雖然歸并算法中含3個(while)循環(huán)語句，但 只