線(xiàn)性結(jié)構(gòu)有很多，今天更第一章鏈表
約瑟夫環(huán)（一）

編號(hào)為1，2，…，n的n個(gè)人按順時(shí)針?lè)较驀谝粡垐A桌周?chē)＝o定一個(gè)正整數(shù)m≤n，從第一個(gè)人開(kāi)始按順時(shí)針?lè)较蜃?開(kāi)始報(bào)數(shù)，每報(bào)到m時(shí)就讓其出列，從他順時(shí)針?lè)较虻南乱粋€(gè)人開(kāi)始重新從1報(bào)數(shù)，數(shù)到m的那個(gè)人又出列。如此下去，直至圓桌周?chē)娜巳砍隽袨橹?。每個(gè)人的出列次序定義了整數(shù)1，2，3，…，n的一個(gè)排列。這個(gè)排列稱(chēng)為一個(gè)（n,m）Josephus排列。例如：（7，3）Josephus排列為3，6，2，7，5，1，4。

思路：創(chuàng)建循環(huán)鏈表——>根據(jù)初始間隔尋找節(jié)點(diǎn)——>刪除節(jié)點(diǎn)——>尋找下一節(jié)點(diǎn)

#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

約瑟夫環(huán)（二）

編號(hào)為1，2，…，n的n個(gè)人按順時(shí)針?lè)较驀谝粡垐A桌周?chē)?，每人持有一個(gè)密碼（正整數(shù)）。一開(kāi)始任選一個(gè)正整數(shù)m作為報(bào)數(shù)上限值，從第一個(gè)人開(kāi)始按順時(shí)針?lè)较蜃?開(kāi)始報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)，報(bào)m的那個(gè)人出列，將他的密碼作為新的m值，從他順時(shí)針?lè)较虻南乱粋€(gè)人開(kāi)始重新從1報(bào)數(shù)，數(shù)到m的那個(gè)人又出列；如此下去，直至圓桌周?chē)娜巳砍隽袨橹?。要求按出列順序輸出n個(gè)人的編號(hào)。

思路：創(chuàng)建循環(huán)鏈表——>根據(jù)初始密碼尋找節(jié)點(diǎn)——>獲取節(jié)點(diǎn)密碼——>刪除節(jié)點(diǎn)——>根據(jù)密碼尋找下一節(jié)點(diǎn)——>循環(huá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

關(guān)注暢校園，下周繼續(xù)數(shù)據(jù)結(jié)構(gòu)