C和数据结构——单循环链表

#include <bits/stdc++.h>
using namespace std;
typedef int ElemType;
typedef struct node
{
    ElemType data;     //数据域
    struct node *next; //指针域
} LNode, *LinkList;

//初始化单循环链表
int InitList_cl(LinkList &L)
{
    L = (LinkList)malloc(sizeof(LNode));
    if (!L)
        exit(OVERFLOW);
    L->next = L; //这里可以对比以下单链表的初始化
    return 1;
}

//求单循环链表的长度
int ListLength(LinkList L)
{
    int i = 0;
    LinkList p = L->next;
    while (p != L) //这里就只是把求单链表的条件换了一下
    {
        i++;
        p = p->next;
    }
    return i;
}

/*example1:
    求单循环链表中所有值为x的结点的个数
    */
int CountNode(LNode *L, ElemType x)
{
    int i = 0;
    LNode *p = L->next;
    while (p != L) //可以对比以下单链表
    {
        if (p->data == x)
            i++;
        p = p->next;
    }
    return i;
}

//删除结点值为x的结点
int Delallx(LNode *&L, ElemType x)
{
    LNode *pre = L, *p = L->next;
    while (p && p->data == x)
    {
        pre->next = p->next; //
        free(p);             //
        p = pre->next;       //
    }
    return 1;
}

// 解决约瑟夫问题：此时的ElemType date 表示小孩的标号
//这里采用不带头节点的单循环链表
void CreateList(LinkList *&L, int n) //创建链表
{
    int i;
    LinkList *p, *tc; //tc指向尾节点
    L = (LinkList *)malloc(sizeof(LinkList));
    L->data = 1; //先建立一个只有一个data为1结点的单链表
    tc = L;
    for (i = 2; i < n; i++)
    {
        p = (LinkList *)malloc(sizeof(LinkList));
        p->data = i;  //建立一个存放编号i的结点
        tc->next = p; //尾插法，将p放在表的尾部，保证顺序输出；
        tc = p;       //tc成为尾部
    }
    tc->next = L; //首结点为L;
}
void Joseph(int n, int m)
{
    int i, j;
    LinkList *L, *p, *q;
    CreateList(L, n);
    for (i = 1; i < n; i++) //报数，直到m-1;
    {
        p = L;
        j = 1;
        while (j < m - 1)
        {
            j++;
            p = p->next;
        }
        q = p->next;           //q指向第m个结点
        printf("%d", q->data); //结点出列
        p->next = q->next;     //删除q结点
        free(q);
        L = p->next; //从下一个结点开始继续报数
    }
}