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

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