數(shù)據(jù)機(jī)構(gòu)第二章-線性表(嚴(yán)蔚敏).ppt

第二章線性表 2 1 了解線性表的邏輯結(jié)構(gòu)特性是數(shù)據(jù)元素之間存在著線性關(guān)系 2 熟練掌握這兩類存儲(chǔ)結(jié)構(gòu) 順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的描述方法 鏈表是本章的重點(diǎn)和難點(diǎn) 扎實(shí)的指針操作和內(nèi)存動(dòng)態(tài)分配的編程技術(shù)是學(xué)好本章的基本要求 3 熟練掌握線性表在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)基本操作 查找 插入和刪除的算法 4 熟練掌握在各種鏈表結(jié)構(gòu)中實(shí)現(xiàn)線性表操作的基本方法 能在實(shí)際應(yīng)用中選用適當(dāng)?shù)逆湵斫Y(jié)構(gòu) 5 能夠從時(shí)間和空間復(fù)雜度的角度綜合比較線性表兩種存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)及其適用場(chǎng)合 學(xué)習(xí)提要 3 在數(shù)據(jù)元素的非空有限集中 存在唯一的一個(gè)被稱作 第一個(gè) 的數(shù)據(jù)元素 存在唯一的一個(gè)被稱作 最后一個(gè) 的數(shù)據(jù)元素 除第一個(gè)外 集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)前驅(qū) 除最后一個(gè)外 集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)后繼 線性結(jié)構(gòu)特點(diǎn) a1 a2 a3 a4 a5 a6 簡(jiǎn)言之 線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是1 1的 線性結(jié)構(gòu)包括 線性表 堆棧 隊(duì)列 字符串 數(shù)組等 其中最典型 最常用的是 線性表 4 a1 a2 ai 1 ai ai 1 an 1 線性表的定義 用數(shù)據(jù)元素的有限序列表示 n 0時(shí)稱為 數(shù)據(jù)元素 線性起點(diǎn) ai的直接前趨 ai的直接后繼 下標(biāo) 是元素的序號(hào) 表示元素在表中的位置 n為元素總個(gè)數(shù) 即表長(zhǎng) 空表 線性終點(diǎn) 2 1線性表的邏輯結(jié)構(gòu) 5 例1 26個(gè)英文字母組成的字母表 A B C Z 例2 某校從1978年到1983年各種型號(hào)的計(jì)算機(jī)擁有量的變化情況 6 17 28 50 92 188 6 例3 學(xué)生健康情況登記表如下 7 從以上例子可看出線性表的邏輯特征是 在非空的線性表 有且僅有一個(gè)開(kāi)始結(jié)點(diǎn)a1 它沒(méi)有直接前趨 而僅有一個(gè)直接后繼a2 有且僅有一個(gè)終端結(jié)點(diǎn)an 它沒(méi)有直接后繼 而僅有一個(gè)直接前趨an 1 其余的內(nèi)部結(jié)點(diǎn)ai 2 i n 1 都有且僅有一個(gè)直接前趨ai 1和一個(gè)直接后繼ai 1 a1 a2 ai ai 1 an 8 1 數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種關(guān)系的數(shù)據(jù)元素的全體 2 一維向量是線性表 但二維或N維數(shù)組不是 3 同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素都具有相同的特性 是指數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)都相等 練 判斷下列敘述的正誤 9 ADTList 數(shù)據(jù)對(duì)象 D ai ai ElemSet i 1 2 n n 0 數(shù)據(jù)關(guān)系 R ai 1 ai D i 2 n 基本操作 1 結(jié)構(gòu)初始化 InitList L 操作結(jié)果 構(gòu)造一個(gè)空的線性表L 2 銷毀結(jié)構(gòu) DestroyList L 初始條件 線性表L已存在 操作結(jié)果 銷毀線性表L 線性表的抽象數(shù)據(jù)類型 10 3 引用型操作 ListEmpty L 初始條件 線性表L已存在 操作結(jié)果 若L為空表 則返回TRUE 否則FALSEListLength L 初始條件 線性表L已存在 操作結(jié)果 返回L中元素個(gè)數(shù) PriorElem L cur e pre e 初始條件 線性表L已存在 操作結(jié)果 若cur e是L的元素 但不是第一個(gè) 則用pre e返回它的前驅(qū) 否則操作失敗 pre e無(wú)定義 NextElem L cur e next e 初始條件 線性表L已存在 操作結(jié)果 若cur e是L的元素 但不是最后一個(gè) 則用next e返回它的后繼 否則操作失敗 next e無(wú)定義 11 3 引用型操作 續(xù) GetElem L i e 初始條件 線性表L已存在 1 i LengthList L 操作結(jié)果 用e返回L中第i個(gè)元素的值 LocateElem L e compare 初始條件 線性表L已存在 compare 是元素判定函數(shù) 操作結(jié)果 返回L中第1個(gè)與e滿足關(guān)系compare 的元素的位序 若這樣的元素不存在 則返回值為0 ListTraverse L visit 線性表遍歷初始條件 線性表L已存在 操作結(jié)果 依次對(duì)L的每個(gè)元素調(diào)用函數(shù)visit 一旦visit 失敗 則操作失敗 12 4 加工型操作ClearList L 初始條件 線性表L已存在 操作結(jié)果 將L重置為空表 PutElem L i e 初始條件 線性表L已存在 1 i LengthList L 操作結(jié)果 L中第i個(gè)元素賦值同e的值 ListInsert L i e 初始條件 線性表L已存在 1 i LengthList L 1操作結(jié)果 在L的第i個(gè)元素前插入新元素e L長(zhǎng)度增1 ListDelete L i e 初始條件 線性表L已存在且非空 1 i LengthList L 操作結(jié)果 刪除L第i個(gè)元素 用e返回其值 L的長(zhǎng)度減1 ADTList 13 某數(shù)據(jù)結(jié)構(gòu)上的基本運(yùn)算 不是它的全部運(yùn)算 而是一些常用的基本的運(yùn)算 而每一個(gè)基本運(yùn)算在實(shí)現(xiàn)時(shí)也可能根據(jù)不同的存儲(chǔ)結(jié)構(gòu)派生出一系列相關(guān)的運(yùn)算來(lái) 讀者掌握了某一數(shù)據(jù)結(jié)構(gòu)上的基本運(yùn)算后 其它的運(yùn)算可以通過(guò)基本運(yùn)算來(lái)實(shí)現(xiàn) 也可以直接去實(shí)現(xiàn) 2 在上面各操作中定義的線性表 僅僅是一個(gè)抽象在邏輯結(jié)構(gòu)層次的線性表 尚未涉及到它的存儲(chǔ)結(jié)構(gòu) 因此每個(gè)操作在邏輯結(jié)構(gòu)層次上尚不能用具體的某種程序語(yǔ)言寫(xiě)出具體的算法 而算法的實(shí)現(xiàn)只有在存儲(chǔ)結(jié)構(gòu)確立之后 說(shuō)明 14 假設(shè) 有兩個(gè)集合A和B分別用兩個(gè)線性表LA和LB表示 即 線性表中的數(shù)據(jù)元素即為集合中的成員 現(xiàn)要求一個(gè)新的集合A A B A 5 3 11 8 B 6 2 8 9 20 15 11 例2 1 15 要求對(duì)線性表作如下操作 擴(kuò)大線性表LA 將存在于線性表LB中而不存在于線性表LA中的數(shù)據(jù)元素插入到線性表LA中去 上述問(wèn)題可演繹為 16 1 從線性表LB中依次察看每個(gè)數(shù)據(jù)元素 2 依值在線性表LA中進(jìn)行查訪 3 若不存在 則插入之 GetElem LB i e LocateElem LA e equal ListInsert LA n 1 e 操作步驟 17 GetElem Lb i e 取Lb中第i個(gè)數(shù)據(jù)元素賦給eif LocateElem La e equal ListInsert La La len e La中不存在和e相同的數(shù)據(jù)元素 則插入之 voidunion List for i 1 i Lb len i union T n O LA length LB length 18 巳知線性表LA和線性表LB中的數(shù)據(jù)元素按值非遞減有序排列 現(xiàn)要求將LA和LB歸并為一個(gè)新的線性表LC 且LC中的元素仍按值非遞減有序排列 求解 設(shè)兩個(gè)指針 i指向LA中的元素a j指向LB中的元素b LC中的元素c a ab LA 3 5 8 11 LB 2 6 8 9 11 15 20 得到LC 2 3 5 6 8 9 11 15 20 例2 2 19 voidMergelist ListLa ListLb List endwhile 20 while i La len Lb為空的情況GetElem La i ai ListInsert Lc k ai while j Lb len La為空的情況GetElem Lb j bj ListInsert Lc k bi T n O LA length LB length 21 2 2線性表的順序表示和實(shí)現(xiàn) 22 用一組地址連續(xù)的存儲(chǔ)單元依次存放線性表中的數(shù)據(jù)元素 a1a2 ai 1ai an 線性表的起始地址稱作線性表的基地址 順序存儲(chǔ)結(jié)構(gòu) 23 元素地址計(jì)算方法 LOC ai LOC a1 i 1 LLOC ai 1 LOC ai L其中 L 一個(gè)元素占用的存儲(chǔ)單元個(gè)數(shù)LOC ai 線性表第i個(gè)元素的地址特點(diǎn) 實(shí)現(xiàn)邏輯上相鄰 物理地址相鄰實(shí)現(xiàn)隨機(jī)存取實(shí)現(xiàn) 可用C語(yǔ)言的一維數(shù)組實(shí)現(xiàn) 順序存儲(chǔ)結(jié)構(gòu) 24 設(shè)有一維數(shù)組 下標(biāo)的范圍是 到 每個(gè)數(shù)組元素用相鄰的 個(gè)字節(jié)存儲(chǔ) 存儲(chǔ)器按字節(jié)編址 設(shè)存儲(chǔ)數(shù)組元素 的第一個(gè)字節(jié)的地址是 則 的第一個(gè)字節(jié)的地址是 113 因此 LOC M 3 98 5 3 0 113 解 已知地址計(jì)算通式為 LOC ai LOC a1 L i 1 25 順序表的C語(yǔ)言描述 typedefstruct SqList 俗稱順序表 defineLIST INIT SIZE80 線性表存儲(chǔ)空間的初始分配量 defineLISTINCREMENT10 線性表存儲(chǔ)空間的分配增量 ElemType elem 存儲(chǔ)空間基址 intlength 當(dāng)前長(zhǎng)度 intlistsize 當(dāng)前分配的存儲(chǔ)容量 以sizeof ElemType 為單位 26 線性表的基本操作在順序表中的實(shí)現(xiàn) InitList L 結(jié)構(gòu)初始化 LocateElem L e compare 查找 ListInsert L i e 插入元素 ListDelete L i 刪除元素 注意 C語(yǔ)言中的數(shù)組下標(biāo)從 0 開(kāi)始 因此 若L是Sqlist類型的順序表 則表中第i個(gè)元素是L elem i 1 27 順序表的初始化 intInitList Sq SqList 函數(shù)調(diào)用 main sqlistL InitList Sq L 28 intLocateElem Sq SqListL ElemTypee 在順序表中查詢第一個(gè)等于e的數(shù)據(jù)元素 若存在 則返回它的位序 否則返回0 LocateElem Sq O ListLength L 算法的時(shí)間復(fù)雜度為 i 1 i的初值為第1元素的位序p L elem p的初值為第1元素的存儲(chǔ)位置 while i L length if i L length return0 elsereturni 29 3 插入在線性表的第i個(gè)位置前插入一個(gè)元素 實(shí)現(xiàn)步驟 將第n至第i位的元素向后移動(dòng)一個(gè)位置 將要插入的元素寫(xiě)到第i個(gè)位置 表長(zhǎng)加1 注意 事先應(yīng)判斷 插入位置i是否合法 表是否已滿 長(zhǎng)度為n的線性表變?yōu)殚L(zhǎng)度為n 1的線性表 a1 a2 ai 1 ai an a1 a2 ai 1 x ai an 30 StatusListInsert Sq SqList L inti ElemTypee 在順序表L的第i個(gè)元素之前插入新的元素e 1 i L length 1 if L length L listsize 當(dāng)前存儲(chǔ)空間已滿 增加分配 newbase ElemType realloc L elem L listsize LISTINCREMENT sizeof ElemType if newbase printf 分配空間失敗 return 1 L elem newbase 新基址L listsize LISTINCREMENT 增加存儲(chǔ)容量 if iL length 1 printf 插入位置錯(cuò)誤 return0 31 for j L length 1 j i 1 j L elem j 1 L elem j 插入位置及之后的元素后移L elem i 1 e 插入eL length 表長(zhǎng)增1return1 32 考慮移動(dòng)元素的平均情況 假設(shè)在第i個(gè)元素之前插入的概率為 則在長(zhǎng)度為n的線性表中插入一個(gè)元素所需移動(dòng)元素次數(shù)的期望值為 若假定在線性表中任何一個(gè)位置上進(jìn)行插入的概率都是相等的 則移動(dòng)元素的期望值為 O n 33 實(shí)現(xiàn)步驟 將第i 1至第n位的元素向前移動(dòng)一個(gè)位置 表長(zhǎng)減1 注意 事先需要判斷 刪除位置i是否合法 4 刪除刪除線性表的第i個(gè)位置上的元素 使 長(zhǎng)度為n的線性表變?yōu)殚L(zhǎng)度為n 1的線性表 a1 a2 ai 1 ai ai 1 an a1 a2 ai 1 ai 1 an 34 StatusListDelete Sq SqList L inti ElemType e ListDelete Sq for j i j L Length 1 j L elme j 1 L elem j 被刪除元素之后的元素前移 L length 表長(zhǎng)減1return1 算法時(shí)間復(fù)雜度為 O ListLength L e L elem i 1 被刪除元素的值賦給e if iL length printf 刪除位置錯(cuò)誤 return0 35 考慮移動(dòng)元素的平均情況 假設(shè)刪除第i個(gè)元素的概率為 則在長(zhǎng)度為n的線性表中刪除一個(gè)元素所需移動(dòng)元素次數(shù)的期望值為 若假定在線性表中任何一個(gè)位置上進(jìn)行刪除的概率都是相等的 則移動(dòng)元素的期望值為 O n 36 小結(jié) 線性表順序存儲(chǔ)結(jié)構(gòu)特點(diǎn) 邏輯關(guān)系上相鄰的兩個(gè)元素在物理存儲(chǔ)位置上也相鄰 優(yōu)點(diǎn) 可以隨機(jī)存取表中任一元素O 1 存儲(chǔ)空間使用緊湊缺點(diǎn) 在插入 刪除某一元素時(shí) 需要移動(dòng)大量元素O n 預(yù)先分配空間需按最大空間分配 利用不充分為克服這一缺點(diǎn) 我們引入另一種存儲(chǔ)形式 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 見(jiàn)2 3節(jié) 37 特點(diǎn) 1 用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素 2 利用指針實(shí)現(xiàn)了用不相鄰的存儲(chǔ)單元存放邏輯上相鄰的元素 3 每個(gè)數(shù)據(jù)元素ai 除存儲(chǔ)本身信息外 還需存儲(chǔ)其直接后繼的信息 結(jié)點(diǎn)數(shù)據(jù)域 元素本身信息指針域 指示直接后繼的存儲(chǔ)位置 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 38 data next 結(jié)點(diǎn) p 定義 結(jié)點(diǎn)中只含一個(gè)指針域的鏈表 也叫單鏈表 TypedefstructLNode ElemTypedata structLNode next Lnode LinkList 若聲明LNode p 則 p malloc sizeof LNode 表示生成一個(gè)新結(jié)點(diǎn) free p 表示系統(tǒng)回收p結(jié)點(diǎn) 單鏈表 39 一個(gè)線性表的邏輯結(jié)構(gòu)為 ZHAO QIAN SUN LI ZHOU WU ZHENG WANG 其存儲(chǔ)結(jié)構(gòu)用單鏈表表示如下 請(qǐng)問(wèn)其頭指針的值是多少 例 答 頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)的指針 因此關(guān)鍵是要尋找第一個(gè)結(jié)點(diǎn)的地址 31 頭指針的值是31 40 上例鏈表的邏輯結(jié)構(gòu)示意圖有以下兩種形式 區(qū)別 無(wú)頭結(jié)點(diǎn) 有頭結(jié)點(diǎn) 41 答 討論1 在鏈表中設(shè)置頭結(jié)點(diǎn)有什么好處 討論2 如何表示空表 頭結(jié)點(diǎn)即在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn) 該結(jié)點(diǎn)的數(shù)據(jù)域中不存儲(chǔ)線性表的數(shù)據(jù)元素 其作用是為了對(duì)鏈表進(jìn)行操作時(shí) 可以對(duì)空表 非空表的情況以及對(duì)首元結(jié)點(diǎn)進(jìn)行統(tǒng)一處理 編程更方便 答 無(wú)頭結(jié)點(diǎn)時(shí) 當(dāng)頭指針的值為空時(shí)表示空表 有頭結(jié)點(diǎn)時(shí) 當(dāng)頭結(jié)點(diǎn)的指針域?yàn)榭諘r(shí)表示空表 42 頭結(jié)點(diǎn) 在單鏈表第一個(gè)結(jié)點(diǎn)前附設(shè)的一個(gè)結(jié)點(diǎn) 頭結(jié)點(diǎn)指針域?yàn)榭毡硎揪€性表為空 43 單鏈表操作的實(shí)現(xiàn) GetElem L i e 取第i個(gè)數(shù)據(jù)元素 ListInsert L i e 插入數(shù)據(jù)元素 ListDelete L i e 刪除數(shù)據(jù)元素 ClearList L 重置線性表為空表 CreateList L n 生成含n個(gè)數(shù)據(jù)元素的鏈表 44 1 在鏈表的頭部插入結(jié)點(diǎn)建立單鏈表鏈表與順序表不同 它是一種動(dòng)態(tài)管理的存儲(chǔ)結(jié)構(gòu) 鏈表中的每個(gè)結(jié)點(diǎn)占用的存儲(chǔ)空間不是預(yù)先分配 而是運(yùn)行時(shí)系統(tǒng)根據(jù)需求而生成的 因此建立單鏈表從空表開(kāi)始 每讀入一個(gè)數(shù)據(jù)元素則申請(qǐng)一個(gè)結(jié)點(diǎn) 然后插在鏈表的頭部 建立單鏈表 45 例如 逆位序輸入n個(gè)數(shù)據(jù)元素的值 建立帶頭結(jié)點(diǎn)的單鏈表 操作步驟 一 建立一個(gè) 空表 二 輸入數(shù)據(jù)元素an 建立結(jié)點(diǎn)并插入 三 輸入數(shù)據(jù)元素an 1 建立結(jié)點(diǎn)并插入 an an an 1 四 依次類推 直至輸入a1為止 46 intCreateList L LinkList L intn 逆序輸入n個(gè)數(shù)據(jù)元素 建立帶頭結(jié)點(diǎn)的單鏈表 CreateList L 算法的時(shí)間復(fù)雜度為 O Listlength L L LinkList malloc sizeof LNode L next NULL 先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表 for i 1 idata 輸入元素值p next L next L next p 插入 returnOK 47 在單鏈表的尾部插入結(jié)點(diǎn)建立單鏈表 以上算法讀入的數(shù)據(jù)元素的順序與生成的鏈表中元素的順序是相反的 若希望次序一致 則用尾插入的方法 因?yàn)槊看问菍⑿陆Y(jié)點(diǎn)插入到鏈表的尾部 所以需加入一個(gè)尾指針r用來(lái)始終指向鏈表中的尾結(jié)點(diǎn) 以便能夠?qū)⑿陆Y(jié)點(diǎn)插入到鏈表的尾部 如下圖所示 48 在單鏈表的尾部插入結(jié)點(diǎn)建立單鏈表 操作步驟 一 建立一個(gè) 空表 尾指針指向頭結(jié)點(diǎn) 二 輸入數(shù)據(jù)元素a1 建立結(jié)點(diǎn) 插入在尾指針的后面 尾指針指向a1結(jié)點(diǎn) 三 輸入數(shù)據(jù)元素a2 建立結(jié)點(diǎn) 插入在尾指針的后面 尾指針指向a2結(jié)點(diǎn) 四 依次類推 直至輸入an為止 voidCreateList L LinkList for依次插入n個(gè)數(shù)據(jù)元素 CreateList L 50 查找操作 1 按序號(hào)查找Get Linklist L i 算法思路 從鏈表的第一個(gè)元素結(jié)點(diǎn)起 判斷當(dāng)前結(jié)點(diǎn)是否是第i個(gè) 若是 則返回該結(jié)點(diǎn)的指針 否則繼續(xù)后一個(gè) 表結(jié)束為止 沒(méi)有第 個(gè)結(jié)點(diǎn)時(shí)返回空 51 intGetElem L LinkList inti ElemType 52 2 按值查找即定位Locate LinkList L e 算法思路 從鏈表的第一個(gè)元素結(jié)點(diǎn)起 判斷當(dāng)前結(jié)點(diǎn)其值是否等于e 若是 返回該結(jié)點(diǎn)的指針 否則繼續(xù)后一個(gè) 表結(jié)束為止 找不到時(shí)返回空 算法如下 LNode LocateElem L LinkListL ElemTypee p L next 初始化p指向第一個(gè)結(jié)點(diǎn)while p 53 插入 1 后插結(jié)點(diǎn) 設(shè)p指向單鏈表中某結(jié)點(diǎn) s指向待插入的值為x的新結(jié)點(diǎn) 將 s插入到 p的后面 操作如下 s next p next p next s p s 思考 Step1和2能互換么 54 intListInsert L LinkListL inti ElemTypee L為帶頭結(jié)點(diǎn)的單鏈表的頭指針 本算法 在鏈表中第i個(gè)結(jié)點(diǎn)之前插入新的元素e LinstInsert L p L j 0 while p i大于表長(zhǎng)或者小于1 s LinkList malloc sizeof LNode 生成新結(jié)點(diǎn)s data e s next p next p next s 插入returnOK 算法的時(shí)間復(fù)雜度為 O ListLength L 55 2 前插結(jié)點(diǎn) 設(shè) 指向鏈表中某結(jié)點(diǎn) 指向待插入的值為x的新結(jié)點(diǎn) 將 s插入到 p的前面 q L while q next p q q next s next q next q next s 先找到p的前驅(qū)結(jié)點(diǎn)再做插入 56 刪除設(shè)q指向單鏈表中某結(jié)點(diǎn) 刪除 q 首先要找到 q的前驅(qū)結(jié)點(diǎn) p 然后完成指針的操作即可 操作由下列語(yǔ)句實(shí)現(xiàn) p next q next free q 思考 省略free q 語(yǔ)句行不行 57 StatusListDelete L LinkListL inti ElemType e 刪除以L為頭指針 帶頭結(jié)點(diǎn) 的單鏈表中第i個(gè)結(jié)點(diǎn) ListDelete L 算法的時(shí)間復(fù)雜度為 O ListLength L p L j 0 while p next 刪除位置不合理 q p next p next q next 刪除并釋放結(jié)點(diǎn)e q data free q returnOK 58 voidClearList ClearList free p 逐個(gè)釋放每個(gè)結(jié)點(diǎn) 算法時(shí)間復(fù)雜度 O ListLength L ClearList 59 鏈表插入刪除實(shí)例 兩個(gè)鏈表的歸并 教材P31例 算法要求 已知 線性表A B 分別由單鏈表La Lb存儲(chǔ) 其中數(shù)據(jù)元素按值非遞減有序排列 要求 將A B歸并為一個(gè)新的線性表C C的數(shù)據(jù)元素仍按值非遞減排列 設(shè)線性表C由單鏈表Lc存儲(chǔ) 假設(shè) A 3 5 8 11 B 2 6 8 9 11 預(yù)測(cè) 合并后將C 2 3 5 6 8 8 9 11 11 60 鏈表示意圖 頭結(jié)點(diǎn) 61 算法設(shè)計(jì) 算法主要包括搜索 比較 插入三個(gè)操作 搜索 需要設(shè)立三個(gè)指針來(lái)指向La Lb和Lc鏈表 比較 比較La和Lb表中結(jié)點(diǎn)數(shù)據(jù)的大小 插入 將La和Lb表中數(shù)據(jù)較小的結(jié)點(diǎn)插入新鏈表Lc 請(qǐng)注意鏈表的特點(diǎn) 僅改變指針便可實(shí)現(xiàn)數(shù)據(jù)的移動(dòng) 即 數(shù)據(jù)不動(dòng) 指針動(dòng) 62 Pa Pb用于搜索La和Lb Pc指向新鏈表當(dāng)前結(jié)點(diǎn) 歸并過(guò)程示意如下 63 算法實(shí)現(xiàn) VoidMergeList L LinkList La LinkList Lb LinkList Lc 按值排序的單鏈表LA LB 歸并為L(zhǎng)C后也按值排序 free Lb 釋放Lb的頭結(jié)點(diǎn) MergeList L pc next pa pa pb 插入剩余段 while papb pb next pa La next pb Lb next Lc pc La 初始化 是條件運(yùn)算符 為真則取第1項(xiàng) Lc用的是La的頭指針 只有Lb頭指針空閑 64 思考 1 不用Lc 直接把La表插到Lb表中 或者把Lb表插到La表中 該如何編程 2 要求歸并后的表中不能有重復(fù)的數(shù)據(jù)元素 該如何編程 應(yīng)能完成作業(yè)2 23 65 教案瀏覽或下載請(qǐng)到 數(shù)據(jù)結(jié)構(gòu)網(wǎng)上課堂 網(wǎng)站 網(wǎng)址是 第2章作業(yè)請(qǐng)全體同學(xué)周四上課時(shí)交 配套習(xí)題集的2 2 2 4 2 5 2 6 2 7 2 8 2 9 2 11 2 19 2 212 22題 建議獨(dú)立完成輔導(dǎo)材料 第2章自測(cè)題 66 內(nèi)容回顧 線性表的邏輯結(jié)構(gòu)順序表的表示和基本操作的實(shí)現(xiàn)單鏈表的表示和基本操作的實(shí)現(xiàn) 67 主要內(nèi)容 循環(huán)鏈表雙向鏈表鏈表的典型習(xí)題應(yīng)用 一元多項(xiàng)式的表示及相加 68 討論1 鏈表能不能首尾相連 怎樣實(shí)現(xiàn) 答 能 只要將表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)即可 P next head 這種形成環(huán)路的鏈表稱為循環(huán)鏈表 其它鏈表形式 69 循環(huán)鏈表是表中最后一個(gè)結(jié)點(diǎn)的指針指向頭結(jié)點(diǎn) 使鏈表構(gòu)成環(huán)狀 特點(diǎn) 從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其他結(jié)點(diǎn) 提高查找效率 循環(huán)鏈表 circularlinkedlist 70 循環(huán)鏈表與單鏈表循環(huán)條件不同 操作與單鏈表基本一致 循環(huán)條件不同 單鏈表 p next NULL循環(huán)鏈表 p next H 71 循環(huán)鏈表中設(shè)立尾指針 找到第一個(gè)結(jié)點(diǎn) rear next next 和最后一個(gè)結(jié)點(diǎn) rear 均需要常數(shù)時(shí)間 72 linklistconnect linklist 例 在單循環(huán)鏈表上實(shí)現(xiàn)將兩個(gè)線性表 a1 a2 a3 an 和 b1 b2 b3 bn 鏈接成一個(gè)線性表的運(yùn)算 73 討論2 單鏈表只能查找結(jié)點(diǎn)的直接后繼 能不能查找直接前驅(qū) 如何實(shí)現(xiàn) 答 能 只要把單鏈表再多開(kāi)一個(gè)指針域即可 例如用 next和 prior 這種有兩個(gè)指針的鏈表稱為雙向鏈表 其特點(diǎn)是可以雙向查找表中結(jié)點(diǎn) 74 雙向循環(huán)鏈表的對(duì)稱性 P next prior p p prior next 很明顯 在雙向鏈表中不僅能直接找到結(jié)點(diǎn)的前驅(qū) 也能即刻找到結(jié)點(diǎn)的后繼 75 雙向鏈表的操作特點(diǎn) 查詢 和單鏈表相同 插入 和 刪除 時(shí)需要同時(shí)修改兩個(gè)方向上的指針 76 雙向鏈表中結(jié)點(diǎn)的插入 設(shè)p指向雙向鏈表中某結(jié)點(diǎn) s指向待插入的值為x的新結(jié)點(diǎn) 將 s插入到 p的前面 操作如下 s prior p prior p prior next s s next p p prior s 77 雙向鏈表中結(jié)點(diǎn)的刪除 設(shè)p指向雙向鏈表中某結(jié)點(diǎn) 刪除 p 操作如下 p prior next p next p next prior p prior free p 78 鏈表的運(yùn)算效率分析 1 查找因線性鏈表只能順序存取 即在查找時(shí)要從頭指針找起 查找的時(shí)間復(fù)雜度為O n 2 插入和刪除因線性鏈表不需要移動(dòng)元素 只要修改指針 一般情況下時(shí)間復(fù)雜度為O 1 但是 如果要在單鏈表中進(jìn)行前插或刪除操作 由于要從頭查找前驅(qū)結(jié)點(diǎn) 所耗時(shí)間復(fù)雜度為O n 空間效率分析 鏈表中每個(gè)結(jié)點(diǎn)都要增加一個(gè)指針空間 相當(dāng)于總共增加了n個(gè)整型變量 空間復(fù)雜度為O n 79 例 已知單鏈表L 寫(xiě)一算法 刪除其重復(fù)結(jié)點(diǎn) 即實(shí)現(xiàn)如下圖2 23的操作 算法思路 用指針p指向第一個(gè)數(shù)據(jù)結(jié)點(diǎn) 從它的后繼結(jié)點(diǎn)開(kāi)始到表的結(jié)束 找與其值相同的結(jié)點(diǎn)并刪除之 p指向下一個(gè) 依此類推 p指向最后結(jié)點(diǎn)時(shí)算法結(jié)束 80 voidpur LinkList LinkListH LNode p q r p H next p指向第一個(gè)結(jié)點(diǎn) if p NULL return while p next q p while q next if q next data p data r q next q next r next free r elseq q next p p next 該算法的時(shí)間性能為O n2 算法 81 例 線性表 a1 a2 am b1 b2 bn 改變成 b1 b2 bn a1 a2 am 解題分析 因?yàn)閷?duì)鏈表來(lái)說(shuō) 插入 和 刪除 僅需修改指針即可完成 并且由于前m個(gè)元素之間和后n個(gè)元素之間的鏈接關(guān)系分別都不需要改變 則算法的實(shí)際操作為 1 從鏈表中刪除 a1 a2