用C語言實(shí)現(xiàn)單鏈表的各種操作(二)

更新時(shí)間：2013年05月24日 17:39:16 作者：

本篇文章是對(duì)用C語言實(shí)現(xiàn)單鏈表的各種操作進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下

上一篇文章<用C語言實(shí)現(xiàn)單鏈表的各種操作(一)>主要是單鏈表的一些最基本的操作，下面，主要是一些其他的典型的算法和測(cè)試程序。

/* 對(duì)單鏈表進(jìn)行排序處理*/
struct LNode *sort(struct LNode *head)
{
  LinkList *p;
  int n,i,j;
  int temp;
  n = ListLength(head);
  if(head == NULL || head->next == NULL)
    return head;
  p = head->next;
  for(j =1;j<n;++j)
  {
    p = head->next;
    for( i =0;i<n-j;++i)
    {
      if(p->data > p->next->data)
      {
        temp = p->data;
        p->data = p->next->data;
        p->next->data = temp;
      }
      p = p->next;
    }
  }
  return head;
}
/*對(duì)單鏈表進(jìn)行逆置*/
LinkList *reverse(LinkList *head)
{
  LinkList *p1,*p2 = NULL,*p3 = NULL;
  if(head == NULL || head->next == NULL)
    return head;
  p1 = head->next;
  while(p1!=NULL)
  {
    p3 = p1->next;
    p1->next = p2;
    p2 = p1;
    p1 = p3;
 }
 head->next = p2;
  // head = p2;
  return head; 
}
Status equal(ElemType c1,ElemType c2)
{
  if(c1== c2)
    return TRUE;
  else
    return FALSE;
}
/*將所有在線性表Lb中但不在La中的數(shù)據(jù)元素插入到La 中*/
void Union(LinkList *La,LinkList *Lb)
{
  ElemType *e;
  int La_len,Lb_len;
  int i;
  La_len = ListLength(La);
  Lb_len = ListLength(Lb);
  for(i=1;i<=Lb_len;i++)
  {
    GetElem(Lb,i,e); //取Lb中第i個(gè)元素賦給e
    if(!LocateElem(La,*e,equal))//La中不存在和e相同的元素，則插入
      ListInsert(La,++La_len,*e);
  }
}
void print(ElemType c)
{
  printf("%4d",c);
}
/* 合并兩個(gè)單鏈表，La和Lb中的數(shù)據(jù)是按非遞減排列，歸并后的Lc還是安非遞減排列*/
void MergeList(LinkList *La,LinkList *Lb,LinkList **Lc)
{
  int i =1,j=1,k=0;
  int La_len,Lb_len;
  ElemType *ai,*bj;
  ai = (ElemType *)malloc(sizeof(ElemType));
  bj = (ElemType *)malloc(sizeof(ElemType));

  InitList(Lc);
  La_len = ListLength(La);
  Lb_len = ListLength(Lb);
  while(i<=La_len && j<=Lb_len)
  {
    GetElem(La,i,ai);
    GetElem(Lb,j,bj);
    if(*ai<*bj)
    {
      ListInsert(*Lc,++k,*ai);
      ++i;
    }
    else
    {
      ListInsert(*Lc,++k,*bj);
      ++j;
    }
  }
  while(i<=La_len)
  {
    GetElem(La,i++,ai);
    ListInsert(*Lc,++k,*ai);
  }
  while(j<=Lb_len)
  {
    GetElem(Lb,j++,bj);
    ListInsert(*Lc,++k,*bj);
  }
}
/*只遍歷一次，找到單鏈表中的中間節(jié)點(diǎn)
 1 定義兩個(gè)指針，一個(gè)指針每次移動(dòng)兩個(gè)步長（快指針），另一個(gè)指針每次移動(dòng)一個(gè)數(shù)據(jù)（慢指針）
 2. 當(dāng)快指針到達(dá)鏈表尾部的時(shí)候，慢指針就到了鏈表的中間節(jié)點(diǎn)
在程序中也可以判斷一個(gè)單鏈表是否有環(huán)，如果快指針一定能夠追趕上慢指針，否則就會(huì)以NULL結(jié)束*/
LinkList *Searchmid(LinkList * head)
{
  if(NULL == head)
    return NULL;
  if(head->next == NULL)
    return head;
  if(head->next->next == NULL)
    return head;

  LinkList *mid= head;
  LinkList *p = mid->next;

  while((p != NULL) && (NULL !=p->next))
  {
    mid = mid->next;
    p = p->next->next;
  }
  return mid;
}

下面主要是單鏈表的一個(gè)測(cè)試的程序。

復(fù)制代碼代碼如下:

Status comp(ElemType c1,ElemType c2)
{
  if(c1==c2)
    return TRUE;
  else
    return FALSE;
}
void visit(ElemType c)
{
  printf("%4d",c);
}
void main()
{
  LinkList *L;
  LinkList *mid;
  mid = (struct LNode *)malloc(sizeof(struct LNode));

  ElemType *e,e0,*e1;
  Status i;
  int j,k;
  e = (ElemType *)malloc(sizeof(ElemType));
  e1 = (ElemType *)malloc(sizeof(ElemType));

  i = InitList(&L);
  for(j=1;j<=6;j++)
  {
    i = ListInsert(L,1,j);
  }
  printf("在L的表頭依次插入1～6后：L=");
    ListTraverse(L,visit);
    printf("L中間節(jié)點(diǎn)的值為mid=：");
    mid = Searchmid(L);
     printf("%d\n",mid->data);

      printf("L逆置后的輸出：L=");
      ListTraverse(reverse(L),visit);
    printf("L排序后依次為：L=");
    ListTraverse(sort(L),visit);

    
  i = ListEmpty(L);
  printf("L 是否為空：i=%d(1:是，0:否)\n",i);
  i = ClearList(L);
  printf("清空L后：L=");
  ListTraverse(L,visit);
  i = ListEmpty(L);
  printf("L是否為空：i=%d\n",i);
  for(j=1;j<=10;j++)
  {
    ListInsert(L,j,j);
  }
  printf("在L的表尾依次插入1~10后：L=");
  ListTraverse(L,visit);
  GetElem(L,5,e);
  printf("第5個(gè)元素的值為：%d\n",*e);
  for(j=0;j<=1;j++)
  {
    k = LocateElem(L,j,comp);
    if(k)
      printf("第%d個(gè)元素的值為%d\n",k,j);
    else
      printf("沒有值為%d的元素\n",j);
  }
  for(j=1;j<=2;j++)
  {
    GetElem(L,j,e1);
    i = PriorElem(L,*e1,e);
    if(i== INFEASIBLE)
      printf("元素%d無前驅(qū)\n",*e1);
    else
      printf("元素%d的前驅(qū)為：%d\n",*e1,*e);
  }
  for(j=ListLength(L) -1;j<=ListLength(L);j++)
  {
    GetElem(L,j,e1);
    i = NextElem(L,*e1,e);
    if(i==INFEASIBLE)
      printf("元素%d無后繼\n",*e1);
    else
      printf("元素%d的后繼為：%d\n",*e1,*e);
  }
   k = ListLength(L);
  for(j=k+1;j>=k;j--)
  {
    i = ListDelete(L,j,e);
    if(i==ERROR)
      printf("刪除第%d個(gè)數(shù)據(jù)失敗\n",j);
    else
      printf("刪除的元素為：%d\n",*e);
  }
  printf("依次輸出L的元素：");
    ListTraverse(L,visit);
  DestroyList(L);
  printf("銷毀L后：L=%u\n",L);
  printf("*************************************************\n");
  LinkList *La,*Lb;
  i = InitList(&La);
  if(i==1)
    for(j=1;j<=5;j++)
      i= ListInsert(La,j,j);
  printf("La=");
  ListTraverse(La,print);
  InitList(&Lb);
  for(j=1;j<=5;j++)
    i = ListInsert(Lb,j,2*j);
  printf("Lb = ");
  ListTraverse(Lb,print);
  Union(La,Lb);
  printf("new La=");
  ListTraverse(La,print);
  printf("*************************************************\n");
  LinkList *La_1,*Lb_1,*Lc_1;
  int a[4]={3,5,8,11},b[7]= {2,6,8,9,11,15,20};
  InitList(&La_1);
  for(j=1;j<=4;j++)
    ListInsert(La_1,j,a[j-1]);
  printf("La_1=");
  ListTraverse(La_1,print);
  InitList(&Lb_1);
  for(j=1;j<=7;j++)
    ListInsert(Lb_1,j,b[j-1]);
  printf("Lb_1=");
  ListTraverse(Lb_1,print);
  MergeList(La_1,Lb_1,&Lc_1);
  printf("Lc_1=");
  ListTraverse(Lc_1,print);
}

下面是在Linux下的部分運(yùn)行結(jié)果：

復(fù)制代碼代碼如下:

在L的表頭依次插入1～6后：L= 6 5 4 3 2 1
L中間節(jié)點(diǎn)的值為mid=：4
L逆置后的輸出：L= 1 2 3 4 5 6
L排序后依次為：L= 1 2 3 4 5 6
L 是否為空：i=0(1:是，0:否)
清空L后：L=
L是否為空：i=1
在L的表尾依次插入1~10后：L= 1 2 3 4 5 6 7 8 9 10
第5個(gè)元素的值為：5
沒有值為0的元素
第1個(gè)元素的值為1
元素1無前驅(qū)
元素2的前驅(qū)為：1
元素9的后繼為：10
元素10無后繼
刪除第11個(gè)數(shù)據(jù)失敗
刪除的元素為：10
依次輸出L的元素： 1 2 3 4 5 6 7 8 9
銷毀L后：L=7954544
*************************************************
La= 1 2 3 4 5
Lb = 2 4 6 8 10
new La= 1 2 3 4 5 6 8 10
*************************************************
La_1= 3 5 8 11
Lb_1= 2 6 8 9 11 15 20
Lc_1= 2 3 5 6 8 8 9 11 11 15 20