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