數(shù)據(jù)結(jié)構(gòu)之線性表課件-文庫(kù)吧
2025-07-28 09:01 本頁(yè)面
【正文】 ， 故將此元素刪除后，它后面的所有元素都需要向前移動(dòng)一個(gè)單元，且數(shù)據(jù)元素總數(shù)由原來(lái)的 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=i。 k； k++) [k1] = [k]。 /*I以后的元 。 /*素前移 return(0) } } 刪除 函數(shù)分析 ?在循環(huán)語(yǔ)句中，當(dāng) i=1時(shí)，需循環(huán) (n1)次，這是要?jiǎng)h除線性表表頭元素，是最不利的情況； ?當(dāng) i=n時(shí)，則循環(huán)一次也不執(zhí)行，只是將元素?cái)?shù)目 n比原來(lái)減少一個(gè)，而第 n個(gè)數(shù)據(jù)元素不必再考慮，其余的各單元的元素均維持不變，這是最好的情況。 算法的時(shí)間復(fù)雜性 ?可以用數(shù)據(jù)元素的移動(dòng)次數(shù)來(lái)度量這兩個(gè)算法的時(shí)間復(fù)雜性。 ?插入時(shí)，最少循環(huán) 0次，最多循環(huán) n次，如 i的各種取值概率相同，則平均循環(huán)次數(shù)為n/2； ?刪除時(shí)最少的循環(huán)次數(shù)為 0次，最多為 n1次，當(dāng) i取值概率相同時(shí)，平均循環(huán)次數(shù)為 (n1)/2。 ?用數(shù)量級(jí)的形式表示線性表插入、刪除運(yùn)算的時(shí)間復(fù)雜性均為 O(n)。 ?刪除一個(gè)值為 X的元素 基本思想 ：在線性表中，查找到值為 X的元素 ai，將 i 之后的元素前移一個(gè)位置，且線性表的長(zhǎng)度減 1。 Int LocateDeleteSeqlist(list sl。 elementtype： x) { Int I=0, j。 /*刪除值為 X的元素 IF（ ==0) printf (“空表！ \n”)。 While(I) { If ([I]!=x) I++。 else { for (j=I+1。j=。j++) [j1]=[j] ； 。 break。 該語(yǔ)句的作用？ } } if (i=) printf(“i值錯(cuò) ！ \n”)。 return(0)。 } 順序表的應(yīng)用舉例 線性表的鏈?zhǔn)酱鎯?chǔ) ? .1 單鏈表 ? 結(jié)點(diǎn) : 在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，結(jié)點(diǎn)不僅存放數(shù)據(jù)元素的值，還附加一個(gè)指針（鏈），用來(lái)指向該結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)。 ? 其中， data部分稱(chēng)為數(shù)據(jù)域，用于存儲(chǔ)線性表的一個(gè)元素， next部分稱(chēng)為指針域或鏈域，用于存放一個(gè)指針，即存放該結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的地址。 data next ?所有結(jié)點(diǎn)通過(guò)指針的鏈接而構(gòu)成的線性表稱(chēng)為單鏈表。線性表（ a1， a2， ……a n，）的單鏈表可直觀地畫(huà)成： ? head是單鏈表的頭指針，指向開(kāi)始結(jié)點(diǎn) a1, an是終端結(jié)點(diǎn)，其指針域?yàn)榭?，不指向任何結(jié)點(diǎn)。 ?一個(gè)單鏈表由頭指針 head唯一標(biāo)識(shí)和確定，因此，可用頭指針來(lái)命名單鏈表。 h e a d a 1 a 2 a i a n ∧ 單鏈表的類(lèi)型定義 ?單鏈表的的結(jié)點(diǎn)類(lèi)型定義如下： typedef struct Lnode { elementtype data。 struct lnode *next； }linklist ?一個(gè)結(jié)點(diǎn)是由兩個(gè)域 data和 next組成的記錄 , data是結(jié)點(diǎn)的數(shù)據(jù)域， next是結(jié)點(diǎn)的鏈域。 ?鏈表舉例 ?空表 …… H ^ a1 an ?為了編程方便，一般在單鏈表的第一個(gè)結(jié)點(diǎn)之前加一個(gè)“頭結(jié)點(diǎn)”，如： ?當(dāng)為空表時(shí)，即 headnext=null, 如下圖。 a1 an ^ head ^ head 指針的概念 ?假設(shè) p是一個(gè) pointer類(lèi)型，應(yīng)正確區(qū)分指針型變量、指針、指針?biāo)傅慕Y(jié)點(diǎn)和結(jié)點(diǎn)的內(nèi)容這四個(gè)密切相關(guān)的不同概念： p的值（如果有的話）是一個(gè)指針，即是一個(gè)所指結(jié)點(diǎn)的地址 。 該指針（若不是 NULL）指向的某個(gè) node型結(jié)點(diǎn)用 *p來(lái)標(biāo)識(shí)。 結(jié)點(diǎn) *p是由兩個(gè)域組成的記錄，這兩個(gè)域分別用p?data域和 p?next域來(lái)標(biāo)識(shí)，它們各有自己的值，p?data的值是一個(gè)數(shù)據(jù)元素， p?next的值是一個(gè)指針。 單鏈表的基本運(yùn)算 ? 1. 遍歷 (Traversal)：根據(jù)已給的表頭指針，按由前向后的次序訪問(wèn)單鏈表的各個(gè)結(jié)點(diǎn)。 ?在實(shí)際應(yīng)用中遍歷是對(duì)單鏈表的最基本運(yùn)算，例如，當(dāng)要打印或顯示出各個(gè)結(jié)點(diǎn)的數(shù)值域值、計(jì)算單鏈表的長(zhǎng)度 (即結(jié)點(diǎn)數(shù)目 )或?qū)ふ夷骋粋€(gè)結(jié)點(diǎn)時(shí)都需要遍歷單鏈表。 ?假設(shè) head是單鏈表的頭指針，計(jì)算一個(gè)已建立好的單鏈表的結(jié)點(diǎn)個(gè)數(shù)的算法如下： 計(jì)算結(jié)點(diǎn)個(gè)數(shù)算法 int length(head) /*求表 head的長(zhǎng)度 */ { int count=0。 /*計(jì)數(shù)器置初值 */ p=head。 /*p指向頭結(jié)點(diǎn) */ while (p!=NULL) { p=pnext。 count++。 } return(count)。 /*返回表長(zhǎng)值 */ } 算法分析 ?此算法的關(guān)鍵是 while循環(huán)語(yǔ)句，開(kāi)始時(shí) p指針指向頭結(jié)點(diǎn)，每一循環(huán)都修改指針值，讓它指向下一個(gè)結(jié)點(diǎn)，同時(shí)將計(jì)數(shù)鏈表長(zhǎng)度的變量 count加 1。 ?這樣每循環(huán)一次就向后推移一個(gè)結(jié)點(diǎn)，直到 p所指結(jié)點(diǎn) *p的鏈域值為 NULL為止。 ?空指針 NULL起標(biāo)志的作用，若無(wú)此標(biāo)志，尾結(jié)點(diǎn)鏈域的值為“無(wú)定義”，上述算法中的 while語(yǔ)句在做最后一次判斷時(shí)將出現(xiàn)“運(yùn)行錯(cuò)”，這是應(yīng)予避免的。 2. 插入 ?所謂插入是指在單鏈表中第 i個(gè)結(jié)點(diǎn) (i≥0)之后插入一個(gè)元素為 x的結(jié)點(diǎn)。 ?實(shí)現(xiàn)插入算法主要完成三個(gè)基本操作： 1) 在單鏈表上找到插入位置 ， 即找到第 i個(gè)結(jié)點(diǎn) 。 可以用遍歷的方法 ， 即從表頭起順次訪問(wèn)單鏈表的結(jié)點(diǎn) ， 直至找到第 i個(gè)結(jié)點(diǎn) 。 2) 生成一個(gè)以 x為值的新結(jié)點(diǎn) 。 可通過(guò) C的庫(kù)函數(shù) malloc(size)來(lái)產(chǎn)生 。 3) 將新結(jié)點(diǎn)鏈入單鏈表中 。 需要改變相關(guān)結(jié)點(diǎn)的指針 ，
法律信息相關(guān)推薦
鄂ICP備17016276號(hào)-1