《数据结构课程实验》大纲

一、 《数据结构课程实验》的地位与作用

　　“数据结构”是计算机专业一门重要的专业技术基础课程，是计算机专业的一门核心的关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查找和排序技术，并做了性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。

　　由于以下原因，使得掌握这门课程具有较大的难度：

　　 （1） 内容丰富，学习量大，给学习带来困难；
　　（2） 贯穿全书的动态链表存储结构和递归技术是学习中的重点也是难点；
　　（3） 所用到的技术多，而在此之前的各门课程中所介绍的专业性知识又不多，因而加大了学习难度；
　　（4） 隐含在各部分的技术和方法丰富，也是学习的重点和难点。
　　
　　 根据《数据结构课程》课程本身的技术特性，设置《数据结构课程实验》实践环节十分重要。通过实验实践内容的训练，突出构造性思维训练的特征, 目的是提高学生组织数据及编写大型程序的能力。实验学时为18。


二、《数据结构课程实验》的目的和要求

　　不少学生在解答习题尤其是算法设计题时，觉得无从下手，做起来特别费劲。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。

　　为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法，如算法设计的构思方法，动态链表，算法的编码，递归技术，与特定问题相关的技术等，要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。在掌握基本算法的基础上，掌握分析、解决实际问题的能力。

三、 《数据结构课程实验》内容

课程实验共18学时，要求完成以下六个题目：
　　实习一 约瑟夫环问题（2学时）
　　　用循环链表实现约瑟夫环问题，熟悉链表结构的使用。
　　实习二 停车场管理（4学时）
　　　利用栈和队列模拟停车场管理，学习利用栈和队列解决实际问题。
　　实习三 二叉树基本操作（3学时）
　　　创建、遍历、插入、删除、显示二叉树，通过二叉树的基本操作，
　　　掌握树结构的处理方法。
　　实习四 图的基本操作（3学时）
　　　分别用邻接矩阵和邻接表实现以下操作：
　　　图的创建、遍历、插入、删除、最短路径。
　　　熟悉图的常用存储结构和基本操作。
　　实习五 哈希表设计（3学时）
　　　给定30个人的姓名，用除留余数法构造哈希函数，用线性探测再散列法处理
　　　冲突，构造哈希表，掌握哈希表的设计与使用。
　　实习六 常用排序算法的对比分析（3学时）
　　　分别实现直接插入排序、冒泡排序、简单选择排序、希尔排序、快速排序、
　　　堆排序，并随机生成30个数，比较各算法的时、空性能和稳定性。
　　　掌握常用排序算法的特点，以便根据实际情况选择使用。

四、 《数据结构课程实验》考核方式

　　采用上机情况、程序质量、实习报告相结合的形式，满分为100分。
　　1． 上机情况（30%）
　　　包括出勤情况、调试表现、是否上网、玩游戏。
　　2． 程序质量（50%）
　　3． 实习报告（20%）

实习一 线性表

　　本次实习的主要目的在于熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉各种链表的操作为侧重点。通过本次实习还可帮助读者复习高级语言的使用方法。

约瑟夫环
[问题描述]
　　约瑟夫（Joeph）问题的一种描述是：编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。
[基本要求]
　　利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。
[测试数据]
　　m的初值为20；密码：3，1，7，2，4，8，4（正确的结果应为6，1，4，7，2，3，5）。
[实现提示]
　　程序运行后首先要求用户指定初始报数上限值，然后读取各人的密码。设n≤30。
[选作内容]
　　向上述程序中添加在顺序结构上实现的部分。

长整数运算
[问题描述]
　　设计一个程序实现两个任意长的整数求和运算。
[基本要求]
　　利用双项循环链表实现长整数的存储，每个结点含一个整型变量。任何整型变量的范围是-（215-1）~（215-1）。输入和输出形式：按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开。
[测试数据]
　　（1） 0；0；应输出“0”。
　　（2） -2345,6789；-7654,3211；应输出“-1,0000,0000”。
　　（3） -9999,9999；1,0000,0000,0000；应输出“9999,0000,0001”。
　　（4） 1,0001,000；-1,0001,0001；应输出“0”。
　　（5） 1,0001,0001；-1,0001,0000；应输出“1”。
[实现提示]
　　（1） 每个结点中可以存放的最大整数为215-1=32767，才能保证两数相加不会溢出。但若这样存，即相当于按32768进制数存，在十进制数与32768进制数之间的转换十分不方便。故可以在每个结点中仅存十进制数的4位，即不超过9999的非负整数，整个链表视为万进制数。
　　（2） 可以利用头结点数据域的符号代表长整数的符号。用其绝对值表示元素结点数目。相加过程中不要破坏两个操作数链表。两操作数的头指针存于指针数组中是简化程序结构的一种方法。不能给长整数位数规定上限。
[选作内容]
　　修改上述程序，使它在整型量范围是-（2n-1）~（2n-1）的计算机上都能有效地运行。其中，n是由程序读入的参量。输入数据的分组方法可以另行规定。

实习二 栈、队列与递归算法设计

　　仅仅认识到栈和队列是两种特殊的线性表是远远不够的，本次实习的目的在于使读者深入了解栈和队列的特征，以便在实际问题背景下灵活运用它们；同时还将巩固这两种结构的构造方法，接触较复杂问题的递归算法设计。

停车场管理
[问题描述]
　　设停车场内只有一个的停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。
[测试数据]
　　设n=2,输入数据为：（‘A’，1，5），（‘A’，2，10），（‘D’，1，15），（‘A’，3， 20）， （‘A’，4，25），（‘A’，5，30），（‘D’，2，35），（‘D’，4，40），（‘E’，0，0）。其中，‘A’表示到达；‘D’表示离去，‘E’表示输入结束。
[基本要求]
　　以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车离去；则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表实现。
[实现提示]
　　需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。
[选作内容]
　　（1） 两个栈共享空间，思考应开辟数组的空间是多少？
　　（2） 汽车可有不同种类，则它们的占地面积不同，收费标准也不同，如1辆客车和1.5辆小汽车的占地面积相同，1辆十轮卡车占地面积相当于3辆小汽车的占地面积。
　　（3） 汽车可以直接从便道上开走，此时派在它前面的汽车要先开走让路，然后再依次排到队尾。
　　（4） 停放在便道上的汽车也收费，收费标准比停放在停车场的车低，请思考如何修改结构以满足这种要求。

实习三 串及其应用

　　本次实习的目的是熟悉串类型的实现方法和文本模式匹配方法，熟悉一般文字处理软件的设计方法，较复杂问题的分解求精方法，在第二次实习的基础上，进一步强化这样一个观念：程序是数据结构结合定义在其上的操作，此外还希望起到训练合作能力和熟悉文件操作的目的。本次实习的难度较大。

文学研究助手
[问题描述]
　　文学研究人员需要统计某篇英文小说中某些形容词的出现次数和位置。试写一个实现这一目标的文字统计系统，称为“文学研究助手”。
[基本要求]
　　英文小说存于一个文本文件中。待统计的词汇集合要一次输入完毕，即统计工作必须在程序的一次运行之后就全部完成。程序的输出结果是每个词的出现次数和出现位置所在行的行号，格式自行设计。
[测试数据]
　　以你的源程序模拟英文小说，程序语言保留字集作为待统计的词汇集。
[实现提示]
　　设小说中的词汇一律不跨行。这样，每读入一行，就统计每个词在这行中的出现次数。出现位置所在行的行号可以用链表存储。若某行中出现了不止一次，不必存多个相同的行号。
如果读者希望达到选作部分（1）和（2）所提出的要求，则首先应把KMP算法改写成如下的等价形式，再将它推广到多个模式的情形。
[选作内容]
　　（1） 模式匹配要基于KMP算法。
　　（2） 整个统计过程中只对小说文字扫描一遍以提高效率。
　　（3） 假设小说中的每个单词或者从行首开始，或者前置以一个空格符。利用单词匹配特点另写一个高效的统计程序，与KMP算法统计程序进行效率比较。
　　（4） 推广到更一般的模式集匹配问题，并设待查模式串可以跨行（提示：定义操作getachar）

简单行编辑程序
[问题描述]
　　文本编辑程序是利用计算机进行文字加工的基本软件工具，实现对文本文件的插入、删除等修改操作。限制这些操作以行为单位进行的编辑程序称为行编辑程序。
被编辑的文本文件可能很大，全部读入编辑程序的数据空间（内存）的做法既不经济，也不总能实现。一种解决方法是逐段地编辑。任何时刻只把待编辑文件的一段放在内存，称为活区。试按照这种方法实现一个简单的行编辑程序。设文件每行不超过320个字符，很少超过80字符。
[基本要求]
　　实现以下4条基本编辑命令：
　　（1） 行插入。格式：i<行号><回车><文本><回车>
　　　　　将<文本>插入活区中第<行号>行之后
　　（2）行删除。格式：d<行号1>[□<行号2>]<回车>
　　　　　删除活区中第<行号1>行（到第<行号2>行）。两种格式的例子是：“d10↙”和“d10□14↙”
　　（3）活区切换。格式：n<回车>
　　　　　将活区写入输出文件，并从输入文件中读入下一段，作为新的活区。
　　（4）活区显示。格式：p<回车>
　　　　　逐页地（每页20行）显示活区内容，每显示一页之后请用户决定是否继续显示以后各页（如果存在）。印出的每一行要前置以行号和一个空格符，行号固定占4位，增量为1。
　　　　　各条命令中的行号均须在活区中各行行号范围之内，只有插入命令的行号可以等于活区第一行行号减1，表示插入当前屏幕中第一行之前，否则命令参数非法。
[实现提示]
　　（1） 设活区的大小用行数activemaxlen（可设为100）来描述。考虑到文本文件行长通常为正态分布，且峰值在60到70之间，用320×activemaxlen大小的字符数组实现存储将造成大量浪费。可以以标准行块为单位为各行分配存储，每个标准行块含81个字符。这些行块可以组成一个数组，也可以利用动态链表连接起来。一行文字可能占多个行块。行尾可用一个特殊的ASCII字符（如(012)8）标识。此外，还应记住活区起始行号。行插入将引起随后各行行号的顺序下推。
　　（2） 初始化过程包括：请用户提供输入文件名（空串表示无输入文件）和输出文件名，两者不能相同。然后尽可能多地从输入文件中读入各行，但不超过activemaxlen-x。x的值可以自定，例如20。
　　（3） 在执行行插入命令的过程中，每接收到一行时到要检查活区大小是否已达activemaxlen。如果是，则为了在插入这一行之后仍保持活区大小不超过activemaxlen，应将插入点之前的活区部分中第一行输出到输出文件中；若插入点为第一行之前，则只得将新插入的这一行输出。
　　（4） 若输入文件尚未读完，活区切换命令可将原活区中最后几行留在活区顶部，以保持阅读连续性；否则，它意味着结束编辑或开始编辑另一个文件。
　　（5） 可令前三条命令执行后自动调用活区显示。
[选作内容]
　　（1） 对于命令格式非法等一切错误作严格检查和适当处理。
　　（2） 加入更复杂的编辑操作，如对某行进行串替换；在活区内进行模式匹配等，格式可以为S<行号>@<串1>@<串2><回车>和m<串><回车>。

实习四 树、图及其应用

　　树和图是两种应用极为广泛的数据结构，也是这门课程的重点。它们的特点在于非线性。广义表本质上是树结构；稀疏矩阵的十字链表存储结构也是图的一种存储结构，故也把它们归在这次实习中。本章实习继续突出了数据结构加操作的程序设计观点，但根据这两种结构的非线性特点，将操作进一步集中在遍历操作上，因为遍历操作是其他众多操作的基础。遍历逻辑的（或符号形式的）结构，访问动作可是任何操作。本次实习还希望达到熟悉各种存储结构的特征，以及如何应用树和图结构解决具体问题（即原理与应用的结合）等目的。

图遍历的演示
[问题描述]
　　很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序，演示连通的无向图上行边全部结点的操作。
[基本要求]
　　以邻接多重表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集。
[实现提示]
　　设图的结点不超过30个，每个结点用一个编号表示（如果一个图有n个结点，则它们的编号分别为1,2,…,n）。通过输入图的全部边输入一个图，每个边为一个数对，可以对边的输入顺序作出某种限制。注意，生成树的边是有向边，端点顺序不能颠倒。
[选作内容]
　　（1） 借助于栈类型（自己定义和实现）将深度优先遍历用非递归算法实现。
　　（2） 以邻接表为存储结构建立深度优先生成树和广度优先生成树，再按凹入表或树形打印生成树。

实习五 查找和排序

本次实习旨在集中对几个专门的问题作较为深入的探讨和理解，也不强调对某些特定的编程技术的训练。

哈希表设计
[问题描述]
　　 针对某个集体中人名设计一个哈希表，使得平均查找长度不超过R，并完成相应的建表和查表程序。
[基本要求]
　　假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用线性探测再散列法或链地址法处理冲突。
[测试数据]
　　取读者周围较熟悉的30个人名。
[选作内容]
　　（1） 从教科书上介绍的集中哈希函数构造方法中选出适用者并设计几个不同的哈希函数，比较他们的地址冲突率（可以用更大的名字集合作实验）。
　　（2） 研究这30个人名的特点，努力找一个哈希函数，使得对于不同的拼音名一定不发生地址冲突。
　　（3） 在哈希函数确定的前提下尝试各种不同处理冲突的方法，考察平均查找长度的变化和造好的哈希表中关键字的聚集性。

内部排序算法比较
[问题描述]
　　各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。
[基本要求]
　　（1） 对以下10种常用的内部排序算法进行比较：直接插入排序；折半折入排序；二路插入排序；希尔排序；起泡排序；快速排序；简单选择排序；堆排序；归并排序；基数排序。
　　（2） 待排序表的表长不少于100；其中的数据要用伪随机数产生程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字移动次数（关键字交换计为3次移动）。
[测试数据]
　　由随机产生器决定。
[实现提示]
　　主要工作是设法在程序中适当的地方插入计数操作。程序还可以包括计算几组数据得出结果波动大小的解释。注意分块调试的方法。
[选作内容]
　　对不同的输入表长做试验，观察检查两个指标相关于表长的变化关系。还可以对稳定性做验证。

实验指导书概述

　　“数据结构”是计算机专业一门重要的专业技术基础课程，是一门关键性核心课程。本课程系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了多种常用的查找和排序技术，并对其进行了性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。

　　 由于以下原因，使得掌握这门课程具有较大难度：
　　 　　

·  内容多，时间短，给学习带来困难；
　　

·  贯穿全书的动态链表存储结构和递归技术是学习中的重点和难点；
　　

·  隐含在各部分的技术和方法丰富，也是学习的重点和难点；
　　

·  先修课程中所介绍的专业性知识不多，加大了学习难度。
　　
　　 由于数据结构课程的技术性与实践性，《数据结构课程实验》的设置十分必要。为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法，如算法设计的构思方法，动态链表，算法的编码，递归技术，与特定问题相关的技术等，要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。在掌握基本算法的基础上，掌握分析、解决实际问题的能力。通过实验实践内容的训练，突出构造性思维训练的特征, 提高学生组织数据及编写大型程序的能力。
　　
　　 上机实习是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。较大的实习题比平时的习题要复杂得多，也更接近实际。实习着眼于原理与应用的结合点，使学生学会如何把书上学到的知识用于解决实际问题，培养软件工作所需要的动手能力。实习还能使书上的知识变“活”，达到深化理解和灵活掌握教学内容的目的。平时的练习较偏重于如何编写功能单一的“小”算法，而实习题是软件设计的综合训练，包括问题分析，总体结构设计，用户界面设计，程序设计基本技能和技巧，多人合作，以至一整套软件工作规范的训练和科学作风的培养。此外，还有很重要的一点是：机器是比任何教师都严格的检查者。

　　 为了达到上述目的，本书安排了6个主实习单元，其中实习0的训练重点是抽象数据类型的定义与实现方法，其它各单元的训练重点在于基本的数据结构和经典算法。各实习单元与教科书的各章只具有粗略的对应关系，一个实习题可能涉及几部分教学内容。在每个实习单元中安排有难度不等的2—5个实习题，每人可以从中选做一个实习题。建议选做难度略高于自己所做过的最难题目的难度，切忌过分追求难题。较大的题目适合于多人合作。

　　 每个实习题采取了统一的格式，由问题描述、基本要求、测试数据、实现提示和选做内容等5个部分组成。

　　 问题描述旨在为读者建立问题提出的背景环境，指明问题“是什么”；

　　 基本要求则对问题进一步求精，划出问题的边界，指出具体的参量或前提条件，并规定该题的最低限度要求；

　　 测试数据部分旨在为检查学生上机作业提供方便，在完成实习题时应自己设计完整和 严格的测试方案，当数据输入量较大时，提倡以文件形式向程序提供输入数据；
　　
　　 实现提示对实现中的难点及其解法思路等问题作了简要提示，个别问题给出了参考实现；

　　 选做内容向那些尚有余力的读者提出了更严峻的挑战，同时也能开拓其他读者的思路，在完成基本要求时就力求避免就事论事的不良思想方法，尽可能寻求具有普遍意义的解法，使得程序结构合理，容易修改扩充。

　　 书中题目设计得比较详细，给出了问题说明和问题分解求精的范例，使读者在无形中学会模仿，它起到把读者的思路引上正轨的作用，避免不良结构程序和坏习惯，同时也传授了系统划分方法和程序设计的一些具体技术，保证实现预定的训练意图，使某些难点和重点不会被绕过去，而且也便于教学检查。题目设计策略是：一方面使其难度和工作量都较大，另—方面给读者提供的辅助和可以模仿的部分也较多。当然还应指出的是，提示的实现方法未必是最好的，读者不应拘泥于此，而应争取找出更好的方法和结构。
在实现的时候应注意，要尽量减少依赖于具体机器计算环境的用法，若使用，也应在注释中指出。这样得出的程序易于在不同机器上运行，有好的可移植性。C语言是结构化程序设计语言，具有递归能力，可移植性也较好，是特别推荐的实现语言。

　　 本书的一个特点是为实习制定了严格的规范。一种普遍存在的错误观念是，调试程序全凭运气。学生花2个小时的机上时间只找出一个错误，甚至一无所获的情况是常见的。其原因在于，很多人只认识到找错误，而没有认识到努力预先避免错误的重要性，也不知道应该如何努力。实际上，结构不好、思路和概念不清的程序可能是根本无法调试正确的。严格按照实习步骤规范进行实习，不但能有效地避免上述种种问题，更重要的是有利于培养软件工作者不可缺少的科学工作方法和作风。

　　 在附录中提供了一个完整的实习报告示例，在起到实习报告规格范例作用的同时，还隐含地提供了很多有益的东西，比如基于数据类型的系统划分方法以及所提倡的程序设计风格等等。计算机学科在不断发展，可以使用的语言工具越来越丰富，在本书中的实习示例是应用面向过程的语言进行设计和编程，同样的实习题，也可以用面向对象的语言来实现。希望书中的实习报告示例能起到一个抛砖引玉的作用，以引来读者更多更优良的设计范例。

实习步骤

　　随着计算机性能的提高，它所面临的软件开发的复杂度也日趋增加，因此软件开发需要系统的方法。一种常用的软件开发方法，是将软件开发过程分为分析、设计、实现和维护四个阶段。虽然数据结构课程中的实习题的复杂度远不如实际中真正的软件系统，但为了培养一个软件工作者所应具备的科学工作的方法和作风，我们制订了如下所述完成实习的5个步骤：

1．问题分析和任务定义

　　 通常，实习题目的陈述比较简洁，或者说有模棱两可的含义。因此，在进行设计之前，首先应该充分地分析和理解问题，明确问题要求做什么，限制条件是什么。注意：本步骤强调的是做什么，而不是怎么做。对问题的描述应避开算法和所涉及的数据类型，而是对所需完成的任务作出明确的回答。例如：输入数据的类型、值的范围以及输入的形式；输出数据的类型、值的范围及输出的形式；若是会话式的输入，则结束标志是什么，是否接受非法的输入，对非法输入的回答方式是什么等等。这一步还应该为调试程序准备好测试数据，包括合法的输入数据和非法形式输入的数据。

2．数据类型和系统设计

　　 在设计这一步骤中需分逻辑设计和详细设计两步实现。逻辑设计指的是，对问题描述中 涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程 序模块和各抽象数据类型。详细设计则为定义相应的存储结构并写出各过程和函数的伪码 算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。作为逻辑设计的结果，应写出每个抽象数据类型的定义（包括数据结构的描述和每个基本操作的规格说明），各个主要模块的算法，并画出模块之间的调用关系图。详细设汁的结果是对数据结构和基本操作的规格说明作出进一步的求精，写出数据存储结构的类型定义，按照算法书写规范用类C语言写出过程或函数形式的算法框架。在求精的过程中，应尽量避免陷入语言细节，不必过早表述辅助数据结构和局部变量。

3．编码实现和静态检查

　　 编码是把详细设计的结果进一步求精为程序设计语言程序。如何编写程序才能较快地完成调试是特别要注意的问题。程序的每行不要超过60个字符。每个过程（函数）体一般不要超过40行，最长不得超过60行，否则应该分割成较小的过程（函数）。要控制if语句连续嵌套的深度，分支过多时应考虑使用switch语句。对函数功能和重要变量进行注释。一定要按格式书写程序，分清每条语句的层次，对齐括号，这样便于发现语法错误。

　　 在上机之前，应该用笔在纸上写出详细的程序编码，并做认真地静态检查。多数初学者在编好程序后处于以下两种状态之一：一种是对自己的“精心作品”的正确性确信不疑；另一种是认为上机前的任务已经完成，纠查错误是上机的工作。这两种态度是极为有害的。对一般的程序设计者而言，当编写的程序长度超过50行时，通常会含有语法错误或逻辑错误。上机动态调试决不能代替静态检查，否则调试效率将是极低的。静态检查主要有两种方法，一是用一组测试数据手工执行程序（通常应先检查单个模块）；二是通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑，在这个过程中再加入一些注解。

4．上机准备和上机调试

　　 上机准备包括以下几个方面：

　　（1）熟悉C语言用户手册或程序设计指导书。
　　（2）注意Turbo C、VC与标准C语言之间的细微差别。
　　（3） 熟悉机器的操作系统和语言集成环境的用户手册，尤其是最常用的命令操作，以便 顺利进行上机的基本活动。
　　（4） 掌握调试工具，考虑调试方案，设计测试数据并手工得出正确结果。“磨刀不误砍柴工”。学生应该熟练运用高级语言的程序调试器DEBUG调试程序。

　　 上机调试程序时要带一本高级语言教材或手册。调试最好分模块进行，自底向上，即先调试低层过程或函数。必要时可以另写一个调用驱动程序。这种表面上麻烦的工作实际上可以大大降低调试所面临的复杂性，提高调试工作效率。

　　 在调试过程中可以不断借助DEBUG的各种功能，提高调试效率。调试中遇到的各种异常现象往往是预料不到的，此时不应“苦思冥想”，而应借助系统提供的调试工具确定错误。调试正确后，认真整理源程序及其注释，印出带有完整注释的且格式良好的源程序清单和结果。

5．总结和整理实习报告

实习报告规范

　　实习报告的开头应给出题目、班级、姓名、学号和完成日期，并包括以下7个内容：

1．需求分析

　　以无歧义的陈述说明程序设计的任务，强调的是程序要做什么？并明确规定：

　　(1) 输入的形式和输入值的范围；

　　(2) 输出的形式；

　　(3) 程序所能达到的功能；

　　(4) 测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。

2．概要设计

　　说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次(调用)关系。

3．详细设计

　　实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法；对主程序和其他模块也都需要写出伪码算法(伪码算法达到的详细程度建议为：按照伪码算法可以在计算机键盘直接输入高级程序设计语言程序)；画出函数和过程的调用关系图。

4．调试分析

　　内容包括：

　　a．调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析；

　　b．算法的时空分析(包括基本操作和其他算法的时间复杂度和空间复杂度的分析)和

　　改进设想；

　　c．经验和体会等。

5．用户使用说明

　　说明如何使用你编写的程序，详细列出每一步的操作步骤。

6．测试结果

　　列出你的测试结果，包括输入和输出。这里的测试数据应该完整和严格，最好多于需求分析中所列。

7．附录

　　带注释的源程序。如果提交源程序软盘，可以只列出程序文件名的清单。

　　在以下各实习单元中都提供了实习报告实例。值得注意的是，实习报告的各种文档资 料，如：上述中的前三部分要在程序开发的过程中逐渐充实形成，而不是最后补写(当然可以也应该最后用实验报告纸誊清或打印)。

实习题目

实习○ 抽象数据类型

三元组ADT

[问题描述]
　　设计实现抽象数据类型“三元组”。每个三元组由任意三个实数的序列构成，基本操作包括：创建一个三元组，取三元组的任意一个分量，置三元组的任意一个分量，求三元组的最大分量，求三元组的最小分量，两个三元组的对应分量相加或相减，给三元组的各分量同乘一个比例因子，显示三元组，销毁三元组等。

[基本要求]
　　实现创建一个三元组，取三元组的任意一个分量，置三元组的任意一个分量，求三元组的最大分量，求三元组的最小分量，显示三元组等基本操作。

[测试数据]
　　由学生任意指定。

[实现提示]
　　用结构体封装“三元组”的三个分量，并利用typedef对结构体或结构体指针重新命名。注意：如果要实现销毁三元组，则应利用typedef对结构体指针重新命名，并使用C语言的动态分配库函数。

[选作内容]
　　实现两个三元组的对应分量相加或相减，给三元组的各分量同乘一个比例因子，销毁三元组等操作。

有理数ADT

[问题描述]
　　设计实现抽象数据类型“有理数”。

[基本要求]
　　实现有理数的加法、减法，以及求有理数的分子、分母等基本操作。

[测试数据]
　　由学生依据软件工程的测试技术自己确定。注意测试边界数据，如有理数0。

[实现提示]
　　用结构体封装与“有理数”对应的分子和分母。

[选作内容]
　　实现有理数的乘法、除法运算。

复数ADT

[问题描述]
　　设计实现抽象数据类型“复数”。

[基本要求]
　　实现复数的加法、减法、乘法，以及求复数的实部、虚部等基本操作。

[测试数据]
　　由学生依据软件工程的测试技术自己确定。注意测试边界数据，如复数0。

[实现提示]
　　用结构体封装与“复数”对应的实部、虚部。

[选作内容]
　　实现复数的除法运算。

实习一 线性表

　　本次实习的主要目的在于熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉各种链表的操作为侧重点。通过本次实习还可帮助读者复习高级语言的使用方法。

城市链表

[问题描述]
　　将若干城市的信息，存入一个带头结点的单链表。结点中的城市信息包括：城市名，城市的位置坐标。要求能够利用城市名和位置坐标进行有关查找、插入、删除、更新等操作。

[基本要求]
　　（1） 给定一个城市名，返回其位置坐标；
　　（2） 给定一个位置坐标P和一个距离D，返回所有与P的距离小于等于D的城市。

[测试数据]
　　由学生依据软件工程的测试技术自己确定。注意测试边界数据。

约瑟夫环

[问题描述]
　　约瑟夫（Joeph）问题的一种描述是：编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。

[基本要求]
　　利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。

[测试数据]
　　m的初值为20；密码：3，1，7，2，4，8，4（正确的结果应为6，1，4，7，2，3，5）。

[实现提示]
　　程序运行后首先要求用户指定初始报数上限值，然后读取各人的密码。设n≤30。

[选作内容]
　　向上述程序中添加在顺序结构上实现的部分。

线性表的逆置

[问题描述]
　　分别以不同存储结构实现线性表的就地逆置。线性表的就地逆置就是在原表的存储空间内将线性表（a1,a2,a3,…,an）逆置为（an，an-1，…，a2，a1）。

[基本要求]
　　用顺序存储结构实现线性表的就地逆置，并将结果输出。

[测试数据]
　　由学生依据软件工程的测试技术自己确定。注意测试边界数据，如空表。

[实现提示]
　　设三个连续的指针，分别指向当前结点、当前结点的前趋、当前结点的后继。

[选作内容]
　　利用单链表作为存储结构。首先先建立线性表的带头结点的单链表表示形式，之后在不借助辅助结点空间的情况下实现单链表的逆置，并将结果输出。

长整数运算

[问题描述]
　　设计一个程序实现两个任意长的整数求和运算。

[基本要求]
　　利用双项循环链表实现长整数的存储，每个结点含一个整型变量。任何整型变量的范围是　-（215-1）~（215-1）。输入和输出形式：按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开。

[测试数据]
　　（1） 0；0；应输出“0”。
　　（2） -2345,6789；-7654,3211；应输出“-1,0000,0000”。
　　（3） -9999,9999；1,0000,0000,0000；应输出“9999,0000,0001”。
　　（4） 1,0001,000；-1,0001,0001；应输出“0”。
　　（5） 1,0001,0001；-1,0001,0000；应输出“1”。

[实现提示]
　　（1） 每个结点中可以存放的最大整数为215-1=32767，才能保证两数相加不会溢出。但若这样存，即相当于按32768进制数存，在十进制数与32768进制数之间的转换十分不方便。故可以在每个结点中仅存十进制数的4位，即不超过9999的非负整数，整个链表视为万进制数。
　　（2） 可以利用头结点数据域的符号代表长整数的符号。用其绝对值表示元素结点数目。相加过程中不要破坏两个操作数链表。两操作数的头指针存于指针数组中是简化程序结构的一种方法。不能给长整数位数规定上限。

[选作内容]
　　修改上述程序，使它在整型量范围是-（2n-1）~（2n-1）的计算机上都能有效地运行。其中，n是由程序读入的参量。输入数据的分组方法可以另行规定。

实习二 栈、队列与递归算法设计

　　仅仅认识到栈和队列是两种特殊的线性表是远远不够的，本次实习的目的在于使读者深入了解栈和队列的特征，以便在实际问题背景下灵活运用它们；同时还将巩固这两种结构的构造方法，接触较复杂问题的递归算法设计。

数制转换问题

[问题描述]
　　将十进制数N和其它d进制数的转换是计算机实现计算的基本问题，其解决方案很多，其中最简单方法基于下列原理：即除d取余法。例如：（1348）10=（2504）8
　　N　　N div 8　　N mod 8
　1348 　　168 　　　　4
　168　　　21　　　　　0
　21 　　　2 　　　　　5
　2　　　　0 　　　　　2
　　从中我们可以看出，最先产生的余数4是转换结果的最低位，这正好符合栈的特性即后进先出的特性。所以可以用顺序栈来模拟这个过程。

[基本要求]
　　对于键盘输入的任意一个非负的十进制整数，打印输出与其等值的八进制数。由于上述的计算过程是从低位到高位顺序产生的八进制数的各个数位，而打印输出，一般来说应从高位到地位进行，恰好和计算过程相反。因此可以先将计算过程中得到的八进制数的各位进栈，待相对应的八进制数的各位均产生以后，再使其按顺序出栈，并打印输出。即得到了与输入的十进制数相对应的八进制数。

[测试数据]
　　由学生依据软件工程的测试技术自己确定。注意测试边界数据。

回文判断

[问题描述]
　　试写一个算法，判断依次读入的一个以@为结束符的字母序列，是否为形如‘序列1　&　序列2’模式的字符序列。其中序列1和序列2　中都不含字符‘&’，且序列2　是序列1的逆序列。例如，‘a+b&b+a’是属该模式的字符序列，而‘１+３&３－１’则不是。

[实现提示]
　　首先，序列1进栈，然后序列1出栈并与序列2比较。

[测试数据]
　　由学生依据软件工程的测试技术自己确定。注意测试边界数据，如序列1和序列2均为空串。

商品货架管理

[问题描述]
　　商品货架可以看成一个栈，栈顶商品的生产日期最早，栈底商品的生产日期最近。　上货时，需要倒货架，以保证生产日期较近的商品在较下的位置。

[基本要求]
　　针对一种特定商品，实现上述管理过程。

[实现提示]
　　用栈模拟货架和周转空间。

[测试数据]
　　由学生依据软件工程的测试技术自己确定。注意测试边界数据，如空栈。

括号匹配的检验

[问题描述]
　　假设表达式中允许有两种括号：圆括号和方括号，其嵌套的顺序随意，即（（）[ ]）或
[（[ ] [ ]）]等为正确格式，[（ ]）或（（（]均为不正确的格式。检验括号是否匹配的方法可用“期待的紧迫程度”这个概念来描述。例如：考虑下列的括号序列：
　　[　(　[　]　[　]　)　]
　　1　2　3　4　5　6　7　8
　　当计算机接受了第1个括号以后，他期待着与其匹配的第8个括号的出现，然而等来的却是第2个括号，此时第1个括号“[”只能暂时靠边，而迫切等待与第2个括号相匹配的 第7个括号“）”的出现，类似的，因只等来了第3个括号“[”，此时，其期待的紧迫程度较第2个括号更紧迫，则第2个括号只能靠边，让位于第3个括号，显然第3个括号的期待紧迫程度高于第2个括号，而第2个括号的期待紧迫程度高于第1个括号；在接受了第4个括号之后，第3个括号的期待得到了满足，消解之后，第2个括号的期待匹配就成了最急迫的任务了，…… ，依次类推。可见这个处理过程正好和栈的特点相吻合。

[基本要求]
　　读入圆括号和方括号的任意序列，输出“匹配”或“此串括号匹配不合法”。

[测试数据]
　　输入（[ ]（）），结果“匹配”
　　输入 [（ ）]，结果“此串括号匹配不合法”

[实现提示]
　　设置一个栈，每读入一个括号，若是左括号，则作为一个新的更急迫的期待压入栈中；若是右括号，并且与当前栈顶的左括号相匹配，则将当前栈顶的左括号退出，继续读下一个括号，如果读入的右括号与当前栈顶的左括号不匹配，则属于不合法的情况。在初始和结束时，栈应该是空的。

[选作内容]
　　考虑增加大括号的情况。

停车场管理

[问题描述]
　　设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。

[测试数据]
　　设n=2,输入数据为：（‘A’，1，5），（‘A’，2，10），（‘D’，1，15），（‘A’，3， 20）， （‘A’，4，25），（‘A’，5，30），（‘D’，2，35），（‘D’，4，40），（‘E’，0，0）。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，其中，‘A’表示到达；‘D’表示离去，‘E’表示输入结束。

[基本要求]
　　以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车离去；则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表实现。

[实现提示]
　　需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。

[选作内容]
　　（1） 两个栈共享空间，思考应开辟数组的空间是多少？
　　（2） 汽车可有不同种类，则它们的占地面积不同，收费标准也不同，如1辆客车和1.5辆小汽车的占地面积相同，1辆十轮卡车占地面积相当于3辆小汽车的占地面积。
　　（3） 汽车可以直接从便道上开走，此时排在它前面的汽车要先开走让路，然后再依次排到队尾。
　　（4） 停放在便道上的汽车也收费，收费标准比停放在停车场的车低，请思考如何修改结构以满足这种要求。

实习三 串及其应用

　　本次实习的目的是熟悉串类型的实现方法和文本模式匹配方法，熟悉一般文字处理软件的设计方法，较复杂问题的分解求精方法，在第二次实习的基础上，进一步强化这样一个观念：程序是数据结构结合定义在其上的操作，此外还希望起到训练合作能力和熟悉文件操作的目的。本次实习的难度较大。

文学研究助手

[问题描述]
　　文学研究人员需要统计某篇英文小说中某些形容词的出现次数和位置。试写一个实现这一目标的文字统计系统，称为“文学研究助手”。

[基本要求]
　　英文小说存于一个文本文件中。待统计的词汇集合要一次输入完毕，即统计工作必须在程序的一次运行之后就全部完成。程序的输出结果是每个词的出现次数和出现位置所在行的行号，格式自行设计。

[测试数据]
　　以你的源程序模拟英文小说，程序语言保留字集作为待统计的词汇集。

[实现提示]
　　设小说中的词汇一律不跨行。这样，每读入一行，就统计每个词在这行中的出现次数。出现位置所在行的行号可以用链表存储。若某行中出现了不止一次，不必存多个相同的行号。
　　如果读者希望达到选作部分（1）和（2）所提出的要求，则首先应把KMP算法改写成如下的等价形式，再将它推广到多个模式的情形。

[选作内容]
　　（1） 模式匹配要基于KMP算法。
　　（2） 整个统计过程中只对小说文字扫描一遍以提高效率。
　　（3） 假设小说中的每个单词或者从行首开始，或者前置以一个空格符。利用单词匹配特点另写一个高效的统计程序，与KMP算法统计程序进行效率比较。
　　（4） 推广到更一般的模式集匹配问题，并设待查模式串可以跨行（提示：定义操作getachar）

简单行编辑程序

[问题描述]
　　文本编辑程序是利用计算机进行文字加工的基本软件工具，实现对文本文件的插入、删除等修改操作。限制这些操作以行为单位进行的编辑程序称为行编辑程序。
　　被编辑的文本文件可能很大，全部读入编辑程序的数据空间（内存）的做法既不经济，也不总能实现。一种解决方法是逐段地编辑。任何时刻只把待编辑文件的一段放在内存，称为活区。试按照这种方法实现一个简单的行编辑程序。设文件每行不超过320个字符，很少超过80字符。

[基本要求]
　　实现以下4条基本编辑命令：
　　（1） 行插入。格式：i<行号><回车><文本><回车>
　　　　　将<文本>插入活区中第<行号>行之后
　　（2）行删除。格式：d<行号1>[□<行号2>]<回车>
　　　　　删除活区中第<行号1>行（到第<行号2>行）。两种格式的例子是：“d10↙”和“d10□14↙”
　　（3）活区切换。格式：n<回车>
　　　　　将活区写入输出文件，并从输入文件中读入下一段，作为新的活区。
　　（4）活区显示。格式：p<回车>
　　逐页地（每页20行）显示活区内容，每显示一页之后请用户决定是否继续显示以后各页（如果存在）。印出的每一行要前置以行号和一个空格符，行号固定占4位，增量为1。
　　各条命令中的行号均须在活区中各行行号范围之内，只有插入命令的行号可以等于活区第一行行号减1，表示插入当前屏幕中第一行之前，否则命令参数非法。

[测试数据]
　　由学生依据软件工程的测试技术自己确定。注意测试边界数据，如首行、尾行。

[实现提示]
　　（1） 设活区的大小用行数activemaxlen（可设为100）来描述。考虑到文本文件行长通常为正态分布，且峰值在60到70之间，用320×activemaxlen大小的字符数组实现存储将造成大量浪费。可以以标准行块为单位为各行分配存储，每个标准行块含81个字符。这些行块可以组成一个数组，也可以利用动态链表连接起来。一行文字可能占多个行块。行尾可用一个特殊的ASCII字符（如(012)8）标识。此外，还应记住活区起始行号。行插入将引起随后各行行号的顺序下推。
　　（2） 初始化过程包括：请用户提供输入文件名（空串表示无输入文件）和输出文件名，两者不能相同。然后尽可能多地从输入文件中读入各行，但不超过activemaxlen-x。x的值可以自定，例如20。
　　（3） 在执行行插入命令的过程中，每接收到一行时到要检查活区大小是否已达activemaxlen。如果是，则为了在插入这一行之后仍保持活区大小不超过activemaxlen，应将插入点之前的活区部分中第一行输出到输出文件中；若插入点为第一行之前，则只得将新插入的这一行输出。
　　（4） 若输入文件尚未读完，活区切换命令可将原活区中最后几行留在活区顶部，以保持阅读连续性；否则，它意味着结束编辑或开始编辑另一个文件。
　　（5） 可令前三条命令执行后自动调用活区显示。

[选作内容]
　　（1） 对于命令格式非法等一切错误作严格检查和适当处理。
　　（2） 加入更复杂的编辑操作，如对某行进行串替换；在活区内进行模式匹配等，格式可以为S<行号>@<串1>@<串2><回车>和m<串><回车>。

实习四 树、图及其应用

　　树和图是两种应用极为广泛的数据结构，也是这门课程的重点。它们的特点在于非线性。广义表本质上是树结构；稀疏矩阵的十字链表存储结构也是图的一种存储结构，故也把它们归在这次实习中。本章实习继续突出了数据结构加操作的程序设计观点，但根据这两种结构的非线性特点，将操作进一步集中在遍历操作上，因为遍历操作是其他众多操作的基础。遍历逻辑的（或符号形式的）结构，访问动作可是任何操作。本次实习还希望达到熟悉各种存储结构的特征，以及如何应用树和图结构解决具体问题（即原理与应用的结合）等目的。

二叉树的建立与遍历

[问题描述]
　　建立一棵二叉树，并对其进行遍历（先序、中序、后序），打印输出遍历结果。

[基本要求]
　　从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），并采用递归算法对其进行遍历（先序、中序、后序），将遍历结果打印输出。

[测试数据]
　　ABCффDEфGффFффф（其中ф表示空格字符）
　　则输出结果为 先序：ABCDEGF
　　中序：CBEGDFA
　　后序：CGBFDBA

[选作内容]
　　采用非递归算法实现二叉树遍历。

打印二叉树结构

[问题描述]
　　按凹入表形式横向打印二叉树结构，即二叉树的根在屏幕的最左边，二叉树的左子树在屏幕的下边，二叉树的右子树在屏幕的上边。
　　例如：

[测试数据]
　　由学生依据软件工程的测试技术自己确定。注意测试边界数据，如空二叉树。
[实现提示]
　　（1）利用RDL遍历方法；
　　（2）利用结点的深度控制横向位置。

打印树结构

[问题描述]
按凹入表形式打印树形结构。
例如：

[测试数据]
　　由学生依据软件工程的测试技术自己确定。注意测试边界数据，如空树。

[实现提示]
　　（1）利用树的先根遍历方法；
　　（2）利用结点的深度控制横向位置。

图遍历的演示

[问题描述]
　　很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序，演示无向图的遍历操作。

[基本要求]
　　以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集。

[测试数据]
　　由学生依据软件工程的测试技术自己确定。注意测试边界数据，如单个结点。

[实现提示]
　　设图的结点不超过30个，每个结点用一个编号表示（如果一个图有n个结点，则它们的编号分别为1,2,…,n）。通过输入图的全部边输入一个图，每个边为一个数对，可以对边的输入顺序作出某种限制。注意，生成树的边是有向边，端点顺序不能颠倒。

[选作内容]
　　（1） 借助于栈类型（自己定义和实现）将深度优先遍历用非递归算法实现。
　　（2） 以邻接多重表为存储结构建立深度优先生成树和广度优先生成树，再按凹入表或树形打印生成树
　　（3） 实现有向图的遍历操作。

实习五 查找和排序

　　本次实习旨在集中对几个专门的问题作较为深入的探讨和理解，不强调对某些特定的编程技术的训练。

二叉排序树

[问题描述]
　　从键盘读入一组数据，建立二叉排序树并对其进行查找、遍历、格式化打印等有关操作。

[基本要求]
　　建立二叉排序树并对其进行查找，包括成功和不成功两种情况，并给出查找长度。

[测试数据]
由学生依据软件工程的测试技术自己确定。注意测试边界数据。

[选作内容]
实现二叉排序树的插入、删除操作。

哈希表设计

[问题描述]
　　针对某个集体中人名设计一个哈希表，使得平均查找长度不超过R，并完成相应的建表和查表程序。

[基本要求]
　　假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用线性探测再散列法或链地址法处理冲突。

[测试数据]
　　取读者周围较熟悉的30个人名。

[选作内容]
　　（1） 从教科书上介绍的集中哈希函数构造方法中选出适用者并设计几个不同的哈希函数，比较他们的地址冲突率（可以用更大的名字集合作实验）。
　　（2） 研究这30个人名的特点，努力找一个哈希函数，使得对于不同的拼音名一定不发生地址冲突。
　　（3） 在哈希函数确定的前提下尝试各种不同处理冲突的方法，考察平均查找长度的变化和造好的哈希表中关键字的聚集性。

内部排序算法比较

[问题描述]
　　各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。

[基本要求]
　　（1） 对以下10种常用的内部排序算法进行比较：直接插入排序；折半折入排序；二路插入排序；希尔排序；起泡排序；快速排序；简单选择排序；堆排序；归并排序；基数排序。
　　（2） 待排序表的表长不少于100；其中的数据要用伪随机数产生程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字移动次数（关键字交换计为3次移动）。

[测试数据]
　　由随机产生器决定。

[实现提示]
　　主要工作是设法在程序中适当的地方插入计数操作。程序还可以包括计算几组数据得出结果波动大小的解释。注意分块调试的方法。

[选作内容]
　　对不同的输入表长做试验，观察检查两个指标相关于表长的变化关系。还可以对稳定性做验证。

统计成绩

[问题描述]
　　给出n个学生的m门考试的成绩表，每个学生的信息由学号、姓名以及各科成绩组成。对学生的考试成绩进行有关统计，并打印统计表。

[基本要求]
　　（1） 按总数高低次序，打印出名次表，分数相同的为同一名次；
　　（2） 按名次打印出每个学生的学号、姓名、总分以及各科成绩。

[测试数据]
　　由学生依据软件工程的测试技术自己确定。注意测试边界数据。

[选作内容]
　　对各科成绩设置不同的权值。

实验计划

实验报告示例

__________级 __________班 _______年_______月_____日
姓名____________ 学号____________ 电话_____________

1．实验题目

　　编制一个演示单链表插入、删除、查找等操作的程序

2．需求分析

　　本演示程序用TC编写，完成单链表的生成，任意位置的插入、删除，以及确定某一元素在单链表中的位置。
　　① 输入的形式和输入值的范围：插入元素时需要输入插入的位置和元素的值；删除元素时输入删除元素的位置；查找操作时需要输入元素的值。在所有输入中，元素的值都是整数
　　② 输出的形式：在所有三种操作中都显示操作是否正确以及操作后单链表的内容。其中删除操作后显示删除的元素的值，查找操作后显示要查找元素的位置。
　　③ 程序所能达到的功能：完成单链表的生成（通过插入操作）、插入、删除、查找操作
　　④ 测试数据：
　　　A． 插入操作中依次输入11，12，13，14，15，16，生成一个单链表
　　　B． 查找操作中依次输入12，15，22返回这3个元素在单链表中的位置
　　　C． 删除操作中依次输入2，5，删除位于2和5的元素

3．概要设计

　　1）为了实现上述程序功能，需要定义单链表的抽象数据类型：
　　ADT LinkList {
　　　数据对象：D={ai|ai∈IntegerSet,i=0,1,2,…,n,n≥0}
　　　数据关系：R={<ai,ai+1>|ai,ai+1 ∈D}
　　　基本操作：
　　　InitLinkList(&L)
　　　操作结果：构造一个空的单链表L.
　　InsLinkList(&L,pos,e)
　　初始条件：单链表L已存在
　　操作结果：将元素e插入到单链表L的pos位置
　　DelLinkList(&L,pos,&e)
　　初始条件：单链表L已存在
　　操作结果：将单链表L中pos位置的元素删除，
　　元素值置入e中返回
　　LocLinkList(L,e)
　　初始条件：单链表L依存在
　　操作结果：单链表L中查找是否元素e，
　　若存在，返回元素在表中的位置；若不存在，返回-1.
　　Menu()
　　操作结果：在屏幕上显示操作菜单

　　2）本程序包含7个函数：
　　① 主函数main()
　　② 初始化单链表函数InitLinkList()
　　③ 显示操作菜单函数menu()
　　④ 显示单链表内容函数dispLinkList()
　　⑤ 插入元素函数InsLinkList()
　　⑥ 删除元素函数DelLinkList()
　　⑦ 查找元素函数LocLinkList()

　　各函数间关系如下：

4．详细设计

　　实现概要设计中定义的所有的数据类型，对每个操作给出伪码算法。对主程序和其他模块也都需要写出伪码算法。
　　1) 结点类型和指针类型
　　typedef struct node {
　　　int data;
　　　struct node *next;
　　}Node,*LinkListl;

　　2) 单链表的基本操作

　　为了方便，在单链表中设头结点，其data域没有意义。

　　bool InitLinkList(LinkList &L)
　　（伪码算法）
　　void DispLinkList(LinkList L)
　　（伪码算法）
　　void menu()
　　（伪码算法）
　　bool InsLinkList(LinkList &L,int pos,int e)
　　（伪码算法）
　　bool DelLinkList(LinkList &L,int pos,int &e)
　　（伪码算法）
　　int LocLinkList(LinkList L,int e)
　　（伪码算法）

　　3) 其他模块伪码算法

5．调试分析
　　(略)

6．使用说明

　　程序名为LinkList.exe，运行环境为DOS。程序执行后显示
　　========================
　　0----EXIT
　　1----INSERT
　　2----DELETE
　　3----LOCATE
　　=======================
　　SELECT:

　　在select后输入数字选择执行不同的功能。要求首先输入足够多的插入元素，才可以进行其他的操作。每执行一次功能，就会显示执行的结果（正确或错误）以及执行后单链表的内容。

　　选择0：退出程序
　　选择1：显示“INSERT pos,e =” ，
　　要求输入要插入的位置和元素的值（都是整数）。
　　选择2：显示“DELETE pos =” ，
　　要求输入要删除元素的位置，执行成功后返回元素的值。
　　选择3：显示“LOCATE e = ” ，
　　要求输入要查找元素的值，执行成功后返回元素在表中的位置

7．测试结果

　　1） 建立单链表：
　　　» 选择1，分别输入（0，11），（0，12），（0，13），（0，14）（0，15）。得到单链表（15，14，13，12，11）
　　2） 插入：
　　　» 选择1输入（1，100），得到单链表（15，100，14，13，12，11）
　　　» 选择1输入（-1，2），显示输入错误
　　　» 选择1输入（7，2），显示输入错误
　　　» 选择1输入（6，2），得到单链表（15，100，14，13，12，11，2）
　　3） 删除：
　　　» 选择2，输入1。返回e=100，得到单链表（15，14，13，12，11，2）
　　　» 选择2，输入0。返回e=15，得到单链表（14，13，12，11，2）
　　　» 选择2，输入4。返回e=2，得到单链表（14，13，12，11）
　　　» 选择2，输入5。返回输入错误
　　4） 查找