《数据结构（C语言版）》循环链表的实现
清华大学计算机系列教材 累计发行超400万册
严蔚敏 吴伟明 编著
数据结构（C语言版）
以下是本人对该紫皮书第二章线性表中循环链表的代码实现， 由于课本惜墨如金，连一行代码都没有给，就只用文字提到了循环链表的合并操作，因此本人仅对该操作进行了代码实现，时间复杂度为O(1)，循环链表的完整数据结构与动态单链表类似
（貌似专栏把我缩进吃了，懒得加了，另外建议用visual studio编译）
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int ElemType;
typedef int Status;
typedef struct LNode
{
ElemType data;
struct LNode* next;
}LNode, * CircularList;
/*
单链表的循环条件与循环链表的循环条件的异同：
单链表 -> 循环链表
p!=NULL -> p!=L
p->next!=NULL -> p->next!=L
循环链表常常加入尾指针R
a1的存储位置为R->next->next
an的存储位置为R
*/
/*由于书上仅设立尾指针而不设立头指针，故用返回尾指针的方式建立链表*/
CircularList CreatList_CL_R(int n);//尾插法建立循环链表
void ShowList_CL(CircularList rear);//打印循环链表
CircularList MergeList_CL(CircularList rear1, CircularList rear2);//循环链表的合并
int main()
{
int n = 0;
printf("请输入你想要创建的循环链表A的元素个数:");
scanf("%d", &n);
CircularList rear1 = CreatList_CL_R(n);
printf("请输入你想要创建的循环链表B的元素个数:");
scanf("%d", &n);
CircularList rear2 = CreatList_CL_R(n);
printf("循环链表A:");
ShowList_CL(rear1);
printf("循环链表B:");
ShowList_CL(rear2);
CircularList rear = MergeList_CL(rear1, rear2);//将循环链表B接在循环链表A的后面
printf("合并后的循环链表：");
ShowList_CL(rear);
return 0;
}
CircularList CreatList_CL_R(int n)//尾插法建立循环链表
{
CircularList head = (CircularList)malloc(sizeof(LNode));
if (!head)
{
exit(OVERFLOW);
}
head->data = 0;
head->next = head;
CircularList rear = head;
int num = 0;
printf("请输入该循环链表中的元素：");
for (int i = 0; i < n; i++)
{
scanf("%d", &num);
LNode* pNew = (CircularList)malloc(sizeof(LNode));
if (!pNew)
{
exit(OVERFLOW);
}
pNew->data = num;
pNew->next = head;
rear->next = pNew;
rear = pNew;
}
return rear;
}
void ShowList_CL(CircularList rear)//打印循环链表
{
CircularList head = rear->next;
CircularList p = rear->next->next;
while (p != head)
{
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
CircularList MergeList_CL(CircularList rear1, CircularList rear2)//循环链表的合并
{
CircularList head1 = rear1->next;//head1存循环链表A的表头节点
rear1->next = rear2->next->next;//循环链表B的表头连接A的表尾
free(rear2->next);//释放循环链表B的表头节点
rear2->next = head1;//修改循环链表B的尾指针
return rear2;
}
