數(shù)據(jù)結(jié)構(gòu)之線性表課件-免費(fèi)閱讀
【正文】 9. 已知一個(gè)指針 p指向單循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)，編寫一個(gè)對(duì)此單循環(huán)鏈表進(jìn)行遍歷的算法。 6. 請(qǐng)利用鏈表來表示下面一元多項(xiàng)式 781194)( 3811 ????? xxxxxA?二、算法設(shè)計(jì)題 1. 有一個(gè)有 n個(gè)結(jié)點(diǎn)的單鏈表，設(shè)計(jì)一個(gè)函數(shù)將第 i1個(gè)結(jié)點(diǎn)與第 i個(gè)結(jié)點(diǎn)互換，但指針不變。 pnextprior=s。 while(p!=NULL amp。 int j。 while(pnext!=head1) p=pnext。 p=q。 例 ? 一個(gè)單鏈表 L(至少有一個(gè)結(jié)點(diǎn) )，其頭結(jié)點(diǎn)指針為 head，編寫一個(gè)函數(shù)將 L倒置。 求此兩多項(xiàng)式之和 C(x)=A(x)+B(x)。 (pprior)next=q。 head ?雙向鏈表為空鏈表時(shí)， head 即 headnext=null ? ? ?雙鏈表較單鏈表雖然要多占用一些存儲(chǔ)單元，但對(duì)其插入和刪除操作以及查找結(jié)點(diǎn)的前趨和后繼都非常方便。 i) s1=(s1+m1)%i。 對(duì)給定的 m（第 1次給定 m，以后即為結(jié)點(diǎn)的pwd），從第一個(gè)結(jié)點(diǎn)開始，尋找第 m個(gè)結(jié)點(diǎn)，將其輸出，并取出該結(jié)點(diǎn)的 pwd，執(zhí)行 m=pwd；從下一個(gè)結(jié)點(diǎn)繼續(xù)尋找第 m個(gè)結(jié)點(diǎn) ,……, 直到表空為止。 ?循環(huán)鏈表并不多占存儲(chǔ)單元，但從循環(huán)鏈表的任一個(gè)結(jié)點(diǎn)出發(fā)都可以訪問到此鏈表的每一個(gè)結(jié)點(diǎn)，因?yàn)楫?dāng)訪問到表尾結(jié)點(diǎn)后又能返回到頭結(jié)點(diǎn)。 ?靜態(tài)鏈表的定義 define maxsize 元素的最大個(gè)數(shù) typedef struct {elementtype data。amp。 ?欲從單鏈表上刪除一個(gè)結(jié)點(diǎn)，需修改該結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)的指針，如下面的圖所示。 return(null)。 return(head) 插入算法 Linklist *insertllist (head, x, k) / 在頭指針為 linklist *head。 需要改變相關(guān)結(jié)點(diǎn)的指針 ， 如下面的圖所示 。 ?這樣每循環(huán)一次就向后推移一個(gè)結(jié)點(diǎn)，直到 p所指結(jié)點(diǎn) *p的鏈域值為 NULL為止。 單鏈表的基本運(yùn)算 ? 1. 遍歷 (Traversal)：根據(jù)已給的表頭指針，按由前向后的次序訪問單鏈表的各個(gè)結(jié)點(diǎn)。線性表（ a1， a2， ……a n，）的單鏈表可直觀地畫成： ? head是單鏈表的頭指針，指向開始結(jié)點(diǎn) a1, an是終端結(jié)點(diǎn)，其指針域?yàn)榭眨恢赶蛉魏谓Y(jié)點(diǎn)。j=。 ?插入時(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ù)分析 ?在循環(huán)語句中，當(dāng) i=1時(shí)，須循環(huán) n次，表示元素插入線性表頭的前面，則原線性表中 n個(gè)元素均須向后移動(dòng)一個(gè)單元，這是最不利的情況。 插入函數(shù) int insert(list L, int i, elementtype x) { int k。 ? 線性表的定義 線性表是由 n個(gè)結(jié)點(diǎn) a1， a2， …..,an 組成的有限序列，當(dāng) n=0時(shí)，線性表為空，即為空表。 ?表中的數(shù)據(jù)元素 , 除了第一個(gè)和最后一個(gè)以外，都有一個(gè)且只有一個(gè)前驅(qū)元素，同時(shí)也都有一個(gè)且只有一個(gè)后繼元素； ?第一個(gè)元素只有一個(gè)后繼元素而無前驅(qū)元素；最后一個(gè)元素只有一個(gè)前驅(qū)元素而無后繼元素。 ?在編程時(shí)以一維數(shù)組表示線性表最簡單，用的也最普遍。 int lenth。 /*將第 i個(gè)元素及其后面的元素后移 */ [i1]=x。 /*I以后的元 。 /*刪除值為 X的元素 IF（ ==0) printf (“空表！ \n”)。 } 順序表的應(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)。 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)的地址 。 count++。 2) 生成一個(gè)以 x為值的新結(jié)點(diǎn) 。 k=k+1。 p=head； pre=null。 prenext=s。 q=head。 /*修改指針 free(p)。 ?例： L=（ a， b， c， d， e， f）， 0 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é)約空間； 速度快。 ?例：約瑟夫（ Josephus）問題。 ? Int josephus_seqlist( pseqlist josephus_sq,int s,m) { /*順序存儲(chǔ)在 josephus_sq中，從第 s個(gè)元素開始 s1=s1。
法律信息相關(guān)推薦
鄂ICP備17016276號(hào)-1