數(shù)據(jù)結(jié)構(gòu)之線性表課件(已修改)
2025-09-11 09:01 本頁面
【正文】 數(shù)據(jù)結(jié)構(gòu) 第 二 章 線性表 第 二 章 線性表 ?知 識 點(diǎn) 線性數(shù)據(jù)結(jié)構(gòu)的基本特征和基本運(yùn)算 線性表的存儲結(jié)構(gòu) 雙向鏈表 循環(huán)鏈表 ?難 點(diǎn) 循環(huán)鏈表 利用本章的基本知識設(shè)計有效的算法解決與線性相關(guān)的應(yīng)用問題 ?要 求 熟練掌握以下內(nèi)容： 線性表的基本運(yùn)算 線性表的特征 、 基本運(yùn)算并能設(shè)計簡單算法 了解以下內(nèi)容： 線性表運(yùn)算時間復(fù)雜性分析 第 二 章 目錄 ? 線性表的邏輯結(jié)構(gòu) ? 線性表的順序存儲 ? 線性表的鏈?zhǔn)酱鎯? ? 循環(huán)鏈表 ? 雙向鏈表 ?小 結(jié) ?習(xí)題與練習(xí) 2 線性表 （ Linear List） ?線性表是由有限數(shù)目的相同類型元素組成的序列。 ?表中的數(shù)據(jù)元素 , 除了第一個和最后一個以外，都有一個且只有一個前驅(qū)元素，同時也都有一個且只有一個后繼元素； ?第一個元素只有一個后繼元素而無前驅(qū)元素；最后一個元素只有一個前驅(qū)元素而無后繼元素。 ?線性表的元素個數(shù) n稱為這個表的長度，當(dāng)n=0時，這個表叫做空表。 ?線性表在計算機(jī)內(nèi)存中采用各元素順序存儲的方式，這種存儲結(jié)構(gòu)叫做向量。 ?每個線性表元素叫做這個向量的一個分量。 ?如果已知線性表第一個元素的地址和每個元素占用的存儲單元數(shù)，由任一元素的序號就可以計算出該元素在內(nèi)存中的地址。 ?在編程時以一維數(shù)組表示線性表最簡單，用的也最普遍。 ? 線性表的定義 例：Ａ＝｛ Monday,Tuesday， Wednesday， Thursday， Friday， Saturday， Sunday｝ 又 Score={sdudent1， 50， student2， 60， student3， 70} [注意 ]線性表和集合的區(qū)別。 線性表元素之間是有序的，而集合元素 之間是無序的。 ? 線性表的定義 線性表是由 n個結(jié)點(diǎn) a1， a2， …..,an 組成的有限序列，當(dāng) n=0時，線性表為空，即為空表。 若 n0, 則 a1是第 1個結(jié)點(diǎn)， an是最后一個結(jié)點(diǎn)。 其形式化的定義為： S=（ D， R） 其中： D是由 n個元素組成的集合， R是定義在集合 D上的一種關(guān)系。 ?線性表的邏輯結(jié)構(gòu) 線性表的元素類型是多樣的，但同一線性表中的元素必須是同一類型，且相鄰元素之間存在一種序偶關(guān)系。 ?線性表的基本運(yùn)算： 1. 求線性表的長度 n； 2. 在第 i個數(shù)據(jù)元素前面插入一個新的數(shù)據(jù)元素； 3. 刪除第 i個數(shù)據(jù)元素； 4. 存取或更新線性表第 i個元素； 5. 將兩個或兩個以上的線性表合并成一個線性表； 6. 將一個線性表拆成多個線性表； 7. 將線性表中各數(shù)據(jù)元素按某個域值（如關(guān)鍵字） 遞增或遞減的順序重新排列； 8. 在線性表中查找滿足某種條件的數(shù)據(jù)元素； 線性表的順序存儲 ?線性表的順序存儲結(jié)構(gòu) (順序表） 例：一順序表 A=（ 3， 6， 8， 9， 2） 順序存放在一維數(shù)組中 順序存儲的特點(diǎn)： 邏輯順序與物理順序一致， 元素之間的關(guān)系由物理位置的相鄰關(guān)系體現(xiàn) 3 6 8 9 2 線性表的順序存儲 ?地址計算 設(shè)順序表的每個元素占 c個存儲單元，并且元素所占的第一個單元的存儲地址作為順序表的存儲位置，則順序表中第 I個元素的存儲位置 Loc（ ai）滿足 Loc（ ai） =Loc（ ai1） + c Loc（ ai） =Loc（ a1） +（ i1） * c 線性表的順序存儲 ?結(jié)點(diǎn)描述 define Maxlen 順序表的最大長度 typedef struct seqenlist {elementtype elements [maxlen]。 int lenth。 } list。 順序存儲下線性表的運(yùn)算 1. 數(shù)據(jù)元素的插入 (insert) 在順序表 L=（ a1,a2,… ,ai,…,an ）中第 i個元素前插入元素 b，使成為 L=（ a1,a2,…, b ,ai,…, an ） 基本思想 ：把順序表表中第 I個元素至第 n個元素后移一個位置，把元素 b插入到第 i個位置上，線性表的長度加 1。 插入函數(shù) int insert(list L, int i, elementtype x) { int k。 if (i1 || i+1) printf(“i值錯 ！ \n”)。 else { for (k=。 k=i1。 k) [k]=[k1]。 /*將第 i個元素及其后面的元素后移 */ [i1]=x。 ++。 /*順序表長度加 1*/ return(0)。 } } 插入函數(shù)分析 ?在循環(huán)語句中，當(dāng) i=1時，須循環(huán) n次，表示元素插入線性表頭的前面，則原線性表中 n個元素均須向后移動一個單元，這是最不利的情況。 ?當(dāng) i=n+1時，則循環(huán)一次也不進(jìn)行，這時元素直接插入到線性表尾的后面，所以線性表的所有 n個元素均不移動，這是最好的情況。 2. 元素的刪除 (Delete) 在順序表 L=（ a1,a2,… ,ai,…,an ）中刪除第 i個結(jié)點(diǎn)，使成為 L=（ a1,a2,…,ai 1, ai+1,…, an ） 基本思想 ：要求刪除第 i個數(shù)據(jù)元素，由于線性表元素在數(shù)組中必須連續(xù)排列，中間不能有空單元
法律信息相關(guān)推薦
鄂ICP備17016276號-1