數(shù)據(jù)結(jié)構(gòu)講解講義課件

第二章線性表 2 1線性表的類型定義2 2線性表的順序表示和實(shí)現(xiàn)2 3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)2 3 1線性鏈表2 3 2循環(huán)鏈表2 3 3雙向鏈表2 4一元多項(xiàng)式的表示和相加 2 1線性表的類型定義 一 線性表的定義線性表是一個(gè)由n n 0 個(gè)同類型的數(shù)據(jù)元素a1 a2 an組成的有限序列 通常記為 a1 a2 ai 1 ai ai 1 an 其中 數(shù)據(jù)元素的個(gè)數(shù)n為表的長(zhǎng)度 當(dāng)n 0時(shí)稱為空表 這里的數(shù)據(jù)元素ai 1 i n 表示線性表中第i個(gè)數(shù)據(jù)元素 它可以是任意類型 2 1線性表的類型定義 例1 26個(gè)英文字母組成的字母表 A B C Z 是一個(gè)長(zhǎng)度為26的線性表 例2 某公司2000年每月產(chǎn)值表 單位 萬(wàn)元 400 420 500 600 650 是一個(gè)長(zhǎng)度為12的線性表 上述兩例中的每一個(gè)數(shù)據(jù)元素都是不可分割的 在一些復(fù)雜的線性表中 每一個(gè)數(shù)據(jù)元素又可以由若干個(gè)數(shù)據(jù)項(xiàng)組成 2 1線性表的類型定義 例3 下圖為10個(gè)學(xué)生的成績(jī)表 它也是一個(gè)線性表 該線性表的數(shù)據(jù)元素類型為結(jié)構(gòu)體 2 1線性表的類型定義 二 線性表的邏輯特征在非空的線性表中 有且僅有一個(gè)被稱作 第一個(gè) 的數(shù)據(jù)元素a1 它沒(méi)有直接前趨 而僅有一個(gè)直接后繼a2 有且僅有一個(gè)被稱作 最后一個(gè) 的數(shù)據(jù)元素an 它沒(méi)有直接后繼 而僅有一個(gè)直接前趨an 1 其余的數(shù)據(jù)元素ai 2 i n 1 都有且僅有一個(gè)直接前趨ai 1和一個(gè)直接后繼ai 1 線性表是一種典型的線性結(jié)構(gòu) 2 1線性表的類型定義 三 線性表的形式定義L List D R D ai ai ElemSet i 1 2 nn 0 R ai 1 ai D i 2 n ElemSet為某一數(shù)據(jù)對(duì)象集 即數(shù)據(jù)元素的集合 n為線性表的長(zhǎng)度 2 1線性表的類型定義 四 線性表的主要操作 庫(kù)函數(shù)中沒(méi)有 需要用戶自己實(shí)現(xiàn) 1 Initiate L 初始化 構(gòu)造一個(gè)空的線性表L 2 Insert L i x 插入 在給定的線性表L中 在第i個(gè)元素之前插入數(shù)據(jù)元素x 線性表L長(zhǎng)度加1 3 Delete L i 刪除 在給定的線性表L中 刪除第i個(gè)元素 線性表L的長(zhǎng)度減1 4 Locate L x 查找定位 對(duì)給定的值x 若線性表L中存在一個(gè)元素ai與之相等 則返回該元素在線性表中的位置的序號(hào)i 否則返回 1 2 1線性表的類型定義 5 Length L 求長(zhǎng)度 對(duì)給定的線性表L 返回線性表L的數(shù)據(jù)元素的個(gè)數(shù) 6 Get L i e 存取 對(duì)給定的線性表L 返回第i 1 i Length L 個(gè)數(shù)據(jù)元素e 7 Traverse L 遍歷 對(duì)給定的線性表L 依次輸出L的每一個(gè)數(shù)據(jù)元素 例 假設(shè)利用兩個(gè)線性表LA和LB分別表示兩個(gè)集合A和B 要求一個(gè)新的集合A A B voidunion List la中不存在和e相同的數(shù)據(jù)元素 則插入之 時(shí)間復(fù)雜度O la length lb length 例 已知線性表LA和LB中的數(shù)據(jù)元素按值非遞減有序排列 要求將LA和LB歸并為一個(gè)新的線性表LC 且LC中的數(shù)據(jù)元素仍按值非遞減有序排列 voidMergeList Listla Listlb List 時(shí)間復(fù)雜度O la length lb length 2 2線性表的順序表示和實(shí)現(xiàn) 一 線性表的順序存儲(chǔ)表示在計(jì)算機(jī)中 用一段地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的各個(gè)數(shù)據(jù)元素 稱作線性表的順序存儲(chǔ)結(jié)構(gòu) 用這種方法存儲(chǔ)的線性表簡(jiǎn)稱順序表 線性表的順序存儲(chǔ)結(jié)構(gòu)中的特點(diǎn)是 其邏輯關(guān)系上前后相鄰的兩個(gè)數(shù)據(jù)元素 在計(jì)算機(jī)中的存儲(chǔ)位置也必定是相鄰的 即ai 1一定存在ai的下一個(gè)存儲(chǔ)單元中 線性表的順序存儲(chǔ)結(jié)構(gòu)示意圖如下 2 2線性表的順序表示和實(shí)現(xiàn) 線性表的順序存儲(chǔ)結(jié)構(gòu)示意圖 2 2線性表的順序表示和實(shí)現(xiàn) 由于線性表中每個(gè)數(shù)據(jù)元素的類型相同 占用的內(nèi)存空間也相同 因此 假設(shè)線性表中的第一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址為L(zhǎng)oc a1 設(shè)每一個(gè)數(shù)據(jù)元素占用d字節(jié)的內(nèi)存空間 則線性表中第i個(gè)元素ai在這段連續(xù)的存儲(chǔ)空間中的存儲(chǔ)地址為 Loc ai Loc a1 i 1 d 2 2線性表的順序表示和實(shí)現(xiàn) 1 線性表的靜態(tài)分配順序存儲(chǔ)結(jié)構(gòu) defineMAXNUM100 定義順序表最大元素個(gè)數(shù) ElemTypeList MAXNUM 定義順序表List 注意 ElemType代表線性表元素的類型 具體編程實(shí)現(xiàn)是要用int或char或float或者struct等類型來(lái)代替 intlength 定義線性表表長(zhǎng) 我們還可將數(shù)組和表長(zhǎng)封裝在一個(gè)結(jié)構(gòu)體中 structL list ElemTypeList MAXNUM 定義數(shù)組域 intlength 定義表長(zhǎng)域 2 2線性表的順序表示和實(shí)現(xiàn) 2 線性表的動(dòng)態(tài)分配順序存儲(chǔ)結(jié)構(gòu) defineList Init Size100 defineListIncrement10typedefstructL List ElemType elem 存儲(chǔ)空間基地址intlength 表長(zhǎng)intlistsize 當(dāng)前分配的存儲(chǔ)容量 SqList SqListL 等價(jià)于structL ListL 2 2線性表的順序表示和實(shí)現(xiàn) 分配存儲(chǔ)空間函數(shù)malloc malloc 函數(shù)的原型為 void malloc unsignedintsize 函數(shù)的作用是在內(nèi)存自由空間開辟一塊大小為size字節(jié)的空間 并將此存儲(chǔ)空間的起始地址作為函數(shù)值帶回 例如 malloc 10 sizeof int 的結(jié)果是分配了一個(gè)長(zhǎng)度為20個(gè)字節(jié)的內(nèi)存空間 若系統(tǒng)設(shè)定的此內(nèi)存空間的起始地址為1800 則其返回值就為1800 2 2線性表的順序表示和實(shí)現(xiàn) 重新分配空間函數(shù)realloc 函數(shù)原型為 void realloc void ptr unsignedintsize 函數(shù)用于使已分配的空間改變大小 即重新分配 其作用是將ptr指向的存儲(chǔ)區(qū) 是原先用malloc函數(shù)分配的 大小改為size個(gè)字節(jié) 可以使原先的分配區(qū)擴(kuò)大也可以縮小 它的返回值是一個(gè)指針 即新的存儲(chǔ)區(qū)的首地址 2 2線性表的順序表示和實(shí)現(xiàn) 二 線性表 動(dòng)態(tài)分配順序存儲(chǔ) 的運(yùn)算1 構(gòu)造一個(gè)空線性表 申請(qǐng)連續(xù)的存儲(chǔ)空間 準(zhǔn)備存放線性表的各個(gè)數(shù)據(jù)元素 其算法如下 voidInitList Sq SqList L L elem ElemType malloc List Init Size sizeof ElemType if L elem Printf Mallocfail Trylater exit 0 L length 0 L listsize List Init Size 2 2線性表的順序表示和實(shí)現(xiàn) 2 順序表的查找算法在順序表中查找一個(gè)值為x的數(shù)據(jù)元素 從第一個(gè)元素開始 依次和x進(jìn)行比較 若找到就返回x的位置i 否則輸出無(wú)此元素 返回 1 算法實(shí)現(xiàn) intLocateList SqListL intx intj for j 0 j L length j if L elem j x returnj printf Nox return 1 2 2線性表的順序表示和實(shí)現(xiàn) 3 線性表的插入運(yùn)算線性表的插入運(yùn)算是指在表的第i 1 i n 1 個(gè)元素之前 插入一個(gè)新元素x 使長(zhǎng)度為n的線性表 a1 ai 1 ai an 0i 2i 1n 1變成長(zhǎng)度為n 1的線性表 a1 ai 1 x ai an 2 2線性表的順序表示和實(shí)現(xiàn) 其算法如下 voidInsertList Sqlist L ElemTypex inti intj ElemType newbase NULL if iL length 1 printf Positionerror exit 0 if L length L listsize newbase ElemType realloc L elem L listsize ListIncrement sizeof ElemType if newbase printf failed exit 0 L elem newbase L listsize ListIncrement for j L length 1 j i 1 j L elem j 1 L elem j L elem i 1 x L length 考慮移動(dòng)元素的平均情況 假設(shè)在第i個(gè)元素之前插入的概率為 則在長(zhǎng)度為n的線性表中插入一個(gè)元素所需移動(dòng)元素次數(shù)的期望值為 若假定在線性表中任何一個(gè)位置上進(jìn)行插入的概率都是相等的 則移動(dòng)元素的期望值為 2 2線性表的順序表示和實(shí)現(xiàn) 4 線性表的刪除運(yùn)算線性表的刪除運(yùn)算是指將線性表的第i個(gè) 1 i n 數(shù)據(jù)元素刪除 使長(zhǎng)度為n的線性表 a1 ai 1 ai ai 1 an 0i 2i 1in 1變成長(zhǎng)度為n 1的線性表 a1 ai 1 ai 1 an 考慮移動(dòng)元素的平均情況 假設(shè)刪除第i個(gè)元素的概率為 則在長(zhǎng)度為n的線性表中刪除一個(gè)元素所需移動(dòng)元素次數(shù)的期望值為 若假定在線性表中任何一個(gè)位置上進(jìn)行刪除的概率都是相等的 則移動(dòng)元素的期望值為 2 2線性表的順序表示和實(shí)現(xiàn) 其算法如下 voidDeleteList Sqlist L inti intj if iL length printf Positionerror exit 0 for j i jlength 1 j L elem j 1 L elem j L length 2 2線性表的順序表示和實(shí)現(xiàn) 三 插入 刪除算法分析 插入 刪除算法的時(shí)間主要花費(fèi)在循環(huán)移動(dòng)元素的語(yǔ)句上 該語(yǔ)句的執(zhí)行次數(shù)不僅依賴于表的長(zhǎng)度 而且還與新元素插入或刪除的位置i有關(guān) 若線性表的表長(zhǎng)為n 具體情況如下 2 2線性表的順序表示和實(shí)現(xiàn) 順序表的查找算法在順序表中查找第一個(gè)值為x的數(shù)據(jù)元素 從第一個(gè)元素開始 依次和x進(jìn)行比較 若找到就返回x的位序 從1開始 i 否則輸出無(wú)此元素 返回0 算法實(shí)現(xiàn) intLocateList SqListL intx inti j for j 0 j L length j if L elem j x return i 1 printf Nox return0 2 2線性表的順序表示和實(shí)現(xiàn) 線性表的合并將兩個(gè)遞增有序的線性表合并為一個(gè)遞增有序的線性表 例如 設(shè)La 3 5 8 11 Lb 2 6 8 9 15 20 則 Lc 2 3 5 6 8 8 9 11 15 20 分析 Lc中的數(shù)據(jù)元素或者是La中的數(shù)據(jù)元素 或者是Lb中的數(shù)據(jù)元素 而La和Lb都是有序表 則只要先將Lc置為空表 然后將La和Lb中的元素逐個(gè)比較 按序插入到Lc中即可 因此 可設(shè)3個(gè)指針i j k i和j分別指向La和Lb中的當(dāng)前待比較的元素 k指向Lc表中當(dāng)前待放入元素的位置 若設(shè)i當(dāng)前所指的元素為a j當(dāng)前所指的元素為b 則當(dāng)前應(yīng)插入到Lc中的元素c為 當(dāng) 時(shí)c 當(dāng) 時(shí)c b 在i所指元素插入到Lc表后 i指針加1 在La表中后移 指向下一個(gè)待比較的元素 j指針操作類似 很顯然 指針i和j的初值均為0 2 2線性表的順序表示和實(shí)現(xiàn) voidmerge intLa intm intLb intn int Lc inti j k i 0 j 0 k 0 Lc int malloc m n sizeof int 初始化表Lc if Lc exit 0 while i m voidMergeList Sq SqListla SqListlb SqList 時(shí)間復(fù)雜度 O la length lb length 2 2線性表的順序表示和實(shí)現(xiàn) 四 順序表存儲(chǔ)結(jié)構(gòu)的特點(diǎn)任意數(shù)據(jù)元素的存儲(chǔ)地址都可由一個(gè)公式直接導(dǎo)出 因此順序存儲(chǔ)結(jié)構(gòu)的線性表可以隨機(jī)存取其中的任意元素 但是 順序存儲(chǔ)結(jié)構(gòu)也有一些不方便之處 主要表現(xiàn)在 1 數(shù)據(jù)元素最大個(gè)數(shù)需預(yù)先確定 需預(yù)先分配相應(yīng)的存儲(chǔ)空間 2 插入與刪除運(yùn)算的效率很低 為了保持線性表中的數(shù)據(jù)元素的順序 在插入操作和刪除操作時(shí)需移動(dòng)大量數(shù)據(jù) 2 3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn) 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是用一組任意的存儲(chǔ)單元 可以是連續(xù)的 也可以是不連續(xù)的 存儲(chǔ)線性表的數(shù)據(jù)元素 借助指針來(lái)指示元素之間一對(duì)一的線性關(guān)系 根據(jù)指針的個(gè)數(shù)以及最后一個(gè)結(jié)點(diǎn)的指針指向可以分為 單鏈表 雙向鏈表 循環(huán)鏈表等鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 一 單鏈表的定義為了表示每個(gè)數(shù)據(jù)元素ai與其后繼元素ai 1之間的邏輯關(guān)系 對(duì)數(shù)據(jù)元素ai來(lái)說(shuō) 除了需要存儲(chǔ)它本身的信息外 還需要存儲(chǔ)它的直接后繼元素的地址 這兩部分信息組成了數(shù)據(jù)元素ai在內(nèi)存中的存儲(chǔ)映象 存儲(chǔ)狀態(tài) 稱為結(jié)點(diǎn) 每個(gè)結(jié)點(diǎn)都有兩個(gè)域構(gòu)成 一個(gè)是存放數(shù)據(jù)元素值的域 稱為數(shù)據(jù)域 存儲(chǔ)直接后繼元素地址的域 稱為指針域 n個(gè)結(jié)點(diǎn)就鏈成了一個(gè)鏈表 若鏈表中的每個(gè)結(jié)點(diǎn)只包含一個(gè)指針域 最后一個(gè)結(jié)點(diǎn)的指針域指向NULL 就稱之為線性鏈表或單鏈表 舉例如下 2 3 1單鏈表 110 130135 160165170 200205 例1 線性表 bat cat eat fat hat jat lat mat 2 3 1單鏈表 bat cat eat mat head 例1的單鏈表可畫成下圖所示的形式 這就是單鏈表的邏輯示意圖head 由上可見 單鏈表可由頭指針唯一確定 因此單鏈表可以用頭指針的名字來(lái)命名 例如 若頭指針名是head 則把該單鏈表稱為單鏈表head 2 3 1單鏈表 有時(shí) 我們?cè)趩捂湵淼牡谝粋€(gè)結(jié)點(diǎn)之前附設(shè)一個(gè)結(jié)點(diǎn) 稱之為頭結(jié)點(diǎn) 頭結(jié)點(diǎn)的數(shù)據(jù)域可以不存儲(chǔ)任何值 也可以存儲(chǔ)如線性表的長(zhǎng)度等之類的附加信息 頭結(jié)點(diǎn)的指針域存儲(chǔ)第一個(gè)結(jié)點(diǎn)的地址 若鏈表為空 則頭結(jié)點(diǎn)的指針域?yàn)?空 如下圖 a 所示為一個(gè)空線性鏈表 圖 b 所示為一個(gè)帶頭結(jié)點(diǎn)的非空線性鏈表 a1 a2 an a b 帶頭結(jié)點(diǎn)的單鏈表的示意圖 引入頭結(jié)點(diǎn)的好處是 2 3 1單鏈表 二 單鏈表存儲(chǔ)結(jié)構(gòu)描述 typedefintElemtype 或者typedefcharElemtype structLnode Elemtypedata structLnode next 實(shí)例中結(jié)構(gòu)如下 structstudent longnum structstudent next 2 3 1單鏈表 三 單鏈表的相關(guān)基本操作創(chuàng)建帶頭結(jié)點(diǎn)的單鏈表單鏈表和順序表不同 它是一種動(dòng)態(tài)結(jié)構(gòu) 它的結(jié)點(diǎn)空間不需要預(yù)先分配 而是在需要時(shí)向系統(tǒng)即時(shí)申請(qǐng) 因此建立線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的過(guò)程就是一個(gè)動(dòng)態(tài)生成結(jié)點(diǎn)并鏈成鏈表的過(guò)程 即從 空表 的初始狀態(tài)開始 依次建立各元素結(jié)點(diǎn) 并逐個(gè)插入鏈表 2 3 1單鏈表 2 3 1單鏈表 帶頭結(jié)點(diǎn)的單鏈表的創(chuàng)建算法實(shí)現(xiàn) 始終從表尾插入新結(jié)點(diǎn) structstudent creat structstudent head p q longx q head structstudent malloc sizeof structstudent head next NULL printf npleaseinputdatdstothelist scanf ld voidprint structstudent head structstudent p p head next printf nTHelistis if p NULL printf thelistisNULL n while p NULL printf 6ld p num p p next printf n 4 單鏈表的插入操作在單鏈表的第i個(gè)結(jié)點(diǎn)之前插入一個(gè)新結(jié)點(diǎn) 示意圖 p 2 3 1單鏈表 voidinsert structstudent head structstudent p q t p structstudent malloc sizeof structstudent printf npleaseinputthestudentyouwanttoinsert scanf ld 5 單鏈表的刪除操作刪除單鏈表中第i個(gè)結(jié)點(diǎn) p s ai 在單鏈表中刪除一個(gè)結(jié)點(diǎn) b 刪除并釋放第i個(gè)結(jié)點(diǎn) a 尋找第i個(gè)結(jié)點(diǎn)的直接前驅(qū)p head 2 3 1單鏈表 voiddel structstudent head structstudent p q longnum printf npleaseinputthestudent numyouwanttodelete scanf ld 以上算法的時(shí)間復(fù)雜度均為O n voidsave structstudent head structstudent p1 FILE fp charfile 20 d aa txt printf filename s n file printf Pleasewait n if fp fopen file wb NULL printf can topenfile s file exit 0 p1 head next while p1 NULL fwrite void p1 sizeof structstudent 1 fp p1 p1 next fclose fp structstudent filein void structstudent p1 p2 head inti 0 FILE fp charfile 20 d aa txt printf filename s n file if fp fopen file rb NULL printf can topenfile s file exit 0 head p2 structstudent malloc sizeof p1 p1 structstudent malloc sizeof p1 while fread p1 sizeof p1 1 fp 1 i p2 next p1 p2 p1 p1 next NULL p1 structstudent malloc sizeof p1 free p1 fclose fp if i 0 printf Norecoredin s return head P302 11voidcreatelist L linklist 6 單鏈表的合并將兩個(gè)遞增有序的單鏈表合并為一個(gè)遞增有序的單鏈表 需設(shè)立3個(gè)指針pa pb pc 其中pa和pb分別指示La表和Lb表中當(dāng)前待比較插入的結(jié)點(diǎn) 而pc指向Lc表中當(dāng)前最后一個(gè)結(jié)點(diǎn) 若pa datadata 則將pa所指結(jié)點(diǎn)從原鏈表斷開 連接到pc所指結(jié)點(diǎn)之后 否則將pb所指結(jié)點(diǎn)鏈接到pc所指結(jié)點(diǎn)之后 顯然 初始狀態(tài)是 當(dāng)La和Lb表非空時(shí) pa和pb分別指向La和Lb中第一個(gè)結(jié)點(diǎn) pc指向空表Lc中的頭結(jié)點(diǎn) 2 3 1單鏈表 單鏈表的合并算法實(shí)現(xiàn)structLnode mergelist l structLnode La structLnode Lb structLnode pa pb pc pa La next pb Lb next Lc structLnode malloc sizeof structLnode Lc next NULL pc Lc while pa NULL 2 3 1單鏈表 2 3 2循環(huán)鏈表 循環(huán)鏈表是另一種形式的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 它的特點(diǎn)是單鏈表中最后一個(gè)結(jié)點(diǎn)的指針域指向鏈表的表頭結(jié)點(diǎn) 整個(gè)鏈表形成一個(gè)環(huán) 這樣 從表中任一結(jié)點(diǎn)出發(fā)都可找到表中其他的結(jié)點(diǎn) 這也是循環(huán)鏈表的優(yōu)點(diǎn) 邏輯結(jié)構(gòu)示意圖如下所示 2 3 2循環(huán)鏈表 圖2 12循環(huán)鏈表 循環(huán)鏈表示意圖 循環(huán)鏈表的操作和單鏈表基本一致 差別僅在于 算法中的循環(huán)條件不是p或p next是否為NULL 而是p或p next是否等于頭指針 2 3 3雙向鏈表 1 雙向鏈表的定義在單鏈表的每個(gè)結(jié)點(diǎn)中只有一個(gè)指示后繼的指針域 因此從任何一個(gè)結(jié)點(diǎn)出發(fā) 都能很容易地通過(guò)指針域找到它的所有后繼結(jié)點(diǎn) 但若需找出該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn) 則必須從表頭出發(fā)重新查找 因此 在單鏈表中 查找某結(jié)點(diǎn)的后繼結(jié)點(diǎn)的執(zhí)行時(shí)間為O 1 而查找其前驅(qū)結(jié)點(diǎn)的執(zhí)行時(shí)間為O n 我們可用雙向鏈表來(lái)克服單鏈表的這種缺點(diǎn) 雙向鏈表中每個(gè)結(jié)點(diǎn)含有兩個(gè)指針域 一個(gè)指向直接前驅(qū) 另一個(gè)指向直接后繼 2 3 3雙向鏈表 priornext head a 空雙向鏈表 head 非空的雙向鏈表雙向鏈表邏輯示意圖 NULL a1 a2 an 2 3 3雙向鏈表 2 雙向鏈表存儲(chǔ)結(jié)構(gòu)描述typedefstructDuLNode Elemtypedata structDuLNode prior structDuLNode next DuLNode 2 3 3雙向鏈表 若p為指向雙向鏈表中的某一個(gè)結(jié)點(diǎn)ai的指針 則顯然有 p next prior p prior next p在雙向鏈表中 有些操作如 求長(zhǎng)度 取元素 查找等 它們只涉及到一個(gè)方向的指針 因此它們的算法與單鏈表的操作相同 但在插入 刪除時(shí) 則需同時(shí)修改兩個(gè)方向上的指針 2 3 3雙向鏈表 3 雙向鏈表的基本操作 1 在雙向鏈表中插入一個(gè)結(jié)點(diǎn)在雙向鏈表的第i個(gè)結(jié)點(diǎn)前插入一個(gè)新結(jié)點(diǎn)時(shí) 設(shè)指針p指向第i個(gè)結(jié)點(diǎn) 稱p結(jié)點(diǎn) 設(shè)s指針指向新結(jié)點(diǎn) 稱s結(jié)點(diǎn) 則操作過(guò)程如下圖所示 2 3 3雙向鏈表 雙向鏈表插入操作的核心語(yǔ)句序列為 s prior p prior 圖中步驟 s prior next s 圖中步驟 s next p 圖中步驟 p prior s 圖中步驟 2 3 3雙向鏈表 2 在雙向鏈表中刪除一個(gè)結(jié)點(diǎn) 在雙向鏈表中刪除一個(gè)結(jié)點(diǎn) ai 1 ai ai 1 p 在雙向鏈表中刪除結(jié)點(diǎn)的核心語(yǔ)句序列 p prior next p next 圖中步驟 p next prior p prior 圖中步驟 free p 2 3 3雙向鏈表 與單向循環(huán)鏈表類似 雙向鏈表也可以有循環(huán)表 讓頭結(jié)點(diǎn)的前驅(qū)指針指向鏈表的最后的一個(gè)結(jié)點(diǎn) 讓最后一個(gè)結(jié)點(diǎn)的后繼指針指向頭結(jié)點(diǎn) 就構(gòu)成了雙向循環(huán)鏈表 下圖為一個(gè)雙向循環(huán)鏈表示例 a1 a2 an head 非空的雙向循環(huán)鏈表 總結(jié) 順序表和鏈表的比較 順序表和鏈表的比較主要從以下兩方面考慮 1 基于空間的考慮 1 當(dāng)線性表的長(zhǎng)度變化較大 難以估計(jì)其存儲(chǔ)規(guī)模時(shí) 以鏈表作為存儲(chǔ)結(jié)構(gòu)好 2 當(dāng)線性表的長(zhǎng)度變化不大 易于事先確定其大小時(shí) 為了節(jié)約存儲(chǔ)空間 宜采用順序存儲(chǔ)結(jié)構(gòu) 2 基于時(shí)間的考慮 1 若線性表主要是進(jìn)行查找 很少做插入 刪除操作時(shí) 宜采用順序存儲(chǔ)結(jié)構(gòu) 2 對(duì)于頻繁進(jìn)行插入和刪除的線性表 宜采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 2 4一元多項(xiàng)式的表示及相加 在數(shù)學(xué)上 一個(gè)一元n次多項(xiàng)式Pn x 可以表示為 Pn x p0 p1x p2x2 pnxn它由n 1個(gè)系數(shù)唯一確定 因此 在計(jì)算機(jī)里 它可以用一個(gè)線性表P來(lái)表示 P p0 p1 p2 pn 每一項(xiàng)的指數(shù)i隱含在其系數(shù)pi的序號(hào)里 同樣 一個(gè)一元m次多項(xiàng)式Qm x 可以表示為 Q q0 q1 q2 qm 設(shè)m n 則兩個(gè)多項(xiàng)式相加的結(jié)果Rn x 可用線性表R表示為 R p0 q0 p1 q1 pm qm pm 1 pn 2 4一元多項(xiàng)式的表示及相加 可以對(duì)P Q和R采用順序存儲(chǔ)結(jié)構(gòu) 只存儲(chǔ)系數(shù) 故若多項(xiàng)式的最高次數(shù)為n則需要n 1個(gè)存儲(chǔ)空間 使用這種存儲(chǔ)結(jié)構(gòu)可以使多項(xiàng)式相加的算法十分簡(jiǎn)單 但是當(dāng)多項(xiàng)式的次數(shù)很高且變化很大時(shí) 多項(xiàng)式中存在大量的零系數(shù) 這種表示方式就會(huì)浪費(fèi)大量存儲(chǔ)空間 例 形如S x 1 4x7 2x100的多項(xiàng)式 線性表中只有3個(gè)非0元素 但卻需要101個(gè)連續(xù)的存儲(chǔ)單元 其中卻存儲(chǔ)了大量的0元素 浪費(fèi)了大量的存儲(chǔ)空間 2 4一元多項(xiàng)式的表示及相加 為了有效而合理地利用存儲(chǔ)空間 只存儲(chǔ)非0項(xiàng)的系數(shù)及其相應(yīng)的指數(shù) 對(duì)于系數(shù)為0的所有項(xiàng)全都不存儲(chǔ) 一般情況下 去掉系數(shù)為0的所有項(xiàng) 一個(gè)一元n次多項(xiàng)式可記作 Pn x p1xe1 p2xe2 pmxem其中 pi是指數(shù)為ei的項(xiàng)的非0系數(shù) 且0 e1 e2 em n那么上述多項(xiàng)式就可以用一個(gè)長(zhǎng)度為m 且每個(gè)數(shù)據(jù)元素有兩個(gè)數(shù)據(jù)項(xiàng) 系數(shù)項(xiàng)和指數(shù)項(xiàng) 的線性表來(lái)唯一確定 p1 e1 p2 e2 pm em 2 4一元多項(xiàng)式的表示及相加 采用鏈表表示多項(xiàng)式時(shí) 每個(gè)結(jié)點(diǎn)的數(shù)據(jù)域有兩項(xiàng) 系數(shù)項(xiàng) 指數(shù)項(xiàng) 則結(jié)點(diǎn)定義如下 structpoly intcoef 系數(shù)項(xiàng)intexp 指數(shù)項(xiàng)structpoly next 2 4一元多項(xiàng)式的表示及相加 假設(shè)多項(xiàng)式A17 x 8 3x 9x10 5x17與B10 x 8x 14x7 9x10則C17 x A x B x 8 11x 14x7 5x17用單鏈表表示如下 其頭指針?lè)謩e為Ah Bh 假設(shè)鏈表是按指數(shù)遞增的有序鏈表 Ah 81 147 910 Bh 多項(xiàng)式的單鏈表存儲(chǔ)結(jié)構(gòu) 2 4一元多項(xiàng)式的表示及相加 其運(yùn)算規(guī)則如下 假設(shè)指針qa和qb分別指向多項(xiàng)式A17 x 和多項(xiàng)式B10 x 中當(dāng)前進(jìn)行比較的某個(gè)結(jié)點(diǎn) 則比較兩個(gè)結(jié)點(diǎn)的數(shù)據(jù)域的指數(shù)項(xiàng) 有三種情況 1 指針qa所指結(jié)點(diǎn)的指數(shù)值 指針qb所指結(jié)點(diǎn)的指數(shù)值時(shí) 則將qa指針?biāo)赶虻慕Y(jié)點(diǎn)插入到 和鏈表 的后面 qa指針后移 2 指針qa所指結(jié)點(diǎn)的指數(shù)值 指針qb所指結(jié)點(diǎn)的指數(shù)值時(shí) 則將qb指針?biāo)赶虻慕Y(jié)點(diǎn)插入到 和鏈表 的后面 qb指針后移 3 指針qa所指結(jié)點(diǎn)的指數(shù)值 指針qb所指結(jié)點(diǎn)的指數(shù)值時(shí) 將兩個(gè)結(jié)點(diǎn)中的系數(shù)相加 若和不為零 則修改qa所指結(jié)點(diǎn)的系數(shù)值 同時(shí)釋放qb所指結(jié)點(diǎn) qa和qb指針均后移 反之 從多項(xiàng)式A17 x 的鏈表中刪除相應(yīng)結(jié)點(diǎn) 并釋放指針qa和qb所指結(jié)點(diǎn) qa和qb指針均后移 2 4一元多項(xiàng)式的表示及相加 多項(xiàng)式相加的算法實(shí)現(xiàn)structpoly add poly structpoly Ah structpoly Bh structpoly qa qb s r Ch qa Ah next qb Bh next qa和q