运维开发网

用C语言实现单链表的各种操作(二)

运维开发网 https://www.qedev.com 2020-02-12 17:07 出处:网络 作者: 网络整理
本篇文章是对用C语言实现单链表的各种操作进行了详细的分析介绍,需要的朋友参考下
上一篇文章<用C语言实现单链表的各种操作(一)>主要是单链表的一些最基本的操作,下面,主要是一些其他的典型的算法和测试程序。

复制代码 代码如下:

/* 对单链表进行排序处理*/

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;

}

/*对单链表进行逆置*/

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中的数据元素插入到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个元素赋给e

    if(!LocateElem(La,*e,equal))//La中不存在和e相同的元素,则插入

      ListInsert(La,++La_len,*e);

  }

}

void print(ElemType c)

{

  printf("%4d",c);

}

/* 合并两个单链表,La和Lb中的数据是按非递减排列,归并后的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);

  }

}

/*只遍历一次,找到单链表中的中间节点

 1 定义两个指针,一个指针每次移动两个步长(快指针),另一个指针每次移动一个数据(慢指针)

 2. 当快指针到达链表尾部的时候,慢指针就到了链表的中间节点

在程序中也可以判断一个单链表是否有环,如果快指针一定能够追赶上慢指针,否则就会以NULL结束*/

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;

}

下面主要是单链表的一个测试的程序。

复制代码 代码如下:

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中间节点的值为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个元素的值为:%d\n",*e);

  for(j=0;j<=1;j++)

  {

    k = LocateElem(L,j,comp);

    if(k)

      printf("第%d个元素的值为%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无前驱\n",*e1);

    else

      printf("元素%d的前驱为:%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个数据失败\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下的部分运行结果:

复制代码 代码如下:

在L的表头依次插入1~6后:L= 6 5 4 3 2 1

L中间节点的值为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个元素的值为:5

没有值为0的元素

第1个元素的值为1

元素1无前驱

元素2的前驱为:1

元素9的后继为:10

元素10无后继

删除第11个数据失败

删除的元素为: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

扫码领视频副本.gif

0

精彩评论

暂无评论...
验证码 换一张
取 消

关注公众号