针对于目录系统，CatalogTree 的结点存放的数据内容为字符串，每个结点对应一个目录项，该目录项可以是目录，也可以是文件，如果是目录就可以再存放其它目录或文件，即非叶结点；如果是文件就是叶结点。从根结点到该结点路经所有结点的字符串用“/”进行组合后就是该目录项的绝对路径，用来唯一的标识该目录。例如：/usr/li/email/student/。 目录系统具有如下基本操作：

1) dir ——列出当前目录下的所有目录项 2) cd ——打出当前目录的绝对路经

3) cd ..——当前目录变为当前目录的父目录

4) cd str——当前目录变为str 所表示路径的目录

5) mkdir str ——在(当前目录下)创建一个子目录(名为str) 6) mkfile str ——在(当前目录下)创建一个文件(名为str) 7) delete str ——删除(当前目录下)名为str 的目录或文件 (2) 课程设计目的

应用树知识模拟一个目录管理系统。 (3) 基本要求

① 描述并实现CatalogTree 的ADT，包括其上的基本操作：如插入一个结点，寻找一个结点，返回一个结点的最左儿子等（具体情况依据应用自定）。

② 应用CatalogTree 的ADT 实现一个完成文件目录系统的Shell 应用程序。

③ 该Shell 是一个不断等待用户输入命令的解释程序，根据用户输入的命令完成相关操作，直到退出（quit）。命令名及其含义如上所述。

④ 目录树结构可以保存（save）到文件中，也可从文件中读出（load *.dat）。 ⑤ dir 命令的结果应能够区分是子目录和还是文件。

⑥ 应对命令4)~7)中的str 区分是绝对路经，还是相对路径。 (4) 实现提示

关键是树上基本操作的实现。

13. 集合的等价划分 (1) 问题描述

构造集合结构的抽象数据型，并在此基础上进行集合的等价划分。 (2) 课程设计目的

掌握集合的表示方法，并设计等价划分算法。 (3) 基本要求

① 选择合理的结构完成集合的表示(要求以ADT 的形式给出)。

② 在进行等价划分前，等价关系需用户输入(从文件输入，格式自定)。 ③ 需要验证用户输入的关系是否为等价关系。

④ 对集合进行等价划分，且要分析该划分的时空复杂性。 (4) 实现提示

可用树结构来表示集合，如果能进行适当的优化并给出理由和实验分析结果将更好。

14. 哈夫曼编码与译码 (1) 问题描述

针对一段文本(推荐为英语)，就这段文本进行相应的哈夫曼编码和译码。 (2) 课程设计目的

9

掌握哈夫曼树的构造。 (3) 基本要求

① 完成文本的频率统计。 ② 构造哈夫曼树。

③ 编写编码程序和译码程序。

④ 计算压缩率，并和任一种压缩算法(自己去找)比较(比较复杂性和压缩效果)。 (4) 实现提示 无。

15. 小型文本编辑器的设计 (1) 问题描述

设计一个文本编辑器，使其具有通常编辑器(如Notepad)所应具备的基本功能。 (2) 课程设计目的

较大规模软件系统的设计与实现，字符串上的基本操作。 (3) 基本要求

① 要求该编辑器在串基本抽象数据型上构建。

② 编辑器应具备如字符串查找，字符串替换，统计字数，统计行数等基本功能。 ③ 具备图形化界面(最好用VC++完成)。 (4) 实现提示

字符串抽象数据型需要为文本编辑器的实现提供足够的支持，所以在此部分需仔细分析、设计；可以行编辑器作为该编辑器的基础。

16．多项式链式存储结构及其代数运算 (1) 问题描述

设计并建立一个链式存储分配系统来表示和操作多项式。为了避免对零和非零多项式进行不同的处理，使用带头结点的循环链表。为了充分利用多项式中不再使用的结点，维护一个可用空间表avail,把不再使用的多项式的结点链入其中。当需要一个新结点时，就查看这个单链表avail。如果表非空，那么可以使用它的一个结点。只有当该表为空时，才使用动态存储分配来创建新结点。 （2）设计目的

掌握循环链表的存储结构及其操作；能够运用循环链表的存储结构表示多项式，并进行代数运算。

(3) 基本要求

设计多项式的存储结构，编写并测试下列函数：

a) get_node 和ret_node，从/向可用空间表申请和插入一个多项式结点。 b) pread，读取一个多项式，并将其转换成循环存储表示。返回指向该多项式的头结点的指针。

c) pwrite，输出多项式，采用能够清楚显示的形式。 d) padd，计算d = a+b。不改变a 和b。 e) psub，计算d = a-b。不改变a 和b。 f) pmult，计算d = a*b。不改变a 和b。

g) eval，计算多项式在某点a 的值，其中a 是一个浮点型常量。返回结果为浮点数。 h) perase，把存储表示为循环链表的多项式返还给可用空间表。 （4）实现提示

10

为了进一步简化加法算法，把多项式的头结点的指数域设为-1

17．稀疏矩阵的完全链表表示及其运算 (1) 问题描述

稀疏矩阵的每个结点包含down，right，row，col 和value 五个域。用单独一个结点表示一个非零项，并将所有结点连接在一起，形成两个循环链表。使得第一个表即行表，把所有结点按照行序（同一行内按列序）用right 域链接起来。使得第二个表即列表，把所有结点按照列序（同一列内按行序）用down 链接起来。这两个表共用一个头结点。另外，增加一个包含矩阵维数的结点。稀疏矩阵的这种存储表示称为完全链表表式。实现一个完全链表系统进行稀疏矩阵运算，并分析下列操作函数的计算时间和额外存储空间的开销。 （2）设计目的

认识和掌握稀疏矩阵的完全链表表示；能够建立并运用这种存储结构 (3) 基本要求

建立一个用户友好、菜单式系统进行下列操作，并使用合当的测试数据测试该系统。 （a） 读取一个稀疏矩阵建立其完全链表表示 （b） 输出一个稀疏矩阵的内容 （c） 删除一个稀疏矩阵 （d） 两个稀疏矩阵相加 （e） 两个稀疏矩阵相减 （f） 两个稀疏矩阵相乘 （g） 稀疏矩阵的转置 （4）实现提示 链表上的操作。

18．简单矢量图形的几何变换 (1) 问题描述

常见的几何图形（二维图形）都是由点、直线和圆组成，而平面上的点和直线都可用矢量进行表示，如果假设几何图形中不包含圆，那么一个无论多么复杂的几何图形都可用矢量表示并存储，且图形上的几何变换都可通过矢量上的变换得以实现。 例如下图：

图8 一矢量图形的实例

图中的十字形状就可用矢量P1,P2-P1 和P3,P3-P4 表示，当然其中P1,P2,P3,P4 都是向 量，分别表示十字图形的四个顶点。其中P1 表示直线段的起点，P2-P1 表示该直线的方向

11

和长度。

而该图的平移变换就可表示如下(向右水平平移5 个单位)：

图9 矢量图形向右平移5 个单位的结果

[P1+H,P2-P1];[P3+H,P3-P4]其中H 为矢量5+0i。 (2) 课程设计目的

能够应用线性数据结构描述简单的矢量图，并能完成简单的几何变换。 (3) 基本要求

① 描述并实现矢量ADT，包括矢量的表示和存储，以及其上的基本操作：矢量 相加；相减；共扼；求模；相乘等。

② 应用矢量实现简单几何图形（由点和直线组成）的表示和存储。同时该几何图 形能够保存在文件中（格式自定），并能从文件中读出。

③ 实现矢量几何图形的基本操作，包括平移（水平加垂直）；旋转；依直线镜像； 依点镜像；放大；缩小等（可自行扩展）。

④ 提供界面实现用户对图形的操作，包括输入图形，进行变换操作等。 ⑤ 每一步操作的结果都能图形化显示。 (4) 实现提示

用二元组表示一个向量，一个几何图形就是一个数组。

参考书目

1、严蔚敏、吴伟民：《数据结构（C语言版）》，清华大学出版社，1997年4月第1版。

12

2、唐策善、李龙澍、黄刘生：《数据结构–用C语言描述》，高等教育出版社，1995年4月第1版。

13