亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

線性表

系統 2232 0

線性表學習筆記之鏈表

?

原創博文,轉載請注明 出處

鏈表分類:單鏈表,插入刪除和查找的時間復雜度均為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元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 久久青草免费免费91线频观看 | 国产欧美视频综合二区 | 神马手机不卡影院 | 香蕉视频免费在线看 | 苦瓜se影院在线视频网站 | 一区二区三区视频网站 | 久久久国产高清 | 国产一区二区三区在线免费 | 一级播放 | 欧美亚洲激情 | 五月色婷婷琪琪综合伊人 | 亚洲日本欧美日韩高观看 | 九九re6精品视频在线观看 | 日日综合 | 国产成人亚洲毛片 | 午夜精品久久久久久久99热 | 日本大胆一区免费视频 | 亚洲精品福利一区二区三区 | 精品国产成人高清在线 | 中文字幕三级理论影院 | 久久黄色精品视频 | 国产精品久久久久久永久牛牛 | 香蕉人人超人人超免费看视频 | 国产精品久久久久毛片真精品 | 99久久精品免费精品国产 | 国产这里只有精品 | 看一级特黄a大片日本片 | 欧美成人在线免费观看 | 久久精品中文 | 九九亚洲精品自拍 | 热久久亚洲 | 伊人久热这里只有精品视频99 | 噜噜狠狠 | 五月婷婷亚洲综合 | 毛片毛片毛片毛片 | 搜毛片| swag系列国产精品 | 国产精品第一页爽爽影院 | 精品伊人久久久久7777人 | 国产激情在线 | 天天躁狠狠躁 |