數(shù)據(jù)結(jié)構(gòu)之線性表課件-預(yù)覽頁
【正文】 c（ a1） +（ i1） * c 線性表的順序存儲(chǔ) ?結(jié)點(diǎn)描述 define Maxlen 順序表的最大長(zhǎng)度 typedef struct seqenlist {elementtype elements [maxlen]。 插入函數(shù) int insert(list L, int i, elementtype x) { int k。 k) [k]=[k1]。 } } 插入函數(shù)分析 ?在循環(huán)語句中，當(dāng) i=1時(shí)，須循環(huán) n次，表示元素插入線性表頭的前面，則原線性表中 n個(gè)元素均須向后移動(dòng)一個(gè)單元，這是最不利的情況。 k； k++) [k1] = [k]。 ?插入時(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。 elementtype： x) { Int I=0, j。j=。 return(0)。線性表（ a1， a2， ……a n，）的單鏈表可直觀地畫成： ? head是單鏈表的頭指針，指向開始結(jié)點(diǎn) a1, an是終端結(jié)點(diǎn)，其指針域?yàn)榭眨恢赶蛉魏谓Y(jié)點(diǎn)。 ?鏈表舉例 ?空表 …… H ^ a1 an ?為了編程方便，一般在單鏈表的第一個(gè)結(jié)點(diǎn)之前加一個(gè)“頭結(jié)點(diǎn)”，如： ?當(dāng)為空表時(shí)，即 headnext=null, 如下圖。 單鏈表的基本運(yùn)算 ? 1. 遍歷 (Traversal)：根據(jù)已給的表頭指針，按由前向后的次序訪問單鏈表的各個(gè)結(jié)點(diǎn)。 /*p指向頭結(jié)點(diǎn) */ while (p!=NULL) { p=pnext。 ?這樣每循環(huán)一次就向后推移一個(gè)結(jié)點(diǎn)，直到 p所指結(jié)點(diǎn) *p的鏈域值為 NULL為止。 可以用遍歷的方法 ， 即從表頭起順次訪問單鏈表的結(jié)點(diǎn) ， 直至找到第 i個(gè)結(jié)點(diǎn) 。 需要改變相關(guān)結(jié)點(diǎn)的指針 ， 如下面的圖所示 。 while ((p!=null) $$ (kI)) { p=pnext。 return(head) 插入算法 Linklist *insertllist (head, x, k) / 在頭指針為 linklist *head。 int j=1。 return(null)。 } else { snext=p。 ?欲從單鏈表上刪除一個(gè)結(jié)點(diǎn)，需修改該結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)的指針，如下面的圖所示。 { linklist *q,*p。amp。 } else { qnext=pnext。 ?靜態(tài)鏈表的定義 define maxsize 元素的最大個(gè)數(shù) typedef struct {elementtype data。 定義了一個(gè)有 maxsize個(gè)元素的數(shù)組，每個(gè)元素由信息域和指針域組成。 ?循環(huán)鏈表并不多占存儲(chǔ)單元，但從循環(huán)鏈表的任一個(gè)結(jié)點(diǎn)出發(fā)都可以訪問到此鏈表的每一個(gè)結(jié)點(diǎn)，因?yàn)楫?dāng)訪問到表尾結(jié)點(diǎn)后又能返回到頭結(jié)點(diǎn)。 h e a d ?若 pnext=head，則 p就是指向最后一個(gè)結(jié)點(diǎn)； ?若 headnext=head，則為空表。 對(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) ,……, 直到表空為止。 } clinklist。 i) s1=(s1+m1)%i。因?yàn)槲步Y(jié)點(diǎn)由尾指針 rear來指示，則頭結(jié)點(diǎn)的位置是 rearnextnext。 head ?雙向鏈表為空鏈表時(shí)， head 即 headnext=null ? ? ?雙鏈表較單鏈表雖然要多占用一些存儲(chǔ)單元，但對(duì)其插入和刪除操作以及查找結(jié)點(diǎn)的前趨和后繼都非常方便。 struct dbnode *next。 (pprior)next=q。 ?這兩個(gè)語句的執(zhí)行順序可以顛倒，執(zhí)行這兩個(gè)語句之后，可調(diào)用 free(p),將 *p結(jié)點(diǎn)釋放。 求此兩多項(xiàng)式之和 C(x)=A(x)+B(x)。 } polyn。 例 ? 一個(gè)單鏈表 L(至少有一個(gè)結(jié)點(diǎn) )，其頭結(jié)點(diǎn)指針為 head，編寫一個(gè)函數(shù)將 L倒置。 p=head。 p=q。 } 例 ?有兩個(gè)循環(huán)單鏈表，頭指針分為 head1和 head2，編寫函數(shù)將鏈表 head2鏈接到鏈表 head1之后，鏈接后的鏈表仍保持是循環(huán)鏈表的形式。 while(pnext!=head1) p=pnext。 qnext=head1。 int j。 headprior=s。 while(p!=NULL amp。 } if(p!=NULL) /*若查找成功 ， 把 s插入到 p之后 */ if(pnext==NULL) /*若 p是最后一個(gè)結(jié)點(diǎn)，則直接把 s結(jié)點(diǎn)鏈入 */ 例3.3算法續(xù) { pnext=s。 pnextprior=s。 } } 返回 小結(jié) ?單鏈表 ?循環(huán)鏈表 ?雙向鏈表 ?雙向循環(huán)鏈表 ?十字鏈表 返回 習(xí)題與練習(xí) ?一、基礎(chǔ)知識(shí)題 1. 試比較順序表與鏈表的優(yōu)缺點(diǎ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)互換，但指針不變。 5. 已知一個(gè)遞增有序的單鏈表，編寫一個(gè)函數(shù)向該單鏈表中插入一個(gè)元素為 x的結(jié)點(diǎn)，使插入后該鏈表仍然遞增有序。 9. 已知一個(gè)指針 p指向單循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)，編寫一個(gè)對(duì)此單循環(huán)鏈表進(jìn)行遍歷的算法。
法律信息相關(guān)推薦
鄂ICP備17016276號(hào)-1