1、 数 据 结 构 课 程 设 计数 据 结 构 课 程 设 计 最小套圈设计最小套圈设计( (课题名称课题名称) ) 专业专业 计算机科学与技术计算机科学与技术 班级班级 学号学号 学生姓名学生姓名 数据结构课程设计最小套圈设计（题目） 目目 录录 1 设计题目 . 1 2 设计分析 . 1 3 设计实现 . 3 4.1 测试目的 . 5 4.2 测试输入 5 4.3 正确输出 6 4.4 实际输出 6 5 分析与探讨 7 5.1 测试结果分析. 7 5.2 探讨与改进 7 6 设计小结 . 9 数据结构课程设计最小套圈设计（题目） 1 1 设计题目 套圈游戏是游乐场中常见的游戏之一，其规则为
2、：游戏者将手中的圆环套圈投 向场中的玩具，被套中的玩具就作为奖品奖给游戏者。 现给定一个套圈游戏场的布局，固定每个玩具的位置，请你设计圆环套圈的半 径尺寸，使得它每次最多只能套中一个玩具。但同时为了让游戏看起来更具有吸引 力，这个全套的半径又需要尽可能大。 把问题进一步简化，假设每个玩具都是平面上的一个没有面积的点，套圈是简 单的圆。一个玩具被套住，是指这个点到圆心的距离严格小于圆半径。如果有两个 玩具被放在同一个位置，那么输出的圆半径就是0。 输入要求： 输入由若干组测试数据组成。 每组数据的第1行包含一正整数N（2x; int compy(const void* a, const void
3、* b) /*实现按 y 排序*/ return (Point*)a)-y-(Point*)b)-y; void main() int i,j=0,numPoints; Point pointsMAX_POINTS; float resultMAX_TEST; /*记录结果*/ for(i=0;ix; 数据结构课程设计最小套圈设计（题目） 9 int compy(const void* a, const void* b) /*实现按 y 排序*/ return (Point*)a)-y-(Point*)b)-y; 经过预排序处理后的算法所需的计算时间 T(n)满足递归方程： 显而易见 T(n)
4、=O(nlogn)，预排序所需的计算时间为 O(n1ogn)。因此，整个算法所 需的计算时间为 O(nlogn)。在渐近的意义下，此算法已是最优的了。 6 设计小结 这次实验共做了一个星期，实际算下来也就三天左右，时间很紧凑，忙忙碌碌， 到最后终于完成了，在这里可以画上一个圆满的句号。 在这过程中，我明白了很多东西：1、巩固和加深了对数据结构的理解，提高 综合运用本课程所学知识的能力。2、培养了我选用参考书，查阅手册及文献资料 的能力。培养独立思考，深入研究，分析问题、解决问题的能力。3、通过实际编 译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。4、通 过课程设计，培养了我严肃认真的工作作风，逐步建立正确的生产观念、经济观念 和全局观念。 根据我在实习中遇到得问题， 我将在以后的学习过程中注意以下几点： 1、 认真上好专业实验课，多在实践中锻炼自己。2、写程序的过程中要考虑周到，严 密。3、在做设计的时候要有信心，有耐心，切勿浮躁。4、认真的学习课本知识， 掌握课本中的知识点，
