大學《數(shù)據(jù)結(jié)構(gòu)》第二章：線性表-第三節(jié)-線性表的鏈式存儲結(jié)構(gòu)（四）

第三節(jié)線性表的鏈式存儲結(jié)構(gòu)（四）

三、循環(huán)鏈表

head..

I頭結(jié)點開始結(jié)點終端結(jié)點I

----------

循環(huán)鏈表與單鏈表的區(qū)別僅僅在于其尾結(jié)點的鏈域值不是NULL,

而是一個指向頭結(jié)點的指針。

循環(huán)鏈表的主要優(yōu)點是：從表中任意一結(jié)點出發(fā)都能通過后移操作

而遍歷整個循環(huán)鏈表。

在循環(huán)鏈表中，將頭指針改設為尾指針（rear）后，無論是找頭結(jié)

點、開始結(jié)點還是終端點都很方便，它們的存儲位置分別是

rear->next,rear->next->next和rear,這樣可以簡化某些操作。

例：已知有一個結(jié)點數(shù)據(jù)域為整型的，且按從大到小JI質(zhì)序排列的頭

結(jié)點指針為L的非空單循環(huán)鏈表，試寫一算法插入一個結(jié)點（其數(shù)據(jù)域

為x）至循環(huán)鏈表的適當位置，使之保持鏈表的有序性。

分析：要解決這個算法問題，首先就是要解決查找插入位置，方

法：使用指針q掃描循環(huán)鏈表，循環(huán)條件應該是

（q->data>x&&q!=L）,同時使用指針p記錄q的直接前驅(qū)，以方

便進行插入操作。

算法描述

voidInsertList(LinkListL,intx)

{〃將值為X的新結(jié)點插入到有序循環(huán)鏈表中適當?shù)奈恢?/p>

ListNode*s,*p,*q;

s=(ListNode*)malloc(sizeof(ListNode));

〃申請結(jié)點存儲空間

s->data=x;p=L;

q=p->next;//q

指向開始結(jié)點

while(q->data>x&&q!=L)//

查找插入位置

{p=p->next;〃p指

向q的前趨結(jié)點

q=p->next;//q

指向當前結(jié)點

)

p->next=s;〃插

入*s結(jié)點

s->next=q;

)

算法分析：

①該算法在最好情況下，也就是插入在第一個結(jié)點前面，循環(huán)一次

也不執(zhí)行；

②在最壞情況下，即插在最后一個結(jié)點之后，當循環(huán)需要執(zhí)行n

次；

③該算法的時間復雜度為O(n)o

真題選解

(例題?單選題)1、對于只在表的首、尾兩端進行插入操作的線性

表，宜采用的存儲結(jié)構(gòu)為()o

A.順序表

B.用頭指針表示的單循環(huán)鏈表

C.用尾指針表示的單循環(huán)鏈表

D.單鏈表

隱藏答案

【答案】C

【解析】在順序表的表頭插入，須將全部元素向表尾方向移動一個

位置，不可取。用頭指針表示的單循環(huán)鏈表和單鏈表很容易找到表

頭，但不易找到表尾。用尾指針表示的單循環(huán)鏈表既容易找到表尾又

容易找到表頭，便于在表的首、尾兩端進行插入操作。

(例題?算法設計題)2、假設以帶頭結(jié)點的單循環(huán)鏈表作非遞減有

序線性表的存儲結(jié)構(gòu)。請設計一個時間復雜度為0(n)的算法，刪除表

中所有數(shù)值相同的多余元素，并釋放結(jié)點空間。例如：

(7,10,10,21,30,42,42,42,51,70)

經(jīng)算法操作后變?yōu)椋?/p>

(7,10,21,30,42,51,70)

隱藏答案

【答案】

voiddeletelkliSt(LinkLiSthead)

{LinkNode*p,*q;

p=head->next;

while(p!=head)〃p掃描整個鏈表

{q=p->next;

while(q!=head&&q->data==p->data)〃發(fā)現(xiàn)相等元

素，刪除并釋放該結(jié)點

{p->next=q->next;

free(q);

q=p->next;

)

p=p->next;

)

)

【解析】題目要求單循環(huán)鏈表中所有數(shù)值相同的多余元素，需要設

置指針變量p從第一個結(jié)點出發(fā)，再用指針變量q從p的直接后繼結(jié)

點開始檢測與p結(jié)點的值相等的結(jié)點。若相等，則刪除q結(jié)點，若不

等，則p移向后繼。如此重復，直到p==head,即直到所有結(jié)點都

被p掃描處理完畢為止。

四、雙向鏈表

雙向循環(huán)鏈表示意圖

頭結(jié)點開始結(jié)點終端結(jié)點

雙向鏈表結(jié)點

prior|data|next

雙向鏈表及其結(jié)點的類型描述

typedefstructdlnode

{DataTypedata;

structdlnode*prior,*next;

}DLNode;〃雙向鏈表結(jié)點的類型定義

typedefDLNode*DLinkList;

DlinkListhead;//head為指向雙向鏈表的指針

雙鏈表結(jié)構(gòu)是一種對稱結(jié)構(gòu)，既有前向鏈，又有后向鏈，這就使得

插入操作及刪除操作都非常方便。設指針p指向雙鏈表的某一結(jié)點，

則雙鏈表結(jié)構(gòu)的對稱性可用下式來描述：

p->prior->next==p->next->prior==p

在雙鏈表上實現(xiàn)求表長、按序號查找、定位、插入和刪除等運算與

單鏈表上的實現(xiàn)方法基本相同，不同的主要是插入和刪除操作。

1、刪除操作.

刪除雙鏈表中p所指結(jié)點

p

分析：操作過程如圖所示

①p->prior->next=p->next;②p->next

->prior=p->prior;

算法描述

DataTypeDLDelete(DLNode*p)

(〃刪除帶頭結(jié)點的雙向鏈表中指定結(jié)點*p

p->prior->next=p->next;

p->next->prior=p->prior;//上面兩條語句的順序可以調(diào)換,

不影響操作結(jié)果。

x=p->data;

free(p);

returnx;

)

算法分析：算法的時間復雜度為0(1)

2、插入操作:

將值為X的新結(jié)點插入到帶頭結(jié)點的雙向鏈表中指定結(jié)點*p之前。

分析：操作過程如圖所示

算法描述

voidDLInsert(DLNode*p,DataTypex)

{〃將值為x的新結(jié)點插入到帶頭結(jié)點的雙向鏈表中指定結(jié)點*p之

前

DLNode*s=(DLNode*)malloc(sizeof(DLNode));〃申

請新結(jié)點

s->data=x;

s->prior=p->prior;〃完成①

步操作

s->next=p;〃完成②

步操作

p->prior->next=s;〃完成③

步操作

p->prior=s;〃完成④

步操作

)

算法分析：算法的時間復雜度為0(1)

補充：在P所指結(jié)點的后面鏈入一個新結(jié)點*S，則需修改四個指

針：

①s->prior=p;②s->next=p->next;

(3)p->next->prior=s;④p->next=s;

注：③和④兩條語句的順序不能調(diào)換，否則操作結(jié)果錯誤。

下面四條語句也可以完成插入操作。

①s->prior=p;②s->next=p->next;

(3)p->next=s;④s->next->prior=s;

真題選解

(例題?單選題)1、在帶頭結(jié)點的雙向循環(huán)鏈表中插入一個新結(jié)

點，需要修改的指針域數(shù)量是()

A.2個B.3個C.4個D.6個

隱藏答案

【答案】C

【解析】如前面講解的在雙鏈表進行插入操作需要修改4個指針

域。

例：假設有一個頭結(jié)點指針為head的循環(huán)雙向鏈表，其結(jié)點類型

結(jié)構(gòu)包括三個域：、和其中為數(shù)據(jù)域，

priordatanextodatanext

為指針域，指向其后繼結(jié)點，prior■也為指針域，其值為空(NULL),

因此該雙向鏈表其實是一個單循環(huán)鏈表。試寫一算法，將其表修改為

真正的雙向循環(huán)鏈表。

分析：鏈表初始狀態(tài)如下圖所示

方法：以p指向頭結(jié)點開始，循環(huán)使用語句p->next->prior=p;

和p=p->next;即可實現(xiàn)題目要求。

當前講授

算法描述

voidtrans(DLinkListhead)

(

DLNode*p;

p=head;〃使p指向頭結(jié)點

while(p->next!=head)