单向链表练习题总结

长期置顶：欢迎大家挑错(友好地)(以及不友好地)……大家请直接在评论区发言（喷），请不要私信我，作业好多…… 还有是请注意公告内容，注意学术诚信，严格遵守我国法律，……（略去10^100字）

说明： 大多数题目来源于《程序设计（C语言）实验指导》（BUPTpress）

1. 约瑟夫问题

显然这是来自luogu的题目，至少我过了luogu的评测……

网址：

https://www.luogu.org/problemnew/show/P1996

以下是代码：

// 约瑟夫问题的各种解法：
// 1.数组；
// 2.单向链表；

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define DATA_TYPE long long
#define MaxN 200

void print_start_information(){
    printf("There are a variety of solutions.\n");
    printf("If you wanna solve the problem by arrays,please input one single number 1.\n");
    printf("If you wanna solve the problem by linked list,please input one single number 2.\n");
}

void solution_array(){
    DATA_TYPE n,m,a[MaxN],cnt=0,presentPtr=1,cnt_times=1;
    scanf("%lld%lld",&n,&m);
    if (n<=0 || m<=0) return;
    if (m>=2) {
        for (DATA_TYPE i = 1; i < n; ++i) {
            a[i] = i + 1;
        }
        a[n] = 1;
        cnt = n;
        while (cnt >= 1) {
            while (cnt_times % (m - 1) != 0) {
                presentPtr = a[presentPtr];
                cnt_times++;
            }
            printf("%lld ", a[presentPtr]);
            a[presentPtr] = a[a[presentPtr]];
            cnt--;
            presentPtr = a[presentPtr];
            cnt_times = 1;
        }
    }
    else if (m==1){
        for (int i = 1; i <= n; ++i) {
            printf("%d ",i);
        }
    }
}

void solution_linked_list(){
    DATA_TYPE n,m;
    struct listNode{
        DATA_TYPE val;
        listNode* next;
    }list[MaxN];
    scanf("%lld%lld",&n,&m);
    if (n<=0 || m<=0) return;
    if (m>=2){
        for (int i = 1; i < n; ++i) {
            list[i].val=i;
            list[i].next=&list[i+1];
        }
        list[n].val=n;
        list[n].next=&list[1];
        listNode *ptr=NULL;
        ptr=&list[1];
        DATA_TYPE cnt=2;
        while(ptr->next != ptr){
            while(cnt%m != 0){
                ptr=ptr->next;
                cnt++;
            }
            printf("%lld ",ptr->next->val);
            ptr->next=ptr->next->next;
            cnt=1;
        }
        printf("%lld",ptr->val);
    }
    else if (m==1){
        for (int i = 1; i <= n; ++i) {
            printf("%d ",i);
        }
    }

}

void solve_Joseph_problem(){
    print_start_information();

    int flag=0;
    scanf("%d",&flag);
    if (flag==1){
        solution_array();
    }
    else if (flag==2){
        solution_linked_list();
    }
    else{
        printf("There might be something wrong with your input.\n");
        printf("Please try it again.\n");
        print_start_information();
    }

}

int main(){
    solve_Joseph_problem();

    return 0;
}