以下是我用循环列表实现约瑟夫问题的代码,通过调试,已经发现了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;
}