约瑟夫环代码，循环链表。程序测试时部分数字组合可以成功运行，大部分都会以乱码输出

已经修改，运行通过：（问题出在头结点被局猜释放后，头指针没有正确调整）

#include <stdio.h>

#include <malloc.h>

//构建结构体

typedef struct Node

{

int Num

struct Node *next

}JosephNode, *PNode, *HeadNode

//初始化循环单链表

int JosephInit(HeadNode *h)

{

if(!h)

{

printf("链表初始化错误！\n")

return 0

}

(*h)->态悄next = (*h)//循环单链表

return 1

}

//单链表插入

int JosephInsert(JosephNode *h, int m, int x)

{

int i = 1

PNode p = h,q

if(m == 1)

{

p->Num = x

p->next = p

return 1

}

while(i <m-1)

{

p = p->next

i++

}

q = (PNode)malloc(sizeof(JosephNode))

q->Num = x

q->next = p->next

p->next = q

return 1

}

//遍历

void TraverseList(HeadNode h, int m)

{

int i = 0

PNode p = h

while(i <m)

{

printf(" %d", p->Num)

p = p->next

i++

}

}

//出局判定

int JosephDelete(HeadNode *h, int n, int k, int m)

{

int i

PNode p = *h,q

while(n >m+1)

{

for(i = 1i <k-1i++)

p = p->next

q = p->next

p->next = q->next

if(*h==q)*h=q->next

free(q)

p = p->next

n--

}

return 1

}

int main()

{

int i//计数数字

int n//总人数

int k//出局数字

int m//存活的朋友个数

printf("假设n个人围成一圈，其桐闭型中有m个你的朋友不想死掉，从第一个开始报数，第k个将被杀掉。为了保护自己和m个朋友，安排自己和m个朋友的初始位置。\n\n")

printf("参与人数：")

scanf("\t%d", &n)

printf("出局数字：")

scanf("\t%d", &k)

printf("朋友数量：")

scanf("\t%d", &m)

HeadNode h = ((HeadNode)malloc(sizeof(JosephNode)))//初始化头结点

JosephInit(&h)//初始化单链表

for(i = 0i <= ni++)//编号插入

JosephInsert(h, i, i)

JosephDelete(&h, n, k, m)//出局循环

printf("\n安全的位置编号为：")

m++

TraverseList(h,m)//遍历剩余位置编号

printf("\n")

return 0

}

#include<iostream>

using namespace std

//链表结点类number为这个人的编号,key为密码

struct person

{

unsigned int number

unsigned int key

person *next

}

//约瑟夫环类,此类包含多个person类,并控制输入输出.

class joseph_ring

{

private:

unsigned int n//用于存放人数

unsigned int m//用于存放初始密码

person *head//链表的头结点

public:

joseph_ring(){m=0n=0head=NULL}//构造函数,把成员变量赋初值

void create()//建立环的成员函数

void show()//运算并输出的成员函数

}

void joseph_ring::create()

{

cout<<"请输入人数:"

cin>>n

cout<<"请输入m的初值:"

cin>>m

//定义2个临时指针

person *p1,*p2

//for循环中用于初始化环

for(int i=1i<=ni++)

{

p1=new person//新实例化一个"人"的对象

p1->number=i//给这个"人"编个号

cout<<"请晌圆输入第 "<<i<<"个人对应密码:"

cin>>p1->key//给这个"人"一密码

//如果当前链表为空,头结点指向第一个"人"

if(i==1)

{

head=p1

p2=p1

}

//否则,p2永远指向尾结点,新建的结点都接到p2之后

else

{

p2->next=p1

p2=p1

}

}

p2->next=head//把链表连成一个循环链表(就是一个环)

}

void joseph_ring::show()

{

person *p1,*p2,*p

p1=head

//有n个人,所以执行n次循环

for(int i=1i<=ni++)

{

int count=1

//用count定位到第m个出圈人,循环后,p1指向这个出圈人,p2指向这个出圈人的上一个人

while(count++<m)

{

p2=p1

p1=p1->next

}

cout<<p1->number<<"\t"//输入当前出圈人的编号

m=p1->key//把当前出圈人的密码作为指向绝卖下一个出圈人所要经过的人数

p=p1//p指向当前这个出圈人

p2->next=p1->next//把出圈人前的人和出圈人后的人连上.

p1=p1->next//下次从当前出圈人的下宴宏塌一个人开始数

delete p//把出圈人毙掉(就是释放这块内存)

}

cout<<endl

cin>>m

}

int main()

{

joseph_ring j

j.create()

j.show()

return 0

}

---