双向循环链表

双向循环链表（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++，看文章比较无聊，不妨关注下关注下小编的视频教程，通俗易懂，深入浅出，一个视频只讲一个知识点。视频不深奥，不需要钻研，在公交、在地铁、在厕所都可以观看，随时随地涨姿势。