Question

josephus环问题

Typedef struct node{
int number;
struct node *next;
}Lnode,*Linklist
Linklist IntRingLList(int n){
Lnode *R,*p,*q;
int I;
R=new Lnode;
q=R;
for(i=1;i<n;i++){
p=new Lnode;
q->number=i;
q->next=p;
q=p;
}
p->number=n;
p->next=R;
R=p;
return R;
}

void Josephus(Linklist R,int n,int k,int quit[N]){
int i,j;
Lnode *p,*q;
p=R;
for(i=0;i<n;i++){
for(j=1;j<=k-1;j++)
p=p->next;
q=p->next;
p->next=q->next;
quit[i]=q->number;
delete q;
}
}

void Outing(int n,int quit[N]){
int i;
for(i=0,i<n,i++)
cout<<quit[i];
}

Answer 1

#include <stdio.h>
#include <malloc.h>

typedef int DataType;

struct node;
typedef struct node *PNode;
struct node {
DataType info;
PNode list;
};

typedef struct node *LinkList;
typedef LinkList *PLinkList;

int init_pclist(PLinkList lcList,int n)
//用1~n为*lclist所示的循环表初始化
{
PNode p, q;
int i;
p = (PNode)malloc(sizeof(struct node));

if (p == NULL) {
printf("Out of space\n");
return 0;
}
*lcList = p;
p ->info = 1;
p->list = p;
if (n == 1)
return 1;
else {
for (i = 2; i <= n; i++) {
q = (PNode)malloc(sizeof(struct node));
if (q == NULL) {
printf("Out of space\n");
return 0;
}
else {
q->info = i;
q->list = p->list;
p->list = q;
p = q;
}
}
}

return 1;
}

void jos_delete(PLinkList lcList, int s, int m)
{
PNode p, pre;
int i;
p = *lcList;

//找第s个元素
if (s == 1) {
pre = p;
p = p->list;
while (p != *lcList) { /*如果s为1，就让p，pre循环一圈，使pre指向p，因为只有设置好p的前节点，才能删除p所指节点 */
pre = p;
p = p->list;
}
}
else {
for (i = 1; i < s; i++) {
pre = p;
p = p->list;
}
}

while (p->list != p) { //当链表中节点个数大于1时，就一直查找&删除
for (i = 1;i < m; i++) {
pre = p;
p = p->list;
}

printf ("%d\t", p->info); //输出删除节点的信息
if (p == *lcList) //当要删除的节点为头结点时，需要特殊处理
*lcList = p->list;

pre->list = p->list; // 删除该节点
free(p);
p = pre->list;
}

printf ("%d ", p->info); //输出最后一个节点
*lcList = NULL;
free(p);
}

int main()
{
int n, s, m; //n为元素个数，s为起始点，m为出列数
LinkList pclist;
printf("Enter the value of n, s, and m: ");
scanf("%d %d %d", &n, &s, &m);

if (init_pclist(&pclist, n))
jos_delete(&pclist, s, m);
return 0;
}
// 这个编译通过，完全可以正确运行。我正好在做，希望对你有帮助。