数据结构--约瑟夫环课程设计报告

《数据结构--约瑟夫环课程设计报告》由会员分享，可在线阅读，更多相关《数据结构--约瑟夫环课程设计报告（9页珍藏版）》请在毕设资料网上搜索。

1、课程设计报告课程设计报告 一、一、需求分析需求分析 1、 本演示程序中，利用单向循环链表存储结构模拟约瑟夫问题的进行。程序运行后， 首先要求用户指定初始报数上限值，然后读取个人的密码。可设 n30。此题所用 的循环链表中不需要“头结点” ，因此在程序设计中应注意空表和非空表的界限。 2、 演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之 后，由用户在键盘上输入演示程序中规定的运算命令：相应的输入数据和运算结果 显示在其后。 3、 程序执行的命令包括： 1） 构造约瑟夫环；2）执行约瑟夫环，并输出出列人的序号以及相应的密码； 3）结束。 4、测试数据 1）m 的初始值为

2、20； 2）n=7，7 个人的密码依次为：3、1、7、2、4、8、4。 3）首先 m 值为 6，正确的出列顺序应为 6、1、4、7、2、3、5。 二、概要设计二、概要设计 为实现上述程序功能， 应以单向循环链表表示约瑟夫环。 为此， 需要两个抽象数据类型： 单向循环链表和约瑟夫环。 1） 、单向循环链表的抽象数据类型定义为： ADT List 数据对象：D=aiaiElemset,i=1,2,n,n0 数据关系：R1=a(i-1),aia(i-1),aiD,i=2,n 基本操作： InitList( /元素类型 Typedef struct NodeType ElemType data; El

3、emType *next; ElemType, *LinkTypet; /结点类型，指针类型 void FreeNode(LinkType If(!s) return NULL; s-data=p-data; s-next=NULL; return s; ElemType Elem(LinkType p) /若指针 p!=NULL,则返回 p 所指结点的数据元素 LinkType SuccNode(LinkType p ) /若指针 p!=NULL,则返回指向 p 所指结点的后继元素的指针， /否则返回 NULL 2、根据单向循环链表的基本操作特点，有序表采用有序链表实现。链表设头、尾两个指针

4、 和表长数据域，但此链表中并未设头结点。 Typedef struct LinkType head,tail; /分别指向线性链表的头结点和尾结点 Int size; /指向链表的当前长度 creatList_L /有序链表类型 有序链表的基本操作设置如下： Int ListLength(creatList_L); /返回链表的长度 LinkType GetElem(creatList_L) /若 L 存在且 0next = p; tail = p; tail-next = head; return tail; 3、约瑟夫环利用单向循环链表类型来实现； typedef struct LNode

5、； 其中部分代码如下： void ListDelete_L(LinkList L,int key,int n) int i; LinkList q; while( n0) for (i = 1; i next; q =L-next; printf(“第%d 个人出列,密码%dn“,q-num,q-password); L-next =q-next; key = q-password; free(q); n-; 4、主函数 void main() LinkList s; int n,m; printf(“请输入总人数 N 和上限数 M:“); scanf(“%d%d“, printf(“请输入%

6、d 个人的密码n“,n); s=creatList_L(n); printf(“序号 密码n“); ListDelete_L(s,m,n); 5、函数的调用关系图反映了演示程序的层次结构： 四、调试分析四、调试分析 1、 由于刚开始对单项循环链表是用的不熟练， 在程序中的一句语句 for (j = 1; j 1。在对程序改正后，这一现象也就不再存在。 2、本程序的模块划分比较合理，且尽可能将指针的操作封装在结点和链表的两个模块中， 致使集合模块的调试比较顺利。 3、本实习作业采用数据抽象的程序设计方法，将程序划分为四个层次结构：元素结点、 单项循环链表、约瑟夫环和主控模块，使得设计时思路清晰，实现时调试顺利，各模块具有 较好的可重用性，确实得到了一次良好的程序设计训练。 五、用户手册五、用户手册 1、本程序的运算环境为 Windows 操作系统，执行文件为：CLD.exe。 2、进入演示程序后即显示文本方式的用户