读书人

循环链表实现约瑟夫环的有关问题

发布时间: 2012-12-18 12:43:41 作者: rapoo

循环链表实现约瑟夫环的问题,求助!
#ifndef STATUS_H
#define STATUS_H

#define OK 1
#define OVERFLOW -2
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int Status;
typedef unsigned int size_t;

#endif

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include"status.h"

typedef int ElemType;

typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode,*LinkList;


/*创建带头结点的循环链表*/
Status CreateList(LinkList *L,int n)
{
int i;
LinkList p,q;
p=q=(LinkList)malloc(sizeof(LNode));
p=q=*L;//???????
for(i=0;i<n;i++)
{
p=(LinkList)malloc(sizeof(LNode));//开辟新结点
p->data=i+1;//将数字依次放入结点的数据域
p->next=NULL;
q->next=p;
q=p;
}
p->next=*L;
return OK;
}

/*约瑟夫环实现函数*/
Status Josephus(LinkList *L,int n,int i,int m)
{
LinkList p,q;
int j;
while(i--)//将指针指向第i个人
{
p=p->next;
}

while(n>1)
{
j=1;
q=p;
p=p->next;
j++;
if(j==m)//判定:数到m的人站出来
{
printf("%d ",p->data);
p=q->next->next;
free(p->next);
q->next=p;
n--;
}
}
return OK;
}

int main()
{
LinkList L;
CreateList(&L,8);
Josephus(&L,8,1,4);
return OK;
}

这段程序在VC上编译能通过,但是运行的时候就直接如图所示了
[最优解释]
这个没很复杂 先把创建链表看明白 再把约瑟夫环看明白 写这样的不难
下面是我之前自己写的 不是很好
肯定还有更好的代码 楼主可以借鉴下



#include "stdafx.h"
#include <iostream>
#include <malloc.h>

using namespace std;

typedef struct linklist{
int data;
linklist * pre;
linklist * next;
}LINKLIST;

LINKLIST * createLink()
{
LINKLIST * head;
LINKLIST * p;
LINKLIST * tail;

head = NULL;

p = (LINKLIST *)malloc(sizeof(LINKLIST));
if(NULL == p)
{
cout<<"ERROR"<<endl;
return NULL;
}
cout<<"-1 to exit:";
cin>>p->data;

while(-1 != p->data)
{
if(NULL == head)
{
head = p;
tail = p;
}else{
tail->next = p;
p->pre = tail;
tail = p;
}

p = (LINKLIST *)malloc(sizeof(LINKLIST));
if(NULL == p)
{
cout<<"ERROR"<<endl;
return NULL;
}
cout<<"-1 to exit:";
cin>>p->data;

}
head->pre = tail;
tail->next = head;

return head;
}

void printInfo(LINKLIST * head,int cnt)
{
LINKLIST * p;
p = head;

if(NULL == p)
{
cout<<"NUll"<<endl;
return ;
}

while(cnt>0)
{
cout<<p->data<<" ";
p = p->next;
cnt--;
}
cout<<endl;
}
//找出约瑟夫环中的人 cnt 为链表长度
void findPerson(LINKLIST * head,int cnt)


{
LINKLIST * p;
p = head;
int m=0,k=0;

if(NULL == p)
{
cout<<"NULL"<<endl;
return ;
}

while(m<cnt-1)
{
if(p->data!=0)
k++;
if(k==3)
{
k = 0;
m++;
p->data = 0;
}
p=p->next;
}
}

int main()
{
LINKLIST * head;
head = createLink();
cout<<"Before find:"<<endl;
printInfo(head,7);
findPerson(head,7);
cout<<"after find:"<<endl;
printInfo(head,7);

return 0;
}


[其他解释]
求高手指教啊!
[其他解释]
多半哪个指针指错了。
自己用debugger跟跟先。

读书人网 >C++

热点推荐