快捷導(dǎo)航

Java數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)之循環(huán)鏈表

更新時(shí)間：2021年12月28日 09:48:19 作者：玄澈_

循環(huán)鏈表是另一種形式的鏈?zhǔn)酱鎯Y(jié)構(gòu)。它的特點(diǎn)是表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)。本文將為大家詳細(xì)介紹一下循環(huán)鏈表的特點(diǎn)與使用，需要的可以了解一下

存儲結(jié)構(gòu)示意圖

優(yōu)點(diǎn) ：能夠通過任意結(jié)點(diǎn)遍歷整個(gè)鏈表結(jié)構(gòu)

初始化循環(huán)鏈表?

1.循環(huán)鏈表的結(jié)點(diǎn)

typedef struct CircularNode {
	ElementType date; //數(shù)據(jù)域
	struct CircularNode* next; //指向下一個(gè)結(jié)點(diǎn)的指針域
 
}CircularNode;

2.循環(huán)鏈表結(jié)構(gòu)

typedef struct CircularLinkList {
	CircularNode* next;   //指向第一個(gè)結(jié)點(diǎn)的頭指針，頭指針
	int length;			  
}CircularLinkList;

循環(huán)鏈表的插入

需要考慮兩種情況

1.插入的鏈表長度為 0? ?node -> next = node;

2.插入的鏈表長度不為0 node -> next = clList -> next? ?lastNode -> next = node?

首位置

?

代碼實(shí)現(xiàn)

其他位置

代碼實(shí)現(xiàn)（總）

void InsertCircularLinkList(CircularLinkList* clList, int pos, ElementType element)
{
	//創(chuàng)建一個(gè)空節(jié)點(diǎn)
	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，就要找到鏈表的最后一個(gè)結(jié)點(diǎn)并改變其指針域
			CircularLinkList* lastNode = clList->next;
			for (int i = 1; i < clList->length; i++)
			{
				lastNode = lastNode->next;
			}
			clList->next = node;
			clList->length++;
		}
		return;
	}
	//插入的不是第一個(gè)結(jié)點(diǎn)
	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;
		}
	}
}

循環(huán)鏈表的刪除

1.操作的為第一個(gè)元素

代碼實(shí)現(xiàn)

2.操作元素不為第一個(gè)元素

代碼實(shí)現(xiàn)

代碼實(shí)現(xiàn)（總）

ElementType DeleteCircularLinkList(CircularLinkList* clList, int pos)
{
	ElementType element;
	element.id = -999;
	if (pos == 1) {
		CircularLinkList* node = clList->next;
		if (node) {
			//找到最后一個(gè)結(jié)點(diǎn)，改變其指針域的指向
			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;
}

循環(huán)鏈表的常見操作?

已知 P 結(jié)點(diǎn)是循環(huán)鏈表的中間結(jié)點(diǎn)，通過該節(jié)點(diǎn)遍歷循環(huán)鏈表

代碼實(shí)現(xiàn)

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數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)之循環(huán)鏈表的詳細(xì)內(nèi)容，更多關(guān)于Java數(shù)據(jù)結(jié)構(gòu) 循環(huán)鏈表的資料請關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: