单向循环链表
与单向链表的区别： 单向链表的最后结点的指针域next设置为NULL，单向循环链表的最后结点的指针域的next指向的是重新指向首元结点位置。
单向循环链表设计
- 单向循环链表定义和单向链表的结构设计是一致的
//定义结点
typedef struct Node{
ElemType data;
struct Node *next;
}Node;
typedef struct Node * LinkList;
单向循环链表创建
在创建链表时，需要考虑两种情况：
- 首次创建链表
- 已经创建成功链表，需要在末尾继续增加数据
/*
循环链表创建!
2种情况:① 第一次开始创建; ②已经创建,往里面新增数据
1. 判断是否第一次创建链表
YES->创建一个新结点,并使得新结点的next 指向自身; (*L)->next = (*L);
NO-> 找链表尾结点,将尾结点的next = 新结点. 新结点的next = (*L);
*/
Status CreateList(LinkList *L){
int item;
LinkList temp = NULL;
LinkList target = NULL;
printf("输入节点的值，输入0结束\n");
while(1) {
// 输入链表的值
scanf("%d",&item);
// 如果输入的0，输入结束
if(item==0) break;
// 如果输入的链表是空
if(*L==NULL) {
// 则创建一个新的结点
*L = (LinkList)malloc(sizeof(Node));
// 判断是否创建结点成功
if(!L)exit(0);
// 将输入的值给L
(*L)->data=item;
// 使其next指针指向自己
(*L)->next=*L;
} else {
//输入的链表不是空的，寻找链表的尾节点
for (target = *L; target->next != *L;
target = target->next);
// 创建一个新的结点
temp=(LinkList)malloc(sizeof(Node));
// 结点是否成功创建
if(!temp) return ERROR;
// 赋值
temp->data=item;
// 新节点的next指向头节点
temp->next=*L;
// 使尾节点的next=新节点
target->next=temp;
}
}
return OK;
}
在上次代码中，我们使用for循环来实现获取最后一个结点，但这种方式会增加时间复杂度。所以我们可以使用一个临时指针来记录最后一个结点，用来确保每次新增数据后，都能添加到最后并且及时修改链表信息。
Status CreateList2(LinkList *L){
int item;
LinkList temp = NULL;
LinkList target = NULL;
// 临时结点，用于记录最后一个结点
LinkList r = NULL;
printf("请输入新的结点, 当输入0时结束!\n");
while (1) {
scanf("%d",&item);
if (item == 0) {
break;
}
//第一次创建
if(*L == NULL){
*L = (LinkList)malloc(sizeof(Node));
if(!*L) return ERROR;
(*L)->data = item;
(*L)->next = *L;
// 第一次创建，最后的结点就是当前的结点L
r = *L;
} else {
// 创建新的结点
temp = (LinkList)malloc(sizeof(Node));
if(!temp) return ERROR;
temp->data = item;
temp->next = *L;
// 在末尾r插入temp
r->next = temp;
// 最新的结点是最后的结点r
r = temp;
}
}
return OK;
}
单向循环链表插入
插入一个新的结点到循环链表中，需要分析2种情况。
- 插入在首元结点的位置上
- 插入在其他位置上（包括链表中间/末尾）
- 插入在首元结点位置
Status ListInsert(LinkList *L, int place, int num) {
LinkList temp ,target;
int i;
if (place == 1) {
// 1.创建新结点temp，判断是否创建成功，成功赋值
temp = (LinkList)malloc(sizeof(Node));
if (temp == NULL) {
return ERROR;
}
temp->data = num;
// 2.找到链表的最后一个结点——尾结点
for (target = *L; target->next != *L; target = target->next);
// 3.将新结点temp的next指向头结点*L
temp->next = *L;
// 4.将尾结点的next指向新结点temp
target->next = temp;
// 5.最后将头结点L指向新结点temp
*L = temp;
}
- 插在其他位置
Status ListInsert2(LinkList *L, int place, int num){
LinkList temp ,target;
int i;
if (place != 1) {
//如果插入的位置在其他位置;
//1. 创建新结点temp,并判断是否创建成功,成功则赋值,否则返回ERROR;
temp = (LinkList)malloc(sizeof(Node));
if (temp == NULL) {
return ERROR;
}
temp->data = num;
//2. 先找到插入的位置,如果超过链表长度,则自动插入队尾;
for ( i = 1,target = *L;
target->next != *L && i != place - 1;
target = target->next,i++) ;
//3. 通过target找到要插入位置的前一个结点, 让target->next = temp;
temp->next = target->next;
//4. 插入结点的前驱指向新结点,新结点的next指向target原来的next位置 ;
target->next = temp;
}
return OK;
}
单向循环链表删除
单向循环链表删除需要考虑到三种情况
- 删除的位置在首元结点上
- 删除时，链表只有最后一个结点
- 删除其他结点
- 删除的位置在首元结点上
需要先判断当前循环链表是否只有一个结点，如果只有一个结点，直接将L置空即可；否则需要找到链表的末尾结点temp，将temp的next重新指向首元结点L的next，新结点做为头结点,则释放原来的头结点，释放首元结点L
Status LinkListDelete(LinkList *L,int place){
LinkList temp,target;
int i;
//temp 指向链表首元结点
temp = *L;
if(temp == NULL) return ERROR;
if (place == 1) {
//①.如果删除到只剩下首元结点了,则直接将*L置空;
if((*L)->next == (*L)){
(*L) = NULL;
return OK;
}
//②.链表还有很多数据,但是删除的是首结点;
// 找到尾结点target
for (target = *L; target->next != *L; target = target->next);
// 记录原头结点
temp = *L;
// 新结点做为头结点
*L = (*L)->next;
// 使得尾结点next 指向头结点的下一个结点
target->next = *L;
// 释放原来的头结点
free(temp);
}
return OK;
}
- 删除其他位置上的结点
Status LinkListDelete(LinkList *L,int place){
LinkList temp,target;
int i;
//temp 指向链表首元结点
temp = *L;
if(temp == NULL) return ERROR;
if (place != 1) {
//如果删除其他结点--其他结点
//1. 找到删除结点前一个结点target
for(i = 1,target = *L;
target->next != *L && i != place -1;
target = target->next,i++) ;
// 2. 使得target->next 指向下一个结点
temp = target->next;
target->next = temp->next;
// 3. 释放需要删除的结点temp
free(temp);
}
return OK;
}
总结
对链表进行操作时，需要考虑到一些特殊场景来保证代码的健壮性。比如首元结点位置，末尾结点的位置及是否是空链表，删除时链表中是否只有一个结点等。
