约瑟夫环

/*
约瑟夫环
*/
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <iomanip>

#define ElemType int        //线性表数据类型

#define OK 0                //操作成功执行
#define ERROR -1            //操作失败
#define OVERFLOW -2         //溢出
typedef int Status;

typedef struct LNode {
    ElemType data;          //数据域
    int index;              //位序
    struct LNode *next;     //指针域
}LNode, *LinkList;

LinkList CreatList_L(int k);
//LinkList InitList_L();                                //1.创建
Status DestroyList_L(LinkList L);                   //2.销毁
Status ClearList_L(LinkList L);                     //3.清空
Status ListEmpty_L(LinkList L);                     //4.判空
int ListLength_L(LinkList L);                       //5.求长
ElemType GetElem_L(LinkList L, int i);              //6.访问元素
int LocateElem_L(LinkList L, ElemType e);           //7.求元素位序
//ElemType PriorElem_L(LinkList L, ElemType *cur_e);    //8.求前驱
//ElemType NextElem_L(LinkList L, ElemType *cur_e);     //9.求后继
//Status ListInsert_L(LinkList L, int i, ElemType e);   //10.插入元素
Status ListDelete_L(LinkList L, int i);             //11.约瑟夫环出列
Status ListTraverse_L(LinkList L, int k);           //12.遍历



LinkList CreatList_L(int k)     //构造约瑟夫环
{
    LinkList L;
    LNode *p, *s;
    L = (LinkList)malloc(sizeof(LNode));
    L->next = L;
    p = L;
    for (int i = 0; i < k;)
    {
        std::cin >> p->data;
        p->index = i + 1;
        i++;
        if (i < k)
        {
            s = (LinkList)malloc(sizeof(LNode));
            p->next = s;
            s->next = L;
            p = p->next;
        }
    }
    return L;
}
Status DestroyList_L(LinkList L)        //2.销毁
{
    LNode *p, *q;
    p = L;
    while (!p)
    {
        q = p->next;
        free(p);
        p = q;
    }
    L = NULL;
    return OK;
}
Status ClearList_L(LinkList L)      //3.清空
{
    LNode *p, *q;
    p = L->next;
    while (!p)
    {
        q = p->next;
        free(p);
        p = q;
    }
    L->data = 0;
    L->next = L;
    return OK;
}
Status ListEmpty_L(LinkList L)      //4.判空
{
    if (L->next == L) return 1;
    else return 0;
}
int ListLength_L(LinkList L)        //5.求长
{
    //return L->data;
    LNode *p;
    p = L;
    int j = 0;
    while (p->next != L)
    {
        p = p->next;
        j++;
    }
    return j;
}
ElemType GetElem_L(LinkList L, int i)      //6.访问元素
{
    LNode *p;
    p = L;
    int j = 0;
    while (p && j < i)
    {
        p = p->next;
        j++;
        if (p && j == i)return p->data;
    }
    if (!p || j > i)return ERROR;
}
int LocateElem_L(LinkList L, ElemType e)            //7.求元素位序
{
    LNode *p;
    p = L;
    int j = 0;
    p = p->next;
    while (p)
    {
        if (p->data == e)return j;
        p = p->next;
        j++;
    }
    if (!p || j > L->data)return ERROR;
}
Status ListDelete_L(LinkList L, int i)          //11.约瑟夫环出列
{
    ElemType e;
    LNode *p, *q;
    p = L;
    int j;
    while (!ListEmpty_L(L))
    {
        j = 1;
        while (j < i - 1)
        {
            p = p->next;
            j++;
        }
        q = p->next;
        std::cout << q->index << "(" << q->data << ")" << "->";
        p->next = q->next;
        i = q->data;
        p = p->next;
        if (q == L)L = q->next;
        free(q);
    }
    return OK;
}
Status ListTraverse_L(LinkList L,int k)         //12.遍历
{
    LNode *p;
    p = L;
    for (int i = 0; i < ListLength_L(L); i++)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    return OK;
}
int main(int argc, char *argv[])
{
    LinkList L;
    int m, k;
    std::cout << "请输入总人数及报数上限：" << std::endl;
    std::cin >> k >> m;
    L = CreatList_L(k);
    //std::cout << ListLength_L(L) << std::endl;
    ListDelete_L(L, m);
    DestroyList_L(L);
    return 0;
}