上章回顧常見的數據結構的形式算法的時間復雜度是如何計算的算法的空間復雜度是什么鏈表第四章預習檢查線性鏈表循環鏈表雙向鏈表課程目標本章概述本章主要介紹運用結構體構造鏈表，以及鏈表的相應的操作本章目標熟練構造和掌握鏈表及相關添加，查找，刪除操作。重點掌握鏈表的構造以及相關操作。難點鏈表的本章結構雙向循環鏈表數據結構與算法初步單向鏈表操作4.1鏈表單鏈表單鏈表上基本運算的實現循環鏈表雙向鏈表靜態鏈表單鏈表的應用實例4.1.1

單鏈表單鏈表的概述動態進行

分配的一種結構在內存中不連續存放頭節點：指向第一個元素節點：鏈表中的每一個元素（結構體）兩部分：實際數據和下一個節點地址尾指針定義typedef

struct

node{datatype

data;struct

node

*next;}

LNode，*LinkList；/*指向本結點類型的指針是實現鏈表的基礎*/4.1.1

單鏈表單鏈表的概述動態進行

分配的一種結構在內存中不連續存放頭節點：指向第一個元素節點：鏈表中的每一個元素（結構體）兩部分：實際數據和下一個節點地址尾指針定義typedef

struct

node{datatype

data;struct

node

*next;}

LNode，*LinkList；/*指向本結點類型的指針是實現鏈表的基礎*/4.1.1

單鏈表頭指針來標識一個單鏈表，如單鏈表L、單鏈表H等，是指某鏈表的第一個結點的地址放在了指針變量L、H

中，頭指針為“NULL”則表示一個空表內存分配函數：void

*malloc(unsigned

int

size)void

*

calloc(unsigned

n,unsigned

size)分配成功返回指向起始地址的指針分配不成功返回零內存

函數void

free(void

*p)申請鏈表空間p=malloc(sizeof(LNode))；4.1.1

單鏈表帶表頭結點的單鏈表表頭結點位于表的最前端，本身不帶數據，僅標志表頭設置表頭結點的目的:簡化鏈表操作的實現非空表空表^ana1^4.1.2.單鏈表上基本運算的實現建立單鏈表求表長

查找操作刪除4.1.2.1建立單鏈表在鏈表的頭部 結點建立單鏈表newnode->next

=

;=

newnode;（ 前）（ 后）newnodenewnode4.1.2.1建立單鏈表在鏈表的頭部 結點建立單鏈表算法如下：LinkList

Creat_LinkList1(

){LinkList

L=NULL；/*空表*/Lnode*s;int

x;

/*設數據元素的類型為int*/scanf(＂%d＂,&x);while(x!=flag){s=malloc(sizeof(LNode));s->data=x;s->next=L;

L=s;Scanf(＂%d＂,&x);}return

L;}4.1.2.1建立單鏈表在單鏈表的尾部 結點建立單鏈表newnode->next

=

p->next;p->next

=newnode；(

前)(

后)newnodenewnodep4.1.2.1建立單鏈表在鏈表的尾部結點建立單鏈表算法如下：LinkList

Creat_LinkList2(

){LinkList

L=NULL;Lnode

*s,*r=NULL;int

x;

/*設數據元素的類型為int*/scanf(＂%d＂,&x);while(x!=flag){s=malloc(sizeof(LNode));s->data=x;if

(L==NULL)

L=s;

/*第一個結點的處理*/else

r->next=s;

/*其它結點的處理*/r=s; /*r

指向新的尾結點*/scanf(＂%d＂,&x);}if(r!=NULL)

r->next=NULL;/*對于非空表，最后結點的指針域放空指針*/return

L;}4.1.2.1建立單鏈表在鏈表中間newnode->next

=

p->next;p->next

=

newnode

；(

前)(

后)newnodepnewnodep4.1.2.2

求表長節點的鏈表算法思路：設一個移動指針ｐ和計數器ｊ，初始化后，ｐ所指結點后面若還有結點，ｐ向后移動，計數器加1。算法如下：int

Length_LinkList1

(LinkList

L){/*

p指向頭結點*/Lnode

*

p=L;int

j=0;while(p->next){

p=p->next;

j++

}/*

p所指的是第j個結點*/return

j;}4.1.2.2

求表長不節點的鏈表算法思路：設一個移動指針ｐ和計數器ｊ，初始化后，ｐ所指結點后還有結點，ｐ向后移動，計數器加1。算法如下：int

Length_LinkList2

(LinkList

L){Lnode

*

p=L;int

j;if(p==NULL)return

0;/*空表的情況*/j=1;

/*在非空表的情況下，p所指的是第一個結點*/;while

(p->next

){

p=p->next;

j++

}return

j;}4.1.2.2

查找操作按序號查找算法思路：從鏈表的第一個元素結點起，判斷當前結點是否是第i個，若是，則返回該結點的指針，否則繼續后一個，表結束為止。沒有第ｉ個結點時返回空。算法如下：Lnode

*

Get_LinkList(LinkList

L,

Int

i);/*在單鏈表L中查找第i個元素結點，找到返回其指針，否則返回空*/{Lnode

*

p=L;int

j=0;while

(p->next

!=NULL

&&

j<i){

p=p->next;

j++;

}if

(j==i)

return

p;else

return

NULL;}4.1.2.2

查找操作按值查找即定位算法思路：從鏈表的第一個元素結點起，判斷當前結點其值是否等于x，若是，返回該結點的指針，否則繼續后一個，表結束為止。找不到時返回空。算法如下：Lnode

*Locate_LinkList(

LinkList

L,

datatype

x)/*在單鏈表L中查找值為x的結點，找到后返回其指針，否則返回空*/{Lnode

*

p=L->next;while

(

p!=NULL

&&

p->data

!=

x)p=p->next;return

p;}4.1.2.3后插結點q->next

=

p->next;p->next

=

q;后qqq^q^pppp前4.1.2.3運算算法如下：int

Insert_LinkList(

LinkList

L,

int

i,datatype

x)/*在單鏈表L的第i個位置上 值為x的元素*/{/*查找第i-1個結點*/Lnode

*

p,*s;p=Get_LinkList(L,i-1);if

(p==NULL){printf(＂參數i錯＂);return

0;}

/*第i-1個不存在不能

*/else

{s=malloc(sizeof(LNode));/*申請、填裝結點*/s->data=x;/*新結點 在第i-1個結點的后面*/s->next=p->next;p->next=sreturn1;}}4.1.2.4刪除在單鏈表中刪除ai結點q

=

p->next;p->next=

q->next;刪除前刪除后Ai-1aiAi+1ai-1aiai+1pqp

4.1.2.4刪除/*刪除單鏈表L上的第i個數據結點*/在單鏈表中刪除ai結點\算法如下int

Del_LinkList(LinkList

L，int

i){LinkList

p,s;p=Get_LinkList(L,i-1);

/*查找第i-1個結點*/if(p==NULL){printf(＂第i-1個結點不存在＂);return-1;}

else{ if

(p->next==NULL){printf(＂第i個結點不存在＂);return

0;}else{s=p->next;/*s指向第i個結點*/p->next=s->next;free(s);

/*/*從鏈表中刪除*/*s

*/}}return

1;}4.1.3循環鏈表特點:可以從表中任意結點開始遍歷整個鏈表不用頭指針而用一個指向尾結點的指針R來標識節點的單循環鏈表(a)非空表圖2.16

結點的單循環鏈表a1Han…(b)空表H4.1.3循環鏈表單循環鏈表H1

、H2的連接操作鏈表若用尾指針R1

、R2來標識將H2的第一個數據結點接到H1的尾結點操作語法p=

R1

–>next;

/*保存R1的頭結點指針*/R1->next=R2->next->next; /*頭尾連接*/free(R2->next);

/*

第二個表的頭結點*/R2->next=p; /*組成循環鏈表*/兩個用尾指針標識的單循環鏈表的連接R2b1bn…×

a1an…R1×p4.1.4雙向鏈表特點一個指向前驅的指針域一個指向后驅的指針域一個數據域定義表達:typedef

struct{dlnodedatatype

data;struct

dlnode

*prior,*next;}DLNode,*DLinkList;雙向鏈表priordatanext4.1.4雙向鏈表鏈表表現模式圖2.19結點的雙循環鏈表(b)空表H(a)非空表…Ha2a1an4.1.5

單鏈表應用舉例例一已知單鏈表H，寫一算法將其倒置。即實現如圖2.22的操作。(a)為倒置前，(b)為倒置后。單鏈表的倒置25∧45187629H29∧76184525H(a)(b)4.1.6

單鏈表應用舉例例一算法表達:void

reverse

(Linklist

H){LNode

*p;p=H->next;/*p指向第一個數據結點*/H->next=NULL;/*將原鏈表置為空表H*/while(p){q=p;

p=p->next;q->next=H->next;/*將當前結點插到頭結點的后面*/H->next=q;}}4.1.6

單鏈表應用舉例例二已知單鏈表L，寫一算法，刪除其重復結點，即實現如圖2.23的操作。(a)為刪除前，(b)為刪除后刪除重復結點10∧15181510H(a)18∧1510H(b)4.1.6

單鏈表應用舉例例二算法實現void

pur_LinkList(LinkList

H){LNode

*p,*q,*r;p=H->next;/*p指向第一個結點*/if(p==NULL)