存储结构示意图
优点 ： 能够通过任意结点遍历整个链表结构
初始化循环链表
1，循环链表的结点
typedefstructCircularNode { ElementTypedate; //数据域structCircularNode*next; //指向下一个结点的指针域}CircularNode;
2，循环链表结构
typedefstructCircularLinkList { CircularNode*next; //指向第一个结点的头指针，头指针intlength; }CircularLinkList;
循环链表的插入
需要考虑两种情况
- 插入的链表长度为 0 node -> next = node;
- 插入的链表长度不为0 node -> next = clList -> next lastNode -> next = node
首位置
代码实现
其他位置
代码实现（总）
voidInsertCircularLinkList(CircularLinkList*clList, intpos, ElementTypeelement) { //创建一个空节点CircularLinkList*node= (CircularLinkList*)malloc(sizeof(CircularLinkList)); node->date=element; node->next=NULL; if (pos==1) { node->next=clList->next; if (!node->next) { //如果插入的链表长度为0node->next=node; } else { //如果长度不为0，就要找到链表的最后一个结点并改变其指针域CircularLinkList*lastNode=clList->next; for (inti=1; i<clList->length; i++) { lastNode=lastNode->next; } clList->next=node; clList->length++; } return; } //插入的不是第一个结点CircularLinkList*currNode=clList->next; for (inti=1; i<pos-1; i++) currNode=currNode->next; if (currNode) { node->next=currNode->next; currNode->next=node; clList->length++; if (pos==clList->length) { node->next=clList->next; } } }
循环链表的删除
1，操作的为第一个元素
代码实现
2，操作元素不为第一个元素
代码实现
代码实现（总）
ElementTypeDeleteCircularLinkList(CircularLinkList*clList, intpos) { ElementTypeelement; element.id=-999; if (pos==1) { CircularLinkList*node=clList->next; if (node) { //找到最后一个结点，改变其指针域的指向CircularLinkList*lastNode=clList->next; for (inti=1; i<clList->length; i++) { lastNode=lastNode->next; } clList->next=node->next; lastNode->next=clList->next; free(node); clList->length--; } return; } CircularLinkList*preNode; CircularLinkList*node=clList->next; for (inti=1; node&&i<pos; i++) { preNode=node; node=node->next; } if (node) { element=node->date; preNode->next=node->next; free(node); clList->length--; } returnelement; }
循环链表的常见操作
已知 P 结点是循环链表的中间结点，通过该节点遍历循环链表
代码实现
CircularNode*GetCircularLinkListNode(CircularLinkList*clList, ELementTypeelement) { CircularNode*node=clList->next; if (!node) returnNULL; do { if (element.id==node->date.id&&strcmp(element.name, node->date.name) ==0) { returnnode; } } while (node==clList->next); returnNULL; }
