您好,登錄后才能下訂單哦!
本文小編為大家詳細介紹“C語言數(shù)據(jù)結(jié)構(gòu)中約瑟夫環(huán)問題如何解決”,內(nèi)容詳細,步驟清晰,細節(jié)處理妥當,希望這篇“C語言數(shù)據(jù)結(jié)構(gòu)中約瑟夫環(huán)問題如何解決”文章能幫助大家解決疑惑,下面跟著小編的思路慢慢深入,一起來學(xué)習(xí)新知識吧。
約瑟夫環(huán)問題的一種描述是:將編號為1,2,...n的n個人按順時針方向圍坐一圈,每人持有一個密碼(正整數(shù))。一開始任選一個正整數(shù)作為報數(shù)上限值m,從第一個人開始按順時針方向自1開始順序報數(shù),報道m(xù)時停止報數(shù)。報m的人出列,將他的密碼作為新的m值,從他在順時針方向上的下一個人開始重新從1報數(shù),如此下去,直至所有人全部出列為止。設(shè)計一個程序求出出列順序。
利用單向循環(huán)鏈表存儲結(jié)構(gòu)模擬此過程,按照出列的順序印出個人的編號。
m的初值為20;n = 7,7個人的密碼依次為:3,1,7,2,4,8,4,首先m值為6(正確的出列順序應(yīng)為6,1,4,7,2,3,5)。
用的是數(shù)組索引。結(jié)合一點點的算法知識。
#include<stdlib.h> #include<stdio.h> //#用數(shù)組索引的模式 int main(){ int m; printf("請輸入m的值:"); scanf("%d",&m); int n; printf("請輸入n的值:"); scanf("%d",&n); int a[100]; for(int i = 0;i<n;i++){ scanf("%d",&a[i]); } int cnt = 0; int cnt1 = 0; int i = 0; while(1){ if (a[i]!=0){ cnt++; if(cnt==m){ m = a[i]; a[i] = 0; cnt = 0; printf("%d ",i+1); cnt1++; } if(cnt1==n){ break; } } i = (++i)%n; } }
利用單項循環(huán)鏈表的方式,上干貨
運用的函數(shù):
創(chuàng)建鏈表
取得鏈表的下標
刪除鏈表指定下標的元素
得到第i個元素值
數(shù)據(jù)結(jié)構(gòu)的定義:
結(jié)構(gòu)體 LNode,成員包括:原始下標,元素值
主函數(shù)的思路:
其中上面的函數(shù)都是參考《數(shù)據(jù)結(jié)構(gòu)(C語言版)》上面。只是將創(chuàng)建鏈表的函數(shù)改成創(chuàng)建單向循環(huán)鏈表的函數(shù)。寫代碼主要時間消耗在主函數(shù)上。
主函數(shù)的思路:
創(chuàng)建一個指定大小(n)的循環(huán)鏈表,每一次循環(huán)得到第m個元素,記錄此元素的下標,然后移動頭結(jié)點到刪除元素前面的結(jié)點,再把此時的頭節(jié)點后面1一個結(jié)點給刪除。依次遍歷到n個。
#include<stdlib.h> #include<stdio.h> //用單項循環(huán)列表的方式 //數(shù)據(jù)類型的定義 typedef struct LNode{ int data; //定義密碼值 int index; //定義數(shù)據(jù)的下標 struct LNode *next; }LNode,*LinkList; int GetElem_L(LinkList L,int i ,int &e){ LNode* p; //注意這里的*號 p = L->next; int j = 1; while(p&&j<i){ p = p->next; ++j; } if(!p || j>i) { return -1; } e = p->data; // printf("%d ",e); return e; }//GetElem_L int GetIndex_L(LinkList L,int i ,int &e){ LNode* p; //注意這里的*號 p = L->next; int j = 1; while(p&&j<i){ p = p->next; ++j; } if(!p || j>i) { return -1; } e = p->index; // printf("%d ",e); return e; }//GetIndex_L int ListDelete_L(LinkList &L,int i,int &e){ LNode* p; //注意這里的*號 p = L; int j = 0; while(p->next&&j<i-1){ p = p->next; ++j; } if(!(p->next)||j>i-1){ return -1; } LNode* q; q = p->next; p->next = q->next; e = q->data; free(q); return e; }//ListDelete_L void CreateList_L(LinkList &L,int n){ L = (LinkList)malloc(sizeof(LNode)); L->next = NULL; LNode* tmp = (LinkList)malloc(sizeof(LNode)); tmp = L; for(int i = 0;i<n-1;++i){ LNode* p = (LinkList)malloc(sizeof(LNode)); scanf("%d",&p->data); p->index = i+1; p->next = tmp->next; tmp->next = p; tmp = tmp->next; } LNode* p = (LinkList)malloc(sizeof(LNode)); //注意這里的*號 scanf("%d",&p->data); p->index = n; p->next = L->next; tmp->next = p; }//創(chuàng)建循環(huán)鏈表 int main(){ int m; int cnt; printf("請輸入m的值:"); scanf("%d",&m); int n; printf("請輸入n的值: "); scanf("%d",&n); LNode* L; //注意這里的*號 CreateList_L(L,n); int e = 0 ; int index = 0; for(int i = 0;i<n;i++){ GetElem_L(L,i+1,e); } for(int i = 0;i<n;i++){ int l = 0; l = GetIndex_L(L,m,index); printf("%d ",l); int tmp = GetElem_L(L,m,e); for(int i = 0;i<m-1;i++){ L = L->next; } ListDelete_L(L,1,e); m = tmp; } }
讀到這里,這篇“C語言數(shù)據(jù)結(jié)構(gòu)中約瑟夫環(huán)問題如何解決”文章已經(jīng)介紹完畢,想要掌握這篇文章的知識點還需要大家自己動手實踐使用過才能領(lǐng)會,如果想了解更多相關(guān)內(nèi)容的文章,歡迎關(guān)注億速云行業(yè)資訊頻道。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。