12.2作业

链表
├── 顺序表
│   ├── 定义
│   │   └── 数据元素在内存中连续存储
│   ├── 优点
│   │   ├── 随机访问能力强
│   │   ├── 查找和修改操作效率高
│   │   └── 实现简单
│   └── 不足
│       ├── 插入和删除操作效率低
│       ├── 需要连续内存空间，大规模数据难以处理
│       └── 存储空间有上限，扩展困难
├── 单向链表
│   ├── 定义
│   │   └── 每个节点包含数据和指向下一个节点的指针
│   ├── 操作
│   │   ├── 创建链表
│   │   ├── 插入节点（头插、尾插、任意位置）
│   │   ├── 删除节点（头删、尾删、任意位置）
│   │   ├── 查找节点
│   │   ├── 修改节点
│   │   ├── 遍历链表
│   │   ├── 翻转链表
│   │   ├── 排序链表
│   │   ├── 去重
│   │   └── 销毁链表
│   └── 概念
│       ├── 节点（数据域和指针域）
│       ├── 头指针（指向链表第一个节点）
│       └── 头结点（包含链表长度等信息）
├── 双向链表
│   ├── 定义
│   │   └── 每个节点包含数据和指向前一个节点及后一个节点的指针
│   ├── 操作
│   │   ├── 创建链表
│   │   ├── 插入节点（头插、尾插、任意位置）
│   │   ├── 删除节点（头删、尾删、任意位置）
│   │   ├── 查找节点
│   │   ├── 修改节点
│   │   ├── 遍历链表
│   │   └── 销毁链表
│   └── 概念
│       └── 节点结构体（包含指向前驱和后继的指针）
└── 循环链表
    ├── 定义
    │   └── 链表最后一个节点的指针指向头结点或第一个节点，形成闭环
    ├── 操作
    │   ├── 创建链表
    │   ├── 尾插节点
    │   ├── 尾删节点
    │   ├── 删除头结点
    │   ├── 遍历链表
    │   └── 销毁链表
    └── 概念
        ├── 单向循环链表（节点只有指向下一个节点的指针）
        └── 双向循环链表（节点有指向前一个节点和后一个节点的指针）

// josephus.h
#ifndef JOSEPHUS_H
#define JOSEPHUS_H

// 函数原型声明
void josephus(int n, int m);

#endif // JOSEPHUS_H

// josephus.c
#include "josephus.h"
#include <stdio.h>
#include <stdlib.h>

// 定义链表节点结构体
typedef struct Node 
{
    int number;
    struct Node* next;
} Node;

// 创建新节点
Node* createNode(int num) 
{
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->number = num;
    newNode->next = NULL;
    return newNode;
}

// 创建循环链表
Node* createCircularList(int n) 
{
    Node* head = createNode(1);
    Node* current = head;
    for (int i = 2; i <= n; i++) 
    {
        current->next = createNode(i);
        current = current->next;
    }
    current->next = head; // 形成循环
    return head;
}

// 约瑟夫环问题解决函数
void josephus(int n, int m) 
{
    Node* head = createCircularList(n);
    Node* prev = NULL;
    Node* current = head;

    while (current->next != current) // 当链表中不止一个节点时
    {
        for (int count = 1; count < m; count++) 
        {
            prev = current;
            current = current->next;
        }
        prev->next = current->next; // 移除当前节点
        printf("移除编号为 %d 的人\n", current->number);
        Node* temp = current;
        current = current->next;
        free(temp);
    }
    printf("最后剩下的人编号为 %d\n", current->number);
    free(current);
}

// main.c
#include "josephus.h"

int main() 
{
    int n = 8; // 总人数
    int m = 3; // 移除的间隔
    josephus(n, m);
    return 0;
}