大二上-p線性結(jié)構(gòu)鏈表

線性結(jié)構(gòu)：鏈表qin寬帶光纖傳輸與通信系統(tǒng)技術(shù)教育部Key

Laboratory

of

Broadband

Optical

Fiber

Transmissionand

Communication

Networks制作：段景山主講：的線性表的線性表（鏈表）的定義鏈表的引入數(shù)組結(jié)構(gòu)的缺點:在 、刪除時要移動大量的節(jié)點表的大小固定。預(yù)先在申明數(shù)組時指定，無法更改原因：存放的連續(xù)性突破離散存放用指針來表示元 間的關(guān)系。的線性表用鏈表實現(xiàn)線性表（非連續(xù)

）線性表元素：a1、a2、a3、a4....鏈表鏈點線性關(guān)系：a1a2a3a4指針域，指針關(guān)系鏈表的定義鏈表的定義鏈點datalink元素域

域元素域（數(shù)據(jù)元素域）：存放一個數(shù)據(jù)元素。

域（關(guān)系域）：存放指向下一個元素的指針——元素間的關(guān)系。元素域

+

域

=結(jié)點（鏈點）鏈表的定義鏈表a1a2an……h(huán)ead由鏈點及鏈點相互間的 構(gòu)成鏈表頭鏈表尾鏈表長度（節(jié)點數(shù)目）taillength鏈表的定義定義typedef

struct

node_type{elemtype

data;struct

node_type

*

next;}node_type

;typedef

struct

list_type{node_type

*head;node_type

*tail;int

length;}list_type;鏈點的定義鏈表的定義datanext鏈表的定義鏈表組織：list_type

*list;list->head

=

a1;a1->next

=

a2;a2->next

=

a3;……an->next

=

NULLlist->tail

=

an;list->length

=

n;a1a2an……h(huán)eadtailNULL，表示指針的值為

“空”，即指針指向空處鏈表的基本操作鏈表的基本操作刪除鏈表的基本操作鏈表的第i個節(jié)點操作問題描述：問題分析：輸入：鏈表，ia1a2an……h(huán)eadtail輸出：鏈點——指向鏈點的指針?biāo)惴▽崿F(xiàn)分析：只能從鏈表頭開始，一個一個“數(shù)”下去，直到第i個。temptemptemp}returnp;a1nextaiai+1anpnode_type

*get_node( list,

i

){int

counter

;node_type

*

p;p=list->head;counter

=

1;while(counter

<

i

&&p!=NULL){counter

=

counter

+1;p=p

->next;}if(

p

=

=

NULL)

return

NULL;a2：counter

3設(shè)i

＝

3操作注意1、p=p->next;沿鏈表前進(jìn)2、循環(huán)結(jié)束條件counter==i

或node==NULLcounter

>

list->length如果希望獲得值為x的元素，如何實現(xiàn)？while(p->data

==x

&&

p!=

NULL)操作新的元素new_node;鏈表

操作問題描述：在元素ai前問題分析：輸入：鏈表，location，x輸出： 新元素后的鏈表。算法實現(xiàn)分析操作a1aianheadtailai-1......anewa1aianheadtailai-1......anew兩個步驟：ai-1->next

=

anew

;anew->next

=

ai;操作void

insertl（list,

new_node

,

location）｛找到ai-1執(zhí)行

動作

兩個步驟：ai-1->next

=

anew

;anew->next

=

ai

;｝操作void

insertl（list,

new_node

,

location）｛找到ai-1ai-1->next

=

anew

;anew->next=

ai

;a1ai-1aianpnewnodea2p

＝list->header;counter

=

1while(

counter

<i

-1

&&p

!=NULL){counter

=

counter

+

1;p

=

p->next;q}q

=

p->next;p->next

=

new_node;new_node->next

=

q;法一｝操作void

insertl（list,

new_node

,

location）｛｝new_node->next

=

p->next;p->next

=

new_node;a1ai-1aianpnewnodea2p

＝list->header;counter

=

1while(

counter

<i

-1

&&p

!=NULL){counter

=

counter

+

1;p=

p->next;}法二操作｝list->length

++;void

insertl（list,

new_node

,

location）｛邊界情況：表首表

入counter

=

1;p=list->head;

初始化while(

counter

<i

-1

&&p

!=NULL){counter

=

counter

+

1;p

=

p->next;}new_node->next

=

p->next;p->next

=

new_node;操作a1ai-1aianlist->headnewnodenew_node->next

=

list->head;list->head=

new_node;void

insertl（list,

new_node

,

location）｛if(location

==

1){}else{new_node

=

list->head;list->head=new_node;counter

=

1;p=list->head;初始化while(

counter

<

i

-1

&&p!=

NULL){counter

=counter

+1;p

=

p->next;}new_node->next

=

p->next;p->next=new_node;｝}

list->length++;邊界情況：表首操作表入a1ai-1aianlist->headcounter=counter+1;

注意當(dāng)循環(huán)執(zhí)行到表尾時p

=

p->next;}new_node->next

=

p->next;p->next

=

new_node;p->next

!=

NULL){NULLp當(dāng)i>鏈表長度時while(

counter<

i

-1

&&p

的值為NULL（空）p->next是懸空的值會造成系統(tǒng)因此循環(huán)結(jié)束應(yīng)以

p->next==NULL為條件}void

insertl（list,

new_node,location）｛if(location==

1){new_node->next

=

list->head;list->head=

new_node;else{counter

=

1;p=list->head;while(

counter

<i

-1

&&p->next

!=NULL){counter

=

counter

+

1;p=

p->next;}new_node->next

=

p->next;p->next

=

new_node;｝}

list->length

++;從 算法中對鏈表操作的體會鏈表操作往往從表頭開始，逐個找到需要的鏈點鏈表操作的有向性不能回退；鏈表指針

使用，謹(jǐn)防丟失。過程沒有對鏈點內(nèi)容進(jìn)行搬移。指針使用一定要注意空指針的判斷鏈表的創(chuàng)建鏈表的創(chuàng)建從鏈點的生成過程中體會動態(tài)內(nèi)存申請的動作問題描述：根據(jù)輸入的元素，生成一個鏈點，并把它 到鏈表頭creat_list(

list, x){new_node=

(node_type*)malloc(sizeof(node_type));new_node->data

=

x;new_node->next

=

NULL;list->head=

new_node;}刪除操作鏈表的刪除操作問題描述：刪除元素ai

;問題分析：輸入：鏈表，location輸出：刪除元素后的鏈表。算法實現(xiàn)分析a1ai+1anheadtailai-1......ai即ai-1->next =

ai->next;ai-1->next

=

ai-1->next->next;void

dele找到ai-1刪除操作（list,location）｛執(zhí)行刪除動作ai-1->next

=

ai-1->next->next注意，從鏈表上取下的鏈點ai需要掛在一個指針上，否則可能丟失a1ai+1anhead｝tailai-1......aitempvoid

dele（list,location）｛｝}if(locat n==1){temp=list->head;list->head

=

list->head->next;free(temp);}else{counter

=

1;p=list->head;

初始化while(

counter

<i

-1

&&p

!=NULL){counter

=

counter

+

1;p

=

p->next;}temp

=

p->next;p->next

=

p->next->next;free(temp);list->length--;從鏈表刪除的鏈點，一般應(yīng)該 其空間刪除操作注意:對刪除鏈點的處理往往需要要free（

）如果希望刪除值為x的元素，如何實現(xiàn)？while(p->data

==x

&&

p

!=

NULL)鏈表的特點１、操作的順序性有平均Ｎ／２次查找過程２、離散存放不受鏈表大小限制不進(jìn)行鏈點內(nèi)容的搬移查找操作：數(shù)組效率優(yōu)于鏈表、刪除操作：鏈表效率優(yōu)于數(shù)組鏈表的特點其它一些操作相同于順序表來說：兩個有序鏈表的合并？思考：1、編程判斷兩個單向鏈表是否相交（假定這兩個鏈表本身不帶有環(huán)）；2、假設(shè)有一個沒有頭指針的單向鏈表。一個指針指向此單鏈表中間的一個節(jié)點（不是第一個，也不是最后一個節(jié)點），將該節(jié)點從單鏈表中刪除。節(jié)點的單鏈表節(jié)點的單鏈表頭節(jié)點：是一個特殊的鏈點，數(shù)據(jù)內(nèi)容無效鏈點指針指向鏈表頭/////a1...aian...a1an......ai頭節(jié)點頭指針鏈表的典型形態(tài)節(jié)點的單鏈表幾個容易 的概念第一個元素節(jié)點 頭指針 頭節(jié)點、鏈表頭a1ai+1anheadtailai-1......ai/////a1...aian...第一個元素節(jié)點、鏈表頭第一個元素節(jié)點頭指針頭節(jié)點head鏈表的典型形態(tài)節(jié)點單鏈表的操作特點和刪除算法不必考慮在表首進(jìn)行時，需要更改頭指針的特殊處理/////a1...aian...headp＝

head；while(location

>

1

&&p

!=NULL

){…}p->next

=

p->next->next;p為什么 中使用**而教案中沒有使用？

中僅定義了鏈點，沒有定義鏈表結(jié)構(gòu)，一個鏈表僅由一個頭指針開始程序中調(diào)用的上下文不同typedef

struct

list_type{node_type

*head;node_type

*tail;intlength;}list_type;headtaillengtha1a2為什么中使用**而教案中沒有使用？void

main（）{node*head;createsl(&head);……}void

createsl(

node

**h){*h

=

node;……}教案void

main（）{list_type

list;create_l(&list);……}void

create_l(list_type

*l){l->head=

node;……}headheadtaillengthheadtaillength為什么 中使用**而教案中沒有使用？本質(zhì)是一樣的：要在函數(shù)調(diào)用中改變頭指針的指向改變指針的指向，即改變指針變量的內(nèi)容要改變指針的內(nèi)容，必須將指針變量的地址傳入中是將指針的地址傳入－－指針的指針教案中將地址所在的結(jié)構(gòu)的地址傳入雙向鏈表a1headtailNa2NPanPPa1N雙向鏈表特點：每一個鏈點包含兩個指針，前趨指針后繼指針P：priorN：next……雙向鏈表的定義typedef

struct

double_link_node_type{struct

double_link_node_type

*

prior;struct

double_link_node_type

*

next;elemtype

data;}dl_node_type

;typedef

struct

double_link_list_type{dl_node_type

*head;dl_node_type

*tail;int

length;}dl_list_type;鏈點的定義鏈表的定義雙向鏈表ai-1NPaiNP問題描述：在第i個元素前 新元素雙向鏈表的

操作anewNP1、anew->next=ai2、

ai-1

->next

=anew3、anew->prior=ai-14、

ai->prior

=

anewpanew->next

=

p;p->prior->next=

anew;anew->prior

=

p->pri