数据结构笔记---循环链表-约瑟夫环问题

数据结构笔记---循环链表-约瑟夫环问题

问题描述

约瑟夫环问题，是一个经典的循环链表问题，题意是：已知 n 个人（分别用编号 1，2，3，…，n 表示）围坐在一张圆桌周围，从编号为 k 的人开始顺时针报数，数到 m 的那个人出列；他的下一个人又从 1 开始，还是顺时针开始报数，数到 m 的那个人又出列；依次重复下去，直到圆桌上剩余一个人 。

假设此时圆周周围有 5 个人，要求从编号为 3 的人开始顺时针数数，数到 2 的那个人出列：

mark

出列顺序依次为：

  • 编号为 3 的人开始数 1，然后 4 数 2，所以 4 先出列；
  • 4 出列后，从 5 开始数 1，1 数 2，所以 1 出列；
  • 1 出列后，从 2 开始数 1，3 数 2，所以 3 出列；
  • 3 出列后，从 5 开始数 1，2 数 2，所以 2 出列；
  • 最后只剩下 5 自己，所以 5 胜出。

循环链表基础

这是个循环链表的典型算法，涉及到循环链表的初始化，查找和删除等操作。

循环链表初始化

mark

node *pHead=NULL;
void IntinalList(node **pNode)                        //尾插法建立链表，指向指针的指针
{
    printf("链表初始化，输入0结束:
");
    int item;
    node *target,*p;
    while(1)
    {
        scanf("%d",&item);
        fflush(stdin);                             //清空缓存
        if(item==0)
            return;                                //判输入是否为0
        if((*pNode)==NULL)                         //如果链表一个节点没有
        {
            (*pNode)=(node *)malloc(sizeof(node)); //开辟一个节点
            if(!(*pNode))
                exit(0);
            (*pNode)->elem=item;
            (*pNode)->next=(*pNode);               //建立单点循环链表
        }
        else
        {
           for(target=(*pNode);target->next!=(*pNode);target=target->next)    //尾插法要找到尾节点
            ;
            p=(node *)malloc(sizeof(node));
            if(!p)  exit(0);
            p->elem=item;
            p->next=(*pNode);
            target->next=p;
        }
    }
}

另外一种方法：（本质上是一样的）

typedef struct node{
    int number;
    struct node * next;
}person;
person * initLink(int n){
    person * head=(person*)malloc(sizeof(person));
    head->number=1;
    head->next=NULL;
    person * cyclic=head;
    for (int i=2; i<=n; i++) {       //i直接从2开始，没有头节点
        person * body=(person*)malloc(sizeof(person));
        body->number=i;
        body->next=NULL; 
        cyclic->next=body;
        cyclic=cyclic->next;
    }
    cyclic->next=head;//首尾相连
    return head;
}

注：这两种方法的实现上略有不同，第一种时来自小甲鱼的源码，它用了一个指向指针的指针做了个参数，这一块当时卡了我半天看不明白，这里简要记录一下：

指向指针的指针也就是二级指针，那么思考什么时候要用到二级指针呢？答案是在一级指针需要修改的时候，这是以及指针的参数传递方式为引用传递。接下来第二个问题，这里的一级指针为什么需要修改呢？这就显而易见了，我们初始化时的node *pHead为NULL，初始化后pHead要指向链表的第一个节点。

第二种是直接把链表首元节点指针作为了返回值，看上去更容易理解一些。

需要注意的是这里初始化循环链表时都没有头节点。

插入操作

/*链表插入,在第i个位置*/

void Insert_List(node **pNode,int i)                        //在第i个位置插入元素，pNode是第一个节点
{
    node *temp,*target;
    int item;
    printf("输入节点的值：
");
    scanf("%d",&item);
    if(i==1)          //插入的节点作为第一个节点，之所以将这种单独讨论，是因为这会因此首元结点的变化
    {
        temp=(node *)malloc(sizeof(node));
        if(!temp)  exit(0);
        for (target=(*pNode);target!=(*pNode);target=target->next)  //找到指向头节点的节点
            ;
        temp->elem=item;
        temp->next=target->next;
        target->next=temp;                              //链如新节点
       (*pNode)= temp;                               //将此节点设为第一个节点
    }
    else
    {
        int j=1;
        target=(*pNode);
        for(;j<(i-1);j++)
            target=target->next;  //找到指向插入位置的节点，找到第i-1个位置
        temp=(node *)malloc(sizeof(node));
        if(!temp)  exit(0);
        temp->elem=item;
        temp->next=target->next;
        target->next=temp;
    }
}

删除

/*链表删除,在第i个位置*/
void delete_list(node **pNode,int i)
{
    int j=1;       //计数变量
    node *target,*temp;
    if(i==1)          //如果删除第一个节点
    {
        for(target=(*pNode);target->next!=(*pNode);target=target->next)  //找到最后一个节点
            ;
        temp=(*pNode)->next;
        target->next=temp;
        free(*pNode);           //释放空间
        (*pNode)=temp;            //将第二个节点作为第一个节点，为什么时刻都要考虑第一个节点的位置呢，因为之后遍历链表时还需要用到第一个节点的位置
    }

    else
    {
        target=(*pNode);
        for(j=1;j<i-1;j++)  //找到第i-1个位置
            target=target->next;
        temp=target->next;
        target->next=temp->next;
        free(temp);
    }
}

遍历

/*遍历*/

void LIst_traver(node *pNode)          //参数为指向结构体的指针
{
   node *temp;
   temp=pNode;
   printf("链表元素为：
");
  do
  {
      printf("%4d",temp->elem);
      temp=temp->next;
  }while(temp!=pNode);
  printf("
");
}

查询位置

/*返回节点位置*/
int Search_list(node *pNode,int elem)    //这里的形参时指向结构体的指针，因为这里不需要对头指针进行变动，所以不用指向指针的指针
{
    node *temp;
    int i=1;           //元素的位置
    temp=pNode;
    while((temp->next)!=pNode&&(temp->elem)!=elem) //跳出循环时要么遍历结束没找到，要么找到了
    {
        temp=temp->next;
        i++;
    }

    if((temp->next)==pNode)  return 0;
    else  return i;
}

c语言实现

//循环链表  实现对循环链表的初始化，创建，插入，删除，输出操作
#include<stdio.h>

#include<stdlib.h>

#define ERROR 0


/*定义节点结构*/
typedef struct CLinkList
{
    int elem;
    struct CLinkList *next;
}node;


/*初始化循环链表*/                                     //这个链表不带头节点

void IntinalList(node **pNode)                        //尾插法建立链表，指向指针的指针
{
    printf("链表初始化，输入0结束:
");
    int item;
    node *target,*p;
    while(1)
    {
        scanf("%d",&item);
        fflush(stdin);                             //清空缓存
        if(item==0)
            return;                                //判输入是否为0
        if((*pNode)==NULL)                         //如果链表一个节点没有
        {
            (*pNode)=(node *)malloc(sizeof(node)); //开辟一个节点
            if(!(*pNode))
                exit(0);
            (*pNode)->elem=item;
            (*pNode)->next=(*pNode);               //建立单点循环链表
        }
        else
        {
           for(target=(*pNode);target->next!=(*pNode);target=target->next)    //尾插法要找到尾节点
            ;
            p=(node *)malloc(sizeof(node));
            if(!p)  exit(0);
            p->elem=item;
            p->next=(*pNode);
            target->next=p;
        }
    }
}

/*链表长度*/
int Length_List(node *pNode)                             //pNode为指向结构体的指针
{
   node *target;
   int j=1;
   target=pNode->next;
   if(target==pNode)  return 1;
   for(target=pNode;target->next!=pNode;target=target->next)
        j++;
   return j;
}


/*链表插入,在第i个位置*/

void Insert_List(node **pNode,int i)                        //在第i个位置插入元素，pNode是第一个节点
{
    node *temp,*target;
    int item;
    printf("输入节点的值：
");
    scanf("%d",&item);
    if(i==1)        //插入的节点作为第一个节点，之所以将这种单独讨论，是因为这会因此首元结点的变化
    {
        temp=(node *)malloc(sizeof(node));
        if(!temp)  exit(0);
        for (target=(*pNode);target!=(*pNode);target=target->next)  //找到指向头节点的节点
            ;
        temp->elem=item;
        temp->next=target->next;
        target->next=temp;                              //链如新节点
       (*pNode)= temp;                               //将此节点设为第一个节点
    }
    else
    {
        int j=1;
        target=(*pNode);
        for(;j<(i-1);j++)
            target=target->next;  //找到指向插入位置的节点，找到第i-1个位置
        temp=(node *)malloc(sizeof(node));
        if(!temp)  exit(0);
        temp->elem=item;
        temp->next=target->next;
        target->next=temp;
    }
}

/*链表删除,在第i个位置*/
void delete_list(node **pNode,int i)
{
    int j=1;       //计数变量
    node *target,*temp;
    if(i==1)          //如果删除第一个节点
    {
        for(target=(*pNode);target->next!=(*pNode);target=target->next)  //找到最后一个节点
            ;
        temp=(*pNode)->next;
        target->next=temp;
        free(*pNode);           //释放空间
        (*pNode)=temp;            //将第二个节点作为第一个节点，为什么时刻都要考虑第一个节点的位置呢，因为之后遍历链表时还需要用到第一个节点的位置
    }

    else
    {
        target=(*pNode);
        for(j=1;j<i-1;j++)
            target=target->next;
        temp=target->next;
        target->next=temp->next;
        free(temp);
    }
}

/*返回节点位置*/
int Search_list(node *pNode,int elem)       //这里的形参时指向结构体的指针，因为这里不需要对头指针进行变动，所以不用指向指针的指针
{
    node *temp;
    int i=1;           //元素的位置
    temp=pNode;
    while((temp->next)!=pNode&&(temp->elem)!=elem) //跳出循环时要么遍历结束没找到，要么找到了
    {
        temp=temp->next;
        i++;
    }

    if((temp->next)==pNode)  return 0;
    else  return i;
}

/*遍历*/

void LIst_traver(node *pNode)          //参数为指向结构体的指针
{
   node *temp;
   temp=pNode;
   printf("链表元素为：
");
  do
  {
      printf("%4d",temp->elem);
      temp=temp->next;
  }while(temp!=pNode);
  printf("
");
}

int main ()
{
    node *pHead=NULL;
    int  num;            //用于条件选择
    int i;
    printf("-------------------------------------------------------

");
    printf("1.初始化链表 

2.插入结点 

3.删除结点 

4.返回结点位置 

5.遍历链表  

0.退出 

6.输出链表长度  

请选择你的操作：");
    do
    {
      scanf("%d",&num);
      switch(num)
      {
        case 1:
            IntinalList(&pHead);    //初始化链表
            printf("
");
            LIst_traver(pHead);
            break;
        case 2:
            printf("输入插入的位置：
");
            scanf("%d",&i);
            Insert_List(&pHead,i);
            printf("在位置%d插入值后：
",  i);
            LIst_traver(pHead);      //遍历输出
            printf("
");
            break;
        case 3:
            printf("输入删除的位置：
");
            scanf("%d",&i);
            delete_list(&pHead,i);
            printf("删除第%d个结点后:
",  i);
            LIst_traver(pHead);      //遍历输出
            printf("
");
            break;
        case 4:
            printf("输入你要查找的数字：
");
            scanf("%d",&i);
            printf("元素%d所在位置：%d
",  i,  Search_list(pHead,i));
            printf("
");
            break;
        case 5:
            LIst_traver(pHead);
            break;
        case 6:
            printf("%d",Length_List(pHead));
            break;
        case 0:
            exit(0);
      }

    }while(num!=0);
    return 0;
}

约瑟夫问题解法

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

typedef struct node{
    int number;
    struct node * next;
}person;

//循环链表初始化（尾插法）
person * initLink(int n){

    printf("输入元素：
");
    int elem;
    person * head=(person*)malloc(sizeof(person));
    scanf("%d",&elem);
    head->number=elem;
    head->next=NULL;
    person * cyclic=head;
    for (int i=2; i<=n; i++) {       //i直接从2开始，没有头节点
        person * body=(person*)malloc(sizeof(person));
        scanf("%d",&elem);
        body->number=elem;
        body->next=NULL;
        cyclic->next=body;
        cyclic=cyclic->next;
    }
    cyclic->next=head;//首尾相连
    return head;
}
//链表遍历
void LIst_traver(person *pNode)          //参数为指向结构体的指针
{
   person *temp;
   temp=pNode;
   //printf("链表元素为：
");
  do
  {
      printf("%4d",temp->number);
      temp=temp->next;
  }while(temp!=pNode);
  printf("
");
}
//与瑟夫问题解决逻辑
void  yuesefu(person *p,int n){
    int m;

    printf("请输入删除的人数间隔：
");
    scanf("%d",&m);
 //判断删除间隔是否为1
    if (m==1){
        printf("相当于遍历链表：
");
        //遍历链表逻辑
        LIst_traver(p);
    }else{

    person *target,*head;
    head=p;
    while(n>=m){

    //寻找第m-1个数的位置
    int j=1;
    for(target=head;j<m-1;target=target->next){
        j++;
    }

    person *t=target->next;
    printf("%d
",t->number);
    target->next=target->next->next;  //删除m个节点
    free(t);

    head=target->next;   //更换头节点
    n--;
    }

    //输出剩余m-1个节点
    LIst_traver(head);

    }
}

int main(){
    int n;
    person *p=NULL;
    printf("--------开始初始化循环链表-------
");
    printf("请输入链表长度
");
    scanf("%d",&n);
    p=initLink(n);

    //调用约瑟夫实现函数

    yuesefu(p,n);
}

核心代码的算法逻辑：

  1. 从第头节点开始属，找到第m个节点并删除
  2. 更换头节点，从新的头节点开始，重复第一步
  3. 当剩余链表长度小于m时，遍历输出剩余节点
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/wind-zhou/p/12931041.html