1. 约瑟夫环

1.1 实验内容

约瑟夫（Joseph）问题的一种描述是：编号为 1, 2, …, n 的 n 个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。开始任选一个正整数作为报数上限值 m，从第一个人开始按顺时针方向自 1 开始顺序报数，报到 m 时停止报数。报 m 的人出列，将他的密码作为新的 m 值，从他在顺时针方向上的下一个人开始重新从 1 报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。

1.2 实验目的

掌握链表的基本操作：插入、删除、查找等运算，能够灵活应用链表这种数据结构。

1.3 程序清单

▶

Code

#include <stdio.h>
#include <stdlib.h>

typedef struct node_s {
    int              id;
    struct node_s *next;
} node_t;

node_t* create_node(int id)
{
    node_t *node = (node_t *)calloc(1, sizeof(node_t));
    if (node == NULL) {
        printf("ERROR: Failed to create new node;\r\n");
        exit(1);
    }

    node->id = id;
    node->next = NULL;

    return node;
}

int main()
{
    int n;  // 总人数
    int m;  // 报数上限

    node_t *head = NULL;
    node_t *tail = NULL;

    if (scanf("%d %d", &n, &m) != 2 || n <= 0 || m <= 0) {
        printf("ERROR: Invalid parameter;\r\n");
        return -1;
    }

    for (int i = 1; i <= n; i++) {
        node_t *node = create_node(i);

        if (head == NULL) {
            head = node;
            tail = node;
        } else {
            tail->next = node;
            tail = node;
        }
    }
    // 将尾节点指向头节点，形成单向循环链表
    tail->next = head;

    node_t *curr = head;
    node_t *prev = tail;

    while (n > 0) {
        // 报数：移动 m-1 次找到要出列的人
        for (int i = 1; i < m; i++) {
            prev = curr;
            curr = curr->next;
        }

        printf("%d", curr->id);

        // 从链表中移除 curr 节点
        prev->next = curr->next;
        node_t *temp = curr;
        curr = curr->next;
        free(temp);

        n--;
        if (n > 0) {
            printf(" ");
        }
    }
    printf("\r\n");

    return 0;
}

1.4 调试步骤

1. 输入测试数据

7 3

2. 程序输出

3 6 2 7 5 1 4

1.5 分析与思考

设人数为 n，初始密码为 m。

• 空间复杂度：$O(n \cdot m)$

• 时间复杂度：$O(n)$

2. 重排链表

2.1 实验内容

给定一个单链表 $L_1 \to L_2 \to \cdots \to L_{n-1} \to L_n$ ，请编写程序将链表重新排列为 $L_n \to L_1 \to L_{n-1} \to L_2 \to \cdots$ 。

例如：给定L为 $1 \to 2 \to 3 \to 4 \to 5 \to 6$ ，则输出应该为 $6 \to 1 \to 5 \to 2 \to 4 \to 3$ 。

2.2 实验目的

掌握链表的基本操作：插入、删除、查找等运算，能够灵活应用链表这种数据结构。

2.3 程序清单

▶

Code

#include <stdio.h>
#include <stdlib.h>

#define MAX_ADDR 100000

typedef struct node_s {
    int            addr;  // 结点地址
    int           value;  // 结点数据
    struct node_s *next;
} node_t;

node_t* create_node(int addr, int value)
{
    node_t *node = (node_t *)calloc(1, sizeof(node_t));
    if (node == NULL) {
        printf("ERROR: Failed to create new node;\r\n");
        exit(1);
    }

    node->addr = addr;
    node->value = value;
    node->next = NULL;

    return node;
}

void print_list(node_t *head)
{
    if (head == NULL) {
        return;
    }

    while (head != NULL) {
        printf("%05d %d ", head->addr, head->value);
        if (head->next != NULL) {
            printf("%05d\r\n", head->next->addr);
        } else {
            printf("-1\r\n");
        }
        head = head->next;
    }
}

node_t* reorder_list(node_t *head)
{
    if (head == NULL || head->next == NULL) {
        return NULL;
    }

    // 快慢指针寻找链表中点
    node_t *slow = head;
    node_t *fast = head->next;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }

    // 断开链表并反转后半部分
    node_t *head_1 = head;
    node_t *head_2 = slow->next;
    slow->next = NULL;

    node_t *prev = NULL;
    node_t *curr = head_2;
    while (curr != NULL) {
        node_t *temp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = temp;
    }
    head_2 = prev;

    // 交替合并
    node_t dummy;
    node_t *tail = &dummy;
    dummy.next = NULL;

    while (head_1 != NULL || head_2 != NULL) {
        if (head_2 != NULL) {
            tail->next = head_2;
            head_2 = head_2->next;
            tail = tail->next;
        }
        if (head_1 != NULL) {
            tail->next = head_1;
            head_1 = head_1->next;
            tail = tail->next;
        }
    }

    return dummy.next;
}

int main()
{
    int          n;
    int first_addr;

    scanf("%d %d", &first_addr, &n);

    int          data[MAX_ADDR];
    int     next_addr[MAX_ADDR];
    int valid[MAX_ADDR] = { 0 };

    for (int i = 0; i < n; i++) {
        int addr, val, nxt;
        scanf("%d %d %d", &addr, &val, &nxt);
        data[addr] = val;
        next_addr[addr] = nxt;
        valid[addr] = 1;
    }

    node_t  *head = NULL;
    node_t  *tail = NULL;
    int cur = first_addr;

    while (cur != -1 && valid[cur]) {
        node_t *node = create_node(cur, data[cur]);
        if (!head) {
            head = tail = node;
        } else {
            tail->next = node;
            tail = node;
        }
        cur = next_addr[cur];
    }

    head = reorder_list(head);
    print_list(head);

    // 释放内存
    node_t *temp;
    while (head != NULL) {
        temp = head;
        head = head->next;
        free(temp);
    }

    return 0;
}

2.4 调试步骤

1. 输入测试数据

00100 6
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

2. 程序输出

68237 6 00100
00100 1 99999
99999 5 12309
12309 2 00000
00000 4 33218
33218 3 -1

2.5 分析与思考

• 空间复杂度：$O(n)$

• 时间复杂度：$O(n)$