数据结构 实验报告-1

第一题 约瑟夫环：

一、实验内容：

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

二、实验目的：

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

三、程序清单：

▶

Code

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

typedef struct list{
    int data;
    struct list *next;
} list;
typedef struct list *LIST;

struct list *listcreat(int n){
    LIST head;
    LIST mid;
    LIST end;
    mid = (LIST)malloc(sizeof(list));
    head = mid;
    for (int i = 1; i <= n; i++){
        mid->data = i;
        end = mid;
        if (i == n){
            end->next = head;
            break;
        }
        mid = (LIST)malloc(sizeof(list));
        end->next = mid;
    }
    return head;
}

int main(){
    int n, p;
    scanf("%d %d", &n, &p);
    LIST HEAD;
    LIST MID;
    HEAD = listcreat(n);
    int x[n];
    int flag = 0;
    for (int i = 1; i <= n * p; i++){
        if (i % p == p - 1){
            MID = HEAD->next;
            x[flag] = MID->data;
            flag++;
            HEAD->next = MID->next;
            free(MID);
            continue;
        }
        HEAD = HEAD->next;
    }
    for (int i = 0; i < flag; i++){
        printf("%d", x[i]);
        if (i < flag - 1)
            printf(" ");
        else
            printf("\n");
    }
    return 0;
}

四、调试步骤：

1. 输入题中的测试数据；
2. 检查程序输出与预期输出的差距，分析错误在程序的哪个部分；
3. 更改程序，再次测试，直到程序输出符合预期；

五、分析与思考：

1. 在使用链表这一数据结构时，要小心使用指针，很多时候bug都是由错误的使用指针造成的；
2. 当IDE不报错，但程序始终无法跑起来的时候，优先检查指针是否使用错误；
3. 在使用链表的时候，将各种功能写成单独的函数在进行调用，会使程序的可读性更高，结构更加分明；

第二题 重排链表：

一、实验内容：

给定一个单链表 L1→L2→⋯→Ln−1→Ln，请编写程序将链表重新排列为 Ln→L1→Ln−1→L2→⋯。例如：给定L为1→2→3→4→5→6，则输出应该为6→1→5→2→4→3；

二、实验目的：

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

三、程序清单：

▶

Code

#include<stdio.h>
 
struct list {
    int data;
    int next;
}list;
typedef struct list LIST;

int main() {
    int HEAD;
    int N;
 
    scanf("%d %d", &HEAD, &N);
 
    LIST list_array[100000];
 
    int list[N];
    int list_changed[N];
 
    int address;
    int data;
    int next;
 
    for (int i = 0; i < N; i++) {
        scanf("%d %d %d", &address, &data, &next);
        list_array[address].data = data;
        list_array[address].next = next;
    }
    int flag = 0;
    int len = 0;
 
    while (HEAD != -1) {
        list[flag] = HEAD;
        HEAD = list_array[HEAD].next;
        flag++; len++;
    }
 
    flag = 0;
    int ind = 0;
    int end = len / 2;
    while (1) {
        list_changed[flag] = list[len - 1 - ind]; flag++;
        if (len % 2 != 0 && ind == end)
            break;
 
        list_changed[flag] = list[ind]; flag++;
        ind++;
 
        if (len % 2 == 0 && ind == end)
            break;
    }
 
    for (int i = 0; i < len; i++) {
        if (i == len - 1)
            printf("%05d %d %d\n", list_changed[i], list_array[list_changed[i]].data, -1);
        else 
            printf("%05d %d %05d\n", list_changed[i], list_array[list_changed[i]].data, list_changed[i + 1]);
    }
 
    return 0;
}

四、调试步骤：

1. 输入题中的测试数据；
2. 检查程序输出与预期输出的差距，分析错误在程序的哪个部分；
3. 更改程序，再次测试，直到程序输出符合预期；

五、分析与思考：

对链表这一数据结构在重排时的地址和其所储存的数据之间的关系有了更深刻的理解；`