循环链表是另一种形式的链式存贮结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。
单向循环链表.png
-
特点
- 循环链表的特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。
- 循环链表中没有NULL指针。涉及遍历操作时，其终止条件就不再是像非循环链表那样判别p或p->next是否为空，而是判别它们是否等于某一指定指针，如头指针或尾指针。
- 在单链表中，从一已知结点出发，只能访问到该结点及其后续结点，无法找到该结点之前的其它结点。而在单循环链表中，从任一结点出发都可访问到表中所有结点，这一优点使某些运算在单循环链表上易于实现。
-
代码实现
-
初始化
/* 循环链表创建! 2种情况:① 第一次开始创建; ②已经创建,往里面新增数据 1. 判断是否第一次创建链表 YES->创建一个新结点,并使得新结点的next 指向自身; (*L)->next = (*L);记录尾节点rear NO-> 找链表尾结点,将尾结点的next = 新结点. 新结点的next = (*L); */ bool ListInit(LinkList *L){ int item; LinkList temp = NULL; LinkList rear = 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; rear = *L; }else{ temp = (LinkList)malloc(sizeof(Node)); if(!temp) return ERROR; temp->data = item; temp->next = *L; rear->next = temp; rear = temp; } } return OK; } -
销毁
/* 销毁线性表，遍历每个结点 */ void destroyList(LinkList *L){ LinkList q = (*L)->next; LinkList p = (*L)->next; while (p != *L) { q = p->next; free(p); p = q; } free(*L); *L = NULL; } -
插入
/* 插入结点 @param L 链表指针 @param place 位置 从1开始记录 @param num 数据 */ void insertNode(LinkList *L,int place,int num){ //1. 创建新结点temp,并判断是否创建成功,成功则赋值,否则返回; LinkList temp = NULL; temp = (LinkList)malloc(sizeof(Node)); if (temp == NULL) { printf("插入失败"); return; } temp->data = num; //如果插入的位置为1,则属于插入首元结点,所以需要特殊处理 if (place == 1) { //找到链表最后的结点_尾结点, LinkList rear = NULL; do{ rear = *L; }while (rear->next != *L); //尾结点的next 指向新的头结点; rear->next = temp; //让新结点的next 执行头结点. temp->next = *L; //让头指针指向temp(临时的新结点) *L = temp; }else{ //找到要插入所在位置前驱 LinkList target = *L; int i = 1; while (i < place - 1) { I++; target = target->next; if (target == *L) { printf("插入失败,索引越界"); return; } } //让新结点的next 指向对应后驱. temp->next = target->next; //让对应结点指向temp(临时的新结点) target->next = temp; } printf("插入成功"); } -
删除
/* 删除结点 @param L 链表指针 @param place 位置 从1开始记录 */ void deleteNode(LinkList *L,int place){ if (*L == NULL){ printf("删除失败,索引越界"); return; } LinkList temp = NULL; //如果插入的位置为1,则属于插入首元结点,所以需要特殊处理 if (place == 1) { //单结点 直接释放 if(*L == (*L)->next){ temp = *L; *L = NULL; free(temp); } //找到链表最后的结点_尾结点, LinkList rear = NULL; do{ rear = *L; }while (rear->next != *L); //temp 指向 L temp = *L; //尾节点的下一个结点指向 L的下一个结点 rear->next = (*L)->next; // L 指向 下一个结点 (*L) = (*L)->next; //释放目标结点 free(temp); }else{ //找到要删除所在位置前驱 LinkList target = *L; int i = 1; while (i < place - 1) { I++; target = target->next; if (target->next == *L) { printf("删除失败,索引越界"); return; } } //临时指针指向目标位置 temp = target->next; //前驱的下一个结点指向新节点 target->next = temp->next; //释放目标 free(temp); } printf("删除成功"); } -
查找
//根据对应值找到第一个对应的结点 LinkList findValue(LinkList *L,int value){ LinkList temp = *L; while (temp->data != value) { temp = temp->next; if (temp->next == *L) { printf("未找到对应结点"); return NULL; } } return temp; }
-
