还剩10页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
⑥处友年便大学世化茂CEuryC-B«pnaUrwvwMyofon4W«wtwthmco«《数据结构与算法设计》约瑟夫环实验报告实验一专业:物联网工程班级:物联网1班学号15180118姓名:刘沛航#includestdlih.h〃引用函数库structLNode|intnum structLNode*next;}〃定义链表typedefstructLNodeNODE;NODE*create1inklistintn//初始化循环链表,并返回I头指针NODE*headinti=1;hcad=p=structLNode*mal1ocsizcofstructLNode;p—num=i;fori=2;i=n;i++q=structLNode*mallocsizeofstructLNode;ifq==0return0;p-next=q;p=q p-num=i;}P—next=head;〃使链表尾指向链表头形成循环链表«rcturnhead;voidjosephNODE*pintnintm〃约瑟夫函数,用于输出约瑟夫环intij;NODE*q;fori=l;i=n i++p=p-next;〃计算出列者序号q=p-next;p-next=q-next;printf%d”q-num;freeq;p—next=NULL;voidmainNODE*head;intnsm;inti;//拟定计算系数printf******水***************物理网1班-*******************\n;prinIf(“围绕圆桌的人数为人n);scanf%dn;prinlf从第几人开始?\n;scanf%ds;printf“数到几的人出列\n;scanf%dm;〃拟定头指针head=createlinklistn;ifs==13fori=l;in i++head=head—next;•elsefori=l;is-l;i++head=head-next;//输出约瑟夫环出列顺序printf出列的顺序如下:\n;josephheadnm;
一、实验目的I、熟悉VC环境,学习使用C语言运用链表的存储结构解决实际的问题
2、在编程、上机调试的过程中,加深对线性链表这种数据结构的基本概念理解
3、锻炼较强的思维和动手能力和更加了解编程思想和编程技巧
二、实验内容
1、采用单向环表实现约瑟夫环请按以下规定编程实现
①从键盘输入整数m通过create函数生成一个具有m个结点的单向环表环表中的结点编号依次为12……mo
②从键盘输入整数sk=sCm和n从环表的第s个结点开始计数为1当计数到第n个结点时,输出该第n结点相应的编号,将该结点从环表中消除从输出结点的下一个结点开始重新计数到n这样不断进行计数,不断进行输出,直到输出了这个环表的所有结点为止例如m=l0s=3n=4o则输出序列为61049521387o
三、程序设计
1、概要设计为了解决约瑟夫环的问题,我们可以建立单向环表来存储每个人的信息该人的编号以及其下一个人的编号,及结点,人后通过查找每个结点,完毕相应的操作来解决约瑟夫问题1抽象数据类型定义ADTJoh{数据对象D={qlqeElemSetz=
12..n0}数据关系Rl={q_1,4GDz=l
2...n基本操作acreateJn“操作结果:构造一个有n个结点的单向环表JoshowJ初始条件单向环表J已存在操作结果按顺序在屏幕上输出J的数据元素sealculateJsn初始条件:单向环表J已存在s0n0s〈环表结点数操作结果:返回约瑟夫环的计算结果}ADTJoh2宏定义defineNULL0defineOK1defineERROR-1
(3)主程序流程输入数据(msn创建环表输出建立好的环计算解决输出结果结束
(4)模块调用关系程序分为下述模块1)主函数模块一一执行输入调用其他的功能函数2)创建环表模块一一创建单向环表3)计算解决模块一一计算出要出列的标号并输出4)显示模块一一输出建立好的环表调用关系如下:主函数模块口创隼环表模块#示模块计算解决模块
2、具体设计1数据类型设计typedefintElemType;//元素类型typedefstruct{oE1emTypedata;structJoh*next;}Joh*LinkList*p;//结点类型,指针类型2操作算法StatuscreateLinkListJintn{〃创建一个有n个结点的单向环表ifn=0ooreturnERROR//n0错误J=LinkListmallocsizeofJ;J-data=1;J-next=J;//建立第一个结点forinti=n;i1-i{p=LinkListma1locsizeofJ;p-data=i;^p-next=J-next;J-next=p;//插入到表头}returnOK;}//createvoidshowLinkListJ{〃重要的操作函数〃顺序输出环表J的结点叩二J;printf%dHp-data;p=p-next;owhi1ep!=J{//循环终止条件sprintf%d”p—data;p=p-next;}//showvoidca1culateLinkListJintsintn{P=J;Joh*head=p;//声明结点owhilep-data!=s{p=p-next;ahead=p;}〃寻找起始结点owhi1ep-next!=p{〃终止条件forinti=0;in-l;i++{head=p;〃保存前置节点gp=p-next;}printf%dnp-data;ohead-next=p-next;〃删除已输出结点6p=head—next;ifn!=1printf%d\np-data;else8Printfn\nn;}//calculate3主函数代码intmain{〃主函数Joh*J;intmsn;printfThenumofnodeis:;-scanfn%dnm;createJm;//创建单向环表JshowJ;〃输出J的数据oprintf\nn;printfHThefirstnodewhichyouwantisoscanf”%ds;printfHTheinterna1whichyouwantisoscanf%dnn;ocalculateJsn;〃计算并输出结果return0;}//main
四、程序调试分析
1、细节决定成败,编程最需要的是严谨,如何的严谨都但是分往往检查了半天发现错误发生在某个括号,分号,引号,或者数据类型上在写重要操作函数caculate时,在终止条件的书写处不是很清楚导致我浪费了很多时间
2、尚有一点很大的感触就是,在自己绞尽脑汁都解决不了碰到的问题时,一个很好的手段就是询问同学,寻求其帮助,就比如我在想函数终止条件时,同学一句简朴的话语就让我如梦初醒这不是什么丢脸的事情,相反的,在快速解决问题的同时还会收获友谊,不是一举两得吗我想,这也是合作学习的真谛吧
五、用户使用说明
1、本程序的运营环境为Windows操作系统下的MicrosoftVisualC++
6.0o
2、在VC环境下打开程序后,按规定键入规定的数字,以等号或空格断开,敲击“回车符”,即可以显示规定的结果
3、按下任意键以继续
六、程序运营结果程序测试1程序测试2
七、程序清单#includestdio.h。