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

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

2、間復(fù)雜度的角度綜合比較線性表兩種存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)、各種操作的算法復(fù)雜度分析及其適用場(chǎng)合。（三）教學(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)鏈表刪除與插入操作時(shí)指針的變化以及特殊情況處理。 學(xué)時(shí)分配：學(xué)時(shí)分配：本章共講授12學(xué)時(shí)。 線性結(jié)構(gòu)的特點(diǎn) 在數(shù)據(jù)元素的非空有限集中 存在唯一的一個(gè)被稱作“第一個(gè)第一個(gè)”的數(shù)據(jù)元素 存在唯一的一個(gè)被稱作“最后一個(gè)最后一個(gè)”的數(shù)據(jù)元素 除第一個(gè)外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)前驅(qū)前驅(qū) 除最后一個(gè)外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)后繼后

3、繼2.1 線性表的類型定義 線性表(Linear List) ：由n(n0)個(gè)數(shù)據(jù)元素組成的有限序列，這里的數(shù)據(jù)元素只是一個(gè)抽象的符號(hào)，其具體含義在不同的情況下可以不同：數(shù)據(jù)元素可以是原子類型，也可以是結(jié)構(gòu)類型。線性表舉例 例 英文字母表（A,B,C,.Z)是一個(gè)線性表 例 計(jì)算機(jī)擁有量（6，17，28，50，92，188） 復(fù)雜線性表中的一個(gè)數(shù)據(jù)元素可由若干數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)組成（結(jié)構(gòu)類型），此時(shí)又把數(shù)據(jù)元素稱作記錄記錄，把含有大量記錄的線性表稱作文件文件。 例學(xué)號(hào)姓名年齡001張三18002李四19數(shù)據(jù)元素文件文件數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)線性表特征 線性表中的元素具有相同屬性， 相鄰元素之間存在序偶關(guān)系，1

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

5、并。2 、不另建新線性表，只需擴(kuò)大表LA，將LB中需要并入的元素插入到LA中。3 、LB中需要并入的元素作為L(zhǎng)A的尾元素插入。 算法2.1void union(List &La，List Lb) /將所有在線形表Lb中但不在La中的數(shù)據(jù)元素插入到La中 La_len=ListLength(La); Lb_len=ListLength(Lb);/求線形表的長(zhǎng)度 for(i=1; i =lb_len; i +) GetElem(Lb， i ，e);/取Lb中第 i個(gè)數(shù)據(jù)元素賦給e if(!LocateElem(La,e,equal) ListInsert(La，+La-len，e); /

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

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

8、=（2，3，5，6，8，8，9，11，15，20）算法2.2void Merge List( List La, List Lb, List &Lc )/已知線性表La和Lb中的數(shù)據(jù)元素按值非遞減排列。 InitList( Lc ); i = j = 1; k = 0; La_len = ListLength( La ); Lb_len = ListLength( Lb ); while( ( i= La_len ) &( j=Lb_len) )/La和Lb均非空 GetElem( La, i, ai ); GetElem( Lb, j, bj ); if ( ai = bj )

9、 ListInsert(Lc, +k, ai); +i; else ListInsert(Lc, +k, bj); +j; /當(dāng)其中一個(gè)線形表的數(shù)據(jù)元素均已插入到線形表Lc中后，只要將另外一個(gè)線形表中的剩余元素依次插入即可。 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歸并算法時(shí)間復(fù)雜度分析歸并算法的時(shí)間復(fù)雜度為：O(ListLenth(A)+ListLenth(B)。 雖然歸并算法中含3個(gè)(wh