【实现提示】
（1）编码结果以文本方式存储在文件CodeFile中。 （2）用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”表示退出运行Quit。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单，直至某次用户选择了“Q”为止。 （3）在程序的一次执行过程中，第一次执行I、D或C命令之后，哈夫曼树已经在内存了，不必再读入。每次执行中不一定执行I命令，因为文件hfmTree可能早已建好。
61. 散列法的实验研究
【问题描述】
（1）基本要求：设每个记录有下列数据项：电话号码、用户名、地址；从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表；采用一定的方法解决冲突；查找并显示给定电话号码的记录；查找并显示给定用户名的记录。 （2）进一步完成内容： 系统功能的完善：
设计不同的散列函数，比较冲突率； 在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变化。
62. 建立通信网络
【问题描述】
在n个城市建设通信网络，只需架设n-1条线路即可。设计一个程序，求出如何以最低的经济代价建设这个通信网。（该问题为最小生成树问题） 【基本要求】
（1）利用图作为存储结构；
（2）键盘输入问题规模n和各条线路的权值； （3）输出生成树中各条边以及他们的权值。
21
附录
一、上机实验概述
上机实践是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，实践题中的问题比平时的习题复杂得多，也更接近实际。实践着眼于原理与应用的结合点，使读者学会如何把书上学到的知识用于解决实际问题，培养软件工作所需要的动手能力；另一方面，能使书上的知识变“活”，起到深化理解和灵活掌握教学内容的目的。平时的练习较偏重于如何编写功能单一的“小”算法，而实践题是软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧，多人合作，以至一整套软件工作规范的训练和科学作风的培养。此外，还有很重要的一点是:机器是比任何教师都严厉的检查者。
每个实践题采取了统一的格式，由问题描述、基本要求、测试数据、实现提示和选做内容五个部分组成。问题描述旨在为读者建立问题提出的背景环境，指明问题“是什么”。基本要求则对问题进一步求精，划出问题的边界，指出具体的参量或前提条件，并规定该题的最低限度要求。测试数据部分旨在为检查学生上机作业提供方便，在完成实践题时应自己设计完整和严格的测试方案，当数据输入量较大时，提倡以文件形式向程序提供输入数据。在实现提示部分，对实现中的难点及其解法思路等问题作了简要提示。选做部分向那些尚有余力的读者提出了更严峻的挑战，同时也能开拓其他读者的思路，在完成基本要求时力求避免就事论事的不良思想方法，尽可能寻求具有普遍意义的解法，使得程序结构合理，容易修改扩充。
不难发现，这里与传统的做法不同，题目设计得非常详细。会不会限制读者的想象力，影响创造力的培养呢？回答是：软件发展的一条历史经验就是要限制程序设计者在某些方面的创造性，从而使其创造能力集中地用到特别需要创造性的环节之上。实践题目本身就给出了问题说明和问题分解求精的范例，使读者在无形中学会模仿，它起到把读者的思路引上正轨的作用，避免坏结构程序和坏习惯，同时也传授了系统划分方法和程序设计的一些具体技术，保证实现预定的训练意图，使某些难点和重点不会被绕过去，而且也便于教学检查。题目的设计策略是：一方面使其难度和工作量都较大，另一方面给读者提供的辅助和可以模仿的成份也较多。当然还应指出的是，提示的实现方法未必是最好的，读者不应拘泥于此，而应努力开发更好的方法和结构。
实践要有严格的规范(见下一节)。一种普遍存在的错误观念是，调试程序全凭运气。学生花两个小时的上机时间只找出一个错误，甚至一无所获的情况是常见的。其原因在于，很多人只认识到找错误，而没有认识到努力预先避免错误的重要性，也不知道应该如何努力。实际上，结构不好、思路和概念不清的程序可能是根本无法调试正确的。严格按照实践步骤规范进行实践不但能有效地避免上述种种问题，更重要的是有利于培养软件工作者不可缺少的科学工作方法和作风。
22
二、实践步骤
随之计算机性能的提高，它所面临的软件开发的复杂度也日趋增加。然而，编制一个10，000行的程序的难度绝不仅仅是一个5，000行的程序两倍，因此软件开发需要系统的方法。一种常用的软件开发方法，是将软件开发过程划分为分析、设计、实现和维护四个阶段。虽然数据结构课程中的实践题的复杂度远不如(从实际问题中提出来的)一个“真正的“软件，但为了培养一个软件工作者所应具备的科学工作的方法和作风，我们制订了如下所述完成实践的五个步骤:
(一) 问题分析和任务定义
通常，实践题目的陈述比较简洁，或者说是有模棱两可的含义。因此，在进行设计之前，首先应该充分地分析和理解问题，明确问题要求做什么?限制条件是什么。注意本步骤强调的是做什么?而不是怎么做。对问题的描述应避开算法和所涉及的数据类型，而是对所需完成的任务作出明确的回答。例如:输入数据的类型、值的范围以及输入的形式；输出数据的类型、值的范围及输出的形式；若是会话式的输入，则结束标志是什么?是否接受非法的输入?对非法输入的回答方式是什么等。这一步还应该为调试程序准备好测试数据，包括合法的输入数据和非法形式的输入数据。
(二) 数据类型和系统设计在设计这一步骤中需分概要设计和详细设计两步实现。
概要设计指的是，对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型；
详细设计则为定义相应的存储结构并写出各函数的伪码算法。
在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。作为概要设计的结果，应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的规格说明)，各个主要模块的算法，并画出模块之间的调用关系图。详细设计的结果是对数据结构和基本操作的规格说明作出进一步的求精，写出数据存储结构的类型定义，按照算法书写规范用类C语言写出函数形式的算法框架。在求精的过程中，应尽量避免陷入语言细节，不必过早表述辅助数据结构和局部变量。
(三) 编码实现和静态检查编码是把详细设计的结果进一步求精为程序设计语言程序。程序的每行不要超过60个字符。每个函数体，即不计首部和规格说明部分，一般不要超过40行，最长不得超过60行，否则应该分割成较小的函数。要控制if语句连续嵌套的深度。如何编写程序才能较快地完成调试是特别要注意的问题。对于编程很熟练的读者，如果基于详细设计的伪码算法就能直接在键盘上输入程序的话，则可以不必用笔在纸上写出编码，而将这一步的工作放在上机准备之后进行，即在上机调试之前直接用键盘输入。
然而，不管你是否写出编码的程序，在上机之前，认真的静态检查是必不可少的。多数初学者在编好程序后处于以下两种状态之一：一种是对自己的“精心作品“的正确性确信不疑；另一种是认为上机前的任务已经完成，纠查错误是上机的工作。这两种态度是极为有害的。事实上，非训练有素的程序设计者编写的程序长度超过50行时，极少不含有除语法错误以外的错误。上机动态调试决不能代替静态检查，否则调试效率将是极低的。
23
静态检查主要有两种方法，一是用一组测试数据手工执行程序(通常应先分模块检查)；二是通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑，在这个过程中再加入一些注解和断言。如果程序中逻辑概念清楚，后者将比前者有效。
(四)上机准备和上机调试
上机准备包括以下几个方面：
(1) 高级语言文本(体现于编译程序用户手册)的扩充和限制。例如，常用的BorlandC(C++)和MicrosoftC(C++)与标准C(C++)的差别，以及相互之间的差别。
(2) 如果使用C或C++语言，要特别注意与教科书的类C语言之间的细微差别。
(3) 熟悉机器的操作系统和语言集成环境的用户手册，尤其是最常用的命令操作，以便顺利进行上机的基本活动。
(4)掌握调试工具，考虑调试方案，设计测试数据并手工得出正确结果。
上机调试程序时要带一本高级语言教材或手册。调试最好分模块进行，自底向上，即先调试低层函数。必要时可以另写一个调用驱动程序。这种表面上麻烦的工作实际上可以大大降低调试所面临的复杂性，提高调试工作效率。
调试中遇到的各种异常现象往往是预料不到的，此时不应“冥思苦想”，而应动手确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，印出带有完整注释的且格式良好的源程序清单和结果。
(五)总结和整理实践报告
三、报告规范
报告的开头应给出题目、班级、姓名、学号和完成日期，并包括以下七个内容：
1. 需求分析
以无歧义的陈述说明程序设计的任务，强调的是程序要做什么?明确规定: (1) 输入的形式和输入值的范围； (2) 输出的形式；
(3) 程序所能达到的功能；
(4) 测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。
2. 概要设计
说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次(调用)关系。
3. 详细设计
实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法；对主程序和其他模块也都需要写出伪码算法(伪码算法达到的详细程度建议为:按照伪码算法可以在计算机键盘直接输入高级程序设计语言程序)；画出函数的调用关系图。
4. 调试分析 内容包括：
(1)调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分
24
析；
(2)算法的时空分析(包括基本操作和其他算法的时间复杂度和空间复杂度的分析)和改进设想；
(3)经验和体会等。 5. 用户使用说明
说明如何使用你编写的程序，详细列出每一步的操作步骤。 6. 测试结果
列出你的测试结果，包括输入和输出。这里的测试数据应该完整和严格，最好多于需求分析中所列。
7. 附录
带注释的源程序。可以只列出程序文件名的清单。
25