实验题目：

1. 假设有一个带头结点的单链表L，每个结点值由单个数字、小写字母和大写字母构成。设计一个算法将其拆分成3个带头结点的单链表L1、L2和L3，L1包含L中的所有数字结点，L2包含L中的所有小写字母结点，L3包含L中的所有大写字母结点。
2. 试用线性表的链表存储结构来实现约瑟夫(Josephu)问题。约瑟夫问题如下：设有n个人围坐圆桌周围。从某个位置上的人开始从1报数，数到m的人便出列，下一个人(第m+1个)又从1报数开始，数到m的人便是第2个出列的人，依次类推，直到最后一个人出列为止，这样就可以得到一个人员排列的新次序。例如，n=8,m=4,从第1个人数起，得到的新次序为48521376。

要求： 请写明：存储结构、基本算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法。

第一题

bash.h (链表的定义和基本操作)

#ifndef LINETABLE_CPP_BASH_H
#define LINETABLE_CPP_BASH_H

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

#define MaxSize 3

typedef char ElemType;
typedef struct LNode {
    ElemType data;
    struct LNode *next;
} LinkNode;

//初始化
void initList(LinkNode *&L) {
    L = (LinkNode *) malloc(sizeof(LinkNode));
    L->next = nullptr;

}

//头插法
void CreateList(LinkNode *&L, ElemType a[], int n) {
    LinkNode *s;
    L = (LinkNode *) malloc(sizeof(LinkNode));
    L->next = nullptr;
    for (int i = 0; i < n; i++) {
        s = (LinkNode *) malloc(sizeof(LinkNode));
        s->data = a[i];
        s->next = L->next;
        L->next = s;
    }
//    LinkNode *p = L->next;
//    while (p != nullptr) {
//        printf(" %c ", p->data);
//        p = p->next;
//    }
//    printf("结束\n");
}
//尾插法
void CreateList2(LinkNode *&L,char a[],int n) {
    LinkNode *p ,*q;
    L = (LinkNode *) malloc(sizeof(LinkNode));
    p = L;
    for(int i = 0; i <n;i++) {
        q = (LinkNode *) malloc(sizeof(LinkNode));
        q->data = a[i];
        p->next = q;
        p = q;
    }
    q->next = nullptr;
}
//销毁
void DestoryList(LinkNode *&L) {
    LinkNode *pre = L, *p = L->next;
    while (p != nullptr) {
        free(pre);
        pre = p;
        p = pre->next;
    }
    free(pre);
}

//求长度
int ListLength(LinkNode *L) {
    int n = 0;
    LinkNode *p = L;
    while (p->next != nullptr) {
        n++;
        p = p->next;
    }
    return n;
}

//
void DispList1(LinkNode *&L) {
    LinkNode *p = L->next;
    while (p != nullptr) {
        printf(" %c ", p->data);
        p = p->next;
    }
    printf("结束\n");
}

#endif //LINETABLE_CPP_BASH_H

sep.h （题目要求的操作，包括改进版Plus)

//
// Created by win10 on 2022/10/29.
//

#ifndef LINETABLE_CPP_DEP_H
#define LINETABLE_CPP_DEP_H
#include "bash.h"
// 插入元素
void CreateLiftR(LinkNode *&L, ElemType e, LinkNode *pNode, LinkNode *pLNode) {
    LinkNode *p = L, *s;
    s = (LinkNode *) malloc(sizeof(LinkNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
}

void dep(LinkNode *&L, LinkNode *&L1, LinkNode *&L2, LinkNode *&L3) {
//    LinkNode *p = L->next;
    LinkNode *p = L->next;
//    while (p != NULL) {
//        printf(" %c ", p->data);
//        p = p->next;
//    }
//    printf("结束\n");
    while (p != nullptr) {
        if (p->data >= '0' && p->data <= '9') {
            CreateLiftR(L1, p->data, nullptr, nullptr);
//            p = p->next;
        } else if (p->data >= 'A' && p->data <= 'Z') {
            CreateLiftR(L3, p->data, nullptr, nullptr);
//            p = p->next;
        } else {
            CreateLiftR(L2, p->data, nullptr, nullptr);
//            p = p->next;
//            printf("小写字母");
        }
        p = p->next;
    }
}

//尝试改进
void depPlus(LinkNode *&L, LinkNode *&L1, LinkNode *&L2, LinkNode *&L3) {
    LinkNode *s, *p = L->next, *r1 = L1, *r2 = L2, *r3 = L3;
    while (p != nullptr) {
        if (p->data <= '9' && p->data >= '0') {
            r1->next = p;
            r1 = p;
        } else if (p->data >= 'a' && p->data <= 'z') {
            r2->next = p;
            r2 =p;
        } else {
            r3->next =p;
            r3 = p;
        }
        p = p->next;
    }
    r1->next = nullptr;
    r2->next = nullptr;
    r3->next = nullptr;
}

#endif //LINETABLE_CPP_DEP_H

mainsep.cpp (主函数)

//
// Created by win10 on 2022/10/26.
//

//#include "bash.h"
#include "sep.h"
int main() {
    LinkNode *L, *L1, *L2, *L3;
    ElemType a[] = {'a', 'b', '1', '2', '3', 'C', 'D', '5','a','2'};
    initList(L);initList(L1);initList(L2);initList(L3);
    CreateList2(L, a, 10);
    depPlus(L, L1, L2, L3);
//    dep(L,L1,L2,L3);
    printf("L:");DispList1(L);
    printf("L1:");DispList1(L1);
    printf("L2:");DispList1(L2);
    printf("L3:");DispList1(L3);
    DestoryList(L);
    DestoryList(L1);
    DestoryList(L2);
    DestoryList(L3);
}

第二题：约瑟夫环

ysf.h

//
// Created by win10 on 2022/11/2.
//

#ifndef LINETABLE_CPP_YSF_H
#define LINETABLE_CPP_YSF_H

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

typedef struct LinkNode {
    int data;
    struct LinkNode *next;
} LinkNode;


//初始化
void initList(LinkNode *&L) {
    L = (LinkNode *) malloc(sizeof(LinkNode));
    L->next = nullptr;

}

void CreateList(LinkNode *&L, int n) {
    int i = 1;
    LinkNode *head = L, *p = L, *q;
    head->data = i;

    while (i < 8) {
        q = (LinkNode *) malloc(sizeof(LinkNode));
        q->data = i + 1;
//        q->next = p;
        p->next = q;
        p = q;
        i++;
    }
    q->next = head;
}

//打印
void DispList1(LinkNode *&L) {
    printf("打印开始");
    LinkNode *p = L;
//    printf("%d", L->data);
    int i = 0;
    while (i < 8) {
        printf(" %d ", p->data);
        p = p->next;
        i++;
    }
    printf("结束\n");
}
//--------------
void Josephu(LinkNode *& L,int n)
{
    int skip = n-1;
    LinkNode * p = L,*start;
    while (true)
    {
        start = p;
        for (int i = 0; i < skip-1; i++)
        {
            p = p->next;
        }
        //如果p的下一个就是前一个，说明只剩下最后俩了
        if (p->next == start)
        {
            printf("%d", start->data);
            printf("%d", start->next->data);
            free(start);
            free(p);
            break;
        }
        LinkNode * over = p->next;
        printf("%d", over->data);
        p->next = over->next;
        free(over);

        p = p->next;

    }
    printf("\n");
}

#endif //LINETABLE_CPP_YSF_H

ysf.cpp

//
// Created by win10 on 2022/11/2.
//
#include "ysf.h"
int main() {
    LinkNode *L;
    initList(L);
    CreateList(L,8);
    DispList1(L);
    Josephu(L,4);
}