Java数据结构与算法学习之循环链表

目录

• 存储结构示意图
• 初始化循环链表 
• 循环链表的插入
• 首位置
• 代码实现
• 其他位置
• 代码实现（总）
• 循环链表的删除
• 1.操作的为第一个元素
• 2.操作元素不为第一个元素
• 代码实现（总）
• 循环链表的常见操作 

存储结构示意图

优点 ： 能够通过任意结点遍历整个链表结构

初始化循环链表 

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;
}

以上就是Java数据结构与算法学习之循环链表的详细内容，更多关于Java数据结构 循环链表的资料请关注我们其它相关文章！