數(shù)據(jù)結(jié)構(gòu)之線性表課件-全文預(yù)覽
【正文】 0 1 1 2 2 3 3 4 4 5 5 6 6 插入 h之后 0 1 a 2 b 3 c 4 d 5 e 6 f 0 0 1 a 2 b 7 c 4 d 5 e 6 f 0 h 3 線性表實現(xiàn)方法比較 ?鏈表：在已知元素個數(shù)的情況下，浪費空間； 在未知元素個數(shù)的情況下，節(jié)約空間； 速度快。 int next。 /*修改指針 free(p)。 (pdata!=x)) { q=p。 q=head。 假設(shè)指針 q指向待刪除結(jié)點的前一個結(jié)點，指針 p指向要刪除的結(jié)點，刪除該結(jié)點的操作如下：將該結(jié)點的前一個結(jié)點 *q的鏈域指向 *p的后繼結(jié)點（即 qnext=pnext）。 prenext=s。 } s=(linklist *)malloc(sizeof(listlist)) if (s= =null) { printf (“沒有足夠的空間 ” ) Return(null) } 插入算法續(xù) sdata=x。 p=head； pre=null。 head的單鏈表的第 K個 elementtype x。 k=k+1。 假設(shè)指針 p指向單鏈表中的第 i個結(jié)點，指針 s指向已生成的新結(jié)點，鏈入新結(jié)點的操作如下： 將新結(jié)點 *s的鏈域指向結(jié)點 *p的后繼結(jié)點 (即 snext=pnext)； 將結(jié)點 *p的鏈域指向新結(jié)點 (即 pnext=s)。 2) 生成一個以 x為值的新結(jié)點 。 ?空指針 NULL起標(biāo)志的作用，若無此標(biāo)志，尾結(jié)點鏈域的值為“無定義”，上述算法中的 while語句在做最后一次判斷時將出現(xiàn)“運行錯”，這是應(yīng)予避免的。 count++。 ?在實際應(yīng)用中遍歷是對單鏈表的最基本運算，例如，當(dāng)要打印或顯示出各個結(jié)點的數(shù)值域值、計算單鏈表的長度 (即結(jié)點數(shù)目 )或?qū)ふ夷骋粋€結(jié)點時都需要遍歷單鏈表。 a1 an ^ head ^ head 指針的概念 ?假設(shè) p是一個 pointer類型，應(yīng)正確區(qū)分指針型變量、指針、指針?biāo)傅慕Y(jié)點和結(jié)點的內(nèi)容這四個密切相關(guān)的不同概念： p的值（如果有的話）是一個指針，即是一個所指結(jié)點的地址 。 ?一個單鏈表由頭指針 head唯一標(biāo)識和確定，因此，可用頭指針來命名單鏈表。 } 順序表的應(yīng)用舉例 線性表的鏈?zhǔn)酱鎯? ? .1 單鏈表 ? 結(jié)點 : 在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，結(jié)點不僅存放數(shù)據(jù)元素的值，還附加一個指針（鏈），用來指向該結(jié)點的直接后繼結(jié)點。j++) [j1]=[j] ； 。 /*刪除值為 X的元素 IF（ ==0) printf (“空表！ \n”)。 ?用數(shù)量級的形式表示線性表插入、刪除運算的時間復(fù)雜性均為 O(n)。 /*I以后的元 。 ?當(dāng) i=n+1時，則循環(huán)一次也不進(jìn)行，這時元素直接插入到線性表尾的后面，所以線性表的所有 n個元素均不移動，這是最好的情況。 /*將第 i個元素及其后面的元素后移 */ [i1]=x。 if (i1 || i+1) printf(“i值錯 ！ \n”)。 int lenth。 若 n0, 則 a1是第 1個結(jié)點， an是最后一個結(jié)點。 ?在編程時以一維數(shù)組表示線性表最簡單，用的也最普遍。 ?線性表的元素個數(shù) n稱為這個表的長度，當(dāng)n=0時，這個表叫做空表。 ?表中的數(shù)據(jù)元素 , 除了第一個和最后一個以外，都有一個且只有一個前驅(qū)元素，同時也都有一個且只有一個后繼元素； ?第一個元素只有一個后繼元素而無前驅(qū)元素；最后一個元素只有一個前驅(qū)元素而無后繼元素。 ?如果已知線性表第一個元素的地址和每個元素占用的存儲單元數(shù)，由任一元素的序號就可以計算出該元素在內(nèi)存中的地址。 ? 線性表的定義 線性表是由 n個結(jié)點 a1， a2， …..,an 組成的有限序列，當(dāng) n=0時，線性表為空，即為空表。 ?線性表的基本運算： 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ù)組中 順序存儲的特點： 邏輯順序與物理順序一致， 元素之間的關(guān)系由物理位置的相鄰關(guān)系體現(xiàn) 3 6 8 9 2 線性表的順序存儲 ?地址計算 設(shè)順序表的每個元素占 c個存儲單元，并且元素所占的第一個單元的存儲地址作為順序表的存儲位置，則順序表中第 I個元素的存儲位置 Loc（ ai）滿足 Loc（ ai） =Loc（ ai1） + c Loc（ ai） =Lo
法律信息相關(guān)推薦
鄂ICP備17016276號-1