Java数据结构 循环链表
玄澈_ 人气:0
存储结构示意图
优点 ： 能够通过任意结点遍历整个链表结构
初始化循环链表
1.循环链表的结点
typedef struct CircularNode {
ElementType date; //数据域
struct CircularNode* next; //指向下一个结点的指针域
}CircularNode;
2.循环链表结构
typedef struct CircularLinkList {
CircularNode* next; //指向第一个结点的头指针，头指针
int length;
}CircularLinkList;
循环链表的插入
需要考虑两种情况
1.插入的链表长度为 0 node -> next = node;
2.插入的链表长度不为0 node -> next = clList -> next lastNode -> next = node
首位置
代码实现
其他位置
代码实现（总）
void InsertCircularLinkList(CircularLinkList* clList, int pos, ElementType element)
{
//创建一个空节点
CircularLinkList* node = (CircularLinkList*)malloc(sizeof(CircularLinkList));
node->date = element;
node->next = NULL;
if (pos == 1) {
node->next = clList->next;
if (!node->next) {
//如果插入的链表长度为0
node->next = node;
}
else {
//如果长度不为0，就要找到链表的最后一个结点并改变其指针域
CircularLinkList* lastNode = clList->next;
for (int i = 1; i < clList->length; i++)
{
lastNode = lastNode->next;
}
clList->next = node;
clList->length++;
}
return;
}
//插入的不是第一个结点
CircularLinkList* currNode = clList->next;
for (int i = 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.操作元素不为第一个元素
代码实现
代码实现（总）
ElementType DeleteCircularLinkList(CircularLinkList* clList, int pos)
{
ElementType element;
element.id = -999;
if (pos == 1) {
CircularLinkList* node = clList->next;
if (node) {
//找到最后一个结点，改变其指针域的指向
CircularLinkList* lastNode = clList->next;
for (int i = 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 (int i = 1; node && i < pos; i++) {
preNode = node;
node = node->next;
}
if (node) {
element = node->date;
preNode->next = node->next;
free(node);
clList->length--;
}
return element;
}
循环链表的常见操作
已知 P 结点是循环链表的中间结点，通过该节点遍历循环链表
代码实现
CircularNode* GetCircularLinkListNode(CircularLinkList* clList, ELementType element)
{
CircularNode* node = clList->next;
if (!node) return NULL;
do {
if (element.id == node->date.id && strcmp(element.name, node->date.name) == 0) {
return node;
}
} while (node == clList->next);
return NULL;
}
加载全部内容