数据结构与算法.pptVIP

数据结构与算法 2006.9-2007.1 作为抽象数据类型的数组 一维数组 一维数组的示例 一维数组的特点 连续存储的线性聚集（别名 向量） 除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。 除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。 一维数组(Array)类的定义 #include iostream.h #include stdlib.h template class Type class Array { Type *elements; //数组存放空间 int ArraySize; //当前长度 void getArray ( ); //建立数组空间 public: Array(int Size=DefaultSize ); Array(const ArrayType x ); 一维数组公共操作的实现 行向量 下标 i 页向量 下标 i 列向量 下标 j 行向量 下标 j 列向量 下标 k 数组的连续存储方式 一维数组  n维数组 各维元素个数为 m1, m2, m3, …, mn 下标为 i1, i2, i3, …, in 的数组元素的存储地址： 顺序表 (Sequential List) 顺序表的定义和特点 定义 n（ ? 0）个表项的有限序列 （a1, a2, …, an） ai是表项，n是表长度。 特点 顺序存取 遍历 逐项访问 从前向后 从后向前 从两端向中间 顺序表(SeqList)类的定义 template class Type class SeqList { Type *data; //顺序表存储数组 int MaxSize; //最大允许长度 int last; //当前最后元素下标 public: SeqList ( int MaxSize = defaultSize ); ~SeqList ( ) { delete [ ] data; } int Length ( ) const { return last+1; } int Find ( Type x ) const; 顺序表部分公共操作的实现 template class Type SeqListType::SeqList ( int sz ) { //构造函数 if ( sz 0 ) { MaxSize = sz; last = -1; data = new Type[MaxSize]; } } 顺序搜索图示 多项式 (Polynomial) n阶多项式Pn(x)有n+1项。 系数 a0, a1, a2, …, an 指数 0, 1, 2, …, n。按升幂排列 多项式(Polynomial)的抽象数据类型 创建power类，计算x的幂 多项式的存储表示 第一种： private: (静态数 int degree; 组表示) float coef [maxDegree+1]; Pn(x)可以表示为： pl.degree = n pl.coef[i] = ai, 0 ? i ? n 两个多项式的相加 结果多项式另存 扫描两个相加多项式，若都未检测完： 若当前被检测项指数相等，系数相加。若未变成 0，则将结果加到结果多项式。 若当前被检测项指数不等，将指数小者加到结果多项式。 若有一个多项式已检测完，将另一个多项式剩余部分复制到结果多项式。 稀疏矩阵 (Sparse Matrix) 用三元组表表示的稀疏矩阵及其转置 稀疏矩阵转置算法思想 设矩阵列数为Cols，对矩阵三元组表扫描Cols次。第k次检测列号为k的项。 第k次扫描找寻所有列号为k的项，将其行号变列号、列号变行号，顺次存于转置矩阵三元组表。 设矩阵三元组表总共有Terms项，其时间代价为 O ( Cols* Terms )。 若矩阵有200行，200列，10,000个非零元素，总共有2,000,000次处理。 快速转置算法 建立辅助数组rowSize和rowStart，记录矩阵转置后各行非零元素个数和各行元素在转置三元组表中开始存放位