2、例程:
#include
#include
typedef int ElemType
typedef struct LNode{
ElemType dataint num
struct LNode *next
}LNode,*LinkList
void CreateList_L(LinkList *L,int n)
{ int i=0
ElemType e
LinkList p,q
*L=(LinkList)malloc(sizeof(LNode))
(*L)->next=NULL(*L)->data=n
q=*L
while(i
data=ep->num=i+1
p->next=NULL
q->next=p
q=p
i++
}
p->next=(*L)->next
}
void PrintList(LinkList L)
{ int i=0
LinkList p
p=L->next
while(i
data)
{
printf("%5d",p->data)
p=p->next
i++
}
printf("\n")
}
void Put(LinkList *L)
{ int i,mLinkList p,q
printf("input a number:\n")
scanf("%d",&m)
q=(*L)->next
while((*L)->data)
{for(i=0i
next
}
printf("%5d",q->num)
m=q->data
p->next=q->next
free(q)
q=p->next
(*L)->data=(*L)->data-1
}
}
void main()
{LinkList L
int a
printf("请输入人数:")
scanf("%d",&a)
printf("请输入密码:")
CreateList_L(&L,a)
printf("您输入的数字为:\n")
PrintList(L)
Put(&L)
}
链表方法这个就是约瑟夫环问题的实际场景,有一种是要通过输入n,m,k三个正整数,来求出列的序列。这个问题采用的是典型的循环链表的数据结构,就是将一个链表的尾元素指针指向队首元素。
p->link=head
解决问题的核心步骤:
1.建立一个具有n个链结点,无头结点的循环链表
2.确定第1个报数人的位置
3.不断地从链表中删除链结点,直到链表为空
void
JOSEPHUS(int
n,int
k,int
m)
//n为总人数,k为第一个开始报数的人,m为出列者喊到的数
{
/*
p为当前结点
r为辅助结点,指向p的前驱结点
list为头节点*/
LinkList
p,r,list
/*建立循环链表*/
for(int
i=0,i<n,i++)
{
p=(LinkList)malloc(sizeof(LNode))
p->data=i
if(list==NULL)
list=p
else
r->link=p
r=p
}
p>link=list
/*使链表循环起来*/
p=list
/*使p指向头节点*/
/*把当前指针移动到第一个报数的人*/
for(i=0i<ki++)
{
r=p;
p=p->link
}
/*循环地删除队列结点*/
while(p->link!=p)
{
for(i=0i<m-1i++)
{
r=p
p=p->link
}
r->link=p->link
printf("被删除的元素:%4d
",p->data)
free(p)
p=r->link
}
printf("\n最后被删除的元素是:%4d",P->data)
}
怎么了,代码看不懂?约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1,最后结果+1即为原问题的解。
首先我们列出一些有关约瑟夫环的结果:
1 1 2 2 3 2 4 1 5 4 6 1 7 4 8 7 9 1 10 4
11 7 12 10 13 13 14 2 15 5 16 8 17 11 18 14 19 17 20 2021 2 22 5 23 8 24 11 25 14 26 17 27 20 28 23 29 26 30 29
31 1 32 4 33 7 34 10 35 13 36 16 37 19 38 22 39 25 40 28
41 31 42 34 43 37 44 40 45 43 46 46 47 2 48 5 49 8 50 11
51 14 52 17 53 20 54 23 55 26 56 29 57 32 58 35 59 38 60 41
61 44 62 47 63 50 64 53 65 56 66 59 67 62 68 65 69 68 70 171 4 72 7 73 10 74 13 75 16 76 19 77 22 78 25 79 28 80 31
81 34 82 37 83 40 84 43 85 46 86 49 87 52 88 55 89 58 90 61
91 64 92 67 93 70 94 73 95 76 96 79 97 82 98 85 99 88 100 91
意思是,前一个数为约瑟夫环的人数,后一个数为最后出去的人的号码。
从上面的表中我们可以归纳出以下两个规则:
规则1:若上一组数字中最后保留号比人数少一,则下一数从1开始记。
例如第三组(3,2)为上一组,最后保留好为2,比3少1,下一组的数字(4,1),最后保留号为1
规则2:若上一组数字为最后保留号与人数相等,则下一数从2开始记。