C\C++，用循坏列表实现约瑟夫问题，求大腿指导！

以下是我用循环列表实现约瑟夫问题的代码，通过调试，已经发现了DeleteDeath（）函数那里存在空指针导致程序崩溃的问题，然后就一头雾水了，求大神指导，我这段程序改怎么改正从而实现约瑟夫问题！谢谢了！！！

 #include<iostream>
#include<stdlib.h>
using namespace std;
//循环链表结构定义
typedef struct node
{
    int data;
    struct node *next;
}ListNode;
typedef ListNode *LinkList;
//建立带头结点的单循环链表
void initRing(int n, LinkList &R)
{
    ListNode *p, *rear;
    p = NULL;
    //构造一个空的循环列表
    R = (LinkList)malloc(sizeof(ListNode)); //建立头结点
    R->next = R;
    rear = R;   //尾指针指向头结点
    for (int i = 1; i <= n; i++) {
        p = (LinkList)malloc(sizeof(ListNode));
        p->data = i;
        p->next = NULL;
        rear->next = p;
        rear = p;
        rear->next = R;
    }
}
//获取出列的人的编号
void DeleteDeath(int n, int m, LinkList &R)
{
    int i;
    LinkList p, q, s;
    s = (LinkList)malloc(sizeof(ListNode));
    q = R;
    p = R;
    while (R->next != NULL) {
        for (int i = 1; i<m; i++) {         
            p = p->next;     //找到第m-1个节点
            q = p;           //用 q 记录第m-1个节点
        }
        s->data = p->next->data;  //将下一个，即第m个节点删除
        cout << s->data << endl;
        free(p->next);      
        q->next = p->next->next;    //问题出在这行，q->next出现了空指针
    }
}
int main()
{
    LinkList R;
    int n, m;
    cout << "总人数n= "<< "   " << "报数上限m=" << endl;
    cin >> n >> m;


    initRing( n, R);
    DeleteDeath( n,  m, R);

    return 0;
}

http://blog.csdn.net/arhaiyun/article/details/12069275?locationNum=2&fps=1

http://blog.csdn.net/C__Monkey/article/details/8079552?locationNum=4&fps=1

改了一下这个函数，其中参数n应该是不需要传的

 void DeleteDeath(int m, LinkList &R)
{
    ListNode* p = R;
    ListNode* front = R;

    while (front != NULL)
    {
        for (int i = 1; i < m;i++)
        {
            p = p->next;
        }

        if (p->next != p)
        {
            cout << p->next->data << " ";
            if (p->next == front)
            {
                front = p->next->next;  
            }
            free(p->next);
            p->next = p->next->next;
        }else{
            cout << p->data << endl;
            front = NULL;
        }
    }
}

这是带头结点的，修改DeleteDeath（）函数后依旧崩溃

 #include<iostream>
#include<stdlib.h>
using namespace std;
//循环链表结构定义
typedef struct node
{
    int data;
    struct node *next;
}ListNode;
typedef ListNode *LinkList;
//建立带头结点的单循环链表
void initRing(int n, LinkList &R)
{
    ListNode *p, *rear;
    p = NULL;
    //构造一个空的循环列表
    R = (LinkList)malloc(sizeof(ListNode)); //建立头结点
    R->next = R;
    rear = R;   //尾指针指向头结点
    for (int i = 1; i <= n; i++) {
        p = (LinkList)malloc(sizeof(ListNode));
        p->data = i;
        p->next = NULL;
        rear->next = p;
        rear = p;
        rear->next = R;
    }
}
//获取出列的人的编号
void DeleteDeath(int m, LinkList &R)
{
    ListNode* p = R;
    ListNode* front = R;

    while (front != NULL)
    {
        for (int i = 1; i < m; i++)
        {
            p = p->next;
        }

        if (p->next != p)
        {
            cout << p->next->data << " ";
            if (p->next == front)
            {
                front = p->next->next;
            }
            free(p->next);
            p->next = p->next->next;
        }
        else {
            cout << p->data << endl;
            front = NULL;
        }
    }
}

int main()
{
    LinkList R;
    int n, m;
    cout << "总人数n= " << "   " << "报数上限m=" << endl;
    cin >> n >> m;


    initRing(n, R);
    DeleteDeath(m, R);

    return 0;
}

这是之后建立不带头结点的循环链表成功实现约瑟夫问题

 #include<iostream>
#include<stdlib.h>
using namespace std;
//循环链表结构定义
typedef struct node
{
    int data;
    struct node *next;
}ListNode;
typedef ListNode *LinkList;
//建立带头结点的单循环链表
LinkList initRing(int n, LinkList &R)
{
    ListNode *p, *q;
    q = p = R = (LinkList)malloc(sizeof(ListNode));
    //构造一个空的循环列表
    //R = (LinkList)malloc(sizeof(ListNode));   //建立头结点
    //R->next = R;
    //rear = R; //尾指针指向头结点
    for (int i = 1; i <= n; i++) {
        p = (LinkList)malloc(sizeof(ListNode));     
        p->data = i;
        p->next = NULL;
        if (1 == i)
        {
            R = p;
        }
        q->next = p;
        q = p;
    }
    p->next = R;
    return p->next;
}
//获取出列的人的编号
void DeleteDeath(int m, LinkList &R)
{
    int i;
    LinkList p, q;
    int s;  //s用来存储被删除的值
    q = R;
    p = R;
    while (p->next != p) {      
        for (int i = 1; i<m; i++) { 
            q = p;
            p = p->next;     //找到第m个节点      
        }
        s = p->data;  //将下一个，即第m个节点删除
        cout << s << endl;                  
        q->next = p->next;      //链接删除节点之前和删除之后的结点
        free(p);
        p = q->next;
    }
    cout << "winner:" << p->data << endl;
    free(p);
    q = R = NULL;
}
int main()
{
    LinkList R;
    int n, m;
    cout << "总人数n= "<< "   " << "报数上限m=" << endl;
    cin >> n >> m;


    R = initRing( n, R );
    DeleteDeath( m, R );

    return 0;
}

//建立带头结点的单循环链表
void initRing(int n, LinkList &R)
{
ListNode *p, *rear;
p = NULL;
//构造一个空的循环列表
R = (LinkList)malloc(sizeof(ListNode)); //建立头结点
R->next = R;
rear = R; //尾指针指向头结点
for (int i = 1; i <= n; i++) {
p = (LinkList)malloc(sizeof(ListNode));
p->data = i;
R->next = p;
p->next = R;
//rear->next = p;
//rear = p;
//rear->next = R;
rear = p;//rear指向最后一个结点.
}
}
这样你在试试看。

头节点不应该有的，因为整个的循环队列不能有空缺，而你的头节点没有数据，也就是结点与结点之间有了空隙，这是不对的。