數(shù)據(jù)結構第周

1、 線性表（下） 學習內容：1 線性表的鏈式存儲結構鏈表2 單鏈表的建立（頭插法與尾插法）3 單鏈表的插入與刪除操作4 雙鏈表與循環(huán)鏈表5 鏈表與順序表的比較 A1094 1249 1249 headB1021CNull 1094 1021 頭指針 單鏈表結構空地址 鏈表是一組結點序列，其中每個結點總要與它前面的一結點相鏈接（但第一個結點除外）。表中每個結點包含兩個部分：一個是用于存放數(shù)據(jù)的數(shù)據(jù)域，另一個是用于指向下一個結點的指針域。表中最后一個結點因為不再指向任何其他節(jié)點，故其指針域的值應為NULL。動態(tài)鏈表的建立動態(tài)鏈表的建立是指在程序執(zhí)行過程中從無到有地建立一個鏈表，即一個一個地開辟結點和

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

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

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

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

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

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

8、結構中的 a與 b之間,以形成新的鏈表結構的語句組是: 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;練習： 答案：DA hFNULL 2 若已建立下面的鏈表結構，指針 p、s 分別指向 圖中所示的節(jié)點，則不能將s所指的節(jié)點插入到鏈表 末尾的語句組是： 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;練習： 答案：C雙鏈表鏈表的另一種存儲方法是:在每個結點中除包含有數(shù)值域外,設置有兩個指針域,分別用來指向其前驅結點和后繼結點,這樣構成的鏈接表稱之為線性雙向鏈接表,簡稱雙鏈表。帶頭結點的雙鏈表示意圖1 在雙向鏈表中,由于每個結點既包含有一個指向后繼結點的指針,又包含有一個指向前驅結點的指針,所以當訪問過一個結點后,既可以依次向后訪問每一個結點,也可以依次向前訪問每一個結點。2 在雙鏈表中，有些操作如求長度、取元素值和查找元素等操作算法與單鏈表中

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