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

鏈表線性鏈表雙向鏈表鏈式棧鏈式隊列數(shù)據(jù)結(jié)構與算法：鏈表全文共18頁，當前為第1頁。5鏈表--線性鏈表順序存儲方式結(jié)構簡單，可以根據(jù)下標隨機存取數(shù)據(jù)，但是也有缺點：插入或刪除操作時需要移動大量元素，效率低；對于長度可變的線性表，要預先分配足夠的空間。

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

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

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

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

hat?head

圖

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

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

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

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

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

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

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

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

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

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

a2

……anhead

head

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

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

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

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

a4

a3

a1?

a2鏈棧存儲形式5鏈表--鏈式棧（選講）數(shù)據(jù)結(jié)構與算法：鏈表全文共18頁，當前為第16頁。4.隊列的鏈式存儲表示隊列的鏈式存儲結(jié)構簡稱為鏈隊列，它是限制僅在表頭進行刪除操作和表尾進行插入操作的單鏈表。需要兩類不同的結(jié)點：數(shù)據(jù)元素結(jié)點，隊列的隊首指針和隊尾指針的結(jié)點，如圖所示。數(shù)據(jù)元素結(jié)點data指針結(jié)點front

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