数据结构之双向循环链表

大家好，欢迎来到IT知识分享网。

双向循环链表

双向循环链表（Doubly Circular Linked List）是一种数据结构，其中每个节点都包含两个指针，一个指向前一个节点，一个指向后一个节点。与普通链表不同的是，双向循环链表的最后一个节点的下一个指针指向头节点，而头节点的前一个指针指向最后一个节点，形成一个循环。双向循环链表常用的操作包括：

• 初始化链表：创建一个空的双向循环链表。
• 插入节点：在链表的指定位置插入一个新的节点。
• 删除节点：从链表中删除指定位置的节点。
• 遍历链表：按顺序遍历链表中的所有节点。
• 查找节点：在链表中查找指定值的节点。

实现代码

#include <stdio.h> #include <stdlib.h> #include <assert.h> typedef struct Node { int data; struct Node* front; struct Node* tail; }NODE, * LPNODE, * LPDLIST; LPDLIST createList() { LPDLIST headNode = (LPDLIST)malloc(sizeof(NODE)); assert(headNode); headNode->front = headNode; headNode->tail = headNode; return headNode; } LPNODE createNode(int data) { LPNODE newNode = (LPDLIST)malloc(sizeof(NODE)); assert(newNode); newNode->front = NULL; newNode->tail = NULL; newNode->data = data; return newNode; } void push_front(LPDLIST headNode, int data) { LPNODE newNode = createNode(data); //headNode->tail不可能为空 headNode->tail->front = newNode; newNode->front = headNode; newNode->tail = headNode->tail; headNode->tail = newNode; } void push_back(LPDLIST headNode, int data) { LPNODE newNode = createNode(data); headNode->front->tail = newNode; newNode->tail = headNode; newNode->front = headNode->front; headNode->front = newNode; } void push_appoin(LPDLIST headNode, int posData, int data) { LPNODE preNode = headNode; LPNODE curNode = headNode->tail; while (curNode != headNode && curNode->data != posData) { preNode = curNode; curNode = preNode->tail; } if (curNode == headNode) { printf("未找到指定位置，无法插入！\n"); } else { LPNODE newNode = createNode(data); preNode->tail = newNode; newNode->front = preNode; newNode->tail = curNode; curNode->front = newNode; } } void pop_front(LPDLIST headNode) { if (headNode == NULL || headNode->front == headNode) { printf("链表为空无法删除!\n"); } else { LPNODE nextNode = headNode->tail; headNode->tail = nextNode->tail; nextNode->tail->front = headNode; free(nextNode); } } void pop_back(LPDLIST headNode) { if (headNode == NULL || headNode->front == headNode) { printf("链表为空无法删除!\n"); } else { LPNODE backNode = headNode->front; backNode->front->tail = headNode; headNode->front = backNode->front; free(backNode); backNode = NULL; } } //指定位置删除 void printByTail(LPDLIST headNode) { LPNODE pmove = headNode->tail; while (pmove != headNode) { printf("%d\t", pmove->data); pmove = pmove->tail; } printf("\n"); } void printByFront(LPDLIST headNode) { LPNODE pmove = headNode->front; while (pmove != headNode) { printf("%d\t", pmove->data); pmove = pmove->front; } printf("\n"); } int main() { LPDLIST list = createList(); push_front(list, 1); push_front(list, 2); printByTail(list); printByFront(list); push_back(list, 888); printByTail(list); // 2 1 888 printByFront(list); push_appoin(list, 888, 666); printByTail(list); // 2 1 888 printByFront(list); push_appoin(list, 2, 999); printByTail(list); // 2 1 888 //printByFront(list); printf("pop_front.....\n"); pop_front(list); printByTail(list); // 2 1 888 printByFront(list); printf("pop_back.....\n"); pop_back(list); printByTail(list); // 2 1 888 printByFront(list); return 0; }

约瑟夫环问题

约瑟夫环问题（Josephus Problem）是一个经典的数学问题，描述了以下情境：有n个人围成一圈，从第一个人开始报数，报到某个数字m的人将被淘汰出局，然后从下一个人重新开始报数，直到最后只剩下一个人。问题是找出最后留下的那个人在初始序列中的位置。解决约瑟夫环问题的一种常用方法是使用循环链表。可以按照以下步骤进行求解：

• 创建一个含有n个节点的循环链表，节点的值分别为1到n，按顺序排列。
• 从第一个节点开始，依次数m个节点，将第m个节点删除（从链表中断开）。
• 从被删除节点的下一个节点重新开始，回到步骤2，直到只剩下一个节点为止。

最后留下的节点即为最后的胜者。

#include <stdio.h> #include <stdlib.h> #include <assert.h> struct Node { int data; struct Node* next; struct Node* prev; }; struct CircularLinkedList { struct Node* head; }; struct Node* createNode(int data) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); assert(newNode); newNode->data = data; newNode->next = newNode; newNode->prev = newNode; return newNode; } void addNode(struct CircularLinkedList* list, int data) { struct Node* newNode = createNode(data); if (list->head == NULL) { list->head = newNode; } else { struct Node* lastNode = list->head->prev; lastNode->next = newNode; newNode->prev = lastNode; newNode->next = list->head; list->head->prev = newNode; } } void removeNode(struct CircularLinkedList* list, struct Node* node) { if (node->next == node) { list->head = NULL; free(node); } else { node->prev->next = node->next; node->next->prev = node->prev; if (list->head == node) { list->head = node->next; } free(node); } } void joseph_circle(int n, int m) { if (n <= 0 || m <= 0) { printf("Invalid input\n"); return; } struct CircularLinkedList circle; circle.head = NULL; for (int i = 1; i <= n; i++) { addNode(&circle, i); } struct Node* current = circle.head; while (n > 1) { for (int i = 0; i < m - 1; i++) { current = current->next; } struct Node* nextNode = current->next; removeNode(&circle, current); current = nextNode; n--; } printf("The winning position is: %d\n", circle.head->data); } int main() { int n = 10; // 一共10个人 int m = 4; // 报数为4的人出列 joseph_circle(n, m); return 0; } 

相关

如果阁下正好在学习C/C++，看文章比较无聊，不妨关注下关注下小编的视频教程，通俗易懂，深入浅出，一个视频只讲一个知识点。视频不深奥，不需要钻研，在公交、在地铁、在厕所都可以观看，随时随地涨姿势。