图片 6

C语言编程丨循环链表实现约瑟夫杯,循环链表和约瑟夫环

NO.1 约瑟夫环问题

图片 1

循环链表的实现

单链表只有向后结点,当单链表的尾链表不指向NULL,而是指向头结点时候,形成了一个环,成为单循环链表,简称循环链表。当它是空表,向后结点就只想了自己,这也是它与单链表的主要差异,判断node->next是否等于head。

代码实现分为四部分:

  1. 初始化
  2. 插入
  3. 删除
  4. 定位寻找

代码实现:

void ListInit(Node *pNode){
    int item;
    Node *temp,*target;
    cout<<"输入0完成初始化"<<endl;

    while(1){
        cin>>item;
        if(!item)
            return ;
        if(!(pNode)){ //当空表的时候,head==NULL 
            pNode = new Node ;
            if(!(pNode))
                exit(0);//未成功申请 
            pNode->data = item;
            pNode->next = pNode;
        }
        else{
            //
            for(target = pNode;target->next!=pNode;target = target->next)
                ;
            temp = new Node;
            if(!(temp))
                exit(0);
            temp->data = item;
            temp->next = pNode;
            target->next = temp;
        }
    }
} 
void ListInsert(Node *pNode,int i){ //参数是首节点和插入位置 
    Node *temp;
    Node *target;
    int item;
    cout<<"输入您要插入的值:"<<endl;
    cin>>item;
    if(i==1){
        temp = new Node;
        if(!temp)
            exit(0);
        temp->data = item;
        for(target=pNode;target->next != pNode;target = target->next)
        ;
        temp->next = pNode;
        target->next = temp;
        pNode = temp;
    }
    else{
        target = pNode;
        for (int j=1;j<i-1;++j)
            target = target->next;
        temp = new Node;
        if(!temp)
            exit(0);
        temp->data = item;
        temp->next = target->next;
        target->next = temp;
    }
}
void ListDelete(Node *pNode,int i){
    Node *target,*temp;
    if(i==1){
        for(target=pNode;target->next!=pNode;target=target->next)
        ;
        temp = pNode;//保存一下要删除的首节点 ,一会便于释放 
        pNode = pNode->next;
        target->next = pNode;
        delete temp; 
    }
    else{
        target = pNode;
        for(int j=1;j<i-1;++j)
            target = target->next;
        temp = target->next;//要释放的node
        target->next = target->next->next;
        delete temp; 
    }
}
int ListSearch(Node *pNode,int elem){ //查询并返回结点所在的位置 
    Node *target;
    int i=1;
    for(target = pNode;target->data!=elem && target->next!= pNode;++i)
        target = target->next;
    if(target->next == pNode && target->data!=elem)
        return 0;
    else return i;
}

采用单向循环表的数据结构,即将链表的尾元素的指针指向链首元素。每个结点除了指针域外,还有两个域分别存放
id 和 password 。

把链表的两头连接,使其成为了一个环状链表,通常称为循环链表。

约瑟夫问题

约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1,2,3…n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。这类问题用循环列表的思想刚好能解决。

注意:编写代码的时候,注意报数为m = 1的时候特殊情况

#include<iostream>
#include<cstdio>
using namespace std;
typedef struct Node{
    int data;
    Node *next;
};

Node *Create(int n){
    Node *p = NULL, *head;
    head = new Node;
    if (!head)
        exit(0);
    p = head; // p是当前指针 
    int item=1;
    if(n){
        int i=1;
        Node *temp;
        while(i<=n){
            temp = new Node;
            if(!temp)
                exit(0);
            temp->data = i++;
            p->next = temp;
            p = temp; 
        }
        p->next = head->next;
    }
    delete head;
    return p->next;
}
void Joseph(int n,int m){
    //n为总人数,m为数到第m个的退出
    m = n%m;

    Node *start = Create(n);

    if(m){//如果取余数后的m!=0,说明 m!=1 
        while(start->next!=start){
            Node *temp = new Node;
            if(!temp)
                exit(0);
            for(int i=0;i<m-1;i++) // m = 3%2 = 1
                start = start->next;
            temp = start->next;
            start->next = start->next->next;
            start = start->next;
            cout<<temp->data<<" ";
            delete temp;
        }
    }
    else{
        for(int i=0;i<n-1;i++){
            Node *temp = new Node;
            if(!temp)
                exit(0);    
            cout<<start->data<<" ";
            temp = start;
            start = start->next;
            delete temp;
        }
    }
    cout<<endl;
    cout<<"The last person is:"<<start->data<<endl;
}
int main(){
    Joseph(3,1);
    Joseph(3,2);
    return 0;
}

图片 2

和它名字的表意一样,只需要将表中最后一个结点的指针指向头结点,链表就能成环儿,如图
1 所示。

约瑟夫环是一个数学的应用问题:

图片 3图1
循环链表

已知n个人(以编号1,2,3…n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1,最后[1]结果+1即为原问题的解。

需要注意的是,虽然循环链表成环状,但本质上还是链表,因此在循环链表中,依然能够找到头指针和首元节点等。循环链表和普通链表相比,唯一的不同就是循环链表首尾相连,其他都完全一样。

解决问题的基本步骤:

循环链表实现约瑟夫环

建立n个结点的单向循环链表;

图片 4

从链表第一个结点起循环计数寻找第m个结点;

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

输出该结点的id值;

如图 2 所示,假设此时圆周周围有 5 个人,要求从编号为 3
的人开始顺时针数数,数到 2 的那个人出列:

根据m值不断从链表中删除结点,直到链表为空。

图片 5
2 循环链表实现约瑟夫环

  1 #include<stdio.h>  2 #include<stdlib.h>  3 #define MAX 100  4   5 typedef struct NodeType        //自定义结构体类型  6 {  7     int id;  8     int password;  9     struct NodeType *next;        //用于指向下一个结点的指针 10 }NodeType; 11  12 void CreatList(NodeType **, int);    //创建单向循环链表 13 NodeType *GetNode(int, int);        //得到一个结点 14 void PrintList(NodeType *);            //打印循环链表 15 int IsEmptyList(NodeType *);        //判空 16 void JosephusOperate(NodeType **, int);        //运行环求解 17  18 int main(void) 19 { 20     int n = 0; 21     int m = 0; 22     NodeType *pHead = NULL; 23     do 24     { 25         if (n>MAX) 26         { 27             printf("人数太多,请重新输入!\n"); 28         } 29         printf("请输入人数n:", MAX); 30         scanf("%d", &n); 31     } while (n>MAX); 32     printf("请输入初始密码m:"); 33     scanf("%d", &m); 34     CreatList(&pHead, n);        //创建单向循环链表 35     printf("\n----------打印循环链表---------\n"); 36     PrintList;        //打印链表 37     printf("\n----------打印出队情况---------\n"); 38     JosephusOperate(&pHead, m);        //运行 39     return 1; 40 } 41  42 void CreatList(NodeType **ppHead, int n)        //创建有n个结点的循环链表pphead  43 { 44     int i = 0; 45     int iPassword = 0; 46     NodeType *pNew = NULL; 47     NodeType *pCur = NULL; 48     for (i = 1; i <= n; i++) 49     { 50         printf("输入第%d个人的密码:",i); 51         scanf("%d", &iPassword); 52         pNew = GetNode(i, iPassword); 53         if (*ppHead == NULL) 54         { 55             *ppHead = pCur = pNew; 56             pCur->next = *ppHead; 57         } 58         else 59         { 60             pNew->next = pCur->next; 61             pCur->next = pNew; 62             pCur = pNew; 63         } 64     } 65     printf("完成单向循环链表的创建!\n"); 66 } 67  68 NodeType *GetNode(int iId, int iPassword) 69 { 70     NodeType *pNew = NULL; 71     pNew = (NodeType *)malloc(sizeof); 72     if (!pNew) 73     { 74         printf("Error, the memory is not enough!\n"); 75         exit(-1); 76     } 77     pNew->id = iId; 78     pNew->password = iPassword; 79     pNew->next = NULL; 80     return pNew; 81 } 82  83 void PrintList(NodeType *pHead) 84 { 85     NodeType *pCur = pHead; 86     if (!IsEmptyList 87     { 88         printf("--ID-- --PASSWORD--\n"); 89         do 90         { 91             printf("%3d %7d\n", pCur->id, pCur->password); 92             pCur = pCur->next; 93         } while (pCur!=pHead); 94     } 95 } 96  97 int IsEmptyList(NodeType *pHead) 98 { 99     if (!pHead)100     {101         printf("The list is empty!\n");102         return 1;103     }104     return 0;105 }106 107 void JosephusOperate(NodeType **ppHead, int iPassword)108 {109     int iCounter = 0;110     int iFlag = 1;111     NodeType *pCur = NULL;112     NodeType *pPrv = NULL;113     NodeType *pDel = NULL;114     pPrv = pCur = *ppHead;115     while (pPrv->next != *ppHead)116     {117         pPrv = pPrv->next;118     }119     while 120     {121         for (iCounter = 1; iCounter < iPassword; iCounter++)122         {123             pPrv = pCur;124             pCur = pCur->next;125         }126         if (pPrv==pCur)127         {128             iFlag = 0;129         }130         pDel = pCur;131         pPrv->next = pCur->next;132         pCur = pCur->next;133         iPassword = pDel->password;134         printf("第%d个人出列\n", pDel->id, pDel->password);135         free;136     }137     *ppHead = NULL;138     getchar();139 }

出列顺序依次为:

2.一元多项式加减计算

编号为 3 的人开始数 1,然后 4 数 2,所以 4 先出列;

  1 #include<stdio.h>  2 #include<malloc.h>  3   4 typedef struct Polynomail  5 {  6     float coef;  7     int expn;  8     struct Polynomail *next;  9 }Polyn; 10  11 Polyn *creatPoly(void); 12 void printPoly(Polyn *P); 13 Polyn *addPoly(Polyn *pa, Polyn *pb); 14 Polyn *subtractPoly(Polyn *pa, Polyn *pb); 15  16 Polyn *subtractPoly(Polyn *pa, Polyn *pb) 17 { 18     Polyn *h = pb; 19     Polyn *p = pb->next; 20     Polyn *pd; 21     while  22     { 23         p->coef *= -1; 24         p = p->next; 25     } 26     pd = addPoly; 27     for (p = h->next; p; p = p->next) 28         p->coef *= -1; 29     return pd; 30 } 31  32 Polyn *addPoly(Polyn *pa, Polyn *pb) 33 { 34     Polyn *qa = pa->next; 35     Polyn *qb = pb->next; 36     Polyn *headc, *pc, *qc; 37  38     pc = malloc(sizeof; 39     pc->next = NULL; 40     headc = pc; 41     while (qa != NULL && qb != NULL) 42     { 43         qc = malloc(sizeof; 44         if (qa->expn < qb->expn) 45         { 46             qc->coef = qa->coef; 47             qc->expn = qa->expn; 48             qa = qa->next; 49         } 50         else if (qa->expn == qb->expn) 51         { 52             qc->coef = qa->coef + qb->coef; 53             qc->expn = qa->expn; 54             qa = qa->next; 55             qb = qb->next; 56         } 57         else 58         { 59             qc->coef = qb->coef; 60             qc->expn = qb->expn; 61             qb = qb->next; 62         } 63         if (qc->coef != 0) 64         { 65             qc->next = pc->next; 66             pc->next = qc; 67             pc = qc; 68         } 69         else 70             free; 71     } 72     while (qa != NULL) 73     { 74         qc = malloc(sizeof; 75         qc->coef = qa->coef; 76         qc->expn = qa->expn; 77         qa = qa->next; 78         qc->next = pc->next; 79         pc->next = qc; 80         pc = qc; 81     } 82     while (qb != NULL) 83     { 84         qc = malloc(sizeof; 85         qc->coef = qb->coef; 86         qc->expn = qb->expn; 87         qb = qb->next; 88         qc->next = pc->next; 89         pc->next = qc; 90         pc = qc; 91     } 92     return headc; 93 } 94  95 void printPoly(Polyn *P) 96 { 97     Polyn *q = P->next; 98     int flag = 1; 99     if (!q)100     {101         putchar('0');102         printf("\n");103         return;104     }105     while 106     {107         if (q->coef > 0 && flag != 1)108             putchar('+');109         if (q->coef != 1 && q->coef != -1)110         {111             printf("%g", q->coef);112             if (q->expn == 1)113                 putchar('X');114             else if (q->expn)115                 printf("X^%d", q->expn);116         }117         else118         {119             if (q->coef == 1)120             {121                 if (!q->expn)122                     putchar('1');123                 else if (q->expn == 1)124                     putchar('X');125                 else126                     printf("X^%d", q->expn);127             }128             if (q->coef == -1)129             {130                 if (!q->expn)131                     printf("-1");132                 else if (q->expn == 1)133                     printf("-X");134                 else135                     printf("-X^%d", q->expn);136             }137         }138         q = q->next;139         flag++;140     }141     printf("\n");142 }143 144 Polyn *creatPoly(void)    //建立 145 {146     Polyn *head, *rear, *s;147     int c, e;148 149     head = malloc(sizeof;150     rear = head;151     printf("请输入多项式的系数和指数项");152     scanf("%d%d", &c, &e);153     while (c != 0)154     {155         s = malloc(sizeof;156         s->coef = c;157         s->expn = e;158         rear->next = s;159         rear = s;160         printf("请继续输入多项式的系数和指数项");161         scanf("%d%d", &c, &e);162     }163     rear->next = NULL;164     return head;165 }166 167 int main(void)168 {169     Polyn *p1, *p2, *p3, *p4;170 171     printf("多项式1:\n");172     p1 = creatPoly();173     printf("多项式2:\n");174     p2 = creatPoly();175     printf("您输入的多项式如下所示:\n");176     printPoly;177     printPoly;178     p3 = addPoly;179     p4 = subtractPoly;180     printf("多项式相加后的结果如下:\n");181     printPoly;182     printf("多项式相减后的结果如下:\n");183     printPoly;184 }

4 出列后,从 5 开始数 1,1 数 2,所以 1 出列;

1 出列后,从 2 开始数 1,3 数 2,所以 3 出列;

3 出列后,从 5 开始数 1,2 数 2,所以 2 出列;

最后只剩下 5 自己,所以 5 胜出。

约瑟夫环问题有多种变形,比如顺时针转改为逆时针等,虽然问题的细节有多种变数,但解决问题的中心思想是一样的,即使用循环链表。

通过以上的分析,我们可以尝试编写 C 语言代码,完整代码如下所示:

#include

#include

typedef struct node{

int number;

struct node * next;

}person;

person * initLink{

person * head=malloc(sizeof;

head->number=1;

head->next=NULL;

person * cyclic=head;

for (int i=2; i<=n; i++) {

person * body=malloc(sizeof;

body->number=i;

body->next=NULL;

cyclic->next=body;

cyclic=cyclic->next;

}

cyclic->next=head;//首尾相连

return head;

}

void findAndKillK(person * head,int k,int m){

person * tail=head;

//找到链表第一个结点的上一个结点,为删除操作做准备

while (tail->next!=head) {

tail=tail->next;

}

person * p=head;

//找到编号为k的人

while (p->number!=k) {

tail=p;

p=p->next;

}

//从编号为k的人开始,只有符合p->next==p时,说明链表中除了p结点,所有编号都出列了,

while (p->next!=p) {

//找到从p报数1开始,报m的人,并且还要知道数m-1de人的位置tail,方便做删除操作。

for (int i=1; i

tail=p;

p=p->next;

}

tail->next=p->next;//从链表上将p结点摘下来

printf(“出列人的编号为:%d\n”,p->number);

free;

p=tail->next;//继续使用p指针指向出列编号的下一个编号,游戏继续

}

printf(“出列人的编号为:%d\n”,p->number);

free;

}

int main() {

printf(“输入圆桌上的人数n:”);

int n;

scanf(“%d”,&n);

person * head=initLink;

printf(“从第k人开始报数(k>1且k<%d):”,n);

int k;

scanf(“%d”,&k);

printf(“数到m的人出列:”);

int m;

scanf(“%d”,&m);

findAndKillK(head, k, m);

return 0;

}.

图片 6有兴趣的可以加上我们交流群一起学习哦!