計算機軟件技術基礎第2章鏈表

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

每個元素(表項)由結點(Node)構成。線性結構

結點可以不連續(xù)存儲表可擴充3單鏈表的存儲映像4單鏈表中的插入與刪除插入第一種情況：在第一個結點前插入

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個結點處插入新元素xNode*p=first;intk=0;while(p!=NULL&&k<i-1){p=p→link;k++;}//找第i-1個結點

Node*newnode=newNode(x,NULL);//創(chuàng)建新結點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刪除第一種情況:刪除表中第一個元素第二種情況:刪除表中或表尾元素在單鏈表中刪除含ai的結點9帶表頭結點的單鏈表表頭結點位于表的最前端，本身不帶數(shù)據(jù)，僅標志表頭。設置表頭結點的目的是統(tǒng)一空表與非空表的操作，簡化鏈表操作的實現(xiàn)。非空表 空表10在帶表頭結點的單鏈表:插入新結點

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;從帶表頭結點的單鏈表中刪除一個結點12靜態(tài)鏈表結構:利用數(shù)組定義，運算過程中存儲空間大小不變13循環(huán)鏈表(CircularList)循環(huán)鏈表是單鏈表的變形。循環(huán)鏈表最后一個結點的link指針不為0(NULL)，而是指向了表的前端。為簡化操作，在循環(huán)鏈表中往往加入表頭結點。循環(huán)鏈表的特點是：只要知道表中某一結點的地址，就可搜尋到所有其他結點的地址。14循環(huán)鏈表的示例帶表頭結點的循環(huán)鏈表

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

n個人圍成一個圓圈，首先從1開始一個人一個人順時針報數(shù),報到第m個人，令其出列。然后再從下一個人開始，從1順時針報數(shù)，報到第m個人，再令其出列，…，如此下去,直到圓圈中只剩一個人為止。此人即為優(yōu)勝者。例如n=8m=31617約瑟夫問題的解法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個人

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

Term{

intcoef;

intexp;

void

Init(int

c,

int

e){coef=c;exp=e;

}};

20多項式鏈表的相加AH=1-10x6+2x8+7x14BH=-x4+10x6-3x10+8x14+4x1821雙向鏈表(DoublyLinkedList)雙向鏈表是指在前驅和后繼方向都能游歷(遍歷)的線性鏈表。雙向鏈表每個結點結構：

前驅方向

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

p==

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