算法与数据结构课设.doc

******************* 实践教学 ******************* 兰州理工大学 计算机与通信学院 2013年春季学期 算法与数据结构 课程设计 题 目：1.约瑟夫问题 2.方程求解问题 3.病人就医管理问题 专业班级：计算机科学与技术1班 姓 名： 苏宇宁 学 号： 指导教师： 成 绩：_______________ 目 录 摘 要 2 一．约瑟夫问题 3 1.采用类语言定义相关的数据类型 3 2.算法设计 3 3.函数的调用关系图 3 4.调试分析 3 5.测试结果 3 6.源程序（带注释） 4 二．方程求解问题 5 1.采用类语言定义相关的数据类型 5 2.算法设计 5 3．函数的调用关系图 5 4.调试分析 5 5.测试结果 5 6.源程序（带注释） 5 三．病人就医管理模拟问题 6 1.采用类语言定义相关的数据类型 6 2.算法设计 6 3．函数的调用关系图 6 4.调试分析 6 5.测试结果 6 6.源程序（带注释） 6 总 结 7 参考文献 8 致 谢 9 摘 要 C是一种通用的程序设计语言，C语言在很多方面继承和发展了以往许多高级程序设计语言的成功经验和特色，具有书写格式自由、数据类型丰富、语句功能强大、执行速度快和存储控制能力强等优点。 本课程主要介绍了本课题的开发背景，所要完成的功能和开发的过程。重点说明了系统的设计思路、总体设计、各个功能模块的设计与实现方法。 1. 约瑟夫（Joeph）问题：在这个循环查找问题中，通过循环链表实现了循环查找到节点。一个关键部分就是删除节点后进行链表的链接，从而保证链表的循环性。在查找方面上，我利用了一个for循环来计数所查找过的节点 2.方程求解问题：解出方程A5+B5+C5+D5+E5=F5刚好满足条件0≤A≤B≤C≤D≤E≤F≤75的整数解,以嵌套的六个for循环语句来实现。 3.病人就医管理模拟问题：病人就医管理系统设计是关于对患者排队、按病历号就诊、查看排队、下班退出的管理来设计的一个系统。整个系统从符合操作简便、界面友好、灵活、实用、安全的要求出发，完成病人就医管理的全过程，包括创建一个链式队列、患者排队、患者就诊、查看排队患者、下班退出等工作。 关键词： 约瑟夫；方程求解；病人就医管理；数据结构。 一．约瑟夫（Joeph）问题 一种描述是：编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 1.采用类语言定义相关的数据类型 head (1)空单循环链表 … head （ 2）非空单循环链表 rear typedef struct Node { int num; int pasword; struct Node *next; }LinkList; 2.算法设计 插入：在把元素插入到循环链表中时，由于是采用的头插法，所以我保留了head头结点。在每加入一个节点时，都会直接连接在head后面，从而保证一开始就赋值的尾节点不用修改。 删除：首先通过p指针查找到所要删除的节点的前一个节点，继而通过q=p-next简单地删除掉。约瑟夫问题的基本思想：在这个循环查找问题中，通过循环链表实现了循环查找到节点。一个关键部分就是删除节点后进行链表的链接，从而保证链表的循环性。在查找方面上，我利用了一个for循环来计数所查找过的节点。 3.函数的调用关系图 4.调试分析 a.在程序运行结果中，虽然编译没有任何错误，在运行过程中也没有逻辑错误，可以得到正确结果，但在运行即将结束时会有“程序已停止执行”的窗口。这是一个我没有解决好的debug。 b、算法的时间复杂度为O（m*n），空间复杂度为O（n）。 测试结果 测试数据：实验人数5人，密码分别为3,4,6,3,2.m初值为3。 6.源程序（带注释）