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