數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-5

1/1數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)>

課

程

設(shè)

計(jì)

班級(jí):111004

姓名:董麗美

學(xué)號(hào):111004122

指導(dǎo)老師:史延新

完成日期:2023_07_10

題目一:約瑟夫環(huán)問題

【問題描述】約瑟夫（Joseph）問題的一種描述是：編號(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時(shí)停止報(bào)數(shù)。報(bào)m的人出列，將他的密碼作為新的m值，從他在順時(shí)針方向上的下一個(gè)人開頭重新從1報(bào)數(shù)，如此下去，直至全部人全部出列為止。試設(shè)計(jì)一個(gè)程序求出列挨次?！净疽蟆坷脝蜗蜓h(huán)鏈表存儲(chǔ)結(jié)構(gòu)模擬此過程，根據(jù)出列的挨次打印出各人的編號(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）

一.需求分析

1．用單循環(huán)鏈表存儲(chǔ)并遍歷及刪除節(jié)點(diǎn)的方法，計(jì)算并輸出約瑟夫環(huán)的問題。

2．環(huán)中總?cè)藬?shù)和節(jié)點(diǎn)信息由用戶輸入，且均為正整數(shù)。3．在窗口界面輸出出列挨次的編號(hào)。

二．概要設(shè)計(jì)

1.設(shè)定鏈表的抽象數(shù)據(jù)類型定義：

ADTList{

數(shù)據(jù)對(duì)象：D={a(i)|a(i)∝Elemset,i=1,2,…,n,n>=0}

數(shù)據(jù)關(guān)系：R1={|a(i-1),a(i)∝D,i=2,…,n}基本操作：

InitList(&L)

操作結(jié)果：構(gòu)造一個(gè)空的線性表

ListInsert(&L,i,e)

初始條件：線性表L已經(jīng)存在。

操作結(jié)果：在L中第i個(gè)位置之前插入新的數(shù)據(jù)元素e,L的長度增加1。

ListDelete(&L,i,&e)

初始條件：線性表L已經(jīng)存在且非空，1

#include

typedefstructNODE

{

intcode;

intnum;

NODE*pnext;

}NODE;

typedefstructCIRCLE_LINK

{

NODE*front;

NODE*rear;

}CIRCLE_LINK;

boolinit_circle_link(CIRCLE_LINK**link){

*link=(CIRCLE_LINK*)malloc(sizeof(CIRCLE_LINK));

if(NULL==*link)

{

returnfalse;

}

(*link)->front=NULL;

(*link)->rear=NULL;

returntrue;

}

boolinsert_circle_link_end(CIRCLE_LINK*link,intcode,intnum)

{

NODE*curt=NULL;

curt=(NODE*)malloc(sizeof(NODE));

if(NULL==curt)

{

returnfalse;

}

curt->num=num;

curt->code=code;

if(NULL==link->front)

{

link->front=curt;

link->rear=link->front;

link->rear->pnext=link->front;

}

else

{

curt->pnext=link->rear->pnext;

link->rear->pnext=curt;

link->rear=curt;

}

returntrue;

}

voiddelete_node(CIRCLE_LINK*link,NODE*pcurt){

NODE*ptem=link->front;

NODE*prear=link->rear;

while(true)

{

if(link->front==link->rear

link->rear=NULL;

break;

}

if(link->front==pcurt)//刪除頭結(jié)點(diǎn)

{

link->front=link->front->pnext;

link->rear->pnext=link->front;

free(pcurt);

pcurt=NULL;

break;

}

ptem=ptem->pnext;

if(ptem->pnext==pcurt

link->rear=ptem;

free(pcurt);

pcurt=NULL;

break;

}

if(ptem->pnext==pcurt)//刪除中間節(jié)點(diǎn)

{

ptem->pnext=pcurt->pnext;

free(pcurt);

pcurt=NULL;

break;

}

}

}

voidfind_key(CIRCLE_LINK*link,intkey){

NODE*pcurt=link->front;

NODE*ptem=NULL;

inti=1;

printf("輸出序列為:\n");

while(link->front!=NULL)

{

for(;ipnext;

}

i=1;

printf("%d\n",pcurt->num);

key=pcurt->code;

ptem=pcurt;

pcurt=pcurt->pnext;

delete_node(link,ptem);

}

}

intmain(intargc,char*argv){

inti=0;

intn=0;

intnum=1;

intcode=0;

intkey=0;

CIRCLE_LINK*link=NULL;

init_circle_link(

printf("請(qǐng)輸入總?cè)藬?shù):");

scanf("%d",

getchar;

for(i=0;ivertex=to;//建立頂點(diǎn)內(nèi)容

newnode->nextnode=NULL;//設(shè)定指標(biāo)初值

ptr=//頂點(diǎn)位置

while(ptr->nextnode!=NULL)//遍歷至鏈表尾ptr=ptr->nextnode;//下一個(gè)頂點(diǎn)

ptr->nextnode=newnode;//插入結(jié)尾

}

}

4、初始化頂點(diǎn)坐標(biāo)

數(shù)組名稱：intnode[60][2]

數(shù)組功能：此為頂點(diǎn)坐標(biāo)，主要用來讀取存儲(chǔ)在文件中的各個(gè)頂點(diǎn)坐標(biāo)信息

詳細(xì)代碼：

intnode[60][2]={{1,10},{10,1},{2,10},{10,2},{2,3},{3,2},{3,4},{4,3},

{3,12},{12,3},{4,13},{13,4},{4,5},{5,4},{5,6},{6,5},{5,7},{7,5},

{7,8},{8,7},{9,10},{10,9},{10,11},{11,10},{11,14},{14,11},

{11,12},{12,11},{12,15},{15,12},{12,13},{13,12},{13,16},{16,13},

{14,17},{17,14},{14,18},{18,14},{15,19},{19,15},{16,20},{20,16},

{17,18},{18,17},{18,23},{23,18},{18,19},{19,18},{19,23},{23,19},

{19,24},{24,19},{19,20},{20,19},{20,21},{21,20},{22,23},{23,22},

{24,25},{25,24}};

源程序代碼：

#include"stdafx.h"

#include

#include

#include

#include

#include

#include

#defineMAXQUEUE70//最大頂點(diǎn)個(gè)數(shù)

structnode

{intvertex;//輸入頂點(diǎn)

structnode*nextnode;//指向下一節(jié)點(diǎn)

};

typedefstructnode*graph;//圖形的結(jié)構(gòu)新形態(tài)

structnodehead[61];//圖形頂點(diǎn)結(jié)構(gòu)數(shù)組

intvisited[61];//遍歷記錄數(shù)組

intqueue[MAXQUEUE];//佇列的最大容量

intfront=-1;//佇列的前端

intrear=-1;//佇列的后端

voidcreategraph(int*node,intnum)

{

graphnewnode;//新頂點(diǎn)指標(biāo)

graphptr;

intfrom;//邊線的起點(diǎn)

intto;//邊線的終點(diǎn)

inti;

for(i=0;ivertex=to;//建立頂點(diǎn)內(nèi)容

newnode->nextnode=NULL;//設(shè)定指標(biāo)初值

ptr=//頂點(diǎn)位置

while(ptr->nextnode!=NULL)//遍歷至鏈表尾ptr=ptr->nextnode;//下一個(gè)頂點(diǎn)

ptr->nextnode=newnode;//插入結(jié)尾

}

}

intenqueue(intvalue)

{

if(rear>=MAXQUEUE)//檢查佇列是否全滿

return-1;//無法存入

rear++;//后端指標(biāo)往前移queue[rear]=value;//存入佇列

return0;

}

intdequeue

{

if(front==rear)//檢查佇列是否為空return-1;//無法取出

front++;//前端指標(biāo)往前移returnqueue[front];//佇列取出

}

/*廣度優(yōu)先*/

voidbfs(intcurrent)

{

graphptr;

enqueue(current);//將頂點(diǎn)存入佇列

visited[current]=1;//記錄已遍歷過

printf("[%d]",current);//印出遍歷頂點(diǎn)值

while(front!=rear)//佇列是否為空

{

current=dequeue;//將頂點(diǎn)從佇列中取出

ptr=head[current].nextnode;//頂點(diǎn)位置

while(ptr!=NULL)//遍歷至鏈表尾{

if(visited[ptr->vertex]==0)//假如沒遍歷過

{

enqueue(ptr->vertex);//遞回遍歷呼叫

visited[ptr->vertex]=1;//記錄已遍歷過

printf("[%d]",ptr->vertex);

}

ptr=ptr->nextnode;//下一個(gè)頂點(diǎn)

}

}

}

/*深度優(yōu)先*/

voiddfs(intcurrent)

{

graphptr;

visited[current]=1;//記錄已遍歷過

printf("[%d]",current);//印出遍歷頂點(diǎn)值

ptr=head[current].nextnode;//頂點(diǎn)位置

while(ptr!=NULL)//遍歷至鏈表尾

{

if(visited[ptr->vertex]==0)//假如沒遍歷過

dfs(ptr->vertex);//遞回遍歷呼叫

ptr=ptr->nextnode;//下一個(gè)頂點(diǎn)}

}

/*將遍歷內(nèi)容印出.*/

intmain(intargc,char*argv)

{

//clrscr;

system("cls");

while(1)

{

charc,a;

graphptr;

inti;

intnode[60][2]={{1,10},{10,1},{2,10},{10,2},{2,3},{3,2},{3,4},{4,3},

{3,12},{12,3},{4,13},{13,4},{4,5},{5,4},{5,6},{6,5},{5,7},{7,5},

{7,8},{8,7},{9,10},{10,9},{10,11},{11,10},{11,14},{14,11},

{11,12},{12,11},{12,15},{15,12},{12,

13},{13,12},{13,16},{16,13},

{14,17},{17,14},{14,18},{18,14},{15,

19},{19,15},{16,20},{20,16},

{17,18},{18,17},{18,23},{23,18},{18,

19},{19,18},{19,23},{23,19},

{19,24},{24,19},{19,20},{20,19},{20,

21},{21,20},{22,23},{23,22},

{24,25},{25,24}};

system("cls");

printf("\n\n\n");

printf("/*funcotion：TraversingGraphalgorithmdisplay*/\n");

printf("Depth_FirstSearchandBreadth_FirstSearch?Y/N?\n");

c=getchar;

if(c!='y'

system("cls");

printf("\n\n");

printf("pleasenoticethefollowingcities

code:\n\n");

printf("1:烏魯木齊;2:呼和浩特;3:北京;4:天津;5:沈陽;\n");

printf("6:大連;7:長春;8:哈爾濱;9:西寧;10:蘭州;\n");

printf("11:西安;12:鄭州;13:徐州;14:成都;15:武漢;\n");

printf("16:上海;17:昆明;18:貴陽;19:株州;20:南昌;\n");

printf("21:福州;22:南寧;23:柳州;24:廣州;25:深圳.\n");

getchar;

for(i=1;i",head[i].vertex);

ptr=head[i].nextnode;

while(ptr!=NULL)

{

printf("%d",ptr->vertex);

ptr=ptr->nextnode;

}

}

printf("\n\n");

printf("pleaseyouchooseyouroperation\n");

printf("1、ifBreadth_Searching,pleaseinput:'g'或'G'\n");

printf("2、ifDepth_Searching,pleaseinput:'s'或'S'\n");

c=getchar;

switch(c)

{

case'g':

case'G':

printf("\nplesaeinputthefirstvex:\n");

scanf("%d",

printf("\n\n");

printf("pleasenoticeall

citiescode:\n\n");

printf("1:烏魯木齊;2:呼和浩

特;3:北京;4:天津;5:沈陽;\n");

printf("6:大連;7:長春;8:哈

爾濱;9:西寧;10:蘭州;\n");

printf("11:西安;12:鄭州;13:

徐州;14:成都;15:武漢;\n");

printf("16:上海;17:昆明;18:

貴陽;19:株州;20:南昌;\n");

printf("21:福州;22:南寧;23:

柳州;24:廣州;25:深圳.\n");

printf("graphBread_Fristsearch