4、电话簿软件的实现（动态查找表算法的应用）
【问题描述】
在很多实际应用中，动态索引结构在文件创建或初始装入记录时生成，在系统运行过程中插入或删除记录时，为了保持较好的检索性能，索引结构本身将随之发生改变。教材上已经介绍的动态查找数据结构包括：二叉搜索树（BST）、平衡二叉树（AVL）、红黑树（RBT）、B-树。本题要求选取一种已经学过的动态搜索树结构，设计并实现一个手机电话薄软件。 【基本要求】
一个完整的电话簿软件应具有以下功能：
（1）支持复式电话簿数据的存储，数据条目不少于500条。
每个人名下可保存的信息包括：姓名、手机号码、住宅电话号码、办公电话号码、电子邮件地址、所属群组、备忘录等。
（2）支持电话簿记录的添加、删除、编辑等操作。
（3）将不同类型的人群按照同事、朋友、家人、商务伙伴等分组，支持群组记录的添加、删除、编辑等操作。
（4）支持所有电话簿记录的导入、导出操作，外部数据采用TXT格式。 （5）支持电话簿记录的各种查询操作，具体包括： ① 逐条翻看
能显示所有的电话簿记录，支持分屏查看。
② 电话号码查找
输入一个电话号码（手机、住宅、办公），能将包含该号码的电话簿记录显示出来。
③ 人名查找
输入一个人名（全名或者部分名），能将包含该姓名的电话簿记录显示出来。 ④ 群组查找
选择一种群组类型，能将属于该群组的所有电话簿记录显示出来。 （6）要求使用BST或者AVL实现动态索引结构。 【提高要求】
（1）系统支持铃声库和图片库的数据存储，提供添加、删除、修改、播放等操作。铃声库和图片库可直接使用文件目录进行管理；铃声格式可使用WAV、MP3或者WMV格式；图片格式可使用BMP、JPG等格式。
（2）电话簿记录信息支持：来电铃声、来电图片等信息，用户可通过界面编辑或者浏览某条电话簿记录的来电铃声、来电图片。
（3）人名查询支持：输入姓名的首字母查找。
（4）使用红黑树或者B-树的数据结构，来实现动态索引结构。 【测试数据】
自行随机生成500~1000条电话簿数据记录。 【实现提示】
（1）设计合适的电话簿数据文件格式； （2）设计合适的索引文件格式。
6
《数据结构与算法》
课程设计报告
学 号： 班级序号： 姓 名： 指导教师：
成
绩：
中国地质大学信息工程学院软件工程系
2013年 12 月
7
课程设计报告格式
1．需求规格说明
（<五号宋体>，具体内容：问题描述，求解的问题是什么）
2．总体分析与设计
（1）设计思想：
（<五号宋体>，具体内容：存储结构、主要的算法思想。）
（2）设计表示：
（<五号宋体>，具体内容：子程序（过程或函数）的规格说明，通过调用关系图表示它们之间的调用关系。）
（3）详细设计表示：
（<五号宋体>，具体内容：主要算法的框架。）
3．编码
（<五号宋体>，具体内容：问题是如何解决的，编码过程中的困难与解决方法。）
4．程序及算法分析
（<五号宋体>，具体内容：使用说明、程序运行结果、讨论与分析、改进设想、经验与体会、时空复杂度等。）
5．小结
（<五号宋体>，具体内容：经验与体会，或需要改进的地方）
6．附录
（<五号宋体>，部分核心代码）
【参考资料】
1、 Sartaj Sahni著，《数据结构、算法与应用》，机械工业出版社 2、 殷人昆 等编著，数据结构(用面向对象方法与C++语言描述)》，清华大学出版社 3、 严蔚敏，吴伟民 编著，《数据结构题集》，清华大学出版社 4、 严蔚敏，陈文博 编著，《数据结构及应用算法》，清华大学出版社
8