網(wǎng)站首頁 編程語言 正文
數(shù)據(jù)結(jié)構(gòu)開講啦!!!
本專欄包括:
- 抽象數(shù)據(jù)類型
- 線性表及其應(yīng)用
- 棧和隊(duì)列及其應(yīng)用
- 串及其應(yīng)用
- 數(shù)組和廣義表
- 樹、圖及其應(yīng)用
- 存儲(chǔ)管理、查找和排序
將從簡(jiǎn)單的抽象數(shù)據(jù)類型出發(fā),深入淺出地講解復(fù)數(shù)
到第二講線性表及其應(yīng)用中會(huì)講解,運(yùn)動(dòng)會(huì)分?jǐn)?shù)統(tǒng)計(jì),約瑟夫環(huán),集合的并、交和差運(yùn)算,一元稀疏多項(xiàng)式計(jì)算器
到最后一步一步學(xué)會(huì)利用數(shù)據(jù)結(jié)構(gòu)和算法知識(shí)獨(dú)立完成校園導(dǎo)航咨詢的程序。
希望我們?cè)趯W(xué)習(xí)的過程中一起見證彼此的成長(zhǎng)。
問題描述
約瑟夫環(huán)問題的一種描述是:將編號(hào)為1,2,...n的n個(gè)人按順時(shí)針方向圍坐一圈,每人持有一個(gè)密碼(正整數(shù))。一開始任選一個(gè)正整數(shù)作為報(bào)數(shù)上限值m,從第一個(gè)人開始按順時(shí)針方向自1開始順序報(bào)數(shù),報(bào)道m(xù)時(shí)停止報(bào)數(shù)。報(bào)m的人出列,將他的密碼作為新的m值,從他在順時(shí)針方向上的下一個(gè)人開始重新從1報(bào)數(shù),如此下去,直至所有人全部出列為止。設(shè)計(jì)一個(gè)程序求出出列順序。
基本要求
利用單向循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)模擬此過程,按照出列的順序印出個(gè)人的編號(hào)。
測(cè)試數(shù)據(jù)
m的初值為20;n = 7,7個(gè)人的密碼依次為:3,1,7,2,4,8,4,首先m值為6(正確的出列順序應(yīng)為6,1,4,7,2,3,5)。
實(shí)現(xiàn)思路1
用的是數(shù)組索引。結(jié)合一點(diǎn)點(diǎn)的算法知識(shí)。
#include<stdlib.h>
#include<stdio.h>
//#用數(shù)組索引的模式
int main(){
int m;
printf("請(qǐng)輸入m的值:");
scanf("%d",&m);
int n;
printf("請(qǐng)輸入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;
}
}
實(shí)現(xiàn)思路2
利用單項(xiàng)循環(huán)鏈表的方式,上干貨
運(yùn)用的函數(shù):
- 創(chuàng)建鏈表
- 取得鏈表的下標(biāo)
- 刪除鏈表指定下標(biāo)的元素
- 得到第i個(gè)元素值
數(shù)據(jù)結(jié)構(gòu)的定義:
- 結(jié)構(gòu)體 LNode,成員包括:原始下標(biāo),元素值
- 主函數(shù)的思路:
其中上面的函數(shù)都是參考《數(shù)據(jù)結(jié)構(gòu)(C語言版)》上面。只是將創(chuàng)建鏈表的函數(shù)改成創(chuàng)建單向循環(huán)鏈表的函數(shù)。寫代碼主要時(shí)間消耗在主函數(shù)上。
主函數(shù)的思路:
創(chuàng)建一個(gè)指定大小(n)的循環(huán)鏈表,每一次循環(huán)得到第m個(gè)元素,記錄此元素的下標(biāo),然后移動(dòng)頭結(jié)點(diǎn)到刪除元素前面的結(jié)點(diǎn),再把此時(shí)的頭節(jié)點(diǎn)后面1一個(gè)結(jié)點(diǎn)給刪除。依次遍歷到n個(gè)。
#include<stdlib.h>
#include<stdio.h>
//用單項(xiàng)循環(huán)列表的方式
//數(shù)據(jù)類型的定義
typedef struct LNode{
int data; //定義密碼值
int index; //定義數(shù)據(jù)的下標(biāo)
struct LNode *next;
}LNode,*LinkList;
int GetElem_L(LinkList L,int i ,int &e){
LNode* p; //注意這里的*號(hào)
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; //注意這里的*號(hào)
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; //注意這里的*號(hào)
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)); //注意這里的*號(hào)
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("請(qǐng)輸入m的值:");
scanf("%d",&m);
int n;
printf("請(qǐng)輸入n的值: ");
scanf("%d",&n);
LNode* L; //注意這里的*號(hào)
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;
}
}
結(jié)果
原文鏈接:https://blog.csdn.net/weixin_54201782/article/details/128614354
相關(guān)推薦
- 2022-04-28 Python可視化學(xué)習(xí)之seaborn繪制矩陣圖詳解_python
- 2023-01-29 Python安裝Talib庫(kù)的詳細(xì)圖文教程_python
- 2023-02-27 Golang設(shè)計(jì)模式中抽象工廠模式詳細(xì)講解_Golang
- 2024-07-15 在物理及和虛擬主機(jī)上配置ftp,實(shí)現(xiàn)上傳和下載的功能(five day)
- 2022-10-23 Android?Handler源碼深入探究_Android
- 2022-06-13 ASP.NET?Core依賴注入(DI)講解_實(shí)用技巧
- 2022-07-04 C#操作配置文件app.config、web.config增刪改_C#教程
- 2022-07-23 C語言詳解用char實(shí)現(xiàn)大小寫字母的轉(zhuǎn)換_C 語言
- 最近更新
-
- window11 系統(tǒng)安裝 yarn
- 超詳細(xì)win安裝深度學(xué)習(xí)環(huán)境2025年最新版(
- Linux 中運(yùn)行的top命令 怎么退出?
- MySQL 中decimal 的用法? 存儲(chǔ)小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎(chǔ)操作-- 運(yùn)算符,流程控制 Flo
- 1. Int 和Integer 的區(qū)別,Jav
- spring @retryable不生效的一種
- Spring Security之認(rèn)證信息的處理
- Spring Security之認(rèn)證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權(quán)
- redisson分布式鎖中waittime的設(shè)
- maven:解決release錯(cuò)誤:Artif
- restTemplate使用總結(jié)
- Spring Security之安全異常處理
- MybatisPlus優(yōu)雅實(shí)現(xiàn)加密?
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務(wù)發(fā)現(xiàn)-Nac
- Spring Security之基于HttpR
- Redis 底層數(shù)據(jù)結(jié)構(gòu)-簡(jiǎn)單動(dòng)態(tài)字符串(SD
- arthas操作spring被代理目標(biāo)對(duì)象命令
- Spring中的單例模式應(yīng)用詳解
- 聊聊消息隊(duì)列,發(fā)送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠(yuǎn)程分支