數(shù)據(jù)結(jié)構(gòu)課件-第02章

數(shù)據(jù)結(jié)構(gòu)計算機(jī)領(lǐng)域本科教育教學(xué)改革試點工作計劃（“101計劃”）研究成果101線性結(jié)構(gòu)第2章1.1問題引入：一元多項式1.2線性表的定義與結(jié)構(gòu)1.3線性表的順序存儲實現(xiàn)1.4線性表的鏈?zhǔn)酱鎯崿F(xiàn)1.5線性表的應(yīng)用1.6拓展延伸1.7應(yīng)用場景：內(nèi)存管理1.8小結(jié)1.1問題引入：一元多項式例2.1一元多項式及其運(yùn)算一元多項式：主要運(yùn)算：多項式相加、相減、相乘等問題：如何在計算機(jī)中表示一元多項式并實現(xiàn)相關(guān)的運(yùn)算？多項式的關(guān)鍵數(shù)據(jù)：多項式項數(shù)、每一項系數(shù)（以及對應(yīng)指數(shù)）方法1：采用順序存儲結(jié)構(gòu)直接表示一元多項式用數(shù)組a存儲多項式的相關(guān)數(shù)據(jù)：數(shù)組分量a[i]表示項xi的系數(shù)例如：a[i]10–3004……下標(biāo)i012345……這種表示的優(yōu)點和缺點？優(yōu)點：多項式相加容易缺點：如何表示方法2：采用順序存儲結(jié)構(gòu)表示多項式的非零項每個非零項

涉及兩個信息：指數(shù)i和系數(shù)ai可以將一個多項式看成是一個(ai，i)二元組的集合。系數(shù)9153–

系數(shù)26–4–1382–指數(shù)1282–

指數(shù)19860–數(shù)組下標(biāo)i012……

數(shù)組下標(biāo)i0123……這種表示的優(yōu)點和缺點？方法3：采用鏈表結(jié)構(gòu)來存儲多項式的非零項鏈表表示多項式：鏈表結(jié)點對應(yīng)一個非零項，包括：系數(shù)、指數(shù)、指針域

系數(shù)指數(shù)指針912p1p215832NIL2619–48–136820NIL這種表示的優(yōu)點和缺點？本章介紹：線性表的抽象定義，并分別討論基于順序存儲和鏈接存儲的線性表實現(xiàn)方法，以及線性表的基本操作，包括插入、刪除等。啟示：數(shù)據(jù)結(jié)構(gòu)的設(shè)計往往需要在算法簡潔、可理解性與時間、空間效率之間權(quán)衡針對具體問題選擇合適的數(shù)據(jù)結(jié)構(gòu)及設(shè)計相應(yīng)的算法2.2.1線性表的定義線性表：由同一類型的數(shù)據(jù)元素構(gòu)成的有序序列的線性結(jié)構(gòu)2.2.2線性表的結(jié)構(gòu)線性表的邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間線性的序列關(guān)系，即數(shù)據(jù)元素之間的前驅(qū)和后繼關(guān)系。線性表的物理結(jié)構(gòu)：線性表在計算機(jī)中的存儲方式，又稱為存儲結(jié)構(gòu)，即從程序?qū)崿F(xiàn)的角度將邏輯結(jié)構(gòu)映射到計算機(jī)存儲單元中。存儲結(jié)構(gòu)主要有兩種形式：順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。順序存儲結(jié)構(gòu)：數(shù)據(jù)元素被順序地存儲在連續(xù)的內(nèi)存空間中，前驅(qū)和后繼元素在物理空間上是相鄰的。鏈?zhǔn)酱鎯Y(jié)構(gòu)：可以動態(tài)地申請存儲數(shù)據(jù)的結(jié)點空間，并使用類似指針這樣的手段將結(jié)點按順序前后鏈接起來2.3線性表的順序存儲實現(xiàn)例如：數(shù)組list.data[kMaxSize]:從list.data[0]開始依次順序存放，kMaxSize代表數(shù)組最大容量，list.last記錄當(dāng)前線性表中最后一個元素在數(shù)組中的位置，表空時list.last=-1。last2.3.1順序表的基本操作1.初始化:順序表的初始化即構(gòu)造一個空表(1)動態(tài)分配表結(jié)構(gòu)所需要的存儲空間(2)將表中l(wèi)ist.last指針置為-1，表示表中沒有數(shù)據(jù)元素。2.3.1順序表的基本操作2.查找查找：在線性表中查找與給定值x相等的數(shù)據(jù)元素方法：從第一個元素起依次和x比較，直到找到一個與x相等的數(shù)據(jù)元素，返回它在順序表中的存儲下標(biāo)；或者查遍整個表都沒有找到與x相等的元素，則返回NIL。時間復(fù)雜性：1~（n+1)/2平均O(n)2.3.1順序表的基本操作3.插入在表的第i個位序上插入一個值為x的新元素

(a1,a2,...,ai-1,ai,ai+1,...,an)-->(a1,a2,...,ai-1,x,ai,ai+1,...,an)時間復(fù)雜度為O(n）執(zhí)行步驟：（1）將ai～an順序向后移動（移動次序從后到前），為新元素讓出位置；（2）將x置入空出的第i個位序；（3）修改list.last指針(相當(dāng)于修改表長)，使之仍指向最后一個元素。2.3.1順序表的基本操作4.刪除將線性表中的第i個位序上的元素刪除

(a1,a2,...,ai-1,ai,ai+1,...,an)-->(a1,a2,...,ai-1,ai+1,...,an)時間復(fù)雜度為O(n）執(zhí)行步驟：(1)將～順序向前移動，元素被覆蓋；(2)修改list.last指針(相當(dāng)于修改表長)使之仍指向最后一個元素。2.4線性表的鏈接存儲實現(xiàn)單向鏈表（簡稱單鏈表）：每個數(shù)據(jù)單元由數(shù)據(jù)域data和鏈接域next兩部分組成，n個數(shù)據(jù)單元通過鏈接域next串聯(lián)起來。list.heada1a2anNIL……鏈?zhǔn)酱鎯Γ翰灰筮壿嬌舷噜彽膬蓚€數(shù)據(jù)元素物理上也相鄰?fù)ㄟ^“鏈”建立起數(shù)據(jù)元素之間的邏輯關(guān)系對線性表的插入、刪除不需要移動數(shù)據(jù)元素，只需要修改“鏈”。2.3.2單鏈表的基本操作1.

求表長:求單鏈表元素個數(shù)（1）設(shè)一個移動指針p和計數(shù)器counter，初始化（2）p逐步往后移，同時計數(shù)器counter加1（3）當(dāng)后面不再有結(jié)點時，counter的值就是結(jié)點個數(shù)，即表長。時間復(fù)雜性O(shè)(n)2.3.2單鏈表的基本操作2.

查找：分按序號查找Get(list,i)、按值查找Search(list,x)（1）按序號查找步驟：從鏈表的第一個元素結(jié)點起，判斷當(dāng)前結(jié)點是否是第i個；若是，則返回該結(jié)點的值，否則繼續(xù)后一個，直到表結(jié)束為止。如果沒有第i個結(jié)點則返回錯誤碼(ErrorCode)。時間復(fù)雜性：O(n)2.3.2單鏈表的基本操作2.查找（2）按值查找步驟：從鏈表的第一個元素結(jié)點起，判斷當(dāng)前結(jié)點其值是否等于x；若是，返回該結(jié)點的位置（即指向該結(jié)點的指針），否則繼續(xù)后一個，直到表結(jié)束為止。找不到時返回空（NIL）。時間復(fù)雜性：O(n)2.3.2單鏈表的基本操作3.

插入：在list的第i個位置上插入元素x步驟：（1）找到第i-1個結(jié)點；（2）若存在，則申請一個新結(jié)點的空間并填上相應(yīng)值x，然后將新結(jié)點插到第i-1個結(jié)點之后；（3）如果不存在則直接退出：時間復(fù)雜度為O(n）注意：表空和不空時候的不同處理方式2.3.2單鏈表的基本操作4.

刪除在單鏈表中刪除指定位序i的元素步驟：找到被刪除結(jié)點的前一個元素再刪除結(jié)點并釋放空間。時間復(fù)雜度為O(n）2.4.3雙向鏈表雙向鏈表：結(jié)點前后之間實現(xiàn)雙向鏈接，即每個結(jié)點都有兩個指針，一個next指向直接后繼，另一個prior指向直接前驅(qū)。1.插入2.3.2單鏈表的基本操作2、刪除：雙向鏈表中p所指向結(jié)點刪除2.3.2單鏈表的基本操作帶頭結(jié)點的雙向鏈表：可以設(shè)置一個空的“頭結(jié)點”，真正的元素鏈接在這個空結(jié)點之后。2.4.4循環(huán)鏈表循環(huán)單鏈表：鏈表終端結(jié)點的指針指向鏈表的起始結(jié)點循環(huán)雙向鏈表：讓終端結(jié)點的后繼指針指向鏈表的起始結(jié)點，同時讓起始結(jié)點的前驅(qū)指針指向鏈表的終端結(jié)點2.4.4循環(huán)鏈表單向循環(huán)鏈表的遍歷：可以從任意結(jié)點start開始將整個鏈表遍歷一遍2.4.5靜態(tài)鏈表靜態(tài)鏈表：用數(shù)組存放線性表中的元素，但并不按照元素順序在數(shù)組中依序存放，而是給每個數(shù)組元素增加一個域，用于指示線性表中下一個元素的位置（即它在數(shù)組中的下標(biāo)）物理存儲空間上依賴于數(shù)組元素邏輯鏈接關(guān)系是采用了鏈表的思想data

gdaebf

hc

next3845691

02

下標(biāo)012345678910（a,b,c,d,e,f,g,h）2.4.6塊狀鏈表

1.查找操作查找第10個元素的查找路徑：（1）在單向鏈表中遍歷第1塊、第2塊、第3塊；（2）進(jìn)入第3塊對應(yīng)的雙向鏈表繼續(xù)查找結(jié)點6、結(jié)點-2，即第10個元素為-2。時間復(fù)雜度：2.4.6塊狀鏈表2.插入操作：在第i個元素之后插入新元素（1）基于查找操作找到第個元素所對應(yīng)的雙向鏈表結(jié)點（2）在雙向鏈表上執(zhí)行插入操作（3）由于第i個元素所在塊多了一個元素，因此該塊之后的所有塊指向的雙向鏈表結(jié)點將變?yōu)樵赶蚪Y(jié)點的前驅(qū)結(jié)點。3.刪除操作:與插入類似插入和刪除時間復(fù)雜度：例如，如果向第10個元素-2之后插入新元素201）在結(jié)點-2和-7之間插入新元素20，變?yōu)?2、20、-7。2）原有元素次序產(chǎn)生變化：原第11個元素變?yōu)楝F(xiàn)第12個、原第12個元素變?yōu)楝F(xiàn)第13個……。3）將第4塊所指向的雙向鏈表結(jié)點從12更新為前驅(qū)10，第5塊的雙向鏈表結(jié)點從-8更新為前驅(qū)-3。值得額外注意的是，插入操作有可能導(dǎo)致新的塊產(chǎn)生，在實現(xiàn)代碼中需要處理好這種特殊情況。2.5線性表的應(yīng)用一元多項式的加法：p1和p2分別指向兩個多項式第一個結(jié)點，不斷循環(huán)比較p1和p2所指的各結(jié)點，做不同處理P1.expon==P2.expon，插入求和結(jié)點，P1=P1.next；P2=P2.nextP1.expon>P2.expon，

插入P1，P1=P1.next;P1.expon<P2.expon,插入P2，P2=P.next;53443-1120-142312-711P1P2P153P2P1P1P2P2P1462-7130-12.5.2大整數(shù)處理大整數(shù)表示：用順序表中的元素依次表示該大整數(shù)的個位數(shù)、十位數(shù)、百位數(shù)……

n=-23456所對應(yīng)的digits[]={6,5,4,3,2}，length=5，sign=-11.加法運(yùn)算：假設(shè)a+b>0,基本過程是：(1)首先將這兩個大整數(shù)的位數(shù)對齊（位數(shù)較少的大整數(shù)的高位補(bǔ)0）(2)將兩個大整數(shù)對應(yīng)的位數(shù)依次相加或相減，同時處理進(jìn)位或借位，并將結(jié)果存入一個新的大整數(shù)c中。(3)處理加法導(dǎo)致的最高位進(jìn)位，或減法導(dǎo)致的前導(dǎo)0問題。處理一個正的大整數(shù)a加一個負(fù)的大整數(shù)-b（a<b）：計算b和-a相加的結(jié)果，并將最終結(jié)果的符號位取反；處理一個負(fù)的大整數(shù)-a加一個負(fù)的大整數(shù)-b：計算a和b相加的結(jié)果，并將最終結(jié)果的符號位取反。時間復(fù)雜度是O(n)2.5.2大整數(shù)處理2.乘法運(yùn)算：兩個正的大整數(shù)a和b相乘（1）用i和j的二重循環(huán)分別枚舉大整數(shù)a和b的每一位（數(shù)組下標(biāo)從0開始）（2）對于a的第i位數(shù)字和b的第j位數(shù)字（按從低位到高位的順序），將它們相乘并累加至表示計算結(jié)果的大整數(shù)c的第i+j位上。（3）對于得到的大整數(shù)c，從最低位到最高位依次處理進(jìn)位問題，得到最終的計算結(jié)果。時間復(fù)雜度是O(n2)2.6拓展延伸1.廣義表

廣義表是線性表的推廣對于線性表而言，n個元素都是基本的單元素；

廣義表中，這些元素不僅可以是單元素也可以是另一個廣義表。12P832NIL9240NIL153–11NIL例如：二元多項式的表示

2.6.2多維數(shù)組和特殊矩陣1.多維數(shù)組的順序存儲：按照行優(yōu)先的順序存放，即先存放第0行的元素，再存放第1行的元素，……，其中每一行中的元素再按照列的順序存放。例如：二維整形數(shù)組a[3][4]的存放順序：a[0][0]a[0][1]a[0][2]a[0][3]a[1][0]a[1][1]a[1][2]a[1][3]a[2][0]a[2][1]a[2][2]a[2][3]一般來說，二維數(shù)組元素a[i][j]的存儲位置（地址）lij計算方法是：lij=l00+（i×nc+j）×size

設(shè)n維數(shù)組各維大小是（s1，s2，……，sn），第一個元素的地址是l(0,0,…,0)，元素占用空間為size個字節(jié)，則下標(biāo)為（i1,i2，…,in）的元素位置是：l(i1,i2,…in)=l(0,0,…,0)+(i1×s2×s3×..×.sn+i2×s3×...sn+...in-1×sn+in)×size

2.6.2多維數(shù)組和特殊矩陣2.特殊矩陣：上三角矩陣和下三角矩陣壓縮空間存儲：如果只存儲上三角（或者下三角）元素，則將近減少了一半的存儲空間對于下三角矩陣，設(shè)單個元素所占空間為size，則a[i][j]的存儲位置lij與矩陣首個元素a[0][0]的地址l00

的關(guān)系是：lij=l00+(i(i+1)/2+j)×size，i≥j

2.6.3稀疏矩陣和舞蹈鏈1.稀疏矩陣：數(shù)值為0的元素數(shù)目遠(yuǎn)遠(yuǎn)多于非0元素的數(shù)目，并且非0元素分布沒有規(guī)律存儲：非0項1)三元組表的順序存儲row0012333col0313014value18227-423-112

0123456采用一種典型的多重鏈表——十字鏈表來存儲稀疏矩陣

只存儲矩陣非0元素項結(jié)點的數(shù)據(jù)域：行坐標(biāo)Row、列坐標(biāo)Col、數(shù)值Value每個結(jié)點通過兩個指針域，把同行、同列串起來;

行指針(或稱為向右指針)Right列指針（或稱為向下指針）Down2)三元組表的鏈?zhǔn)酱鎯Γ菏宙湵?.6.3稀疏矩陣和舞蹈鏈稀疏矩陣的十字鏈表結(jié)構(gòu)用一個標(biāo)識域Tag來區(qū)分頭結(jié)點和非0元素結(jié)點：頭節(jié)點的標(biāo)識值為“Head”，矩陣非0元素結(jié)點的標(biāo)識值為“Term”。(a)結(jié)點的總體結(jié)構(gòu)(b)矩陣非0元素結(jié)點(c)頭結(jié)點TagDownRightURegionDownRightRowColValueTermDownRightNextHead稀疏矩陣的十字鏈表實現(xiàn)的一個例子HeadTerm457ATerm0018HeadHeadHeadHeadHeadHeadTerm3023HeadHeadHeadTerm1127Term31-1Term032Term23-4Term34122.6.3稀疏矩陣和舞蹈鏈2.舞蹈鏈D.E.Knuth提出X算法：采用回溯搜索在矩陣中尋找合適的行實現(xiàn)“精確覆蓋”X算法的執(zhí)行需要大量的矩陣行和列的