數(shù)據(jù)結(jié)構(gòu)與算法：鏈表

鏈表線性鏈表雙向鏈表鏈?zhǔn)綏ｆ準(zhǔn)疥?duì)列數(shù)據(jù)結(jié)構(gòu)與算法：鏈表全文共18頁，當(dāng)前為第1頁。5鏈表--線性鏈表順序存儲(chǔ)方式結(jié)構(gòu)簡單，可以根據(jù)下標(biāo)隨機(jī)存取數(shù)據(jù)，但是也有缺點(diǎn)：插入或刪除操作時(shí)需要移動(dòng)大量元素，效率低；對(duì)于長度可變的線性表，要預(yù)先分配足夠的空間。

鏈?zhǔn)酱鎯?chǔ)：用一組任意的存儲(chǔ)單元存儲(chǔ)線性表中的數(shù)據(jù)元素。用這種方法存儲(chǔ)的線性表簡稱線性鏈表。1.線性鏈表存儲(chǔ)鏈表中結(jié)點(diǎn)的一組任意的存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的，甚至是零散分布在內(nèi)存中的任意位置上的。

鏈表中結(jié)點(diǎn)的邏輯順序和物理順序不一定相同。數(shù)據(jù)結(jié)構(gòu)與算法：鏈表全文共18頁，當(dāng)前為第2頁。結(jié)點(diǎn)元素：值與指針。存儲(chǔ)指示其直接后繼結(jié)點(diǎn)的地址(或位置)，稱為指針(pointer)或鏈(link)，如下圖所示。鏈表是通過每個(gè)結(jié)點(diǎn)的指針域?qū)⒕€性表的n個(gè)結(jié)點(diǎn)按其邏輯次序鏈接在一起的。每一個(gè)結(jié)只包含一個(gè)指針域的鏈表，稱為單鏈表。為操作方便，總是在鏈表的第一個(gè)結(jié)點(diǎn)之前附設(shè)一個(gè)頭結(jié)點(diǎn)(頭指針)head指向第一個(gè)結(jié)點(diǎn)。頭結(jié)點(diǎn)的數(shù)據(jù)域可以不存儲(chǔ)任何信息(或鏈表長度等信息)。datanext圖

鏈表結(jié)點(diǎn)結(jié)構(gòu)data：數(shù)據(jù)域，存放結(jié)點(diǎn)的值。next：指針域，存放結(jié)點(diǎn)的直接后繼的地址。5鏈表--線性鏈表數(shù)據(jù)結(jié)構(gòu)與算法：鏈表全文共18頁，當(dāng)前為第3頁。

headfat1100bat1300…………cat1305eat3700hatNULL…………1100370013001305batcateatfat

hat?head

圖

帶頭結(jié)點(diǎn)的單鏈表的邏輯狀態(tài)、物理存儲(chǔ)方式單鏈表是由表頭唯一確定，因此單鏈表可以用頭指針的名字來命名。例1、線性表L=(bat，cat，eat，fat，hat)其帶頭結(jié)點(diǎn)的單鏈表的邏輯狀態(tài)和物理存儲(chǔ)方式如圖所示。5鏈表--線性鏈表36953695數(shù)據(jù)結(jié)構(gòu)與算法：鏈表全文共18頁，當(dāng)前為第4頁。結(jié)點(diǎn)的描述與實(shí)現(xiàn)

C語言中用帶指針的結(jié)構(gòu)體類型來描述typedefstructLnode{ElemTypedata;/*數(shù)據(jù)域，保存結(jié)點(diǎn)的值*/structLnode*next;/*指針域*/}LNode;/*結(jié)點(diǎn)的類型*/結(jié)點(diǎn)的實(shí)現(xiàn)

結(jié)點(diǎn)是通過動(dòng)態(tài)分配和釋放來的實(shí)現(xiàn)，即需要時(shí)分配，不需要時(shí)釋放。實(shí)現(xiàn)時(shí)是分別使用C語言提供的標(biāo)準(zhǔn)函數(shù)：malloc()，realloc()，sizeof()，free()。5鏈表--線性鏈表數(shù)據(jù)結(jié)構(gòu)與算法：鏈表全文共18頁，當(dāng)前為第5頁。常見的指針操作①

q=p;pa……操作前pa……q操作后②

q=p->next;bpa……操作前操作后qbpa……③

p=p->next;bpa……操作前操作后pba……數(shù)據(jù)結(jié)構(gòu)與算法：鏈表全文共18頁，當(dāng)前為第6頁。常見的指針操作④

q->next=p;c…pbqa……操作前操作后qb……ac…p(a)操作前ypx……bqa…操作后ypx……bqa…(b)數(shù)據(jù)結(jié)構(gòu)與算法：鏈表全文共18頁，當(dāng)前為第7頁。⑤

q->next=p->next;(a)xy…pbqa……操作前操作后qb……axy…p操作前ypx……bqa…操作后ypx……bqa…(b)數(shù)據(jù)結(jié)構(gòu)與算法：鏈表全文共18頁，當(dāng)前為第8頁。線性鏈表的基本運(yùn)算：查找、插入、刪除(1)單鏈表的查找按值查找是在鏈表中，查找是否有結(jié)點(diǎn)值等于給定值key的結(jié)點(diǎn)?若有，則返回首次找到的值為key的結(jié)點(diǎn)的存儲(chǔ)位置；否則返回NULL。查找時(shí)從開始結(jié)點(diǎn)出發(fā)，沿鏈表逐個(gè)將結(jié)點(diǎn)的值和給定值key作比較。5鏈表--線性鏈表的基本操作數(shù)據(jù)結(jié)構(gòu)與算法：鏈表全文共18頁，當(dāng)前為第9頁。（2）單鏈表的插入

插入運(yùn)算是將值為e的新結(jié)點(diǎn)插入到表的第i個(gè)結(jié)點(diǎn)的位置上，即插入到ai-1與ai之間。因此，必須首先找到ai-1所在的結(jié)點(diǎn)p，然后生成一個(gè)數(shù)據(jù)域?yàn)閑的新結(jié)點(diǎn)q，q結(jié)點(diǎn)作為p的直接后繼結(jié)點(diǎn)。具體操作語句：q->next=p->next;p->next=q;5鏈表--線性鏈表的基本操作ai-1nextainextenextpqai-1nextainextenextpq插入前插入后×數(shù)據(jù)結(jié)構(gòu)與算法：鏈表全文共18頁，當(dāng)前為第10頁。（3）單鏈表的刪除為了刪除第i個(gè)結(jié)點(diǎn)ai，必須找到結(jié)點(diǎn)的存儲(chǔ)地址。該存儲(chǔ)地址是在其直接前趨結(jié)點(diǎn)ai-1的next域中，因此，必須首先找到ai-1的存儲(chǔ)位置p，然后令p–>next指向ai的直接后繼結(jié)點(diǎn)，即把a(bǔ)i從鏈上摘下。最后釋放結(jié)點(diǎn)ai的空間，將其歸還給“存儲(chǔ)池”。具體操作：p->next=(p->next)->next5鏈表--線性鏈表的基本操作ai-1nextainextai+1nextpai-1nextainextai+1nextp××操作前操作后數(shù)據(jù)結(jié)構(gòu)與算法：鏈表全文共18頁，當(dāng)前為第11頁。5.5鏈表--循環(huán)鏈表2.循環(huán)鏈表(CircularLinkedList)：是一種頭尾相接的鏈表。其特點(diǎn)是最后一個(gè)結(jié)點(diǎn)的指針域指向鏈表的頭結(jié)點(diǎn)，整個(gè)鏈表的指針域鏈接成一個(gè)環(huán)。從循環(huán)鏈表的任意一個(gè)結(jié)點(diǎn)出發(fā)都可以找到鏈表中的其它結(jié)點(diǎn)，使得表處理更加方便靈活。下圖是帶頭結(jié)點(diǎn)的單循環(huán)鏈表的示意圖?？毡?/p>

單循環(huán)鏈表示意圖非空表a1

a2

……anhead

head

數(shù)據(jù)結(jié)構(gòu)與算法：鏈表全文共18頁，當(dāng)前為第12頁。循環(huán)鏈表的操作對(duì)于單循環(huán)鏈表，除鏈表的合并外，其它的操作和單線性鏈表基本上一致，僅僅需要在單線性鏈表操作算法基礎(chǔ)上作以下簡單修改：⑴判斷是否是空鏈表：head->next==head;⑵判斷是否是表尾結(jié)點(diǎn)：p->next==head;5鏈表--循環(huán)鏈表數(shù)據(jù)結(jié)構(gòu)與算法：鏈表全文共18頁，當(dāng)前為第13頁。

雙向鏈表(DoubleLinkedList):指的是構(gòu)成鏈表的每個(gè)結(jié)點(diǎn)中設(shè)立兩個(gè)指針域：一個(gè)指向其直接前趨的指針域prior，一個(gè)指向其直接后繼的指針域next。這樣形成的鏈表中有兩個(gè)方向不同的鏈，故稱為雙向鏈表。和單鏈表類似，雙向鏈表一般增加頭指針也能使雙鏈表上的某些運(yùn)算變得方便。

將頭結(jié)點(diǎn)和尾結(jié)點(diǎn)鏈接起來也能構(gòu)成循環(huán)鏈表，并稱之為雙向循環(huán)鏈表。雙向鏈表是為了克服單鏈表的單向性的缺陷而引入的。5鏈表--雙向鏈表數(shù)據(jù)結(jié)構(gòu)與算法：鏈表全文共18頁，當(dāng)前為第14頁。datanextprior

雙向鏈表結(jié)點(diǎn)形式……非空雙向鏈表head?a2a1an?空雙向鏈表head??帶頭結(jié)點(diǎn)的雙向鏈表形式5鏈表--雙向鏈表數(shù)據(jù)結(jié)構(gòu)與算法：鏈表全文共18頁，當(dāng)前為第15頁。3.鏈?zhǔn)綏５逆準(zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為鏈?zhǔn)綏?，是運(yùn)算受限的單鏈表。其插入和刪除操作只能在表頭位置上進(jìn)行。因此，鏈棧沒有必要像單鏈表那樣附加頭結(jié)點(diǎn)，棧頂指針top就是鏈表的頭指針。右圖是棧的鏈?zhǔn)酱鎯?chǔ)表示形式?？諚op?非空棧top

a4

a3

a1?

a2鏈棧存儲(chǔ)形式5鏈表--鏈?zhǔn)綏＃ㄟx講）數(shù)據(jù)結(jié)構(gòu)與算法：鏈表全文共18頁，當(dāng)前為第16頁。4.隊(duì)列的鏈?zhǔn)酱鎯?chǔ)表示隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡稱為鏈隊(duì)列，它是限制僅在表頭進(jìn)行刪除操作和表尾進(jìn)行插入操作的單鏈表。需要兩類不同的結(jié)點(diǎn)：數(shù)據(jù)元素結(jié)點(diǎn)，隊(duì)列的隊(duì)首指針和隊(duì)尾指針的結(jié)點(diǎn)，如圖所示。數(shù)據(jù)元素結(jié)點(diǎn)data指針結(jié)點(diǎn)front

rear鏈隊(duì)列結(jié)點(diǎn)示意圖5鏈表--鏈?zhǔn)疥?duì)列（選講）數(shù)據(jù)結(jié)構(gòu)與算法：鏈表全文共18頁，當(dāng)前為第17頁。鏈隊(duì)的操作實(shí)際上是單鏈表的操作，只不過是刪除在表頭進(jìn)行，插入在表尾進(jìn)行。插入、刪除時(shí)分別修改不