《數(shù)據(jù)結(jié)構(gòu)課件、代碼》第2章 線性表.ppt

第2章線性表 二 張成文北京郵電大學(xué)計算機學(xué)院 主要內(nèi)容 2 7線性表的鏈式存儲結(jié)構(gòu)表示2 8單鏈表2 9循環(huán)鏈表2 10雙向鏈表2 11各種鏈式存儲結(jié)構(gòu)的比較2 12順序表與鏈表的比較2 13小結(jié) 線性表的鏈式存儲結(jié)構(gòu)表示 結(jié)點 Node 既要存儲線性表的每個數(shù)據(jù)元素值 又要存儲指示其后繼結(jié)點的地址 或位置 信息 以表示結(jié)點間的邏輯關(guān)系 這兩部分信息組成的存儲映象叫做結(jié)點 Node 1線性表的鏈式存儲結(jié)構(gòu)表示 讓每個存儲結(jié)點都包含兩部分 數(shù)據(jù)域和指針域 數(shù)據(jù)域 存儲元素的值 指針域 存儲直接后繼或直接前驅(qū)元素的存儲地址 設(shè)計思想 犧牲空間效率換取時間效率 其結(jié)點在存儲器中的位置是隨意的 即邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰 如何實現(xiàn) 通過指針來實現(xiàn) 鏈式存儲結(jié)構(gòu)特點 a1 a2 a3 與鏈式存儲有關(guān)的術(shù)語 1 結(jié)點 數(shù)據(jù)元素的存儲映像 由數(shù)據(jù)域和指針域兩部分組成 2 鏈表 n個結(jié)點由指針鏈組成一個鏈表 它是線性表的鏈式存儲映像 稱為線性表的鏈式存儲結(jié)構(gòu) 3 單鏈表 雙向鏈表 循環(huán)鏈表 結(jié)點只有一個指針域的鏈表 稱為單鏈表或線性鏈表 有兩個指針域 直接前驅(qū)和直接后繼 的鏈表 稱為雙向鏈表 首尾相接的鏈表稱為循環(huán)鏈表 循環(huán)鏈表示意圖 head 4 頭指針 頭結(jié)點和首元結(jié)點的區(qū)別 示意圖如下 頭指針 頭結(jié)點 首元結(jié)點 頭指針是指向鏈表中第一個結(jié)點 或為頭結(jié)點或為首元結(jié)點 的指針 頭結(jié)點是在鏈表的首元結(jié)點之前附設(shè)的一個結(jié)點 數(shù)據(jù)域內(nèi)只放空表標志和表長等信息 它不計入表長度 首元結(jié)點是指鏈表中存儲線性表第一個數(shù)據(jù)元素a1的結(jié)點 下面舉例說明 頭指針L 頭指針L 頭結(jié)點 首元結(jié)點 首元結(jié)點 空表 L NULL L 1264 1264 4016 4016 頭結(jié)點的作用 插入和刪除第一個數(shù)據(jù)元素時不必對頭指針進行特殊處理 與鏈式存儲有關(guān)的術(shù)語 一個線性表的邏輯結(jié)構(gòu)為 ZHAO QIAN SUN LI ZHOU WU ZHENG WANG 其存儲結(jié)構(gòu)用單鏈表表示如下 請問其頭指針的值是多少 例1 答 頭指針是指向鏈表中第一個結(jié)點的指針 因此關(guān)鍵是要尋找第一個結(jié)點的地址 31 稱 頭指針H的值是31 例2 線性表具有兩種存儲方式 即順序方式和鏈接方式 現(xiàn)有一個具有五個元素的線性表L 23 17 47 05 31 若它以鏈接方式存儲在下列100 119號地址空間中 每個結(jié)點由數(shù)據(jù) 占2個字節(jié) 和指針 占2個字節(jié) 組成 如下圖所示 其中指針X Y Z的值分別為多少 該線性表的首結(jié)點起始地址為多少 末結(jié)點的起始地址為多少 100 119 答 X Y Z 首址 末址 104 108 116 112 116 NULL 0 100 108 112 單鏈表 單鏈表 鏈表中的每個結(jié)點只有一個指針域 我們將這種鏈表稱為單鏈表 單鏈表包括兩個域 數(shù)據(jù)域用來存儲結(jié)點的值 指針域用來存儲數(shù)據(jù)元素的直接后繼的地址 或位置 從鏈表的整體結(jié)構(gòu)上看 鏈表可以是空鏈 也可以由一個或多個結(jié)點組成 每條鏈有一個入口的頭結(jié)點 該結(jié)點僅指示鏈中第一個結(jié)點的地址 如是空鏈 則可表示為 0 或 它類似于一個常量 每條鏈的最后一個結(jié)點的鏈指針為 0 也可用 作為鏈的結(jié)束標志 下圖給出了鏈表的示意形式 圖 a 中有一個頭結(jié)點和具有A B C D數(shù)據(jù)元素的鏈 圖 b 所示為線性鏈表的一般表示 結(jié)點與結(jié)點之間用箭頭鏈接 單鏈表 鏈表圖示 a 鏈表的圖示 b 鏈表的一般表示 以線性表中第一個數(shù)據(jù)元素的存儲地址作為線性表的地址 稱作線性表的頭指針 頭結(jié)點 頭指針 頭指針 有時為了操作方便 在第一個結(jié)點之前虛加一個 頭結(jié)點 以指向頭結(jié)點的指針為鏈表的頭指針 空指針 線性表為空表時 頭結(jié)點的指針域為空 討論 鏈表的數(shù)據(jù)元素有兩個域 不再是簡單數(shù)據(jù)類型 編程時該如何表示 因每個結(jié)點至少有兩個分量 且數(shù)據(jù)類型通常不一致 所以要采用結(jié)構(gòu)數(shù)據(jù)類型 答 以26個字母的鏈表為例 每個結(jié)點都有兩個分量 假設(shè)每個結(jié)點用變量node表示 結(jié)點指針用p表示 其中兩個分量分別用data和 next表示 該如何書寫 方式1 直接表示為node data a node next q方式2 p指向結(jié)點首地址 然后p data a p next q 方式3 p指向結(jié)點首地址 然后 p data a p next q 單鏈表的存儲結(jié)構(gòu)描述 typedefstructNode 結(jié)點類型定義 ElemTypedata structNode next Node LinkList LinkList為結(jié)構(gòu)指針類型 設(shè)p為指向鏈表的第i個元素的指針 則第i個元素的數(shù)據(jù)域?qū)憺?指針域?qū)憺?練習(xí) p data ai的值 p next ai 1的地址 鏈表不具備的特點是 A 可隨機訪問任何一個元素B 插入 刪除操作不需要移動元素C 無需事先估計存儲空間大小D 所需存儲空間與線性表長度成正比 靜態(tài)鏈表用數(shù)組模擬可利用空間表 0123456789381 16cur 游標 a2a1a4a3data defineMAXSIZE10 鏈表的最大長度typedefstruct ElemTypedata intcur componet SLinkList MAXSIZE 第1個元素的下標 SLinkList 0 cur 帶頭結(jié)點的單鏈表上的基本運算 1建立單鏈表2單鏈表查找3單鏈表插入4單鏈表刪除第i個結(jié)點 建立單鏈表 1 頭插法建表 逆序 操作步驟 建立一個 空表 輸入數(shù)據(jù)元素an 建立結(jié)點并插入 輸入數(shù)據(jù)元素an 1 建立結(jié)點并插入 an an 1 依次類推 直至輸入a1為止 頭插法建表算法 LinklistCreateFromHead LinkListL Node s intflag 1 標志flag初值為1L Linklist malloc sizeof Node 分配頭結(jié)點L next NULL while flag 輸入 時 flag置0 建表結(jié)束 c getchar if c 為新結(jié)點分配存儲空間 s Node malloc sizeof Node s data c s next L next L next s 鏈接elseflag 0 returnL 2 尾插法建表 設(shè)尾指針r建立一個 空表 r指向頭結(jié)點 輸入數(shù)據(jù)元素C1 建立結(jié)點并鏈接 r指向該結(jié)點 輸入數(shù)據(jù)元素C2 建立結(jié)點并鏈接 r指向該結(jié)點 輸入數(shù)據(jù)元素Cn 建立結(jié)點并鏈接 r指向該結(jié)點 尾插法建表算法 LinklistCreateFromTail 新結(jié)點加到鏈表末尾 LinkListL Node r s intflag 1 flag初值L Node malloc sizeof Node 分配頭結(jié)點L next NULL r L r始終指向鏈表的表尾while flag 輸入 時flag為0 建表結(jié)束 c getchar if c s Node malloc sizeof Node s data c r next s r s 鏈接else flag 0 r next NULL returnL 單鏈表查找 1 按序號查找算法描述 設(shè)帶頭結(jié)點的單鏈表的長度為n 要查找表中第i個結(jié)點 則需要從單鏈表的頭指針L出發(fā) 從頭結(jié)點 L next 開始順著鏈域掃描 用指針p指向當前掃描到的結(jié)點 初值指向頭結(jié)點 p L 用j做記數(shù)器 累計當前掃描過的結(jié)點數(shù) 初值為0 當j i時 指針p所指的結(jié)點就是要找的第i個結(jié)點 算法實現(xiàn) 算法演示 線性表的操作Get L i 在單鏈表中i 3時 Get的實現(xiàn)過程 j 1 2 3 P data 30 因此 查找第i個數(shù)據(jù)元素的基本操作為 移動指針 比較j和i 令指針p始終指向線性表中第j個數(shù)據(jù)元素 單鏈表是一種順序存取的結(jié)構(gòu) 為找第i個數(shù)據(jù)元素 必須先找到第i 1個數(shù)據(jù)元素 按序號查找算法實現(xiàn) 找第i個結(jié)點 找到返回指向它的指針 否則返回空Node Get LinkListL inti Node p p L j 0 從頭結(jié)點開始掃描while p next NULL jnext j 掃描下一結(jié)點 if i j returnp 找到了第i個結(jié)點elsereturnNULL 找不到 i 0或i n 算法時間復(fù)雜度為 O Length L 2 按值查找算法描述 按值查找是指在單鏈表中查找是否有結(jié)點值等于e的結(jié)點 若有的話 則返回首次找到的其值為e的結(jié)點的存儲位置 否則返回NULL 查找過程從單鏈表的頭指針指向的頭結(jié)點出發(fā) 順著鏈逐個將結(jié)點的值和給定值e作比較 算法實現(xiàn) 算法演示 按值查找算法實現(xiàn) 查找其結(jié)點值等于key的結(jié)點 若找到則返回該結(jié)點的位置p 否則返回NULL Node Locate LinkListL ElemTypekey Node p p L next 從表中第一個結(jié)點比較while p NULL if p data key p p next elsebreak 找到結(jié)點key 退出循環(huán)returnp 算法時間復(fù)雜度為 O Length L 3 單鏈表插入操作InsList L i e 的實現(xiàn) 有序?qū)Ω淖優(yōu)楹?可見 插入結(jié)點需要修改第i 1個結(jié)點的指針和新結(jié)點的指針 在單鏈表第i個結(jié)點之前插入結(jié)點的步驟為 1 找到單鏈表的第i 1個結(jié)點并由指針pre指示 2 然后申請一個新結(jié)點并由指針s指示 3 將pre指示結(jié)點的指針值賦給s指示結(jié)點的指針域 將第i個結(jié)點鏈接到新結(jié)點上 4 然后修改pre指示結(jié)點的指針域 使它等于s 新結(jié)點鏈接到第i 1個結(jié)點上 單鏈表插入 intInsList LinkListL inti ElemTypee 在單鏈表L第i個結(jié)點前插入值為e的新結(jié)點Node pre s pre L intk 0 先找到第i 1個結(jié)點的存儲位置 讓Pre指向它while pre NULL 算法時間復(fù)雜度為 O Length L s Node malloc sizeof Node 申請新結(jié)點s data e 將e賦給s的數(shù)據(jù)域s next pre next pre next s 鏈接 如下圖所示的是鏈表插入前 后的邏輯狀態(tài) 從圖中可以看出 要插入一個結(jié)點 首先要從空間表中取一個空結(jié)點k 使得q結(jié)點 前趨結(jié)點的地址 的指針指向k k結(jié)點的指針指向p 存儲ai值的結(jié)點地址 同時把數(shù)據(jù)x存入k 即q next k k next p 鏈表插入邏輯示意圖 a 插入前 b 插入后 在鏈表的插入操作中 結(jié)點插入的位置可能有四種情況 下面分別加以介紹 設(shè)Head是鏈表入口或表頭 x是插入結(jié)點的存儲地址 1 原來鏈表為空表 即Head NULL 則插入結(jié)點為表首結(jié)點 表示為Head x x next NULL 2 插入位置在表中第一個結(jié)點Head之前 則插入結(jié)點為新的表頭 表示為x next Head Head x 3 插入位置在表的中間 為q結(jié)點之后 p結(jié)點之前 表示為q next x x next p 4 插入位置在鏈尾 即新結(jié)點x作為原表尾結(jié)點p之后的新表尾 表示為x next p next p next x 或p next x x next NULL 單鏈表刪除第i個結(jié)點操作為 找到線性表中第i 1個結(jié)點 p 修改其指針域讓它指向第i 1個結(jié)點 釋放第i個結(jié)點的空間 r p next p next r next free r p r intDelList LinkListL inti ElemType e 刪除單鏈表L中第i個元素 并保存其值到變量 e中 Node p r p L intk 0 while p next NULL 算法的時間復(fù)雜度為 O Length L 鏈表刪除的邏輯示意圖 a 刪除前 b 刪除后 從上圖中可以看出 要刪除某一個結(jié)點 必須知道被刪除結(jié)點的前趨結(jié)點 設(shè)被刪除結(jié)點的地址為s s的前趨結(jié)點為q s的后繼結(jié)點為p 則被刪除的基本操作步驟為q next p 或q next s next 刪除操作和插入操作相同 即在鏈表中搜索到被刪除的結(jié)點 修改相應(yīng)的指針 同時把被刪除的結(jié)點通過調(diào)用free x 將該結(jié)點的空間送空間表 根據(jù)被刪除結(jié)點在鏈表中的位置 刪除操作有如下四種情況 1 鏈表中只有一個結(jié)點 該結(jié)點就是被刪除的結(jié)點 其操作為Head NULL 或Head Head next 2 被刪除的結(jié)點是鏈中第一個結(jié)點 其操作為Head Head next 3 被刪除的結(jié)點在鏈的中間 其中刪除結(jié)點的地址為p 前趨結(jié)點的地址為q 其操作為q next p next 4 被刪除的結(jié)點在鏈尾 其中刪除結(jié)點的地址為p 前趨結(jié)點的地址為q 其操作為q next NULL 或q next p next 下圖給出了線性表刪除算法的框圖 線性鏈表刪除算法框圖 刪除算法 DELETE head key 在head為入口的鏈表中刪除值為key的結(jié)點 i head w i 設(shè)置前趨結(jié)點的地址 while i NULL i data key w i i i next 查找刪除結(jié)點的位置 if i NULL printf 無此結(jié)點 return else if head i head i next 刪除頭結(jié)點 elsew next i next 刪除鏈中間和鏈尾結(jié)點 free i 用上述定義的單鏈表實現(xiàn)線性表的操作時 存在的問題 改進鏈表的設(shè)置 1 單鏈表的表長是一個隱含的值 1 增加表長 表尾指針和當前位置指針 2 在單鏈表的最后一個元素之后插入元素時 需遍歷整個鏈表 3 在鏈表中 元素的 位序 概念淡化 結(jié)點的 位置 概念加強 2 將基本操作中的 位序i 改變?yōu)?指針p 3循環(huán)鏈表 最后一個結(jié)點的指針域的指針又指回第一個結(jié)點 或頭結(jié)點 的鏈表 和單鏈表的差別 判別鏈表中尾結(jié)點的條件不再是 后繼指針是否為空 而是 后繼指針是否為頭指針 帶頭結(jié)點的循環(huán)單鏈表示意圖 通過查詢 確定關(guān)鍵字值KEY不在鏈中 該結(jié)點插入的位置和插入的操作有如下幾種情況 1 若表空 Head NULL 則插入結(jié)點后是只有一個結(jié)點的環(huán)鏈表 2 若表非空 則分為三種情況 插入的位置是在第一個結(jié)點 即原表的第一個結(jié)點成為結(jié)點插入后新表的第二個結(jié)點 同時為了保持循環(huán)鏈表的結(jié)構(gòu)特征 在形成新的入口后 鏈表中最末一個結(jié)點的鏈指針應(yīng)修正指向新的入口結(jié)點 循環(huán)鏈表的插入操作 插入的位置是在最末一個結(jié)點之后 那么 最末一個結(jié)點的指針指向插入的結(jié)點 插入結(jié)點的指針仍指向首結(jié)點 插入的位置是在鏈的中間 那么可通過插入位置的前趨結(jié)點的指針 完成新結(jié)點的插入 下圖所示為四種插入操作的示意圖 循環(huán)有序鏈表的插入操作示意圖 下圖給出了循環(huán)鏈表刪除關(guān)鍵字值為KEY的結(jié)點的算法框圖 循環(huán)鏈表的刪除操作 循環(huán)鏈表刪除算法框圖 必須注意 在循環(huán)鏈表中 要充分考慮到可能出現(xiàn)被刪除結(jié)點位置不同的各個邊界條件 若被刪除結(jié)點在鏈首 則必須修改入口Head 而且還要考慮到鏈表中最末一個記錄的指針要指向結(jié)點刪除后的新入口 該情況的操作示意圖如下圖所示 特殊情況下 被刪除結(jié)點是第一個且僅只有這一個結(jié)點 那么循環(huán)鏈表入口因設(shè)置為空 Head NULL 其他情況與單鏈表的刪除結(jié)點的算法相似 循環(huán)鏈表刪除首結(jié)點 a 刪除結(jié)點之前 b 刪除結(jié)點之后 例有兩個帶頭結(jié)點的循環(huán)單鏈表LA LB 編寫算法 將兩個循環(huán)單鏈表合并為一個循環(huán)單鏈表 其頭指針為LA 算法思想 先找到兩個鏈表的尾 并分別由指針p q指向它們 然后將第一個鏈表的尾與第二個表的第一個結(jié)點鏈接起來 并修改第二個表的尾q 使它的鏈域指向第一個表的頭結(jié)點 LinkListmerge 1 LinkListLA LinkListLB 此算法將兩個循環(huán)單鏈表的首尾連接起來 Node p q p LA q LB while p next LA p p next 找到LA的表尾while q next LB q q next 找到LB的表尾p next LB next 使LA尾指針指向LB第1個結(jié)點q next LA 使LB的尾指針指向表LA的頭結(jié)點free LB 釋放LB的頭結(jié)點空間return LA 4雙向鏈表 typedefstructNode 結(jié)點類型定義 ElemTypedata structNode next structNode prior Node LinkList LinkList為結(jié)構(gòu)指針類型 雙向鏈表的結(jié)構(gòu) 雙向鏈表的結(jié)構(gòu)有以下特點 1 若Head為空 NULL 則雙向鏈表為空 2 在雙向鏈表中 若結(jié)點i有i Lnext NULL則該結(jié)點是鏈的第一個結(jié)點 若結(jié)點i有i Lnext i Rnext NULL則該結(jié)點i是鏈的第一個結(jié)點且該鏈僅有這個結(jié)點i 3 在雙鏈表中 若結(jié)點i有i Rnext NULL則該結(jié)點是鏈的最末一個結(jié)點 4 在雙向鏈表中 若結(jié)點i是表中任意結(jié)點的地址 則該結(jié)點的前趨結(jié)點是i Lnext 后繼結(jié)點的地址是i Rnext 對結(jié)點i也可以表示為i i Rnext Lnext i Lnext Rnext這個表達式非常直觀地反映了雙向鏈表結(jié)構(gòu)的本質(zhì)特點 即無論是沿著表向前 還是向后都同樣方便 雙向鏈表的操作特點 查詢 和單鏈表相同 可增加一種從后向前的 查詢 方式 插入 和 刪除 時需要同時修改兩個方向上的指針 s next p next p next s s next prior s s prior p s 插入 刪除 q p next p next q next p next prior p free q p 雙向鏈表刪除操作是否可不用工作指針q q 刪除 p next p next next free p next prior p next prior p p 空表 非空表 he he 雙向循環(huán)鏈表 單鏈表和循環(huán)單鏈表均只有一個鏈指針next 指向后繼結(jié)點 而雙向鏈表有兩個指針 即向前指針Lnext和向后指針Rnext 單鏈表結(jié)構(gòu)的查詢只能從鏈表入口開始 按結(jié)點的鏈指針逐個查詢 直至結(jié)束 循環(huán)單鏈表