[数据结构与算法]数据结构实验——约瑟夫环

一.?Experimental purpose：

• Understand the basic logical structure of linear list, and complete the implementation of linked list and circular linked list
• Through experiments, we can further understand the logical structure and storage structure of linear list, improve the ability to use theoretical knowledge to guide and solve practical problems, and master the practical application of linked list.

二.?Experimental content：

Title: Josephus ring problem

Problem description：

One description of Joseph's problem is that n individuals numbered 1,2,..., n sit clockwise. Select a positive integer as the upper limit of the number m. from the k person, the number shall be reported in clockwise direction from 1, and the number shall be stopped when the person reporting m is reported. The person reporting m shall list, and the next person in clockwise direction shall start to report from 1 number again until all the people are listed. Try to design a program to find out the sequence.

Basic requirements：

This process is simulated by using the one-way circular linked list storage structure, and the numbers of each person are printed in the order of listing.

#include "stdio.h"
#include "stdlib.h"

typedef struct LNode {
    int data;
    struct LNode* next;
}LNode, * LinkList;

LinkList Create(int n) {
    int flag = 1;
    LinkList L;
    LNode* s, * rear;
    L = (LinkList)malloc(sizeof(LNode));
    L->data = flag;
    flag++;
    rear = L;
    while (flag <= n) {
        s = (LNode*)malloc(sizeof(LNode));
        s->data = flag;
        rear->next = s;
        rear = rear->next;
        flag++;
    }
    rear->next = L;
    return L;
}

void Pri(LinkList L, int m, int n, int k) {
    // k开始节点，m出列数字，n节点总数
    LNode* rear,*free1;
    rear = L;
    int flag = 0;
    int k1 = 0 ,rear1=1;
    while (rear1 < n) {
        rear = rear->next;
        rear1++;
    }

    while (k1 < k - 1) {
        rear = rear->next;
        L = L->next;
        k1++;
    }
    k1 = 0;
    while (flag < n) {
        while (k1 < m - 1) {
            rear = rear->next;
            L = L->next;
            k1++;
        }
        printf("%d", L->data);
        printf("  ");
        L = L->next;
        free1 = rear->next;
        rear->next = rear->next->next;
        free(free1);
        k1 = 0;
        flag++;
    }
}

int main() {
    int m, n, k;
    printf("请输入结点总数：\n");
    scanf("%d", &n);
    printf("请输入开始结点数：\n");
    scanf("%d", &k);
    printf("请输入出列数字");
    scanf("%d", &m);
    LinkList L;
    L = Create(n);
    Pri(L, m, n, k);
    return 0;
}