关于向量分类问题的解答.pdf

关于向量分类问题的 解答 04 计 4 030402523 王泳 问题描述 给定 m 个 n 维向量 a 1 a2 am，向量分类问 题要求将相同的向量划分为同一类。试用抽象 数据类型表设计解向量分类问题的有效算法。例如:3 5 7 9 4 3 7 5 3 5 7 9 3 5 7 94 3 7 5 2 1 4 6 判断为 2 1 4 6 3 5 7 9 共 3 类 2 1 4 6 编程任务与输入输出说明 任务:给定 m 个 n 维向量，编程计算这 m个 n 维向 量可分为多少个类。输入:由文件 input.txt 给出输入数据。第 1 行有 2 个正整数 m 和 n，分别表示给定的向量个数和每 个向量的维数。接下来的 m 行中，每行有 n 个整数，表示相应的 n 维向量。输出:将计算出的向量的等价类数输出到文件 output.txt。运行结果:输入文件示例 输出文件示例 input.txt output.txt 64 3 3579 4375 3579 2146 35792146 思路:方案一首先考虑所建的数据结构最初考虑了 3 种方案:方案一:把每一个 n 维向量放入一张表共建 m 张 表比较每张表对应的每一个元素 m1 m2 m3 mn 这个方法可以直接调 用 retrieve 函数依次 返回每张表的每个元 素进行可是要再写 比较函数则较为复杂 最后没有采用 思路:方案二 思路:方案二:建一张表，将每一个向量都放入表的每 一个单元，比较每一个单元是否完全相同。m 1 m2 mn 由于每个表单元的数据 类型是一个数组，用 c 语言表述实在很困 难，也放弃了！思路:方案三 思路:方案三：最终方案 将每个向量依次读入一张表，形成一张 mn 大小的表然后再处理 好处说明：（1）适合于我的比较算法（2）数据结构简单，计算起来快（3）可以采用已有的表模版 m1 m2m3 mn m12 m22 m32 mn2 创建表的类 class Listprotected:int n int MaxSize int data public:Listint Max/构造函数 ListList list/复制构造函数 Listdelete data/析构函数int Length constreturn n/求表长 bool Retrieveint kint x const/返回表中第k个 元素x void Addconst int x/在表尾加元素x 构造函数和复制构造函数 List:Listint Max MaxSizeMaxdatanew intMaxSize n0/构造函数 List:ListList list nlist.nMaxSizelist.MaxSize datanew intMaxSize forint i0imn anewintn List Lmn fork0kai if L.Length0completeLnumna for j0j