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