線性表學習筆記之鏈表
原創博文,轉載請注明 出處
鏈表分類:單鏈表,插入刪除和查找的時間復雜度均為O(n)
? ? ? ? ? ? ? 雙鏈表,插入、刪除和查找的時間復雜度為O(1)
? ? ? ? ? ? ? 循環鏈表,表中最后一個節點的指針不是NULL,而改為指向頭結點,從而整個鏈表形成一個環。
? ? ? ? ? ? ?靜態鏈表,借助數組來描述線性表的鏈式存儲結構,這兒的指針是結點的相對地址。和順序表一樣需要預先分配一塊連續的內存空間。以next==0作為其結束的標志。
綜合應用:
1.設計一個遞歸算法,刪除不帶頭節點的單鏈表L中所有值為x的節點。
? ? ? ? ? ? 思路:可以設計一個函數f(L,x)刪除以L為首結點指針的單鏈表中所有值為x的結點,那么f(L->next,x)則是刪除以L->next為首結點指針的單鏈表中所有值等于x的結點。
? ? ? ? ? ? ? ? ? ? 借助一個遞歸工作棧,深度為O(n),時間復雜度為O(n)

void Del_x(Linklist &L, ElemType x){
LNode *p; //p指向待刪除結點
if(L==NULL)
return;
if(L->data==x){
p=L;
L=L->next;
free(p);
Del_x(L, x);
}
else
Del_x(L->next, x);
}
1 void Del_x(Linklist & L, ElemType x){ 2 LNode *p; // p指向待刪除結點 3 4 if (L== NULL) 5 return ; 6 if (L->data== x){ 7 p= L; 8 L=L-> next; 9 free(p); 10 Del_x(L, x); 11 } 12 else 13 Del_x(L-> next, x); 14 }
? ? ? ? ? 2. 設L為帶頭結點 的單鏈表,編寫算法實現從尾到頭反向輸出每個結點的值。
? ? ? ? ? ?思路:方法一、將鏈表逆置,改變鏈表的方向。
? ? ? ? ? ? ? ? ? 方法二、借助一個棧,將結點放入棧中。在遍歷完整個鏈表后,再從棧頂開始輸出結點值。
? ? ? ? ? ? ? ? ? 方法三、使用遞歸,當訪問一個結點時,先遞歸輸出它后面的結點,再輸出該結點自身。實現如下

void R_Print(LinkList L){ 2 if (L->next!= NULL){ 3 R_Print(L-> next) 4 } 5 print(L-> next) 6 }
1 void R_Print(LinkList L){ 2 if (L->next!= NULL){ 3 R_Print(L-> next) 4 } 5 print(L-> next) 6 }
? ? ? ? 3.試編寫在帶頭結點的單鏈表L中刪除一個最小值結點的高效算法(假設最小值結點唯一)
? ? ? ??

LinkList Delete_Min(LinkList &L){
LNode *pre=L, *p=L->next; //p為工作指針,pre指向其前驅
LNode *minpre=pre, *minp=p;
while(p!=NULL){
if(p->data<minpre->data){
minp=p;
minpre=pre;
}
pre=p;
p=p->next;
}
minpre->next=minp->next;
free(minp);
return L;
}
1 LinkList Delete_Min(LinkList & L){ 2 LNode *pre=L, *p=L->next; // p為工作指針,pre指向其前驅 3 LNode *minpre=pre, *minp= p; 4 5 while (p!= NULL){ 6 if (p->data<minpre-> data){ 7 minp= p; 8 minpre= pre; 9 } 10 pre= p; 11 p=p-> next; 12 } 13 minpre->next=minp-> next; 14 free(minp); 15 return L; 16 }
? ? ? ? 4.編寫算法將帶頭結點的單鏈表就地逆置,就地指輔助空間為O(1)
? ? ? ? ?方法一:將頭結點摘下,然后從第一結點開始,依次前插入到頭節點后面(頭插法建立鏈表),直到最后一個節點為止。

LinkList Reverse(LinkList &L){
p=L->next;
L->next=NULL;
while(p!=NULL){
r=p->next;
p->next=L->next;
L->next=p;
p=r;
}
return L;
}
1 LinkList Reverse(LinkList & L){ 2 p=L-> next; 3 L->next= NULL; 4 while (p!= NULL){ 5 r=p-> next; 6 p->next=L-> next; 7 L->next= p; 8 p= r; 9 } 10 return L; 11 }
? ? ? ? 方法二:將結點的next域指向前驅結點。在處理完最后一個結點時,需要將頭結點的指針指向它。時間復雜度均為O(n)

LinkList Reverse(LinkList &L){
LNode *pre,*p=L->next,*r=p->next;
p->next=NULL;
while(r!=NULL){
pre=p;
p=r;
r=r->next;
p->next=pre;
}
L->next=p;
return L;
}
1 LinkList Reverse(LinkList & L){ 2 LNode *pre,*p=L->next,*r=p-> next; 3 p->next= NULL; 4 while (r!= NULL){ 5 pre= p; 6 p= r; 7 r=r-> next; 8 p->next= pre; 9 } 10 L->next= p; 11 return L; 12 }
? ? ? 5. 有一個帶頭結點的單鏈表L,設計一個算法使其元素遞增有序。
? ? ? 思路:采用直接插入排序的算法,先構成只含一個數據結點的有序單鏈表,然后依次掃描單鏈表中剩下的結點*p。
?

void Sort(LinkList &L){
LNode *p=L->next, *pre
LNode *r=p->next;
p->next=NULL;
p=r;
while(p!=NULL){
r=p->next;
pre=L;
while(pre->next!=NULL&&pre->next->data<p->data)
pre=pre->next;
p->next=pre->next;
pre->next=p;
p=r;
}
}
1 void Sort(LinkList & L){ 2 LNode *p=L->next, * pre 3 LNode *r=p-> next; 4 p->next= NULL; 5 p= r; 6 while (p!= NULL){ 7 r=p-> next; 8 pre= L; 9 while (pre->next!=NULL&&pre->next->data<p-> data) 10 pre=pre-> next; 11 p->next=pre-> next; 12 pre->next= p; 13 p= r; 14 } 15 16 }
? ? 6.在單鏈表L中刪除p所指結點,能夠實現在O(1)的時間內刪除該結點?
? ? ?思路:傳統的做法需要順序查找刪除結點的前驅結點,再修改鏈接。但是時間復雜度為O(n)。由于我們知道該結點的下一結點P->next,所以我們只需要將下一結點的數據復制到該結點,然后刪除它的下一結點。如果該結點位于鏈表尾部 即P=NULL,這時候我們需要從鏈表的頭結點開始順序遍歷給定節點的前驅結點,這時雖然時間復雜度為O(n),但在平均情況下,仍為O(1)。
? ?7.給定兩個單鏈表,編寫算法找出兩個鏈表的公共結點。
? ? 思路:比較麻煩的做法就是在第一個鏈表上順序遍歷每個節點,每遍歷一個結點都要在第二個鏈表上順序遍歷所有結點。找到兩個相同的結點,該算法時間復雜度為O(len1*len2)。
? ? ? ? ? ? 由于每個單鏈表結點只有一個next域,因此從第一個公共結點開始,之后所有的結點都是重合的,拓撲形狀看起來像Y,而不是X。但是,兩個鏈表有可能不一樣長,所以我們需要截取長鏈表多余的部分。

LinkList Search_Common(LinkList &L1,LinkList &L2){
int len1=Length(L1),len2=Length(L2);
LinkList longList,shorList;
if(len1>len2){
longList=L1->next;shortList=L2->next;
dist=len1-len2;
}
else{
longList=L2->next,shortList=L1->next;
dist=len2-len1;
}
while(dist--)
longList=longList->next
while(longList!=NULL){
if(longList==shortList)
return longList;
else{
longList=longList->next;
shortList=shortList->next;
}
}
return NULL;
}
1 LinkList Search_Common(LinkList &L1,LinkList & L2){ 2 int len1=Length(L1),len2= Length(L2); 3 LinkList longList,shorList; 4 if (len1> len2){ 5 longList=L1->next;shortList=L2-> next; 6 dist=len1- len2; 7 } 8 else { 9 longList=L2->next,shortList=L1-> next; 10 dist=len2- len1; 11 } 12 while (dist-- ) 13 longList=longList-> next 14 while (longList!= NULL){ 15 if (longList== shortList) 16 return longList; 17 else { 18 longList=longList-> next; 19 shortList=shortList-> next; 20 } 21 } 22 return NULL; 23 }
? ?8.設C={a1,b1,a2,b2,...,an,bn}為線性表,采用帶頭結點的hc單鏈表存放,設計一個就地算法,將其拆分為兩個線性表,使得A={a1,a2,...,an}, B={bn,...,b2,b1}.
? ?思路:采用頭插法新建B表,而A表則使用尾插法。

LinkList DisCreat(LinkList &A){
LinkList B=(LinkList)malloc(sizeof(LNode))
B->next=NULL;
LNode *p=A->next;
LNode *ra=A; //ra始終指向A的尾結點
while(p!=NULL){
ra->next=p;
ra=p;
p=p->next;
q=p->next;
p->next=B->next;
B->next=p;
p=q;
}
ra->next=NULL;
return B;
}
1 LinkList DisCreat(LinkList & A){ 2 LinkList B=(LinkList)malloc( sizeof (LNode)) 3 B->next= NULL; 4 LNode *p=A-> next; 5 LNode *ra=A; // ra始終指向A的尾結點 6 while (p!= NULL){ 7 ra->next= p; 8 ra= p; 9 p=p-> next; 10 q=p-> next; 11 p->next=B-> next; 12 B->next= p; 13 p= q; 14 } 15 ra->next= NULL; 16 return B; 17 }
? 9.假設有兩個按元素值遞增次序排列的線性表,均以單鏈形式存儲。請編寫算法將這兩個鏈表歸并為一個按元素值遞減的單鏈表,并要求利用原來兩個單鏈表的結點存放歸并后的鏈表。
? 思路:由于兩個鏈表均是遞增的,將其合并時,從第一個結點起進行比較,將小的結點存入鏈表中,同時后移工作指針。由于要求鏈表元素遞減,故采用頭插法。

void MergeList(LinkList &A,LinkList &B){
LNode *pa=A->next, *pb=B->next, *r;
A->next=NULL;
while(pa&&pb){
if(pa->data<pb->data){
r=pa->next;
pa->next=A->next;
A->next=pa;
pa=r;
}
else{
r=pb->next;
pb->next=A->next;
A->next=pb;
pb=r;
}
}
if(pa)
pb=pa;
while(pb){
r=pb->next;
pb->next=A->next;
A->next=pb;
pb=r;
}
}
1 void MergeList(LinkList &A,LinkList & B){ 2 LNode *pa=A->next, *pb=B->next, * r; 3 A->next= NULL; 4 while (pa&& pb){ 5 if (pa->data<pb-> data){ 6 r=pa-> next; 7 pa->next=A-> next; 8 A->next= pa; 9 pa= r; 10 } 11 else { 12 r=pb-> next; 13 pb->next=A-> next; 14 A->next= pb; 15 pb= r; 16 } 17 } 18 if (pa) 19 pb= pa; 20 while (pb){ 21 r=pb-> next; 22 pb->next=A-> next; 23 A->next= pb; 24 pb= r; 25 } 26 }
? 10.設A和B 是兩個單鏈表帶頭結點,其中元素遞增有序。設計一個算法從A和B中公共元素產生鏈表C,要求不破壞A和B的結點。
? ? ? ?思路:尾插法新建鏈表C ,要求不破壞A和B的結點,所以才有比較復制的方法。

void Get_Common(LinkList &A , LinkList &B){
LNode *p=A->next, *q=B->next, *r, *s;
LinkList C =(LinkList)malloc(sizeof(LNode));
r=C;
while(p!=NULL&&q!=NULL){
if(p->data<q->data)
p=p->next;
else if(p->data>q->data)
q=q->next;
else{
s=(LNode *)malloc(sizeof(LNode));
s->data=q->data;
r->next=s;
r=s;
p=p->next;
q=q->next;
}
}
r->next=NULL;
}
1 void Get_Common(LinkList &A , LinkList & B){ 2 LNode *p=A->next, *q=B->next, *r, * s; 3 LinkList C =(LinkList)malloc( sizeof (LNode)); 4 r= C; 5 while (p!=NULL&&q!= NULL){ 6 if (p->data<q-> data) 7 p=p-> next; 8 else if (p->data>q-> data) 9 q=q-> next; 10 else { 11 s=(LNode *)malloc( sizeof (LNode)); 12 s->data=q-> data; 13 r->next= s; 14 r= s; 15 p=p-> next; 16 q=q-> next; 17 } 18 } 19 r->next= NULL; 20 }
11. 已知兩個鏈表A和B分別表示兩個集合,其元素遞增有序。編制函數,求A與B的交集,并存放于A的鏈表中。
? 思路:采用歸并思想,設置兩個工作指針pa和pb,對兩個鏈表進行掃描,當同時出現在兩集合中的元素才鏈接到結果表中,且僅保留一個,其他的結點全部釋放。
當一個鏈表遍歷結束后,釋放另一個表剩下的全部結點。

LinkList Union(LinkList &A , LinkList &B){
pa=A->next;
pb=B->next;
pc=A;
LNode *u;
while(pa&&pb){
if(pa->data==pb->data){
pc->next=pa;
pc=pa;
pa=pa->next;
u=pb;
pb=pb->next;
free(u);
}
else if(pa->data>pb->data){
u=pb;
pb=pb->next;
free(u);
}
else{
u=pa;
pa=pa->next;
free(u)
}
while(pa){
u=pa
pa=pa->next;
free(u)
}
while(pb){
u=pb
pa=pb->next;
free(u)
}
pc->next-NULL;
free(B);
return A;
}
}
1 LinkList Union(LinkList &A , LinkList & B){ 2 pa=A-> next; 3 pb=B-> next; 4 pc= A; 5 LNode * u; 6 while (pa&& pb){ 7 if (pa->data==pb-> data){ 8 pc->next= pa; 9 pc= pa; 10 pa=pa-> next; 11 u= pb; 12 pb=pb-> next; 13 free(u); 14 } 15 else if (pa->data>pb-> data){ 16 u= pb; 17 pb=pb-> next; 18 free(u); 19 } 20 else { 21 u= pa; 22 pa=pa-> next; 23 free(u) 24 } 25 while (pa){ 26 u= pa 27 pa=pa-> next; 28 free(u) 29 } 30 while (pb){ 31 u= pb 32 pa=pb-> next; 33 free(u) 34 } 35 pc->next- NULL; 36 free(B); 37 return A; 38 } 39 }
12.設計一個算法用于判斷帶頭結點的循環雙鏈表是否對稱。
思路:讓P從左向右掃描,q從右向左掃描。直到它們指向同一結點(結點個數為奇數時)或相鄰(結點個數為偶數時)為止,若它們所指結點值相同,則繼續進行下去,否則返回0,若比較全部相同則返回1。
?

int Symmetry(DLinkList L){
DNode *p=L->next, *q=L->prior;
while(p!=q&&p->next!=q)
if(p->data==q->data){
p=p->next;
q=q->prior;
}
else
return 0;
return 1;
}
1 int Symmetry(DLinkList L){ 2 DNode *p=L->next, *q=L-> prior; 3 while (p!=q&&p->next!= q) 4 if (p->data==q-> data){ 5 p=p-> next; 6 q=q-> prior; 7 } 8 else 9 return 0 ; 10 return 1 ; 11 }
13. 設有一個帶頭結點的循環單鏈表,其結點值均為正整數。設計一個算法,反復找出單鏈表中結點值最小的結點并輸出,然后將該結點從中刪除,直到單鏈表空為止,再刪除表頭結點。

void Del_All(LinkList &L){
LNode *p, *pre, *minp, *minpre;
while(L->next!=L){
p=L->next;pre=L;
minp=p,minpre=L;
while(p!=L){
if(p->data<minp->data){minp=p;minpre=pre;}
pre=p;
p=p->next;
}
printf("%d",minp->data);
minpre->next=minp->next;
free(minp);
Del_All(L)
}
free(L);
}
1 void Del_All(LinkList & L){ 2 LNode *p, *pre, *minp, * minpre; 3 while (L->next!= L){ 4 p=L->next;pre= L; 5 minp=p,minpre= L; 6 while (p!= L){ 7 if (p->data<minp->data){minp=p;minpre= pre;} 8 pre= p; 9 p=p-> next; 10 } 11 printf( " %d " ,minp-> data); 12 minpre->next=minp-> next; 13 free(minp); 14 Del_All(L) 15 } 16 free(L); 17 }
14. 已知一個帶有表頭結點的單鏈表,假設該鏈表只給出了頭指針list。在不改變鏈表的前提下,請設計一個盡可能高效的算法,查找鏈表中倒數第K個位置上的結點。若查找成功,算法輸出該結點的data域的值,否則,只返回0。
? ? ?設計思想:定義兩個指針變量p和q,初始時均指向頭結點的下一個結點,即鏈表的第一個結點。p指針沿鏈表移動;當p指針移動到第k個結點時,q指針開始于p指針同步移動;當p指針移動到最后一個結點時,q指針所指示的結點為倒數第k個結點。

typedef int ElemType;
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
int Search(LinkList L, int k){
LNode *p=L->next, *q=L->next;
int count=0;
while(p!=NULL){
if(count<k)count ++;
else q=q->next;
p=p->next;
}
if(count<k)
return 0;
else{
printf("%d",q->data);
return 1;
}
}
1 typedef int ElemType; 2 typedef struct LNode{ 3 ElemType data; 4 struct LNode * next; 5 }LNode, * LinkList; 6 7 int Search(LinkList L, int k){ 8 LNode *p=L->next, *q=L-> next; 9 int count= 0 ; 10 while (p!= NULL){ 11 if (count<k)count ++ ; 12 else q=q-> next; 13 p=p-> next; 14 } 15 if (count< k) 16 return 0 ; 17 else { 18 printf( " %d " ,q-> data); 19 return 1 ; 20 } 21 22 }
15.設頭指針為L的帶有表頭結點的非循環雙向鏈表,其每個結點除了有pred(前驅指針),data和next域外,還有一個訪問頻度域freq。在鏈表被啟用前,其值均初始化為零。每當在鏈表中進行一次Locate(L ,x )運算時,令元素值為x的結點中freq域的值增1,并使此鏈表中結點保持按訪問頻度遞減的序列排列,同時最近訪問的結點排在頻度相同的結點的前面,以便使頻繁訪問的結點總是靠近表頭。使編寫符合上述要求的Locate(L ,x )運算的算法,該運算為函數過程,返回找到結點的地址,類型為指針型。
? ?設計思想: 首先找到鏈表中數據值為x的結點,查到后,將結點從鏈表上摘下,然后順著結點的前驅查到該結點的插入位置。頻度遞減,且排在同頻度的第一個。

DLinkList Locate(DLinkList &L, ElemType x){
DNode *p=L->next, *q;
while(p&&p->data!=x)
p=p->next;
if(!p){
printf("不存在值為x的結點\n");
exit(0)
}
else{
p->freq++;
p->next->pred=p->pred;
p->pred->next=p->next;
q=p->pred;
while(q->freq<p->freq&&q!=L)
q=q->pred;
p->next=q->next;
q->next->pred=p;
q->next=p;
p->pred=q;
}
return p; //返回值為x的結點的指針
}
1 DLinkList Locate(DLinkList & L, ElemType x){ 2 DNode *p=L->next, * q; 3 while (p&&p->data!= x) 4 p=p-> next; 5 if (! p){ 6 printf( " 不存在值為x的結點\n " ); 7 exit( 0 ) 8 } 9 else { 10 p->freq++ ; 11 p->next->pred=p-> pred; 12 p->pred->next=p-> next; 13 q=p-> pred; 14 while (q->freq<p->freq&&q!= L) 15 q=q-> pred; 16 p->next=q-> next; 17 q->next->pred= p; 18 q->next= p; 19 p->pred= q; 20 } 21 return p; // 返回值為x的結點的指針 22 }
?歡迎查看關于順序表的學習,見上篇 http://www.cnblogs.com/tracylining/p/3394038.html
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
