数据结构课程设计报告团队需解决的难题

数据构造课程设计系别_____________________________________4________专业____________________班级学号__________________________________姓名__________________________________指导教师__________________________________成绩int data;struct node*next;定义结点类型*/JLNode;/*创立循环链表*/LNode*CREATint n/*LNode*s,*q,*t;int i;ifn!=0t=q=LNode*mallocsizeofLNode;生成第一种结点并使其值为q-data=1;/*data1*/fori=2;i=n;i++自动生成结点*/s=LNode*mallocsizeofLNode;/*q-next=s;给第个结点赋值q-next-data=i;/*i i*/q=q-next;q-next=t;}/*生成后续结点，并使其值即为它所在链表（队伍）中的位置*/datareturn t;}链表欧删除*/DELETE LNode*t,int m/*1LNode*a;int i;while t-next!=t查找要删除结点的前一结点*/for i=l;im-l;i++/*J t=t-next;a=t-next;t-next=a-next;释放结点*/freea;/*t=t-next;循环依次删除被点到的士兵*/}/*while；printf\nreturn t-data;mainLNode*p;int m,n,z,y;printfnExit please input O Or Go on...\nPlease input the tatal of the team:1;scanf n%dn,n;/*输入队员总数*//*当队员总数等于时退出*/whilen!=0doprintfnPlease inputthe excursion:1;/*输入偏移数*/scanfn%dn,m;while m=0;if m=lprintfThe wanted position islth.\nn;else二p CREATn;y=DELETEp,m;z=n-y+2;/*排除特殊状况*/ifz%n=0printf The wanted position is%dth:\nH,z;elseprintfnThe wantedposition is%dth:\nH,n-y+2%n;}/*通过数学思想求得试验规定状况下的数值*/JprintfnExit please input OOr Go on...\nPlease inputthe tatal of theteam:n;scanfH%dn,n;/*输入敢死队员总数*/二.线性表数据构造一需求分析本程序任务是通过输入任意队伍人数和报数上限输出使排长最终一种执行任务而

1.n m,开始记数的初始位置首先输入队伍人数然后输入报数上限〈=从号开始报数，当n,n ni n,1到达报数上限时，那名士兵出列执行任务，从下个人开始记数，再次循环，直到只剩一人，得到其在队伍中日勺位置，记下该位置视为排长位置，则号即可视为最先报数的人,通过数学1计算即可获得所求功能模块和流程

2.功能模块1该程序功能比较单一，重要是为处理敢死队问题而设计通过输入队伍人数和报数上限即可获得开始报数的位置程序流程2如下图数据测试

3.当输出成果为规定日勺位置是n=109-详细设计算法思想本程序其实质是约瑟夫环问题，本次试验用了线性表和循环队列两种数据构

1.造，并运用模块化的程序设计思想，算法的实现是这样的I定义构造体类型1定义变量并初始化2线性表初始化3队员报数，是的倍数出列45当队员数等于时，输出51流程图从排长位置即号开始报数，共有个人，到达报数上限时战士出列，继续进行1n m=5报数，直到剩余最终一人，记下该位置为若将该位置视为排长位置，则原先的号位置k II即位所有日勺开始报数时位置贝z iJz=n-k+

2.模块设计2宏定义#define LIST_INIT_SIZE100#define LISTINCCREMENT10数据类型定义:typedef intElemType;定义数据构造/*定义数据构造体类型*/typedef structKList/*存储空间基址*/ElemType*elem;/*目前长度*/int length;/*目前分派的存储容量以为单位*/int listsize;1sizeofElemTypeJSqList;模块一:创立线性表函数/*创立线性表函数*/SqList InitList_Sq{SqList L;L.elem=ElemType*mallocLIST_INIT_SIZE*sizeofElemType;if!L.elem printfnFailin newcreat listn,exit0;/*存储分派失败*/else/*空表长度为L.length=O;0*/二」初始存储容量*/模块二线性表再分派函数L.listsize LIST NIT_SIZE;/*/*线性表再分派函数*/SqList ListInsert_SqSqList L{/*SqList L;*/int*newbase;newbase=ElemType*reallocL.elem,L.listsize+LISTINCCREMENT*sizeofElemType;/*为次序表增长一种大小为存储个数据元素区空间刃LISTINCCREMENT Iif!newbase printfnFailin newadd list,exit0;/*存储分派失败*/else/*新基址*/L.elem=newbase;/*增长存储容量*/L.listsize+=LISTINCCREMENT;主模块:实现总体功能mainSqList L;/*申明变量*/int s,i,m,count=0;L=InitList_Sq;printfHPlease inputthe tatalof theteam:;/*输入敢死队员总数*/scanf%d”,m;当输入为时退出程序*/whilem!=O/*0/*当次序表目前分派的存储空间大小局限性时进行再分派*/whilemL.length JL=ListInsert_SqL;/*为队员赋值*/fori=0;im;i++L.elem[i]=i+1;s=m;i=0;/*当所剩敢死队员总数为时，总循环结束*/whilesl1fori=0;im;i-t-+count+4-;/*报数循环*/ifcount==5表达队员出列*/L.elem[i]=O;/*/*计数器清零*/count=0;/*敢死队员数s-;-1*//*输出*/fori=0;im;i++ifL.elem[i]!=Oifm-L.elem[i]+2%m==0/**/printfn\nThe wantedorder is%dth\nH,m;elseprintfn\nThe wantedorder is%dth\nH,m-L.elem[i]+2%m;printfnExit please input OOr Go on...\nPlease inputthe tatalof theteam:;scanfn%dn,m;/*输入敢死队员总数*/

（三）调试分析敢死队问题问题描述有个敢死队员要炸掉敌人的;一碉堡，谁都不想去，排长决定用轮回数数日勺措施来决定M哪个战士去执行任务假如前一种战士没完毕任务，则要再派一种战士上去现给每个战士编一种号，大家围坐成一圈，随便从某一种战士开始计数，当数到时，对应的战士就去执行任5务，且此战士不再参与下一轮计数假如此战士没完毕任务，再从下一种战士开始数数，被数到第时，此战士接着去执行任务以此类推，直到任务完毕为止5排长是不乐意去的假设排长为号，请你设计一程序，求出从第几号战士开始计数才能I,1让排长最终一种留下来而不去执行任务规定至少采用两种不一样的数据构造的措施实现

一、单循环链表数据构造-*需求分析本程序任务是通过输入任意队伍人数和报数上限输出使排长最终一种执行任务而

1.n m,开始记数区初始位置首先输入队伍人数然后输入报数上限从号开始报数，当I n,mmCn,1到达报数上限时，那名士兵出列执行任务，从下个人开始记数，再次循环，直到只剩一人，得到其在队伍中的位置，记下该位置视为排长位置，则号即可视为最先报数日勺人,通过数学1计算即可获得所求功能模块和流程

2.功能模块1该程序功能比较单一，重要是为处理敢死队问题而设计通过输入队伍人数和报数程序正常运行后应当为:L exitplease input Oor goon...pleaseinputthe totalof theteam输入总共人数The wantedposition isth输出所求勺开始报数位置H在程序调试运行的过程中产生了多种各样的问题，有日勺是多了空格，有的是拼写错误，尚

2.有的是少了括号，类似的问题有诸多处理勺措施是一遍遍尝试，不停逐行逐句进行修改例H如程序调试过程中出现了下面的警告ICompiling二二Main fileMYDESI3c CompilingEDITOR-MYDESI3cTotal FileLines compiled7373Warnings22Errors00Available memory295K WarningsPress anykeyCompiling C\DOCUME~1\^HNI，卜4斗尚g-lMYDESI七.C5~1\MYDESI~3・C25Non-portable pointerassignmentin functionListInsert_Sq UarningC\DOCUME~1\IF|HMIL DESI^

3.C31Non-portable pointeras经查询错误为:不可移动日勺指针（地址常数）赋值最终发现是下面的定义错误导致的在变量定义中int*newbase=0;定义成了int newbase=0;经改正程序运行正常了.=Compiling二Main fileMYDESI3c CompilingEDITOR iMYDESI3cTotal FileLines compiled7373Warnings00Errors00Available memory295K SuccessPress anykey.经验与体会3通过这次课程设计我又学到了诸多东西，如程序的模块化设计思想，同步也加深了对数据构造这门课程的理解和学会了怎样在实际中应用数据构造编程I我首先是用线性表来做欧开始的想法是想用试验的措施来查找到所规定的位置，即首先I,从第一号开始报数，然后检查最终剩余的一种与否是队首，然后从第二个开始报数……从第三个开始报数……直到所剩余的最终一种是队首虽然这种措施可以实现查找，可却是以消耗更多日勺时间为代价的，于是我又想到了这个措施总是从第一种开始报数，报到出列,直到5剩余最终一种为止，然后就令这个位置为队长位置，队首为开始报数的位置，并按此设计输出即可这种措施大大的减少了时间复杂度，复杂度为Omn四测试成果、c D:\tc\TC.EXEExit pleaseinput0Or Go on...Please inputthe tatalof the tean2The uantedpos it ion is2thExit pleaseinput0Or Go on...Please inputthe tatalof theteam9The uantedposit ion is4thExit pleaseinput0Or Go on...Please inputthe tatalof thetean89The wantedposit ion is9thExit pleaseinput0Or Goon...Please inputthe tatalof thetean158The wantedposition is80thExit pleaseinput0Or Goon...Please inputthe tatalof thetean589The wantedpos ition is357thExit pleaseinput0Or Goon...Please inputthe tatalof thetean1256The wantedposit ion is275thExit pleaseinput0Or Goon...Please inputthe tatalof thetean0五附件程序源代码#define LISTJNIT.SIZE100#define LISTINCCREMENT10typedef intElemType;/*定义数据构造体类型*/typedef structKList/*存储空间基址*/ElemType*elem;/*目前长度*/int length;/*目前分派欧存储容量以为单位*/int listsize;I sizeofElemType}SqList;/*创立线性表函数*/SqList InitList_SqSqList L;L.elem=ElemType*mallocLIST_INIT_SIZE*sizeofElemType;if!L.elem printfnFailin newcreat listn,exit0;/*存储分派失败*/else/*空表长度为L.length=0;0*/」初始存储容量*/L.listsize=LISTNIT_SIZE;/*/*线性表再分派函数*/SqList ListInsert_SqSqList L/*SqList L;*/int*newbase;newbase=ElemType*reallocL.elem,L.Iistsize+LTSTINCCREMENT*sizeofElemType;/*为次序表增长一种大小为存储个数据元素的空间*/LISTINCCREMENT Jif!newbase printfnFailin newadd listexitO;/*存储分派失败*/else/*新基址*/L.elem=newbase;/*增长存储容量*/L.listsize+=LISTINCCREMENT;mainSqList L;L=InitList_Sq;printfHPlease inputthe tatalof theteam:;/*输入敢死队员总数*/scanf%d”,m;当输入为时退出程序*/whilem!=0/*0/*当次序表目前分派日勺存储空间大小局限性时进行再分派*/whilemL.lengthL=ListInsert_SqL;/*为队员赋值*/fori=0;im;i++L.elem[i]=i+1;s=m;i=0;/*当所剩敢死队员总数为时，总循环结束*/whilesl1fori=0;im;i++/*报数循环*/ifL.elem[i]!=Ocount++;ifcount==5表达队员出列*/L.elem[i]=0;/*/*敢死队员数-1*/S-；fori=0;im;i++ifm-L.elem[i]4-2%m==0/**/printfH\nThe wantedorder is%dth\nn,m;elseprintfn\nThe wantedorder is%dth\n,,,m-L.elem[i]+2%m;printfHExit pleaseinputOOr Goon..AnPlease inputthe tatalof theteam:\nH;scanfn%dn,m;/*输入敢死队员总数*/上限即可获得开始报数的位置）程序流程2（）构造链表（）数据输入（）执行删除（）输出规定数值（）结束12345数据测试

3.当输出成果为规定的位置是n=10,m=5,9o

（二）详细设计.算法设计1本程序其实质是约瑟夫环问题从排长位置即号开始报数，共有个人，到达报数上限1n的战士出列，继续进行报数，直到剩余最终一人，记下该位置为若将该位置视为排长m=5ko位置，则原先的号位置即位所有日勺开始报数的位置则』次+II z22以单循环链表为存储构造，包括三个模块

2.（）主程序模块1（）构造链表并初始化2（）删除结点3结点类型和指针类型

3.typedef struct node（int data;structnode*next;定义结点类型*/}LNode;/*LNode*p;每个模块的分析

4.主程序模块1main!LNode*p;int m,n,z,y;doprintf CPlease inputthe peoplenumber:\n，z;〃〃scanf%d,n;}while n=0;do]printf〃Please inputthe excursion:\n，z;〃％〃，scanf dm;}while m=0;if n=lprintf，zthe position is:1〃；elsep=CREAT n;二y DELETEp,m;z=n-y+2;/*排除特殊状况*/if z%n=0，printf theposition is:\n%d\n,,z;else〃，printfCthe position is:\n%d\n n-y+2%n;}/*通过数学思想求得试验规定状况下的数值*/构造单循环链表并初始化模块2创立循环链表*/LNode*CREATint n/*LNode*s,*q,*t;int i;if n!=0t=q=LNode*mallocsizeofLNode;生成第一种结点并使其值为q-data=l;/*data1*/〈=for i=2;in;i++{自动生成结点*/s=LNode*mallocsizeof LNode;/*q-next=s;q-next-data=i;/*给第i个结点赋值i*/q=q-next;}q-next=t;}/*生成后续结点，并使其值即为它所在链表队伍中日勺位置*/data return t;删除结点模块3链表欧删除*/DELETE LNode*t,int m/*JLNode*a;int i;while t-next!=t{查找要删除结点的前一结点*/for i=l;i++/*t=t-next;a=t-next;t-next=a-next;释放结点*/free a;/*t=t-next;循环依次删除被点到的士兵*/}/*while〃〃printf\n;returnt-data;三调试分析.本程序运行后的成果应是如下提醒1Exit pleaseinputOOr Go onPlease inputthe tatalof theteam:输入队伍总人数Please inputthe excursion:输入间隔人数成果显示The wantedposition is选择的位置.在程序调试运行日勺过程中产生了多种各样日勺问题，有的是多了空格，有的是拼写错误，2尚有口勺是少了括号，类似的问题有诸多处理的措施是一遍遍尝试，不停逐行逐句进行修改例如程序调试过程中碰到警告发现错误为ifm=l后改正为程序运行对的了，运行如下:ifm=l显示输出如图:Exit pleaseinput:0*Oi Goon...Please inpu€€he七atzal of€ie七Please inpu€the excui*s ion5The wfintzed.pos it:ionis3七h Ex±€plea.seinpu€90*Oi*Goon...Please inpu€the七atalof the七eam=10Please input;the excui*s ion5The weintzedpos i€ionis9t h=Exit pleaseinpu€*0*Oi*Goon---Please input:the七atzal of the tzeeini1Please inpu€theexcuvs ion=1The wantedpos i€ionis.Exit pleaseinput0Ork Goon...Please inpu€七he七ata]of€he七eam88Pleaseinpu€the excui*s ion5Ihe wantzedpos itionis12€hExit七plea.seinput;0’OvGo on---Please input;the七atzal o£the七eam..由程序分析可得本程序时间复杂度为30nm!

①在设计生成循环单链表时，考虑到程序成果需要士兵的位序，故将每个结点的值设

4.data置为他们在队列中日勺位置，以便返回

②在删除单链表时，假如在报数时直接数到出列士兵则不以便链表的删除，可设置〈找到i ni-1出列士兵的前一位执行如下查找要删除结点的前一结点*/for i=1;im-l;i++/*It=t-next;a=t-next;t-next=a-next;释放结点*/free a;/*t=t-next;

③.在程序设计前，假如按原题所设，则需设队长为第一位，再分别测试从第几种开始才能符合条件目前变化思想，通过数学思想单循环链表自身是一种循环体，可先求出当从第一种出发日勺话，求出每隔个出去一种最终是谁未出列，然后再设置它为链头，求出当他为队首m时从第几种开始方能使其不出列（）即可实现这功能！n-y+2%n.经验与体会5通过这次课程设计我又学到了诸多东西，如程序区模块化设计思想，同步也加深了对数据I构造这门课程的理解和学会了怎样在实际中应用数据构造.这个措施是用单循环链表来做的，实现日勺措施是这样日勺首先从第一号开始报数，循环到指定的偏移位置删除结点，直至剩余一种结点然后设计输出，令这个位置为队长位置,队首为开始报数的位置，并按此输出即为所求这种措施大大的减少了时间复杂度，复杂度为O（）mno

（五）测试成果c、*D:\Progra Files\Bicrosoft VisualStudio\MyProjects\EXPE\Debug\

1.exeExit pleaseinput*0*Oi*Goon...▲Please inputthe tatalo£thetean9Please inputthe excursionThevianted positionis3thExit pleaseinput0Oi*Goon...Please inputthe tatalofthetean）10Pleaseinput the excursionThe uantedpositionis9thExit pleaseinput0Oi*Goon...Please inputthe tatalofthetean lPlease inputtheexcursion1Thewantedpositionis1th.Exit pleaseinput0Oi*Goon...Please inputthe tatalof theteam88Please inputtheexcursionThewantedpositionis12thExit pleaseinput0OrGoon...Please inputthetataloftheteam.

（六）附件typedef structnode。