循环链表与单向链表十分相似,两者唯一不同之处就是,循环链表的尾节点的next属性指向了链表的首节点(非头节点,头节点是没有数据的,头节点的下一个有数据的节点我们称为首节点)。他的表现形式有常见的两种,如下图:
一种是上面我们说的,而另外一种,则是将尾节点的next指向了头节点,这种做法不是方便,所以用的比较少,并不是不可用。
在循环链表中,我们增加了一个新的功能“游标”,在循环链表中可以定义一个“当前”指针,这个指针通常称为游标,可以通过这个游标来遍历链表中的所有元素,而我们不需要去动头节点的指针指向。以下为循环链表的增删改查操作,同样,我们使用了数据类型与算法分离的思路编写了代码(以下代码出自 传智播客 教师课件)
#ifndef _CIRCLE_LIST_H #define _CIRCLE_LIST_H //自定义循环链表数据类型 typedef void CircleList; //自定义循环链表节点数据类型 typedef struct tag_CirclListNode { struct tag_CirclListNode *next; }CircleListNode; //创建循环链表 CircleList* CircleList_Create(); //销毁循环链表 void CircleList_Destroy(CircleList* list); //清空循环链表 void CircleList_Clear(CircleList* list); //获取循环链表长度 int CircleList_Length(CircleList* list); //在循环链表中插入新节点 int CircleList_Insert(CircleList* list, CircleListNode* node, int pos); //获取循环链表中的指定位置的节点 CircleListNode* CircleList_Get(CircleList* list, int pos); //删除循环链表中的指定位置的节点 CircleListNode* CircleList_Delete(CircleList* list, int pos); //------------------ new add ------------------ //直接指定删除链表中的某个数据元素 CircleListNode* CircleList_DeleteNode(CircleList* list, CircleListNode* node); //将游标重置指向链表中的第一个数据元素 CircleListNode* CircleList_Reset(CircleList* list); //获取当前游标指向的数据元素 CircleListNode* CircleList_Current(CircleList* list); //将游标移动指向到链表中的下一个数据元素 CircleListNode* CircleList_Next(CircleList* list); #endif //_CIRCLE_LIST_H
#include <stdio.h> #include <stdlib.h> #include <string.h> #include "CircleList.h" //创建结构体管理链表 typedef struct tag_CircleList { //循环链表头结点 CircleListNode header; //循环链表游标 CircleListNode *slider; //循环链表长度 int length; }TCircleList; //创建循环链表 CircleList* CircleList_Create() { //定义TCircleList指针变量,并分配内存空间 TCircleList* tlist = (TCircleList*)malloc(sizeof(TCircleList)); if (tlist == NULL) { printf("error: TCircleList* tlist = (TCircleList*)malloc(sizeof(TCircleList)) \n"); return NULL; } //数据初始化 tlist->header.next = NULL; tlist->slider = NULL; tlist->length = 0; return (CircleList*)tlist; } //销毁循环链表 void CircleList_Destroy(CircleList* list) { //定义TCircleList指针变量 TCircleList *tlist = NULL; //判断list是否为有效指针 if (list == NULL) { printf("Destory error: list 为无效指针\n"); return; } free(list); } //清空循环链表 void CircleList_Clear(CircleList* list) { //定义TCircleList指针变量 TCircleList *tlist = NULL; //判断list是否为有效指针 if (list == NULL) { printf("Clear error: list 为无效指针\n"); return; } //类型转换并赋值 tlist = (TCircleList*)list; //将长度重置为0 tlist->length = 0; //头结点指针域指向空 tlist->header.next = NULL; //游标指向空 tlist->slider = NULL; } //获取循环链表长度 int CircleList_Length(CircleList* list) { //定义TCircleList指针变量 TCircleList *tlist = NULL; //判断list是否为有效指针 if (list == NULL) { printf("Length error: list 为无效指针\n"); return -1; } //类型转换并赋值 tlist = (TCircleList*)list; return tlist->length; } //在循环链表中插入新节点 int CircleList_Insert(CircleList* list, CircleListNode* node, int pos) { int i; //定义TCircleList指针变量 TCircleList *tlist = NULL; //定义辅助指针变量 CircleListNode *currentNode = NULL; //判断list是否为有效指针 if (list == NULL || node == NULL || pos < 0) { printf("Insert error: if (list == NULL || node == NULL || pos < 0)\n"); return -1; } //类型转换并赋值 tlist = (TCircleList*)list; //元素插入 //step 1: 使用辅助指针变量,指向头结点 currentNode = &tlist->header; //step 2: 找到pos-1位置节点 for (i = 0; i < pos; ++i) { //判断是否有后继节点 if (currentNode->next != NULL) { //指针后移 currentNode = currentNode->next; } else { //没有后继节点跳出循环 break; } } //step 3: 将node节点的指针指向当前节点(pos-1)的后继节点(pos) node->next = currentNode->next; //step 4: 当前节点的指针指向node节点的地址 currentNode->next = node; //step 5: 如果是第一次插入节点 if (tlist->length == 0) { //将游标指向新插入节点 tlist->slider = node; } //step 6: 链表长度加1 tlist->length++; //step 7:若头插法 currentNode仍然指向头部 //原因: 跳0步, 没有跳走 if (currentNode == &tlist->header) { CircleListNode* lastNode = CircleList_Get(list, tlist->length - 1); //最后一个节点的指针,指向第一个数据节点 lastNode->next = currentNode->next; } return 0; } //获取循环链表中的指定位置的节点 CircleListNode* CircleList_Get(CircleList* list, int pos) { int i; //定义TCircleList指针变量 TCircleList *tlist = NULL; //定义辅助指针变量 CircleListNode *currentNode = NULL; //判断list是否为有效指针 if (list == NULL || pos < 0) { printf("CircleList_Get error: if (list == NULL || pos < 0)\n"); return NULL; } //类型转换并赋值 tlist = (TCircleList*)list; //step 1: 使用辅助指针变量,指向头结点 currentNode = &tlist->header; //step 2: 找到pos位置节点 for (i = 0; i <= pos; ++i) { //判断是否有后继节点 if (currentNode->next != NULL) { //指针后移 currentNode = currentNode->next; } else { //没有后继节点跳出循环 printf("error: 没找到指定位置的元素\n"); return NULL; } } return currentNode; } //删除循环链表中的指定位置的节点 //------------------------------- CircleListNode* CircleList_Delete(CircleList* list, int pos) { int i; //定义TCircleList指针变量 TCircleList *tlist = NULL; //定义链表节点指针,保存要删除的节点地址 CircleListNode *deleteNode = NULL; //定义链表节点指针,保存最后一个节点 CircleListNode *lastNode = NULL; //定义辅助指针变量 CircleListNode *currentNode = NULL; //判断list是否为有效指针 if (list == NULL || pos < 0) { printf("CircleList_Delete error: if (list == NULL || pos < 0)\n"); return NULL; } //类型转换并赋值 tlist = (TCircleList*)list; //判断链表中是否有节点 if (tlist->length <= 0) { printf("error: 链表为空,不能删除\n"); return NULL; } //元素删除 //step 1: 辅助指针变量,指向头结点 currentNode = &tlist->header; //step 2: 找到pos-1位置节点 for (i = 0; i < pos; ++i) { //指针后移 currentNode = currentNode->next; } //step 3: 保存要删除的节点的地址 deleteNode = currentNode->next; //step 4-1: 判断删除的元素是否为第一个元素 if (currentNode == &tlist->header) { //step 4-2: 找到最后一个节点 lastNode = CircleList_Get(list, tlist->length - 1); } //step 4-3: 判断lastNode是否为空 if (lastNode != NULL) { //step 4-4: 将最后一个节点的地址指向要删除节点的后继节点 lastNode->next = deleteNode->next; } //step 4-5: 将头结点的指针指向要删除节点的后继节点 currentNode->next = deleteNode->next; //step 5: 链表长度减1 tlist->length--; //step 6-1: 判断删除的元素是否为游标指向的元素 if (tlist->slider == deleteNode) { //step 6-2: 游标后移 tlist->slider = deleteNode->next; } //step 7-1: 判断删除元素后,链表长度是否为零 if (tlist->length == 0) { //step 7-2: 链表头结点指针域指向空 tlist->header.next = NULL; //step 7-3: 链表游标指向空 tlist->slider = NULL; } return deleteNode; } //------------------ new add ------------------ //直接指定删除链表中的某个数据元素 CircleListNode* CircleList_DeleteNode(CircleList* list, CircleListNode* node) { int i; int nPos = 0; //定义TCircleList指针变量 TCircleList *tlist = NULL; //判断list是否为有效指针 if (list == NULL || node == NULL) { printf("CircleList_DeleteNode error: if (list == NULL || node == NULL)\n"); return NULL; } //类型转换并赋值 tlist = (TCircleList*)list; //定义辅助指针变量,指向头结点 CircleListNode* currentNode = &tlist->header; //定义辅助指针变量,用来保存要删除的节点地址 CircleListNode* delNode = NULL; //查找node节点在循环链表中的位置 for (i = 0; i < tlist->length; ++i) { //从第一个数据节点开始判断,查找等于node的节点 if (currentNode->next == node) { //保存与node节点相等的节点的位置 nPos = i; //保存要删除的节点地址 delNode = currentNode->next; //跳出循环 break; } //当前节点指针后移 currentNode = currentNode->next; } //如果找到delNode,根据nPos删除该节点 if (delNode != NULL) { //删除指定位置的元素 CircleList_Delete(list, nPos); } return delNode; } //将游标重置指向链表中的第一个数据元素 CircleListNode* CircleList_Reset(CircleList* list) { //定义TCircleList指针变量 TCircleList *tlist = NULL; //判断list是否为有效指针 if (list == NULL) { printf("CircleList_Reset error: if (list == NULL)\n"); return NULL; } //类型转换并赋值 tlist = (TCircleList*)list; //重置游标位置 tlist->slider = tlist->header.next; return tlist->slider; } //获取当前游标指向的数据元素 CircleListNode* CircleList_Current(CircleList* list) { //定义TCircleList指针变量 TCircleList *tlist = NULL; //判断list是否为有效指针 if (list == NULL) { printf("CircleList_Current error: if (list == NULL)\n"); return NULL; } //类型转换并赋值 tlist = (TCircleList*)list; return tlist->slider; } //将游标移动指向到链表中的下一个数据元素 CircleListNode* CircleList_Next(CircleList* list) { //定义链表节点指针变量 CircleListNode *currNode = NULL; //定义TCircleList指针变量 TCircleList *tlist = NULL; //判断list是否为有效指针 if (list == NULL) { printf("CircleList_Next error: if (list == NULL)\n"); return NULL; } //类型转换并赋值 tlist = (TCircleList*)list; //存储当前游标位置 currNode = tlist->slider; //判断当前游标是否指向空 if (tlist->slider != NULL) { //游标后移 tlist->slider = currNode->next; } return currNode; }
#include <stdio.h> #include <stdlib.h> #include <string.h> #include "CircleList.h" typedef struct tag_value { CircleListNode circleNode; int v; }Value; int main() { int i; //定义Value结构体数组 Value val[10]; //创建循环链表 CircleList* list = CircleList_Create(); //循环初始化数组 for (i = 0; i < sizeof(val) / sizeof(Value); ++i) { val[i].v = i + 20; //往循环链表中插入数据 CircleList_Insert(list, (CircleListNode*)&val[i], i); } //遍历循环链表 //************* 怎么证明是循环链表? ************* for (i = 0; i < CircleList_Length(list) * 2; ++i) //打印两遍 { Value *pVal = (Value*)CircleList_Get(list, i); printf("Value %d = %d\n", i, pVal->v); } //删除节点 while (CircleList_Length(list) > 0) { Value *pVal = (Value*)CircleList_Delete(list, 0); printf("Delete Value: val = %d\n", pVal->v); } //销毁循环链表 CircleList_Destroy(list); return 0; }
最后我们详细分析一下循环链表中,插入数据和删除数据时具体步骤的图解,这样有助于我们有深刻的理解。(大部分内容源自 传智播客 教师课件)
【插入元素】
插入元素分很多中情况,如在中间插入元素、在尾部插入元素、在头部插入元素、首次插入元素,下面我们分别来看一下。
1、普通插入元素(和单链表是一样的)
2、尾插法(和单链表是一样的,单链表的写法支持尾插法;
分析:辅助指针向后跳length次,指向最后面那个元素(length-1位置),因为是循环
链表,所以length位置元素即为第一个数据节点。)
3、头插法
要进行头插法,需要求出尾节点,连接新的0号位置节点
第一次插入元素时,让游标指向0号结点(即第一个数据节点)
4、第一次插入元素(相当于头插法)
求出尾节点,尾节点指针指向第一个数据节点(即自己指向自己)
【删除节点】
1、删除普通结点
2、删除头结点(删除0号位置处元素),需要求出尾结点,连接新的零号位置节点
以上便是针对循环链表的操作详细介绍,其对比单向链表来看,不但增强了功能,有了游标使遍历更加方便了。但是缺点是点吗的复杂度少有提高,不太好理解。不过完全可以替换掉单向链表了。