为了方便，本文介绍的单向循环链表不包含头节点
单向循环链表内容
- 单向循环链表的的定义
- 单向循环链表的创建
- 单向循环链表插入
- 单向循环链表的删除
- 单向循环链表的查询
单向循环链表的的定义
在单链表中，将终端结点的指针域NULL改为指向表头结点或开始结点
它的有点是：从任一结点出发都可访问到表中所有结点。
单向循环链表的创建
单向循环链表有两种表现形式，如下图：
表现形式
在创建单向循环链表，分为两种情况：
第一次创建、已创建，新增元素，所以，思路如下
判断是否第一次创建
YES：创建节点，将指针域指向自己
NO：找到链表结尾的位置
创建新的节点
尾节点->next=新节点
新节点->next=头节点
早
//单向循环链表的创建
Status createSCycleList(Linklist *node){
int item;
Linklist temp;
Linklist tail = NULL;//记录最后一个节点
while (1) {
scanf("%d", &item);
if (item == 0)
break;
if (*node == NULL) {
//节点为空时，第一次创建，将节点的next指向自己，同时记录尾节点
*node = malloc(sizeof(lNode));
if (*node == NULL)
return ERROR;
(*node)->data=item;
(*node)->next = *node;
tail = *node;
}else{
//创建节点
temp = malloc(sizeof(lNode));
if (temp == NULL)
return ERROR;
temp->data=item;
//指向头节点
temp->next = *node;
//尾节点指向新建节点
tail->next = temp;
tail = temp;
}
}
return OK;
}
//在其他地方调用
LinkList sCycleList;
createSCycleList(&sCycleList);
上面一直是把节点插在后面，下面这个是把节点插在前面
Status createSCycleList(Linklist *node){
int item;
Linklist temp;
Linklist tail = NULL;//记录最后一个节点
while (1) {
scanf("%d", &item);
if (item == 0)
break;
if (*node == NULL) {
//节点为空时，第一次创建，将节点的next指向自己，同时记录尾节点
*node = malloc(sizeof(lNode));
if (*node == NULL)
return ERROR;
(*node)->data=item;
(*node)->next = *node;
tail = *node;
}else{
//创建节点
temp = malloc(sizeof(lNode));
if (temp == NULL)
return ERROR;
temp->data=item;
//指向头节点
temp->next = *node;
//尾节点指向新建节点
tail->next = temp;
//将头指针指向新首元节点
*node = temp;
}
}
return OK;
}
单向循环链表插入
单向循环链表插入分为两种情况：
如果是在第一个位置：
1.首先创建新节点p，将值赋值给p节点的数据域；
2.将p->next指向首元节点node；
3.遍历找到尾节点tail，将tail->next指向新的首元节点p
4.将头指针指向新的首元节点：*node = p
如果不是在第一个位置：
1.找到要插入位置的前一个节点p；
2.将新建节点的next指向p->next；
3.将p->next指向新建节点
//单循环链表插入
Status insertCycleList(Linklist *node,int place,int num){
//链表为空
if (*node == NULL)
return ERROR;
//插入位置不对
if (place < 1)
return ERROR;
Linklist target,temp;
int i = 0;
if (place == 1) {
//创建temp
temp = malloc(sizeof(lNode));
if (temp == NULL)
return ERROR;
temp->data = num;
//找尾节点
//尾节点下一个节点等于头节点时，找到尾节点
for (target = *node; target->next != *node; target = target->next);
//新节点->next
temp->next = *node;
//尾节点->next = 新节点
target->next = temp;
//让头节点 = temp
*node = temp;
}else{
//创建新节点 temp
temp = malloc(sizeof(lNode));
if (temp == NULL)
return ERROR;
temp->data = num;
//找到插入前的一个位置target
for (i = 1,target = *node; target->next != *node && i != place-1 ; target = target->next,i++);
if (*node == target->next && (i+1) < place) {
//第i-1位置的节点的下一个节点是头节点，且插入位置大于末尾位置，超出插入范围
//比如，只有四个元素，你可以插在第五个的位置，你不能插入到第六个位置
return ERROR;
}
//新节点next指向target->next
temp->next = target->next;
//target后继是新节点
target->next = temp;
}
return OK;
}
单向循环链表的删除
单向循环链表的删除分为两种情况：
如果是在第一个位置：
1.遍历找到尾节点tail；
2.temp记录首元节点；
3.首元节点=首元节点->next
4.尾节点指向首元节点，同时释放temp
如果不是在第一个位置：
1.找到要删除位置的前一个节点p；
2.将p->next赋值要删除的节点q；
3.将p->next指向q->next,并释放q
//单循环链表的删除
Status deleteCycleList(Linklist *node,int place){
if(*node == NULL || place < 1) return ERROR;
lNode *target,*temp;
int i = 0;
//如果只有一个节点
if ((*node)->next == *node) {
if (place > 1) {
return ERROR;
} else {
temp = *node;//记录该节点
*node = NULL;//将头节点指向NULL
free(temp);//释放该节点
return OK;
}
}
if (place == 1) {
//找尾节点
//尾节点下一个节点等于头节点时，找到尾节点
for (target = *node; target->next != *node; target = target->next);
temp = *node;
*node = (*node)->next;
target->next = *node;
free(temp);
} else {
//找到删除前的一个位置target
for (i = 1,target = *node; target->next != *node && i != place-1 ; target = target->next,i++);
if (*node == target->next) {//第i-1位置的节点的下一个节点是头节点，超出删除范围
return ERROR;
}
temp = target->next;
target->next = temp->next;
free(temp);
}
return OK;
}
单向循环链表的查询
//单循环链表的查询
int findNodeFromCycleList(Linklist node, int value){
if (node == NULL) {
return -1;
}
int i = 1;
Linklist temp = node;
while (temp && temp->data != value && temp->next != node) {
i++;
temp = temp->next;
}
//防止没有找到，返回了1
if (temp->next == node && temp->data != value) {
return -1;
}
return i;
}
