目錄
首先什么是約瑟夫環(huán)
約瑟夫環(huán)實現(xiàn)方式
一、創(chuàng)建結(jié)構(gòu)體變量
二、初始化鏈表
三、構(gòu)建循環(huán)鏈表
四、刪除鏈表
?五、完整代碼及注釋講解
首先什么是約瑟夫環(huán)
約瑟夫環(huán)是循環(huán)鏈表中的一個經(jīng)典問題；題目描述：n?個人圍成一圈，從第一個人開始報數(shù),數(shù)到?m?的人出列，再由下一個人重新從?1?開始報數(shù)，數(shù)到?m?的人再出圈，依次類推，直到所有的人都出圈；
假設(shè)10個人圍成一圈，依次編號1到10，按從小到大順序報數(shù)，報到3的人出局，流程示意圖如下
約瑟夫環(huán)實現(xiàn)方式
我個人傾向于循環(huán)鏈表；
一、創(chuàng)建結(jié)構(gòu)體變量
typedef struct Node{
int data; //數(shù)據(jù)域
struct Node* next; //指針域
}Node;二、初始化鏈表
Node* Create(){
Node* head;
head = (Node*)malloc(sizeof(Node));
if (head == NULL) {
exit(1);
}
head->next = NULL;
return head;
}三、構(gòu)建循環(huán)鏈表
?創(chuàng)建一個臨時結(jié)點tail，將頭結(jié)點head賦予tail，插入新結(jié)點p，讓tail的next指向p，p的next指向head的下一個結(jié)點即結(jié)點p；同時讓tail移到p的位置，為下個結(jié)點插入做準(zhǔn)備；這樣一個循環(huán)鏈表就初步完成了；
代碼塊
Node* Push(Node* head,Node* tail,int 1){
p->data=i;
tail->next =p;
p->next = head->next;
tail = p;
return head;
}
?
?最重要的一件事，每次插入新結(jié)點后，要將tail移動到新結(jié)點位置！
四、刪除鏈表
?文章來源：http://www.zghlxwxcb.cn/news/detail-513554.html
void Print(Node* head){
Node* q=head;
q->next = p->next;
printf("%d ", p->data);
free(p);
p = q->next;
}?五、完整代碼及注釋講解
#include<stdio.h>
#include<stdlib.h>
typedef struct Node{
int data;
struct Node* next;
}Node;
//創(chuàng)建結(jié)構(gòu)體變量
Node* Create(){
Node* head;
head = (Node*)malloc(sizeof(Node));
if (head == NULL) {
exit(1);
}
head->next = NULL;
return head;
}
int main()
{
int n, m,i;
Node * tail, * p, * q;
Node* head=Create();
scanf("%d %d", &n, &m); //輸入n個人圍一圈及報數(shù)m的人出局
//判斷如果插入的數(shù)據(jù)為0或者以報數(shù)0為出局，則結(jié)束操作
if (n == 0 || m == 0) {
return 0;
}
else {
tail = head; //開始沒有數(shù)據(jù)，故尾結(jié)點tail與頭結(jié)點重合
for ( i = 0; i < n; i++) {
p = (Node*)malloc(sizeof(Node)); //插入新結(jié)點需，先申請動態(tài)內(nèi)存
if (p == NULL) { //判斷動態(tài)內(nèi)存是否申請成功
printf("申請失敗!");
exit(1);
}
p->data = i+1; //以下4步為插入新結(jié)點及數(shù)據(jù)的操作，具體分析請看上面構(gòu)建循環(huán)鏈表
tail->next =p;
p->next = head->next;
tail = p;
}
}
p =head->next; //插入完數(shù)據(jù)后，將最后一個結(jié)點的臨時結(jié)點移到第一個數(shù)據(jù)處
q =tail; //然后臨時結(jié)點到尾結(jié)點處
i = 1;
while (p != q) { //首尾結(jié)點是否重合，重合則表示只剩一個數(shù)據(jù)，結(jié)束循環(huán)
if (i == m) { //對報數(shù)m的人進(jìn)行出局操作
q->next = p->next; //以下四步為刪除操作
printf("%d ", p->data);
free(p); //一定記得將刪除鏈表處的內(nèi)存釋放，以免內(nèi)存內(nèi)存泄漏
p = q->next;
i = 1; //刪除后，重新從1開始報數(shù)
}
else { //沒有報數(shù)到m，則p，q結(jié)點都往后移一位
q = p; //先q移到p的位置
p = q->next; //然后p移到q的下一個位置
i++;
}
}
printf("%d", p->data); //打印最后一位出局的人的號數(shù)
return 0;
}有什么不足的地方希望個位大佬在評論區(qū)多多指點！
文章來源地址http://www.zghlxwxcb.cn/news/detail-513554.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)—約瑟夫環(huán)問題(C語言版)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
