數(shù)據(jù)結(jié)構(gòu)之線性表課件-文庫吧資料
2024-09-08 09:01本頁面
【正文】 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é)約空間； 速度快。 如： slinklist sl[maxsize]。 int next。 } 返回 靜態(tài)鏈表 ?在某些語言中，沒有指針類型，就不能實(shí)現(xiàn)鏈表，可用一數(shù)組來模擬鏈表，這就是靜態(tài)鏈表。 /*修改指針 free(p)。 } 刪除算法續(xù) if (p=NULL) { printf (“x不存在 ” ) return(null)。 (pdata!=x)) { q=p。 while((p!=null) amp。 q=head。 elementtype x。 假設(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）。主要操作 是： 1) 用遍歷的方法在單鏈表上找到該結(jié)點(diǎn)； 2) 從單鏈表上刪除該結(jié)點(diǎn)。 prenext=s。 /*表的頭部 ， 即 k=1 head=s。 } s=(linklist *)malloc(sizeof(listlist)) if (s= =null) { printf (“沒有足夠的空間 ” ) Return(null) } 插入算法續(xù) sdata=x。 /*結(jié)點(diǎn) pre j++ } 插入算法續(xù) if(j!=k) { printf(“k超出鏈表的長度 ” )。 p=head； pre=null。 {linklist *p,*pre,*s。 head的單鏈表的第 K個(gè) elementtype x。 pnext=s。 k=k+1。 int k=0。 假設(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)。 3) 將新結(jié)點(diǎn)鏈入單鏈表中 。 2) 生成一個(gè)以 x為值的新結(jié)點(diǎn) 。 ?實(shí)現(xiàn)插入算法主要完成三個(gè)基本操作： 1) 在單鏈表上找到插入位置 ， 即找到第 i個(gè)結(jié)點(diǎn) 。 ?空指針 NULL起標(biāo)志的作用，若無此標(biāo)志，尾結(jié)點(diǎn)鏈域的值為“無定義”，上述算法中的 while語句在做最后一次判斷時(shí)將出現(xiàn)“運(yùn)行錯(cuò)”，這是應(yīng)予避免的。 /*返回表長值 */ } 算法分析 ?此算法的關(guān)鍵是 while循環(huán)語句，開始時(shí) p指針指向頭結(jié)點(diǎn)，每一循環(huán)都修改指針值，讓它指向下一個(gè)結(jié)點(diǎn)，同時(shí)將計(jì)數(shù)鏈表長度的變量 count加 1。 count++。 /*計(jì)數(shù)器置初值 */ p=head。 ?在實(shí)際應(yīng)用中遍歷是對(duì)單鏈表的最基本運(yùn)算，例如，當(dāng)要打印或顯示出各個(gè)結(jié)點(diǎn)的數(shù)值域值、計(jì)算單鏈表的長度 (即結(jié)點(diǎn)數(shù)目 )或?qū)ふ夷骋粋€(gè)結(jié)點(diǎn)時(shí)都需要遍歷單鏈表。 結(jié)點(diǎn) *p是由兩個(gè)域組成的記錄，這兩個(gè)域分別用p?data域和 p?next域來標(biāo)識(shí)，它們各有自己的值，p?data的值是一個(gè)數(shù)據(jù)元素， p?next的值是一個(gè)指針。 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)的地址 。 struct lnode *next； }linklist ?一個(gè)結(jié)點(diǎn)是由兩個(gè)域 data和 next組成的記錄 , data是結(jié)點(diǎn)的數(shù)據(jù)域， next是結(jié)點(diǎn)的鏈域。 ?一個(gè)單鏈表由頭指針 head唯一標(biāo)識(shí)和確定，因此，可用頭指針來命名單鏈表。 data next ?所有結(jié)點(diǎn)通過指針的鏈接而構(gòu)成的線性表稱為單鏈表。 } 順序表的應(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)。 該語句的作用？ } } if (i=) printf(“i值錯(cuò) ！ \n”)。j++) [j1]=[j] ； 。 else { for (j=I+1。 /*刪除值為 X的元素 IF（ ==0) printf (“空表！ \n”)。 Int LocateDeleteSeqlist(list sl。 ?用數(shù)量級(jí)的形式表示線性表插入、刪除運(yùn)算的時(shí)間復(fù)雜性均為 O(n)。 算法的時(shí)間復(fù)雜性 ?可以用數(shù)據(jù)元素的移動(dòng)次數(shù)來度量這兩個(gè)算法的時(shí)間復(fù)雜性。 /*I以后的元 。 else { for (k=i。 ?當(dāng) i=n+1時(shí)，則循環(huán)一次也不進(jìn)行，這時(shí)元素直接插入到線性表尾的后面，所以線性表的所有 n個(gè)元素均不移動(dòng)，這是最好的情況。 /*順序表長度加 1*/
法律信息相關(guān)推薦
鄂ICP備17016276號(hào)-1