文字描述
循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。由此，从表中任一结点出发均可找到表中其他结点。
示意图
算法分析
插入、删除、查找等同单链表。
代码实现
//
// Created by lady on 19-1-27.
// #include <stdio.h>
#include <stdlib.h> //线性表的单向循环链表存储结构
typedef struct ElemType{
char data[];
}ElemType;
typedef struct CNode{
ElemType e;
struct CNode *next;
}CNode;
typedef struct {
CNode *head;//指向第一个指针
CNode *tail;//指向最后一个指针
int length;//表示链表数据元素个数
}CLinkNode, *CLinkList; //构造一个空的线性表
static int InitList_CL(CLinkList *L)
{
(*L) = (CLinkList)malloc(sizeof(CLinkNode));
(*L)->length = ;
(*L)->head = NULL;
(*L)->tail = NULL;
} //销毁线性表
static int Destory_CL(CLinkList *L)
{
if(L == NULL || (*L) == NULL){
return -;
}
CNode *p = (*L)->head;
CNode *q;
while(p){
q = p;
p = p->next;
free(q);
if(p == (*L)->head)
break;
}
free(*L);
(*L) = NULL;
} //返回1表示空， 0表示非空
static int ListEmpty_CL(CLinkList L)
{
return L->length ? : ;
} //返回线性表L中的数据元素个数
static int ListLength_CL(CLinkList L)
{
return L->length;
} //在线性表末尾插入数据元素e
static int ListInsert_CL(CLinkList *L,ElemType e)
{
CNode *new = (CNode *)malloc(sizeof(CNode));
if(new == NULL){
return -;
}
CNode *p;
new ->e = e;
new->next = NULL;
if(ListEmpty_CL(*L)){
(*L)->length += ;
new->next = new;
(*L)->head = new;
(*L)->tail = new;
}else{
(*L)->length +=;
new->next = (*L)->head;
(*L)->tail->next = new;
(*L)->tail = new;
}
return ;
} //删除L中的第loc个数据元素，并将被删元素的值存放在e中
static int ListDelete_CL(CLinkList *L, int loc, ElemType *e)
{
CNode *p = (*L)->head;
CNode *q = NULL;
int i = ;
int f = ;
while(p){
if(i == loc){
f = ;
break;
}
i += ;
q = p;
p = p->next;
if(p == (*L)->head){
f = -;
break;
}
}
if(f<)
return -;
(*L)->length -= ;
(*e) = p->e;
if((*L)->length == ){
free(p);
(*L)->head = NULL;
(*L)->tail = NULL;
}
if(q == NULL){
q = p->next;
free(p);
(*L)->tail->next = q;
}else{
q->next = p->next;
free(p);
}
return ;
} //依次对L的每个数据元素调用函数fun
static int ListTraverse_CL(CLinkList L, int (*fun)(ElemType,int), char note[])
{
printf("遍历循环链表%s:", note);
CNode *p = L->head;
int i = ;
while(p){
if(fun(p->e, ++i)){
return -;
}
p = p->next;
if(p == L->head)
break;
}
printf("\n");
return ;
} static int print(ElemType e, int loc)
{
printf("%3d=%-10s", loc, e.data);
return ;
} //创建一个长度为n的链表
static int CreateList_CL(CLinkList *L, int n, char note[])
{
printf("创建一个长度为%d的循环链表%s!\n", n, note);
InitList_CL(L);
ElemType e;
int i = ;
for(i=; i<n; i++){
printf("输入第%d个元素:", i+);
scanf("%s[^\\n]", e.data);
ListInsert_CL(L, e);
}
} int main(int argc, char *argv[])
{
CLinkList L;
ElemType e;
int location = ; CreateList_CL(&L, , "L:");
ListTraverse_CL(L, print, "L"); printf("输入删除元素的位置:");
scanf("%d", &location);
ListDelete_CL(&L, location, &e);
printf("位于%d的元素%s已经从循环链表中被删除！\n", location, e.data);
ListTraverse_CL(L, print, "L"); Destory_CL(&L);
return ;
}
循环链表
代码运行
/home/lady/CLionProjects/untitled/cmake-build-debug/untitled
创建一个长度为5的循环链表L:!
输入第1个元素:WU
输入第2个元素:ZHENG
输入第3个元素:WANG
输入第4个元素:SUN
输入第5个元素:LI
遍历循环链表L: 1=WU 2=ZHENG 3=WANG 4=SUN 5=LI
输入删除元素的位置:2
位于2的元素ZHENG已经从循环链表中被删除！
遍历循环链表L: 1=WU 2=WANG 3=SUN 4=LI Process finished with exit code 0