數(shù)據(jù)結(jié)構(gòu)第周

1、 線性表（下） 學(xué)習(xí)內(nèi)容：1 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈表2 單鏈表的建立（頭插法與尾插法）3 單鏈表的插入與刪除操作4 雙鏈表與循環(huán)鏈表5 鏈表與順序表的比較 A1094 1249 1249 headB1021CNull 1094 1021 頭指針 單鏈表結(jié)構(gòu)空地址 鏈表是一組結(jié)點(diǎn)序列，其中每個(gè)結(jié)點(diǎn)總要與它前面的一結(jié)點(diǎn)相鏈接（但第一個(gè)結(jié)點(diǎn)除外）。表中每個(gè)結(jié)點(diǎn)包含兩個(gè)部分：一個(gè)是用于存放數(shù)據(jù)的數(shù)據(jù)域，另一個(gè)是用于指向下一個(gè)結(jié)點(diǎn)的指針域。表中最后一個(gè)結(jié)點(diǎn)因?yàn)椴辉僦赶蛉魏纹渌?jié)點(diǎn)，故其指針域的值應(yīng)為NULL。動(dòng)態(tài)鏈表的建立動(dòng)態(tài)鏈表的建立是指在程序執(zhí)行過程中從無到有地建立一個(gè)鏈表，即一個(gè)一個(gè)地開辟結(jié)點(diǎn)和

2、輸入各結(jié)點(diǎn)數(shù)據(jù)，并建立起前后相鏈的關(guān)系。 采用頭插法建立單鏈表的過程bcdai=0i=1i=2i=3headheadaheaddaheadcdaheadbcda第1步:建頭結(jié)點(diǎn)第2步:i0,新建a結(jié)點(diǎn),插入到頭結(jié)點(diǎn)之后第3步:i1,新建d結(jié)點(diǎn),插入到頭結(jié)點(diǎn)之后第4步:i2,新建c結(jié)點(diǎn),插入到頭結(jié)點(diǎn)之后第5步:i3,新建b結(jié)點(diǎn),插入到頭結(jié)點(diǎn)之后采用頭插法建立單鏈表的過程總結(jié)為：1 建立新結(jié)點(diǎn)2 將頭結(jié)點(diǎn)的指針域指向新結(jié)點(diǎn)3 將新結(jié)點(diǎn)的指針域指向原來鏈表中的第一個(gè)結(jié)點(diǎn)4 特殊情況，若原來的鏈表為空，則將新結(jié)點(diǎn)的指針域置為空指針。尾插法建立單鏈表head 建立新結(jié)點(diǎn) 向新結(jié)點(diǎn)的數(shù)據(jù)域中添入內(nèi)容 將原

3、來鏈表中最后一個(gè)結(jié)點(diǎn)的指針域指向新結(jié)點(diǎn) 將新結(jié)點(diǎn)的指針域置為空指針單鏈表的插入操作10010 68.5 10011 77.8 1001288.5 NULL head200080.5 abcx例: 已有一個(gè)按學(xué)生分?jǐn)?shù)從低到高排好序的鏈表,要求插入一個(gè)結(jié)點(diǎn)后,學(xué)生的分?jǐn)?shù)域仍然有序。 為了能做到正確插入，必須解決兩個(gè)問題： 怎樣找到插入的位置； 怎樣實(shí)現(xiàn)插入10010 68.5 10011 77.8 1001288.5 NULL 200080.5 x 思路：1 先用指針變量p0指向待插入的結(jié)點(diǎn)，p1指向第一個(gè)結(jié)點(diǎn)2 將p0-score與p1-score相比較，如果p0-score大于p1-score

4、 ，則待插入的結(jié)點(diǎn)不應(yīng)插在p1所指的結(jié)點(diǎn)之前。此時(shí)將p1后移，并使p2指向剛才p1所指的結(jié)點(diǎn)。 p1 p2 head p0 10010 68.5 10011 77.8 1001288.5 NULL 200080.5 x 思路：3 再將p1-score與p0-score比,如果仍然是p0-score大，則應(yīng)使p1繼續(xù)后移，直到p0-scorescore為止。4 這時(shí)將p0所指的結(jié)點(diǎn)插到p1所指結(jié)點(diǎn)之前。則將p0的值賦給p2-next，使p2-next指向待插入的結(jié)點(diǎn)，然后將p1的值賦給p0-next，使得p0-next指向p1指向的變量。 p2 head p0 p1 10010 68.5 100

5、11 77.8 1001288.5 head200090.5 NULL abcx思考：當(dāng)插入的位置在第一個(gè)結(jié)點(diǎn)之前或者最后一個(gè)結(jié)點(diǎn)之后的時(shí)候，該如何操作？1 如果插入位置為第一個(gè)結(jié)點(diǎn)之前，則將p0賦給head，將p1 賦給p0-next2 如果要插到表尾之后，應(yīng)將p0賦給p1-next，NULL賦給 p0-next200360.5 p0 p0 p1 p1 Y動(dòng)態(tài)鏈表的刪除操作從一個(gè)動(dòng)態(tài)鏈表中刪去一個(gè)結(jié)點(diǎn)，并不是真正從內(nèi)存中把它抹掉，而是把它從鏈表中分離開來，只要撤銷原來的鏈接關(guān)系即可。動(dòng)態(tài)鏈表的刪除操作例：在一個(gè)鏈表中刪去一個(gè)學(xué)號(hào)為n的結(jié)點(diǎn)。總體思路:從p指向的第一個(gè)結(jié)點(diǎn)開始，檢查該結(jié)點(diǎn)中的學(xué)

6、號(hào)值是否等于輸入的要求刪除的那個(gè)學(xué)號(hào)。如果相等就將該結(jié)點(diǎn)刪除，如不相等，就將p后移一個(gè)結(jié)點(diǎn)，再如此進(jìn)行下去，直到遇到表尾為止。動(dòng)態(tài)鏈表的刪除操作例：在一個(gè)鏈表中刪去一個(gè)學(xué)號(hào)為n的結(jié)點(diǎn)。思路: 1 可以設(shè)兩個(gè)指針變量p1和p2，先使p1指向第一個(gè)結(jié)點(diǎn). 2 如果要?jiǎng)h除的不是第一個(gè)結(jié)點(diǎn)，則使p1后移指向下一個(gè)結(jié)點(diǎn)(將p1-next賦給p1)，在此之前應(yīng)將p1的值賦給p2 ，使p2指向剛才檢查過的那個(gè)結(jié)點(diǎn) 3 將p1-next賦給p2-next ，p2-next原來指向p1指向的結(jié)點(diǎn)，現(xiàn)在p2-next改為指向p1-next所指向的結(jié)點(diǎn)。p1所指向的結(jié)點(diǎn)不再是鏈表的一部分。動(dòng)態(tài)鏈表的刪除的特殊操作例

7、：在一個(gè)鏈表中刪去第一個(gè)結(jié)點(diǎn)。思路: 1 要?jiǎng)h的是第一個(gè)結(jié)點(diǎn)（的值等于的值，則應(yīng)將-賦給。這時(shí)指向原來的第二個(gè)結(jié)點(diǎn)。第一個(gè)結(jié)點(diǎn)雖然仍存在，但它已與鏈表脫離，因?yàn)殒湵碇袥]有一個(gè)結(jié)點(diǎn)或頭指針指向它。雖然還指向它，它仍指向第二個(gè)結(jié)點(diǎn)，但仍無濟(jì)于事，現(xiàn)在鏈表的第一個(gè)結(jié)點(diǎn)是原來的第二個(gè)結(jié)點(diǎn)，原來第一個(gè)結(jié)點(diǎn)已“丟失” ，即不再是鏈表中的一部分了。 2 還需要考慮鏈表是空表（無結(jié)點(diǎn)）和鏈表中找不到要?jiǎng)h除的結(jié)點(diǎn)的情況。 圖11-20 1 若有以下定義: struct link int data; struct link *next; a,b,c,*p,*q;5 p a9 b7 c q能將節(jié)點(diǎn)C 插入到上述鏈表

8、結(jié)構(gòu)中的 a與 b之間,以形成新的鏈表結(jié)構(gòu)的語句組是: A) a.next=c; c.next=b; B) p.next=q; q.next=p.next; C) p-next=&c; q- next=p-next; D) (*p).next=q; (*q).next=&b;練習(xí)： 答案：DA hFNULL 2 若已建立下面的鏈表結(jié)構(gòu)，指針 p、s 分別指向 圖中所示的節(jié)點(diǎn)，則不能將s所指的節(jié)點(diǎn)插入到鏈表 末尾的語句組是： pC s A) s-next=NULL; p=p-next; p-next=s; B) p=p-next; s-next=p-next; p-next=s; C) p=p-

9、next; s-next=p; p-next=s; D) p=(*p).next; (*s).next=(*p).next; (*p).next=s;練習(xí)： 答案：C雙鏈表鏈表的另一種存儲(chǔ)方法是:在每個(gè)結(jié)點(diǎn)中除包含有數(shù)值域外,設(shè)置有兩個(gè)指針域,分別用來指向其前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn),這樣構(gòu)成的鏈接表稱之為線性雙向鏈接表,簡稱雙鏈表。帶頭結(jié)點(diǎn)的雙鏈表示意圖1 在雙向鏈表中,由于每個(gè)結(jié)點(diǎn)既包含有一個(gè)指向后繼結(jié)點(diǎn)的指針,又包含有一個(gè)指向前驅(qū)結(jié)點(diǎn)的指針,所以當(dāng)訪問過一個(gè)結(jié)點(diǎn)后,既可以依次向后訪問每一個(gè)結(jié)點(diǎn),也可以依次向前訪問每一個(gè)結(jié)點(diǎn)。2 在雙鏈表中，有些操作如求長度、取元素值和查找元素等操作算法與單鏈表中

10、相應(yīng)算法是相同的。但在單鏈表中,進(jìn)行結(jié)點(diǎn)插入和刪除時(shí)涉及到前后結(jié)點(diǎn)的一個(gè)指針域的變化。而在雙鏈表中,結(jié)點(diǎn)的插入和刪除操作涉及到前后結(jié)點(diǎn)的兩個(gè)指針域的變化。循環(huán)鏈表是另一種形式的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。它的特點(diǎn)是表中最后一個(gè)結(jié)點(diǎn)的指針域不再是空,而是指向表頭結(jié)點(diǎn),整個(gè)鏈表形成一個(gè)環(huán)。由此,從表中任一結(jié)點(diǎn)出發(fā)均可找到鏈表中其他結(jié)點(diǎn)。 順序表和鏈表的比較基于時(shí)間的考慮1）順序表的是一種隨機(jī)存取結(jié)構(gòu)，而鏈表中的結(jié)點(diǎn)都需要從頭指針開始遍歷鏈表。2）在鏈表中任何位置上插入與刪除都只要修改指針，而順序表需要移動(dòng)表中將近一半的元素。尤其是對(duì)于結(jié)點(diǎn)信息量較大的表，開銷很大。順序表和鏈表的比較基于空間的考慮1）順序表的存儲(chǔ)空間在程序執(zhí)行之間必須明確規(guī)定它的存儲(chǔ)規(guī)模，若表的