計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第2章鏈表

1單鏈表(SinglyLinkedList)循環(huán)鏈表(CircularList)多項(xiàng)式及其相加雙向鏈表(DoublyLinkedList)稀疏矩陣第二章鏈表2單鏈表特點(diǎn)

每個(gè)元素(表項(xiàng))由結(jié)點(diǎn)(Node)構(gòu)成。線性結(jié)構(gòu)

結(jié)點(diǎn)可以不連續(xù)存儲(chǔ)表可擴(kuò)充3單鏈表的存儲(chǔ)映像4單鏈表中的插入與刪除插入第一種情況：在第一個(gè)結(jié)點(diǎn)前插入

newnode→link=first;first=newnode；（插入前）（插入后）x

5(插入前)(插入后)

第二種情況：在鏈表中間插入newnode→link=p→link;

p→link=newnode；6

第三種情況：在鏈表末尾插入

newnode→link=p→link;

p→link=last=newnode；(插入前)(插入后)7voidList::Insert(constintx,constinti){//在鏈表第i個(gè)結(jié)點(diǎn)處插入新元素xNode*p=first;intk=0;while(p!=NULL&&k<i-1){p=p→link;k++;}//找第i-1個(gè)結(jié)點(diǎn)

Node*newnode=newNode(x,NULL);//創(chuàng)建新結(jié)點(diǎn)if(first==NULL||i==0){//插在表前newnode→link=first; if(first==NULL)last=newnode; first=newnode;}else{//插在表中或末尾newnode→link=p→link; if(p→link==NULL)last=newnode;p→link=newnode;}}8刪除第一種情況:刪除表中第一個(gè)元素第二種情況:刪除表中或表尾元素在單鏈表中刪除含ai的結(jié)點(diǎn)9帶表頭結(jié)點(diǎn)的單鏈表表頭結(jié)點(diǎn)位于表的最前端，本身不帶數(shù)據(jù)，僅標(biāo)志表頭。設(shè)置表頭結(jié)點(diǎn)的目的是統(tǒng)一空表與非空表的操作，簡(jiǎn)化鏈表操作的實(shí)現(xiàn)。非空表 空表10在帶表頭結(jié)點(diǎn)的單鏈表:插入新結(jié)點(diǎn)

newnode→link=p→link; if(p→link==NULL)last=newnode;p→link=newnode;11

q=p→link;p→link=q→link;deleteq;if(p→link==NULL)last=p;從帶表頭結(jié)點(diǎn)的單鏈表中刪除一個(gè)結(jié)點(diǎn)12靜態(tài)鏈表結(jié)構(gòu):利用數(shù)組定義，運(yùn)算過(guò)程中存儲(chǔ)空間大小不變13循環(huán)鏈表(CircularList)循環(huán)鏈表是單鏈表的變形。循環(huán)鏈表最后一個(gè)結(jié)點(diǎn)的link指針不為0(NULL)，而是指向了表的前端。為簡(jiǎn)化操作，在循環(huán)鏈表中往往加入表頭結(jié)點(diǎn)。循環(huán)鏈表的特點(diǎn)是：只要知道表中某一結(jié)點(diǎn)的地址，就可搜尋到所有其他結(jié)點(diǎn)的地址。14循環(huán)鏈表的示例帶表頭結(jié)點(diǎn)的循環(huán)鏈表

15用循環(huán)鏈表求解約瑟夫問(wèn)題約瑟夫問(wèn)題的提法

n個(gè)人圍成一個(gè)圓圈，首先從1開(kāi)始一個(gè)人一個(gè)人順時(shí)針報(bào)數(shù),報(bào)到第m個(gè)人，令其出列。然后再?gòu)南乱粋€(gè)人開(kāi)始，從1順時(shí)針報(bào)數(shù)，報(bào)到第m個(gè)人，再令其出列，…，如此下去,直到圓圈中只剩一個(gè)人為止。此人即為優(yōu)勝者。例如n=8m=31617約瑟夫問(wèn)題的解法voidJosephus(int

n,intm){

for(int

i=0;

i<n-1;

i++){

//執(zhí)行n-1次

for(int

j=0;

j<m-1;

j++)Next();

cout<<“Deleteperson”<<

getData()<<endl;//數(shù)m-1個(gè)人

Remove();//刪去}}18多項(xiàng)式及其相加在多項(xiàng)式的鏈表表示中每個(gè)結(jié)點(diǎn)增加了一個(gè)數(shù)據(jù)成員link，作為鏈接指針。優(yōu)點(diǎn)是：多項(xiàng)式的項(xiàng)數(shù)可以動(dòng)態(tài)地增長(zhǎng)，不存在存儲(chǔ)溢出問(wèn)題。插入、刪除方便，不移動(dòng)元素。19多項(xiàng)式(polynomial)類(lèi)的鏈表定義struct

Term{

intcoef;

intexp;

void

Init(int

c,

int

e){coef=c;exp=e;

}};

20多項(xiàng)式鏈表的相加AH=1-10x6+2x8+7x14BH=-x4+10x6-3x10+8x14+4x1821雙向鏈表(DoublyLinkedList)雙向鏈表是指在前驅(qū)和后繼方向都能游歷(遍歷)的線性鏈表。雙向鏈表每個(gè)結(jié)點(diǎn)結(jié)構(gòu)：

前驅(qū)方向

后繼方向雙向鏈表通常采用帶表頭結(jié)點(diǎn)的循環(huán)鏈表形式。22結(jié)點(diǎn)指向

p==

p→lLink→rLink==p→rLink→lLink非空表 空表23搜索成功搜索不成功雙向循環(huán)鏈表的搜索算法24p→lLink=current; p→rLink=current→rLink; current→rLink=p;current=current→rLink;