《數(shù)據(jù)結(jié)構(gòu)（C語言版）》循環(huán)鏈表的實現(xiàn)
清華大學計算機系列教材? ?累計發(fā)行超400萬冊
嚴蔚敏 吳偉明 編著
數(shù)據(jù)結(jié)構(gòu)（C語言版）
以下是本人對該紫皮書第二章線性表中循環(huán)鏈表的代碼實現(xiàn)， 由于課本惜墨如金，連一行代碼都沒有給，就只用文字提到了循環(huán)鏈表的合并操作，因此本人僅對該操作進行了代碼實現(xiàn)，時間復雜度為O(1)，循環(huán)鏈表的完整數(shù)據(jù)結(jié)構(gòu)與動態(tài)單鏈表類似
（貌似專欄把我縮進吃了，懶得加了，另外建議用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;
/*
單鏈表的循環(huán)條件與循環(huán)鏈表的循環(huán)條件的異同：
?單鏈表 ? ->? ?循環(huán)鏈表
p!=NULL -> ? ?p!=L
p->next!=NULL? ? ->? ? ?p->next!=L
循環(huán)鏈表常常加入尾指針R
a1的存儲位置為R->next->next
an的存儲位置為R
*/
/*由于書上僅設(shè)立尾指針而不設(shè)立頭指針，故用返回尾指針的方式建立鏈表*/
CircularList CreatList_CL_R(int n);//尾插法建立循環(huán)鏈表
void ShowList_CL(CircularList rear);//打印循環(huán)鏈表
CircularList MergeList_CL(CircularList rear1, CircularList rear2);//循環(huán)鏈表的合并
int main()
{
int n = 0;
printf("請輸入你想要創(chuàng)建的循環(huán)鏈表A的元素個數(shù):");
scanf("%d", &n);
CircularList rear1 = CreatList_CL_R(n);
printf("請輸入你想要創(chuàng)建的循環(huán)鏈表B的元素個數(shù):");
scanf("%d", &n);
CircularList rear2 = CreatList_CL_R(n);
printf("循環(huán)鏈表A:");
ShowList_CL(rear1);
printf("循環(huán)鏈表B:");
ShowList_CL(rear2);
CircularList rear = MergeList_CL(rear1, rear2);//將循環(huán)鏈表B接在循環(huán)鏈表A的后面
printf("合并后的循環(huán)鏈表：");
ShowList_CL(rear);
return 0;
}
CircularList CreatList_CL_R(int n)//尾插法建立循環(huán)鏈表
{
CircularList head = (CircularList)malloc(sizeof(LNode));
if (!head)
{
exit(OVERFLOW);
}
head->data = 0;
head->next = head;
CircularList rear = head;
int num = 0;
printf("請輸入該循環(huán)鏈表中的元素：");
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)//打印循環(huán)鏈表
{
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)//循環(huán)鏈表的合并
{
CircularList head1 = rear1->next;//head1存循環(huán)鏈表A的表頭節(jié)點
rear1->next = rear2->next->next;//循環(huán)鏈表B的表頭連接A的表尾
free(rear2->next);//釋放循環(huán)鏈表B的表頭節(jié)點
rear2->next = head1;//修改循環(huán)鏈表B的尾指針
return rear2;
}
