線性表的鏈?zhǔn)酱鎯?chǔ).ppt

《線性表的鏈?zhǔn)酱鎯?chǔ).ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、第三章線性表的鏈?zhǔn)酱鎯?chǔ)主講人：張雄線性表定義：線性表是一個(gè)線性結(jié)構(gòu)，它是一個(gè)含有n≥0個(gè)結(jié)點(diǎn)的有限序列，對(duì)于其中的結(jié)點(diǎn)，有且僅有一個(gè)開始結(jié)點(diǎn)沒有前驅(qū)但有一個(gè)后繼結(jié)點(diǎn)，有且僅有一個(gè)終端結(jié)點(diǎn)沒有后繼但有一個(gè)前驅(qū)結(jié)點(diǎn)，其它的結(jié)點(diǎn)都有且僅有一個(gè)前驅(qū)和一個(gè)后繼結(jié)點(diǎn)。一般地，一個(gè)線性表可以表示成一個(gè)線性序列：k1,k2,…,kn，其中k1是開始結(jié)點(diǎn)，kn是終端結(jié)點(diǎn)。線性表在計(jì)算機(jī)中的存儲(chǔ)基本上市采取順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種方式。2.1線性表的定義及其運(yùn)算線性表舉例:(A,B,C,...,Z)表中數(shù)據(jù)元素為單個(gè)字母字

2、符(400,420,500,...,600,650)表中數(shù)據(jù)元素為整數(shù)(stu1,stu2,...,stu100)數(shù)據(jù)元素類型為下列所示的結(jié)構(gòu)類型：structstu{intnum;//學(xué)生學(xué)號(hào)char*name;//學(xué)生姓名intc;//C語言成績...;}鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)用一組任意的存儲(chǔ)單元來存放線性表的結(jié)點(diǎn)（這組存儲(chǔ)單元既可以是連續(xù)的，也可以是不連續(xù)的）結(jié)點(diǎn)結(jié)構(gòu)數(shù)據(jù)域指針域鏈表中結(jié)點(diǎn)的邏輯次序和物理次序不一定相同，為了能夠正確的表現(xiàn)結(jié)點(diǎn)之間的邏輯關(guān)系，在存儲(chǔ)每個(gè)結(jié)點(diǎn)的同時(shí)，還必須存儲(chǔ)指

3、示其后繼結(jié)點(diǎn)的地址（或位置）信息（稱為指針（pointer）或鏈（link））順序存儲(chǔ)結(jié)構(gòu)與鏈表存儲(chǔ)結(jié)構(gòu)比較1.存儲(chǔ)空間的比較順序表的存儲(chǔ)空間利用率為100%。在鏈表中的每個(gè)結(jié)點(diǎn)，除了數(shù)據(jù)域外，還要額外設(shè)置指針域，它的的存儲(chǔ)存儲(chǔ)空間利用率只為50%。由此可見，當(dāng)線性表的長度變化不大，易于事先確定其大小時(shí)，宜采用順序表作為存儲(chǔ)結(jié)構(gòu)。2.運(yùn)行時(shí)間的比較順序表是一種隨機(jī)存取結(jié)構(gòu)，可以在O(1)時(shí)間內(nèi)直接地存取表中任一結(jié)點(diǎn)，所以當(dāng)很少做插入和刪除、僅做查找操作時(shí)時(shí)，宜采用順序表做存儲(chǔ)結(jié)構(gòu)。對(duì)于插入和刪除操作，

4、在鏈表中只需要修改指針不必移動(dòng)數(shù)據(jù)元素。而在順序表中進(jìn)行時(shí)，平均要移動(dòng)表中近一半的結(jié)點(diǎn)。因此，對(duì)于頻繁進(jìn)行插入和刪除的線性表來說，宜采用鏈表做存儲(chǔ)結(jié)構(gòu)。3.應(yīng)用語言的比較靜態(tài)鏈表在存儲(chǔ)分配上有不足之處，但它仍然具有插入和刪除方便的特點(diǎn)。即使對(duì)于具有指針類型的語言，當(dāng)線性表的長度不變，僅需改變結(jié)點(diǎn)之間的相對(duì)關(guān)系時(shí)，靜態(tài)鏈表比動(dòng)態(tài)鏈表可能更方便。鏈?zhǔn)酱鎯?chǔ)單鏈表帶頭結(jié)點(diǎn)的單鏈表循環(huán)單鏈表雙鏈表?xiàng)：完?duì)列的鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)1.單鏈表與指針術(shù)語表示每個(gè)數(shù)據(jù)元素的兩部分信息組合在一起被稱為結(jié)點(diǎn)

5、；其中表示數(shù)據(jù)元素內(nèi)容的部分被稱為數(shù)據(jù)域（data）；表示直接后繼元素存儲(chǔ)地址的部分被稱為指針或指針域（next）。單鏈表的簡化形式如圖2.3所示：圖2.3單鏈表結(jié)構(gòu)示意圖單鏈表單鏈表是線性表鏈?zhǔn)酱鎯?chǔ)的一種形式，其中的節(jié)點(diǎn)一般含有兩個(gè)域，一個(gè)存放數(shù)據(jù)信息的info,另一個(gè)是指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)存放地址的指針next域?？諉捂湵恚篽ead——>^非空單鏈表：Head……^單鏈表的實(shí)現(xiàn)鏈表實(shí)現(xiàn)的頭文件：typedefintdatatype;typedefstructlink_node{datatypein

6、fo;structlink_node*next;}node;例1刪除單鏈表：刪除實(shí)際上就是要把第i個(gè)位置上的元素從鏈表中刪除，例如下圖為把第i個(gè)元素從鏈表中刪除：Pi-1Xtempi+1i由于刪除的是第i個(gè)位置上的元素，因此i的取值范圍是1到表長，具體做法：先用p指針找到第I個(gè)元素的前驅(qū)，然后用指針temp事先保存好p的指針域，接著讓p的指針域指向第i+1個(gè)結(jié)點(diǎn)。最后釋放temp指向的空間，這樣就完成了刪除的操作。帶頭結(jié)點(diǎn)鏈表的刪除代碼：intListDelete(LinkListL,inti){in

7、tj=1;linklistp=L,temp;for(;p->next&&jnext,j++);if(i<1

8、

9、!p->next)returnERROR;temp=p->next;p->next=temp->next;Free(temp);returnOK}例2單鏈表的插入：插入實(shí)際上就是要把新元素插入到第i個(gè)元素之前，下圖為把元素s插入到第i個(gè)元素結(jié)點(diǎn)之前。SPi-121i由于s是插入到第i個(gè)位置之前的，因此i的取值范圍是1到表長+1.具體做法：先用指針p找到第i-1個(gè)結(jié)點(diǎn)的位置，

10、然后修改S的指針域，讓其指向第i個(gè)結(jié)點(diǎn)，接著再去修改p的指針域讓其指向S，這樣就完成了插入的操作了帶頭結(jié)點(diǎn)的插入代碼：intListLinsert(LinkListL,intI,ElemTypevalue){intj=1;linklistp=L,s;for(;p&&jnext,j++);if(i<1

11、

12、p==NULL)returnERROR;S=(linklist)malloc(sizeof(LNode));S->next=p->next