数据结构课件C 版第四章.ppt

快速转置算法 设矩阵三元组表总共有 t 项，上述算法的时间代价为 O ( n* t )。当非零元素的个数 t 和 m*n 同数量级时，算法transmatrix的时间复杂度为O(m*n2)。 若矩阵有 200 行，200 列，10,000 个非零元素，总共有 2,000,000 次处理。 快速转置算法的思想为：对 原矩阵A 扫描一遍，按 A 中每一元素的列号，立即确定在转置矩阵 B 三元组表中的位置，并装入它。 为加速转置速度，建立辅助数组 rowSize 和 rowStart： rowSize记录矩阵转置前各列，即转置矩阵各行非零元素个数； rowStart记录各行非零元素在转置三元组表中开始存放位置。 扫描矩阵三元组表，根据某项列号，确定它转置后的行号, 查 rowStart 表, 按查到的位置直接将该项存入转置三元组表中。 举例 稀疏矩阵的快速转置算法 见p147 带行指针数组的二元组表 稀疏矩阵的三元组表可以用带行指针数组的二元组表代替。 在行指针数组中元素个数与矩阵行数相等。第 i 个元素的下标 i 代表矩阵的第 i 行，元素的内容即为稀疏矩阵第 i 行的第一个非零元素在二元组表中的存放位置。 二元组表中每个二元组只记录非零元素的列号和元素值，且各二元组按行号递增的顺序排列。 行指针数组 row 0 0 1 3 2 4 3 6 4 7 5 7 二元组表 data col value 0 0 12 1 2 11 2 5 13 3 6 14 4 1 - 4 5 5 3 6 3 8 7 1 - 9 8 4 2 字符串 (String) 字符串是 n ( ? 0 ) 个字符的有限序列， 记作 S : “c1c2c3…cn” 其中，S 是串名字 “c1c2c3…cn”是串值 ci 是串中字符 n 是串的长度，n = 0 称为空串。 例如, S = “Tsinghua University”。 注意：空串和空白串不同，例如 “ ” 和 “” 分别表示长度为1的空白串和长度为0的空串。 串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。 通常将子串在主串中首次出现时，该子串首字符对应的主串中的序号，定义为子串在主串中的位置。例如，设A和B分别为 A = “This is a string” B = “is” 则 B 是 A 的子串，A 为主串。B 在 A 中出现了两次，首次出现所对应的主串位置是2（从0开始）。因此，称 B 在 A 中的位置为2。 特别地，空串是任意串的子串，任意串是其自身的子串。 通常在程序中使用的串可分为两种：串变量和串常量。 串常量在程序中只能被引用但不能改变它的值，即只能读不能写。通常串常量是由直接量来表示的，例如语句 Error (“overflow”) 中“overflow”是直接量。但有的语言允许对串常量命名，以使程序易读、易写。如C++中，可定义 const char path[] = “dir/bin/appl”; 这里path是一个串常量。串变量和其它类型的变量一样，其取值可以改变。 字符串的类定义 #ifndef ASTRING_H //定义在文件“Astring.h”中 #define ASTRING_H #define defaultSize = 128; //字符串的最大长度 class AString { //对象: 零个或多个字符的一个有限序列。 private: char *ch; //串存放数组 int curLength; //串的实际长度 int maxSize; //存放数组的最大长度 public: AString(int sz = defaultSize); //构造函数 AString(const char *init ); //构造函数 AString(const AString ob); //复制构造函数 ～AString() {delete [ ]ch; } //析构函数 int Length() const { return curLength; } //求长度 Astring