日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

C語言數據結構中約瑟夫環問題探究_C 語言

作者：Li&&Tao ? 更新時間： 2023-03-02 編程語言

數據結構開講啦！！！

本專欄包括：

  • 抽象數據類型
  • 線性表及其應用
  • 棧和隊列及其應用
  • 串及其應用
  • 數組和廣義表
  • 樹、圖及其應用
  • 存儲管理、查找和排序

將從簡單的抽象數據類型出發，深入淺出地講解復數

到第二講線性表及其應用中會講解，運動會分數統計，約瑟夫環，集合的并、交和差運算，一元稀疏多項式計算器

到最后一步一步學會利用數據結構和算法知識獨立完成校園導航咨詢的程序。

希望我們在學習的過程中一起見證彼此的成長。

問題描述

約瑟夫環問題的一種描述是：將編號為1，2，...n的n個人按順時針方向圍坐一圈，每人持有一個密碼（正整數）。一開始任選一個正整數作為報數上限值m,從第一個人開始按順時針方向自1開始順序報數，報道m時停止報數。報m的人出列，將他的密碼作為新的m值，從他在順時針方向上的下一個人開始重新從1報數，如此下去，直至所有人全部出列為止。設計一個程序求出出列順序。

基本要求

利用單向循環鏈表存儲結構模擬此過程，按照出列的順序印出個人的編號。

測試數據

m的初值為20；n = 7,7個人的密碼依次為：3，1，7，2，4，8，4，首先m值為6（正確的出列順序應為6，1，4，7，2，3，5）。

實現思路1

用的是數組索引。結合一點點的算法知識。

#include<stdlib.h>
#include<stdio.h>
//#用數組索引的模式 
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;
	} 
}

實現思路2

利用單項循環鏈表的方式，上干貨

運用的函數：

  • 創建鏈表
  • 取得鏈表的下標
  • 刪除鏈表指定下標的元素
  • 得到第i個元素值

數據結構的定義：

  • 結構體 LNode，成員包括：原始下標，元素值
  • 主函數的思路：

其中上面的函數都是參考《數據結構（C語言版）》上面。只是將創建鏈表的函數改成創建單向循環鏈表的函數。寫代碼主要時間消耗在主函數上。

主函數的思路：

創建一個指定大小（n）的循環鏈表，每一次循環得到第m個元素，記錄此元素的下標，然后移動頭結點到刪除元素前面的結點，再把此時的頭節點后面1一個結點給刪除。依次遍歷到n個。

#include<stdlib.h>
#include<stdio.h>
//用單項循環列表的方式 
//數據類型的定義 
typedef struct LNode{
	int data;		//定義密碼值 
	int index; 		//定義數據的下標 
	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;
}//創建循環鏈表 
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;
	}
}

結果

原文鏈接：https://blog.csdn.net/weixin_54201782/article/details/128614354

欄目分類
最近更新