Question

c语言链表写约瑟夫环问题

Answer 1

C语言的约瑟夫环问题，利用单循环链表，代码如下：

#include<stdio.h>  //利用单循环链表！！！！！
#include<stdlib.h>
#include<malloc.h>
typedef int ElemType;
typedef struct SingleNode
{
 ElemType data;
 struct SingleNode *next;
}SLL,*LinkList;
int main()
{
 SLL *head ,*use,*temp;
 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;i<n;i++)
 {
  printf("%d ",temp->data);
  temp=temp->next;
 }
 printf("\n");
  
 for(i=0;i<m-1;i++)//use指向第m-1个，为了从m位开始数
 {
  use=use->next;
 }
printf("人员出列顺序为：");
while (n) {
 for (i = 1; i < k; i++)//掠过k－1个
  use = use->next;
 temp = use->next;//temp指向第k个
 use->next = temp->next;//第k个从环中脱钩
 printf("%d ", temp->data);
 free(temp);//释放第k个表元占用的空间
 n--;
}
printf("\n");
 return 0;
}

 

单链表实现代码如下：

#include<stdio.h>  //这是使用单链表做的约瑟夫环
#include<stdlib.h>
#include<malloc.h>
typedef int ElemType;
typedef struct SingleNode
{
ElemType data;
struct SingleNode *next;
}SLL,*LinkList;
void ListInitialize(SLL **head)   //初始化
{
if ((*head=(SLL *)malloc(sizeof(SLL)))==NULL)
exit(1);
(*head)->next=NULL;
}
int ListInsert(SLL *head,int i,ElemType x)  //插入
{
SLL *p,*q;
int j;
p=head;
j=-1;
while(p->next!=NULL&&j<i-1)
{
p=p->next;
j++;
}
if(j!=i-1)
{
printf("the i is wrong!");
return 0;
}
if((q=(SLL *)malloc(sizeof(SLL)))==NULL)
exit(1);
q->data=x;
q->next=p->next;
p->next=q;
return 1;
}
int ListGet(SLL *head,int i,ElemType *x)   //取
{
SLL *p;
int j;
p=head;
j=-1;
while(p->next!=NULL&&j<i)
{
p=p->next;
j++;
}
    if(j!=i)
{
printf("ERROR!");
return 0;
}
  *x=p->data;
return 1;
}
void yuesefu(SLL *head, ElemType n,ElemType m,ElemType k)  //约瑟夫删除操作
{ElemType x;
SLL *p,*s;
    p=head;
int i=0,j=0,b=0;
while(b!=m-1)  //将指针指到第m-1个元素
{
p=p->next;
b=b+1;
}
while(p->next!=NULL)  
{while(i!=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->data;
        if(s->next==NULL)  s->next=head->next;  //控制循环  
p->next=s->next;
printf("%d ",x);  //输出第k个元素
j=j+1;   //用以统计总共输出了多少个元素
free(s);
if(j==n) break;
i=0;   //i清零
}
}
void main()
{
SLL *head;
int x,i,n,m,k,a=0;
ListInitialize(&head); //调用初始化函数
printf("请输入总人数n："); 
scanf("%d",&n);
    
printf("从第m个人开始数起，请输入m:"); 
scanf("%d",&m);
    
printf("数到第k个人，该人出列，请输入k:"); 
scanf("%d",&k);
for(i=0;i<n;i++)   //生成人员的序号
{   a=a+1;
ListInsert(head,i,a);
}
printf("人员序号为：");  //输出人员的序号
for(i=0;i<n;i++)
{
ListGet(head,i,&x);
printf("%d ",x);
}
printf("\n");
printf("人员出列顺序为：");
    yuesefu(head,n,m,k);
printf("\n");
}

Answer 2

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

typedef struct node//节点存放一个数据和指向下一个节点的指针
{
int data;
struct node* pnext;
} Node;

Node *link_create(int n)//创建n个节点的循环链表
{
//先创建第1个节点
Node *p,*q,*head;
int i ;
p = (Node *)malloc(sizeof(Node));
head = p;
p->data = 1;

for(i = 2;i<=n;i++)//再创建剩余节点
{
q = (Node *)malloc(sizeof(Node));
q->data = i;
p->pnext = q;
p = q;
}
p->pnext = head;//最后一个节点指向头部，形成循环链表
return head;
}

void link_process(Node *head,int k,int m)//从编号为k(1<=k<=n)的人开始报数，数到m的那个人出列；
{
int i;
Node *p = head,*tmp1;
while(p->data != k)//p指向的节点data为k
p = p->pnext;

while(p->pnext != p)
{
for(i=0;i<m;i++)
{
tmp1 = p;
p = p->pnext;
}
printf("%d ",p->data);
tmp1->pnext= p->pnext;
free(p);
p = tmp1->pnext;

}
printf("%d ",p->data);
free(p);
}

int main()
{

Node *head = link_create(5);
link_process(head,3,1);
system("pause");
return 0;
}
有点长，但是应该看得懂，
循环链表的。