c语言约瑟夫环问题链表
链表方法
这是约瑟夫环问题的真实场景。一种是输入n，m，k m，k三个正整数求列的顺序，这个问题采用了典型的循环链表的数据结构，即链表尾元素的指针指向队列头元素。p-link=head
解决问题的核心步骤:
1.建立一个有N个链接点和无头节点的循环链表。
2.确定第一个呼叫者的位置。
3.不断地从链表中删除链接点，直到链表为空。
Void Joseph (int n，int k，int m)//n是总人数，k是第一个开始报数的人，m是出列呼叫的人数。
{
/* p是当前节点R作为辅助节点，指向p的前任节点列表是头节点*/
链表p，r，list
/*创建循环链表*/
for(int i=0，in，I)
{
p =(LinkList)malloc(sizeof(LNode))；
p-data = I；
if(list==NULL)
list = p；
其他
r-link = p；
r = p；
}
plink = list/*循环链表*/
p =列表；/*点P指向头节点*/
/*将当前指针移动到第一个报数的人*/
for(I = 0；ik；我)
{
r = p；
p = p-link；
}
/*循环删除队列节点*/
而(p-link！=p)
{
for(I = 0；im-1；我)
{
r = p；
p = p-link；
}
r-link = p-link；
Printf("删除元素:M "，p-data)；
免费(p)；
p = r-link；
}
printf(" \ n最后删除的元素是:% 4d "，p-data)；
}
如何用C语言写数据结构中的约瑟夫环问题？ 题目:一个圈里有n个人，按顺序编号。从第一个人开始报数(从1到3)，谁报3就退出。
圈圈，问最后一个走的是原号。
1.程序分析:这是一个经典算法——约瑟夫环问题。
2.个人分析:算法经典，这类问题用链表的形式会更容易。约瑟夫环算法
体现了用数组完成链表的功能。虽然形式上完全不同，但是已经解决了。
同样的结果，同样的效果。总之我个人认为是数组中非常经典的算法。我希望这样。
人家写的代码不会让大家骂的！
3.程序源代码:
#包含stdio.h
#定义N 50
#定义S 3
void main()
{
int ac语言链表中约瑟夫环的书写问题 c语言约瑟夫环问题，使用单循环链表，代码如下:
# includes dio . h//使用单一循环链表！！！！！
#includestdlib.h
# includemalloc.h
typedef int ElemType
typedef结构单节点
{
元素类型数据；
struct SingleNode * next
}SLL，*链接列表；
int main()
{
SLL *头，*用途，*温度；
int i，n，m，k，a = 0；
Printf("请输入总人数n:")；
scanf("%d "，n)；
Printf("请输入m:从第m个人开始")；
scanf("%d "，m)；
Printf("数到第k个人，这个人就出列了，请输入k:")；
scanf("%d "，k)；
head = use =(SLL *)malloc(sizeof(SLL))；//建立一个链表，形成一个链表头。
head-data = 1；
for(I = 2；I = n；I )//形成剩余的n-1。
{
use-next =(SLL *)malloc(sizeof(SLL))；
use = use-next；
use-data = I；//第I个设定数I
}
use-next = head；//总理结束，形成一个环。
Printf("人员序号:")；//输出人的序列号。
temp = head
for(I = 0；在；我)
{
printf("%d "，temp-data)；
temp = temp-next；
}
printf(" \ n ")；
for(I = 0；im-1；I)//使用指向第m位的指针，以便从第m位开始计数。
{
use = use-next；
}
Printf("人员出列顺序:")；
while (n) {
for(I = 1；我k；I )//通过k-1。
use = use-next；
temp = use-next；//temp指向第k个
use-next = temp-next；//第k次从环上脱钩
printf("%d "，temp-data)；
免费(临时)；//释放第k个表格元素占用的空间。
n-；
}
printf(" \ n ")；
返回0；
}
单链表实现代码如下:
# includes dio . h//这是一个由单链表构成的约瑟夫环。
#includestdlib.h
# includemalloc.h
typedef int ElemType
typedef结构单节点
{
元素类型数据；
struct SingleNode * next
}SLL，*链接列表；
Voidlist initialize (SLL * *头)//初始化
{
if((* head =(SLL *)malloc(sizeof(SLL)))= = NULL)
出口(1)；
(* head)-next = NULL；
}
Intlist insert (sll * head，int i，elementtype x)//insert
{
SLL *p，* q；
int j；
p =头部；
j =-1；
while(p-next！=NULLji-1)
{
p = p-next；
j；
}
如果(j！=i-1)
{
printf(" I是错的！");
返回0；
}
if((q =(SLL *)malloc(sizeof(SLL)))= = NULL)
出口(1)；
q-data = x；
q-next = p-next；
p-next = q；
返回1；
}
Int list get (sll * head，int i，elemtype * x)//fetch。
{
SLL * p；
int j；
p =头部；
j =-1；
while(p-next！=NULLji)
{
p = p-next；
j；
}
如果(j！=i)
{
printf("错误！");
返回0；
}
* x = p-数据；
返回1；
}
void fu(sll * head，elementtype n，elementtype m，elementtype k)//Joseph删除操作。
{ elem type x；
SLL *p，* s；
p =头部；
int i=0，j=0，b = 0；
而(b！=m-1) //将指针指向第m-1个元素。
{
p = p-next；
b = B1；
}
while(p-next！=空)
{while(我！=k-1)
{ I = I ^ 1；
p = p-next；
if(p = = NULL)p = head-next；//控制循环
}
if(p-next = = NULL)p-next = head-next；//控制循环
s = p-next；//删除第k个元素
x = s-数据；
if(s-next = = NULL)s-next = head-next；//控制循环
p-next = s-next；
printf("%d "，x)；//输出第k个元素
j = j 1；//用于统计总共输出了多少个元素。
免费；
if(j = = n)break；
I = 0；//我清除
}
}
void main()
{
SLL *头；
int x，I，n，m，k，a = 0；
list initialize(head)；//调用初始化函数
Printf("请输入总人数n:")；
scanf("%d "，n)；
Printf("请输入m:从第m个人开始")；
scanf("%d "，m)；
Printf("数到第k个人，这个人就出列了，请输入k:")；
scanf("%d "，k)；
for(I = 0；在；I) //生成该人的序列号。
{ a = a 1；
ListInsert(head，I，a)；
}
Printf("人员序号:")；//输出人的序列号。
for(I = 0；在；我)
{
ListGet(head，I，x)；
printf("%d "，x)；
}
printf(" \ n ")；
Printf("人员出列顺序:")；
月色夫(头，n，m，k)；
printf(" \ n ")；
}
c语言中的约瑟夫环问题 修订版解决了初始m为1的情况。
# includestdio.h
# includemalloc.h
typedef结构节点{
int num
int val
结构节点* next
} listnode
//可以合并两个结构，降低程序复杂度。
typedef listnode * linklist
int main(){
int n，I，b，m，j；
linklist q =(listnode *)malloc(sizeof(listnode))；
q-next = q；//即使只有一个元素，也是循环链表。
listnode * p；
Printf("请输入总人数:")；
scanf("%d "，n)；
p = q；
for(j = 1；j = n；j ){
Printf("请输入学生%d的密码:"，j)；
scanf("%d "，b)；
q-val = b；
q-num = j；
如果(j！=n){
q-next =(listnode *)malloc(sizeof(listnode))；
q = q-next；
}
q-next = p；
}//循环结束后，q-next是链表的头。
printf("last: num-%d val-%d\n "，q-num，q-val)；
Printf("请输入初始值:")；
scanf("%d "，m)；
如果(m=0){
Printf("错误！\ n ")；
返回(1)；
}
m = m-1；//提前停Q，p=q-next，p为目标。
printf(" Result:\ n ")；
Printf("出列顺序为:")；
//以q为起点。
做{
I = 0；//避免M减一后为零的问题。
而(我！=m){
q = q-next；
我；
}
p = q-next；
q-next = p-next；
printf(" %d "，p-num)；
m = p-val；//你错过了这一步。
m = m-1；//提前停Q，p=q-next，p为目标。
免费(p)；
}while(q-next！= q)；
printf(" %d\n "，q-num)；
免费(q)；
//free(头)；//这个时候，head可能已经被free掉了。
getchar()；
getchar()；
return(0)；
}
最后更新于 2023-10-08 05:16:24 并被添加「」标签，已有 位童鞋阅读过。
本站使用「署名 4.0 国际」创作共享协议，可自由转载、引用，但需署名作者且注明文章出处
相关文章