Java數據結構與算法學習之循環鏈表
存儲結構示意圖
優點 : 能夠通過任意結點遍歷整個鏈表結構
初始化循環鏈表
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數據結構 循環鏈表的資料請關註WalkonNet其它相關文章!