请教:约瑟夫环问题

到百度贴吧首页
新闻   网页   贴吧   知道   MP3   图片   视频   百科
    吧内搜索 | 帮助

请教:约瑟夫环问题

1楼

请问,如何用C语言来实现一个循环链表?请各位指教,最好能给我一个例子.
我的 QQ是410521729
谢谢!

2楼

#include <malloc.h>
#define LEN sizeof(struct shu)
#define NULL 0
struct shu
{int num;
 struct shu *next;
 };
 main()
 {struct shu *p,*q,*head;
 int i,a,b;
 head=NULL;
 p=q=(struct shu *)malloc(LEN);
 scanf("%d",&p->num);
 while(p->num!=NULL)
 {if(head==NULL)head=p;
 else {q->next=p;q=p;}
 p=(struct shu *)malloc(LEN);
 scanf("%d",&p->num);
 }
 q->next=head;
 scanf("\n%d%d\n",&a,&b);
 while(q->num!=a)
 q=q->next;
 p=q->next;
 while(p!=q)
 {for(i=1;i<=b-2;i++)
 {q=p;p=p->next;}
 q->next=p->next;
 printf("%d,",p->num);
 q=q->next;
 p=q->next;
 }
 printf("%d",q->num);
}

3楼

谢谢

4楼

不用，只是我最近也刚好再做这个题目，就拿来班门弄斧啦！！！！
 有什么问题还请指教哦！！
 有空长联系，我的qq是“283263249”
 加的时候附加 ：c朋友
61.243.229.*

5楼

有没人了
222.134.245.*

6楼

?
222.170.98.*

7楼

约瑟夫环问题,是什么哦
210.43.131.*

8楼

不用头结点行不行啊??
210.43.131.*

9楼

可以呀很简单的问题
# define NULL 0
# define LEN sizeof(struct Londe)
main()
{ struct Londe {
 int number;
 int password;
 struct Londe *next;
 };
 int n=0,m,j=1;
 struct Londe *p1,*p2,*head;
 p1=p2=(struct Londe*)malloc(sizeof(LEN));
 printf("input the first number:");
 scanf("%d",&p1->number);
 printf("input the first password:");
 scanf("%d",&p1->password);
 head=NULL;
 while(p1->number!=0 && p1->password!=0)
 {n++;
 if(n==1)
 head=p1;
 else
 p2->next=p1;
 p2=p1;
 p1=(struct Londe *)malloc(sizeof(LEN));
 printf("input the %dth number:",n+1);
 scanf("%d",&p1->number);
 printf("input the password of the %dth number:",n+1);
 scanf("%d",&p1->password);
 }
 p1=p2->next=head;
 printf("input m:");
 scanf("%d",&m);
 while(n!=1)
 {while(m!=j)
 {
 j++;
 p1=p1->next;
 p2=p2->next;
 }
 printf("%d,",p1->number);
 m=p1->password;
 p2->next=p1->next;
 p1=p2->next;
 j=1;
 n--;
 }
 printf("%d\n",p1->number);
}
欢迎和对c语言有兴趣的朋友交流，qq:253968497 验证时注明c语言交流
61.156.49.*

10楼

以7个人为例，用链表实现，每个人都有自己的密码，当他出列时，以他的密码作为下一个的个数，例这七个人的密码分别是3，1，7，2，4，8，4。第一个执行的个数是20
218.4.189.*

11楼

不该用一个函数
219.216.84.*

12楼

#include <stdio.h>
#include <stdlib.h>

/* to test something about LIST data structure
2005.9.26 */
struct list
{
 int data;
 int key;
 struct list* nextPtr;
};
typedef struct list List;
typedef List* ListPtr;

ListPtr insert(ListPtr*,int);
void constructList(ListPtr*,int);
void print(ListPtr,int);
void distroy(ListPtr);
void maintain(ListPtr,int);

int main()
{
 int n;
 ListPtr sPtr;
 sPtr=NULL;
 printf("\ninput n:");
 scanf("%d",&n);
 constructList(&sPtr,n);
 print(sPtr,n);
 #if 1
 maintain(sPtr,n);
 #endif
 getch();
 return 0;
}


ListPtr insert(ListPtr* sPtr,int value)
{
 ListPtr currentPtr,previousPtr,newPtr;
 static int i=1;
 newPtr=(ListPtr)malloc(sizeof(ListPtr));
 currentPtr->nextPtr=NULL;
 if(newPtr!=NULL)
 {
newPtr->data=i;
newPtr->key=value;
newPtr->nextPtr=NULL;
currentPtr=*sPtr;
 previousPtr=NULL;
 while(currentPtr!=NULL)
 {
 previousPtr=currentPtr;
 currentPtr=currentPtr->nextPtr;
 }
 if(previousPtr==NULL){
 *sPtr=newPtr;
 i++;
 return *sPtr;
}else{
 previousPtr->nextPtr=newPtr;
 i++;
 return newPtr;
 }
 }else{
 printf("can't malloc \n");
 }



}


void constructList(ListPtr* sPtr,int n)
{
 int i;
 int key;
 ListPtr currentPtr;

 currentPtr=NULL;
 for(i=0;i<n;i++)
 {
 printf("input key of %d:",i+1);
 scanf("%d",&key);
 currentPtr=insert(sPtr,key);
 }
 currentPtr->nextPtr=*sPtr;

}

void print(ListPtr sPtr,int n)
{
 int i;
 printf("List is:");
 for(i=0;i<n;i++)
 {
 printf("%d with",sPtr->data);
 printf(" %d ->",sPtr->key);
 sPtr=sPtr->nextPtr;
 }
 printf("\n");
}


void distroy(ListPtr sPtr)
{
 ListPtr tempPtr;
 while(sPtr!=NULL)
 {
 tempPtr=sPtr;
 sPtr=sPtr->nextPtr;
 free(tempPtr);

 }
 printf("free success!\n");
}


void maintain(ListPtr sPtr,int n)
{
 int m,length,posit;
 ListPtr currentPtr,previousPtr,tempPtr;

 length=n;
 currentPtr=previousPtr=sPtr;
 printf("input the first KEY:");
 scanf("%d",&m);

 while(length>=1)
 {
 posit=m-2;
 if(posit==-1)
 {
 m=currentPtr->key;
 printf("%d--",currentPtr->data);
 currentPtr=previousPtr=currentPtr->nextPtr;


 }else{

 while(posit)
 {

 currentPtr=currentPtr->nextPtr;
 posit--;
 }
 previousPtr=currentPtr;
 tempPtr=currentPtr->nextPtr;
 m=tempPtr->key;
 printf("%d--",tempPtr->data);
 currentPtr=tempPtr->nextPtr;
 previousPtr->nextPtr=currentPtr;
 length--;

 }
 }
 printf("\n");

}


13楼

我的一个实验

14楼

我们老师是要求是用约瑟夫问题来解决八仙选首的问题，就是说报数Ｍ可以从一到８开始变化，最后出列的就是首领，八趟后就会出现八个首领（位置可能重复），把这些首领放在一个数组里跟原来的八个数相比，看哪个数是没现在首领的位置上，把没出现的数输出就行了．

15楼

急！大家帮帮忙吧！感恩不尽

16楼

请教
两个SCANF函数，第一个输入的是密码，第二个输入总人数和初始值吗 ？

17楼

佳晟 编的C 语言中的输入语句

18楼

用一维数组实现约瑟夫问题


#include"stdio.h"
main()
{int m,n,s,i,count,k,array[100];
printf("\nPLease tell me how many children are there?\n");
scanf("%3d",&n);
printf("\nFrom which to count\n");
scanf("%3d",&m);
printf("\nHow shall I count\n");
scanf("%3d",&s);
for(i=1;i<=n;i++)
array[i]=i;
count=n;k=m;
while(count!=0)
{k=k-1+s;
while(k>count)k=k-count;
printf("%7d",array[k]);
if((n-count+1)%10==0)printf("\n");
if(k!=count)
for(i=k;i<count;i++)
array[i]=array[i+1];
count--;

19楼

用链表方式实现约瑟夫问题
#include"stdio.h"
typedef struct node
{int no;
struct node *link;
}NODE;
create_link(NODE *p,int n)
{NODE *q;
for(;n>1;n--)
{q=(NODE*)malloc(sizeof(NODE));
q->no=n;
q->link=p->link;
p->link=q;
}
}
NODE *select_no(NODE *p,int s)
{NODE *q;
for(;s>2;s--)
p=p->link;
q=p->link;
p->link=q->link;
printf("%d\t",q->no);
free(q);
return(p->link);
}
main()
{NODE *p;int n,m,s;
p=(NODE*)malloc(sizeof(NODE));
p->no=1;p->link=p;
printf("How many children are there?\n");
scanf("%d",&n);
create_link(p,n);
printf("From where would you like to count:\n");
scanf("%d",&m);
for(;m>1;m--)
p=p->link;
printf("How many do you want to count?\n");
scanf("%d",&s);
if(s==1)printf("no sense");
else
{printf("OUTPUT:\n");
for(;n>0;n--)
p=select_no(p,s);
}
}
218.4.189.*

21楼

谁给我分析分析它的时间、空间复杂度，并给出进一步改进方案
59.44.72.*

22楼

那个叫天地蒙胧龙的人，我很喜欢你写的程序，我想和你做朋友！可以吗？希望你能看到！！
59.44.72.*

23楼

那个叫天地蒙胧龙的人，我很喜欢你写的程序，我想和你做朋友！可以吗？希望你能看到！！
59.44.72.*

24楼

我的QQ是369742582，加我哦！！

25楼

回复：已经加上了
221.215.216.*

26楼

struct sq
{
int hao;
int mi;
};
typedef struct Lnode
{
sq data;
Lnode * next;
}*Link;

typedef struct
{
int len;
Link head;
} LinkList;


void InsertList(LinkList &L,int pos,sq e) //依次插入元素,注意第一个和以后的不同,如果有头结点,就不会有这方面的问题
{
Lnode *s=new Lnode ;Lnode *q=new Lnode;
s->data.hao=e.hao ;
s->data.mi=e.mi ;
int i=0;
if (L.head ) 
{
Lnode *p=L.head ;
while (i<1)
{
q=p;
p=p->next ;
if (p==L.head ) i++;
}
q->next =s;
}
else
{
L.head =s;
}
s->next =L.head ;
}

void CreatCycle(LinkList &L,int n) //建立循环链表
{
L.head =NULL; //无头结点
sq e;
for (int i=1;i<=n;i++)
{
e.hao =i;
cout<<"请输入第"<<i<<"人的密码:";
cin>>e.mi ;
InsertList(L,i,e);
}
}

Link TravelCycle(LinkList L,Lnode * p,int n) //把p定位在第n个被点到的元素元素的前一个位置上，以便删除第n个
{
for (int i=1;i<n-1;i++)
{
p=p->next ;
}
return p;

}

int DeleteCycle(LinkList &L,Link p,sq& e) 
{
if (L.head !=NULL)
{
Lnode *q=p->next;
p->next =q->next;
e=q->data;
delete q;
return OK;
}
}
int _tmain(int argc, _TCHAR* argv[])
{
const int n=7;int m=20;
LinkList L;CreatCycle(L,n);
Lnode *p=L.head ;
sq e;int order[n];

for (int i=1;i<=n;i++)
{

p=TravelCycle(L,p,m);

if (DeleteCycle(L,p,e))
{
m=e.mi ;order[i-1]=e.hao ;
}
if (L.head !=NULL) p=p->next;
}
cout<<"出队列的顺序是:";
for (int i=1;i<=n;i++)
cout<<order[i-1]<<",";


return 0;
}



VC下实现的,但学的是C版本
220.160.7.*

27楼

最短路径问题:设计一个校园导游程序
61.234.136.*

28楼

你们能帮我编一个程序吗？？
就是敢死队的的那个，但是至少要用2中数据结构实现。

29楼

哈哈，我怎么觉得题目好熟悉啊
是不是有系友啊
218.7.221.*

31楼

taixiexienile !

32楼

我们老师以前也要我们做过，这个我做的，不是太好，就是可以控制从第几个开始，一次数几个人。
struct List
{int data;
 struct List * next;
};


void CreateList(struct List * L, int n)
{int i;
 struct List * p=L;
 for(i=1;i<=n-1;i++)
 {p->data=i;
 p->next=(struct List *)malloc(sizeof(struct List));
 p=p->next;
 if(!p) exit(0);
 }
 p->data=n;
 p->next=L;
}


void Joseph(struct List * L, int n, int m, int r)
{struct List * p=L, * q;
 int i, j, k=0;
 for(i=2;i<=r;i++)
 p=p->next;
 while(k!=n)
 {for(j=1;j<=m;j++)
 p=p->next;
 q=p;
 while(q->next!=p)
 q=q->next;
 q->next=p->next;
 printf(" %d",p->data);
 if(k%10==0)
 printf("\n");
 free(p);
 p=q;
 k++;
 }

}


void main()
{struct List * L;
 int n, m, r;
 scanf("%d %d %d",&n,&m,&r);
 CreateList(L,n);
 Joseph(L,n,m,r);
}

发表回复

内　容:
用户名:
  
©2010 Baidu 贴吧协议  意见反馈