原创 连接2个链表构成循环链表

/*//////////////////////////////////////////////////////////////////////////////
文件名:循环链表

功能实现:
有2个循环单链表，头指针分别是head1和head2，实现算法将链表
head2连接在head1之后，连接后的链表仍然是循环链表的形式

时间:2011年10月5日
修改时间:2011年10月6日
//////////////////////////////////////////////////////////////////////////////*/

////////////////////////////////////////////////////////////////////////////////

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>

////////////////////////////////////////////////////////////////////////////////

#define ListSize 100

typedef int DataType;

////////////////////////////////////le="FONT-SIZE: 14pt">typedef struct Node
{
 DataType data;
 struct Node *next;
}ListNode, *LinkList;

/*//////////////////////////////////////////////////////////////////////////////
函数名:       Link(LinkList head1, LinkList head2)
函数功能: 将2个链表head1和head2连接在一起形成一个循环链表
入口参数: (LinkList head1, LinkList head2)
出口参数: head1
//////////////////////////////////////////////////////////////////////////////*/
LinkList Link(LinkList head1, LinkList head2)
{
 ListNode *p,*q;
 p=head1;
 
 while(p->next != head1)/*指针p指向链表的最后一个结点*/
  p=p->next;

 q=head2;
 while(q->next != head2)
  q=q->next;

 p->next = head2;
 q->next = head1;
 return head1;
}

/*//////////////////////////////////////////////////////////////////////////////
函数名:  CreateCycList(int n)
函数功能: 创建一个不带头结点的循环单链表
入口参数:
出口参数:
//////////////////////////////////////////////////////////////////////////////*/
LinkList CreateCycList(int n)
{
 DataType e;
 LinkList head=NULL;
 ListNode *p,*q;
 int i;
 i=1;
 q=NULL;
 while(i <= n)
  {
   printf("请输入第%d个元素.",i);
   scanf("%d",&e);
   if(i == 1)
    {
     head=(LinkList)malloc(sizeof(ListNode));
     head->data=e;
     head->next=NULL;
     q=head;/*指针q指向链表的最后一个结点*/
    }
   else
    {
     p=(ListNode *)malloc(sizeof(ListNode));
     p->data=e;
     p->next=NULL;
     q->next=p;/*将新结点连接到链表中*/
     q=p;/*q始终指向最后一个结点*/
    }
   i++;
  }
 if(q != NULL)
  q->next = head; /*将最后一个结点的指针指向头指针
 使其形成一个循环链表*/
}

/*//////////////////////////////////////////////////////////////////////////////
函数名:  DisplayCycList(LinkList head)
函数功能: 输出循环链表的每一个元素
入口参数: (LinkList head)
出口参数:
//////////////////////////////////////////////////////////////////////////////*/
void DisplayCycList(LinkList head)
{
 ListNode *p;
 p=head;
 if(p == NULL)
  {
   printf("该链表是空表");
   return;
  }
 while(p->next != head )
  {
   printf("%4d",p->data);
   p=p->next;
  }
 printf( "%4d\n" , p->data );/*输出最后一个结点*/
}

/*//////////////////////////////////////////////////////////////////////////////
函数名:  main()
函数功能: 主函数
入口参数:
出口参数:
//////////////////////////////////////////////////////////////////////////////*/
void main()
{
 LinkList h1,h2;
 int n;
 printf("创建一个循环单链表h1:\n");
 printf("请输入元素个数:\n");
 scanf("%d",&n);
 h1=CreateCycList(n);
 printf("创建一个循环单链表h2:\n");
    printf("请输入元素个数:\n");
 scanf("%d",&n);
 h2=CreateCycList(n);
 printf("输出循环单链表h1\n");
 DisplayCycList(h1);
 printf("输出循环单链表h2\n");
 DisplayCycList(h2);
 h1=Link(h1,h2);
 printf("输出连接后的循环单链表h1+h2\n");
 DisplayCycList(h1);
}
////////////////////////////////////////////////////////////////////////////////