數(shù)據(jù)結(jié)構(gòu)之線性表課件-wenkub
2022-09-11 09:01:44 本頁面
【正文】 X的元素 基本思想 ：在線性表中，查找到值為 X的元素 ai，將 i 之后的元素前移一個位置，且線性表的長度減 1。 /*素前移 return(0) } } 刪除 函數(shù)分析 ?在循環(huán)語句中，當(dāng) i=1時，需循環(huán) (n1)次，這是要刪除線性表表頭元素，是最不利的情況； ?當(dāng) i=n時，則循環(huán)一次也不執(zhí)行，只是將元素數(shù)目 n比原來減少一個，而第 n個數(shù)據(jù)元素不必再考慮，其余的各單元的元素均維持不變，這是最好的情況。 2. 元素的刪除 (Delete) 在順序表 L=（ a1,a2,… ,ai,…,an ）中刪除第 i個結(jié)點，使成為 L=（ a1,a2,…,ai 1, ai+1,…, an ） 基本思想 ：要求刪除第 i個數(shù)據(jù)元素，由于線性表元素在數(shù)組中必須連續(xù)排列，中間不能有空單元， 故將此元素刪除后，它后面的所有元素都需要向前移動一個單元，且數(shù)據(jù)元素總數(shù)由原來的 n減少到 n1. 刪除 函數(shù) Int delete(list L, int i) /*刪除順序表中第 I個結(jié)點 { int k； if (i1||i) printf(“i值錯 ！ \n”)。 ++。 else { for (k=。 } list。 其形式化的定義為： S=（ D， R） 其中： D是由 n個元素組成的集合， R是定義在集合 D上的一種關(guān)系。 ? 線性表的定義 例：Ａ＝｛ Monday,Tuesday， Wednesday， Thursday， Friday， Saturday， Sunday｝ 又 Score={sdudent1， 50， student2， 60， student3， 70} [注意 ]線性表和集合的區(qū)別。 ?線性表在計算機內(nèi)存中采用各元素順序存儲的方式，這種存儲結(jié)構(gòu)叫做向量。數(shù)據(jù)結(jié)構(gòu) 第 二 章 線性表 第 二 章 線性表 ?知 識 點 線性數(shù)據(jù)結(jié)構(gòu)的基本特征和基本運算 線性表的存儲結(jié)構(gòu) 雙向鏈表 循環(huán)鏈表 ?難 點 循環(huán)鏈表 利用本章的基本知識設(shè)計有效的算法解決與線性相關(guān)的應(yīng)用問題 ?要 求 熟練掌握以下內(nèi)容： 線性表的基本運算 線性表的特征 、 基本運算并能設(shè)計簡單算法 了解以下內(nèi)容： 線性表運算時間復(fù)雜性分析 第 二 章 目錄 ? 線性表的邏輯結(jié)構(gòu) ? 線性表的順序存儲 ? 線性表的鏈?zhǔn)酱鎯? ? 循環(huán)鏈表 ? 雙向鏈表 ?小 結(jié) ?習(xí)題與練習(xí) 2 線性表 （ Linear List） ?線性表是由有限數(shù)目的相同類型元素組成的序列。 ?每個線性表元素叫做這個向量的一個分量。 線性表元素之間是有序的，而集合元素 之間是無序的。 ?線性表的邏輯結(jié)構(gòu) 線性表的元素類型是多樣的，但同一線性表中的元素必須是同一類型，且相鄰元素之間存在一種序偶關(guān)系。 順序存儲下線性表的運算 1. 數(shù)據(jù)元素的插入 (insert) 在順序表 L=（ a1,a2,… ,ai,…,an ）中第 i個元素前插入元素 b，使成為 L=（ a1,a2,…, b ,ai,…, an ） 基本思想 ：把順序表表中第 I個元素至第 n個元素后移一個位置，把元素 b插入到第 i個位置上，線性表的長度加 1。 k=i1。 /*順序表長度加 1*/ return(0)。 else { for (k=i。 算法的時間復(fù)雜性 ?可以用數(shù)據(jù)元素的移動次數(shù)來度量這兩個算法的時間復(fù)雜性。 Int LocateDeleteSeqlist(list sl。 else { for (j=I+1。 該語句的作用？ } } if (i=) printf(“i值錯 ！ \n”)。 data next ?所有結(jié)點通過指針的鏈接而構(gòu)成的線性表稱為單鏈表。 struct lnode *next； }linklist ?一個結(jié)點是由兩個域 data和 next組成的記錄 , data是結(jié)點的數(shù)據(jù)域， next是結(jié)點的鏈域。 結(jié)點 *p是由兩個域組成的記錄，這兩個域分別用p?data域和 p?next域來標(biāo)識，它們各有自己的值，p?data的值是一個數(shù)據(jù)元素， p?next的值是一個指針。 /*計數(shù)器置初值 */ p=head。 /*返回表長值 */ } 算法分析 ?此算法的關(guān)鍵是 while循環(huán)語句，開始時 p指針指向頭結(jié)點，每一循環(huán)都修改指針值，讓它指向下一個結(jié)點，同時將計數(shù)鏈表長度的變量 count加 1。 ?實現(xiàn)插入算法主要完成三個基本操作： 1) 在單鏈表上找到插入位置 ， 即找到第 i個結(jié)點 。 3) 將新結(jié)點鏈入單鏈表中 。 int k=0。 pnext=s。 {linklist *p,*pre,*s。 /*結(jié)點 pre j++ } 插入算法續(xù) if(j!=k) { printf(“k超出鏈表的長度 ” )。 /*表的頭部 ， 即 k=1 head=s。主要操作 是： 1) 用遍歷的方法在單鏈表上找到該結(jié)點； 2) 從單鏈表上刪除該結(jié)點。 elementtype x。 while((p!=null) amp。 } 刪除算法續(xù) if (p=NULL) { printf (“x不存在 ” ) return(null)。 } 返回 靜態(tài)鏈表 ?在某些語言中，沒有指針類型，就不能實現(xiàn)鏈表，可用一數(shù)組來模擬鏈表，這就是靜態(tài)鏈表。 如： slinklist sl[maxsize]。
法律信息相關(guān)推薦
鄂ICP備17016276號-1