数据结构课程设计-5

1/1数据结构课程设计>

课

程

设

计

班级:111004

姓名:董丽美

学号:111004122

指导老师:史延新

完成日期:2023_07_10

题目一:约瑟夫环问题

【问题描述】约瑟夫（Joseph）问题的一种描述是：编号为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．用单循环链表存储并遍历及删除节点的方法，计算并输出约瑟夫环的问题。

2．环中总人数和节点信息由用户输入，且均为正整数。3．在窗口界面输出出列挨次的编号。

二．概要设计

1.设定链表的抽象数据类型定义：

ADTList{

数据对象：D={a(i)|a(i)∝Elemset,i=1,2,…,n,n>=0}

数据关系：R1={|a(i-1),a(i)∝D,i=2,…,n}基本操作：

InitList(&L)

操作结果：构造一个空的线性表

ListInsert(&L,i,e)

初始条件：线性表L已经存在。

操作结果：在L中第i个位置之前插入新的数据元素e,L的长度增加1。

ListDelete(&L,i,&e)

初始条件：线性表L已经存在且非空，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)//删除头结点

{

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)//删除中间节点

{

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("请输入总人数:");

scanf("%d",

getchar;

for(i=0;ivertex=to;//建立顶点内容

newnode->nextnode=NULL;//设定指标初值

ptr=//顶点位置

while(ptr->nextnode!=NULL)//遍历至链表尾ptr=ptr->nextnode;//下一个顶点

ptr->nextnode=newnode;//插入结尾

}

}

4、初始化顶点坐标

数组名称：intnode[60][2]

数组功能：此为顶点坐标，主要用来读取存储在文件中的各个顶点坐标信息

详细代码：

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//最大顶点个数

structnode

{intvertex;//输入顶点

structnode*nextnode;//指向下一节点

};

typedefstructnode*graph;//图形的结构新形态

structnodehead[61];//图形顶点结构数组

intvisited[61];//遍历记录数组

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

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

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

voidcreategraph(int*node,intnum)

{

graphnewnode;//新顶点指标

graphptr;

intfrom;//边线的起点

intto;//边线的终点

inti;

for(i=0;ivertex=to;//建立顶点内容

newnode->nextnode=NULL;//设定指标初值

ptr=//顶点位置

while(ptr->nextnode!=NULL)//遍历至链表尾ptr=ptr->nextnode;//下一个顶点

ptr->nextnode=newnode;//插入结尾

}

}

intenqueue(intvalue)

{

if(rear>=MAXQUEUE)//检查佇列是否全满

return-1;//无法存入

rear++;//后端指标往前移queue[rear]=value;//存入佇列

return0;

}

intdequeue

{

if(front==rear)//检查佇列是否为空return-1;//无法取出

front++;//前端指标往前移returnqueue[front];//佇列取出

}

/*广度优先*/

voidbfs(intcurrent)

{

graphptr;

enqueue(current);//将顶点存入佇列

visited[current]=1;//记录已遍历过

printf("[%d]",current);//印出遍历顶点值

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

{

current=dequeue;//将顶点从佇列中取出

ptr=head[current].nextnode;//顶点位置

while(ptr!=NULL)//遍历至链表尾{

if(visited[ptr->vertex]==0)//假如没遍历过

{

enqueue(ptr->vertex);//递回遍历呼叫

visited[ptr->vertex]=1;//记录已遍历过

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

}

ptr=ptr->nextnode;//下一个顶点

}

}

}

/*深度优先*/

voiddfs(intcurrent)

{

graphptr;

visited[current]=1;//记录已遍历过

printf("[%d]",current);//印出遍历顶点值

ptr=head[current].nextnode;//顶点位置

while(ptr!=NULL)//遍历至链表尾

{

if(visited[ptr->vertex]==0)//假如没遍历过

dfs(ptr->vertex);//递回遍历呼叫

ptr=ptr->nextnode;//下一个顶点}

}

/*将遍历内容印出.*/

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