数据结构（一）——线性结构

线性结构有很多，今天更第一章链表
约瑟夫环（一）

编号为1，2，…，n的n个人按顺时针方向围坐在一张圆桌周围。给定一个正整数m≤n，从第一个人开始按顺时针方向自1开始报数，每报到m时就让其出列，从他顺时针方向的下一个人开始重新从1报数，数到m的那个人又出列。如此下去，直至圆桌周围的人全部出列为止。每个人的出列次序定义了整数1，2，3，…，n的一个排列。这个排列称为一个（n,m）Josephus排列。例如：（7，3）Josephus排列为3，6，2，7，5，1，4。

思路：创建循环链表——>根据初始间隔寻找节点——>删除节点——>寻找下一节点

#include "stdio.h"
#include "stdlib.h"
typedef struct list{
    int num;
    struct list * pNext;
}List;
List * creat(int n){
    int i;
    List * Head=NULL, * pNew=NULL, * pEnd=NULL;
    Head = (List *)malloc(sizeof(List));
    Head->pNext = NULL;
    Head->num = 0;
    pEnd = Head;
    for(i=1;i<=n;i++){
        pNew = (List *)malloc(sizeof(List));
        pNew->pNext = NULL;
        pNew->num = i;
        pEnd->pNext = pNew;
        pEnd = pNew;
    }
    pNew->pNext = Head->pNext;
    return Head;
}

int main()
{
    List * pHead=NULL ,* pTemp=NULL;
    int i,j,n,m;
    while(scanf("%d %d",&n,&m)!=EOF){
        fflush(stdin);
        j = n;
        pHead = creat(n);
        while(j!=0){
            for(i=0;i<3-1;i++){
                pHead=pHead->pNext;
            }
            pTemp = pHead->pNext;
            if(j==1){
                printf("%d",pTemp->num);
                fflush(stdout);
            }
            else{
                printf("%d ",pTemp->num);   
                fflush(stdout);
            }
            pHead->pNext->pNext = pTemp->pNext;
            pHead->pNext = pTemp->pNext;
            free(pTemp);
            //pHead = pHead->pNext;
            j--;
          }
    }
   return 0;
}

image.png

约瑟夫环（二）

编号为1，2，…，n的n个人按顺时针方向围坐在一张圆桌周围，每人持有一个密码（正整数）。一开始任选一个正整数m作为报数上限值，从第一个人开始按顺时针方向自1开始报数，报到m时停止报数，报m的那个人出列，将他的密码作为新的m值，从他顺时针方向的下一个人开始重新从1报数，数到m的那个人又出列；如此下去，直至圆桌周围的人全部出列为止。要求按出列顺序输出n个人的编号。

思路：创建循环链表——>根据初始密码寻找节点——>获取节点密码——>删除节点——>根据密码寻找下一节点——>循环

#include "stdio.h"
#include "stdlib.h"
typedef struct list{
    int num;
    int pass;
    struct list * pNext;
}List;
List * creat(int n){
    int i;
    List * Head=NULL, * pNew=NULL, * pEnd=NULL;
    Head = (List *)malloc(sizeof(List));
    Head->pNext = NULL;
    Head->num = 0;
    Head->pass = 0;
    pEnd = Head;
    for(i=1;i<=n;i++){
        pNew = (List *)malloc(sizeof(List));
        pNew->pNext = NULL;
        pNew->num = i;
        scanf("%d",&pNew->pass);
        pEnd->pNext = pNew;
        pEnd = pNew;
    }
    pNew->pNext = Head->pNext;
    return Head;
}

int main()
{
    List * pHead=NULL ,* pTemp=NULL;
    int i,j,n,m;
    while(scanf("%d %d",&n,&m)!=EOF){
        j = n;
        pHead = creat(n);
        while(j!=0){
            for(i=0;i<m-1;i++){
                pHead=pHead->pNext;
            }
            pTemp = pHead->pNext;
            m = pTemp->pass;
            printf("%d ",pTemp->num);
            pHead->pNext->pNext = pTemp->pNext;
            pHead->pNext = pTemp->pNext;
            free(pTemp);
            //pHead = pHead->pNext;
            j--;
          }
    }
   return 0;
}

image.png

关注畅校园，下周继续数据结构