数据结构 学习讲义 02

1、一维数组多维数组特殊矩阵的压缩存储线性表顺序表 稀疏矩阵字符串第二章 数组1一维数组定义 相同类型的数据元素的集合。一维数组的示例与顺序表的不同在于数组可以按元素的下标直接存储和访问数组元素。35 27 49 18 60 54 77 83 41 020 1 2 3 4 5 6 7 8 92数组的定义和初始化#include class sizecl int e; public: sizecl ( ) e = 0; sizecl ( int value ) e = value; int get_value ( ) return e; void put_value ( int value ) e

2、= value; 3main ( ) sizecl a3 = 3, 5, 7 , *elem; for ( int i = 0; i 3; i+ ) cout ai.get_value ( ) “n”; /静态 elem = a; for ( int i = 0; i 3; i+ ) cout get_value( ) “n”; /动态 elem+; return 0;4一维数组(Array)类的定义 #include #include const int DefaultSize = 30; template class Array Type *elements; /数组存放空间 int Ar

3、raySize; /当前长度 void getArray ( ); /建立数组空间 public: Array( int size = DefaultSize );5 Array( const Array& x ); Array( ) delete elements; Array & operator = /数组复制 ( const Array & A ); Type& operator ( int i ); /取元素值 int Length ( ) const return ArraySize; /取数组长度 void ReSize ( int size ); /扩充数组 6 templat

4、e void Array : getArray ( ) /私有函数：创建数组存储空间 elements = new TypeArraySize; if ( elements = NULL ) ArraySize = 0; cerr “存储分配错！ endl; return; 一维数组公共操作的实现7 template Array : Array ( int size ) /构造函数 if ( size = 0 ) ArraySize = 0; cerr “非法数组大小” endl; return; ArraySize = size; getArray ( ); 8 template /复制构造

5、函数 Array : Array ( Array & x ) int n = ArraySize = x.ArraySize; elements = new Typen; if ( elements = NULL ) ArraySize = 0; cerr “存储分配错” endl; return; Type *srcptr = x.elements; Type *destptr = elements; while ( n- ) * destptr+ = * srcptr+; 9template Type& Array : operator ( int i ) /按数组名及下标 i，取数组元素

6、的值 if ( i ArraySize-1 ) cerr “数组下标超界” endl; return NULL; return elementi; 使用该函数于赋值语句 Pos = Positioni + Numberi10 template void Array : Resize ( int size ) if ( size = 0 & size != ArraySize ) Type * newarray = new Typesize; /创建新数组 if ( newarray = NULL ) cerr “存储分配错” endl; return; int n = (size 0 a, i

7、 = 0 a+i*la15 二维数组行优先存放： 设数组开始存放位置 LOC( 0, 0 ) = a, 每个元素占用 l 个存储单元 LOC ( j, k ) = a + ( j * m + k ) * l16 二维数组列优先存放： 设数组开始存放位置 LOC( 0, 0 ) = a, 每个元素占用 l 个存储单元 LOC ( j, k ) = a + ( k * n + j ) * l17 三维数组 各维元素个数为 m1, m2, m3 下标为 i1, i2, i3的数组元素的存储地址： （按页/行/列存放） LOC ( i1, i2, i3 ) = a + ( i1* m2 * m3 +

8、i2* m3 + i3 ) * l 前i1页总元素个数第i1页的前i2行总元素个数第 i2 行前 i3 列元素个数18 n 维数组 各维元素个数为 m1, m2, m3, , mn 下标为 i1, i2, i3, , in 的数组元素的存储地址： LOC ( i1, i2, , in ) = a + ( i1*m2*m3*mn + i2*m3*m4*mn+ + + in-1*mn + in ) * l 19特殊矩阵的压缩存储特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。特殊矩阵的压缩存储主要是针对阶数很高的特殊矩阵。为节省存储空间，对可以不存储的元素，如零元素或对称元素，不再存储。对称矩

9、阵三对角矩阵20对称矩阵的压缩存储设有一个 nn 的对称矩阵 A。在矩阵中，aij = aji21为节约存储，只存对角线及对角线以上的元素，或者只存对角线或对角线以下的元素。前者称为上三角矩阵，后者称为下三角矩阵。下三角矩阵22上三角矩阵把它们按行存放于一个一维数组 B 中，称之为对称矩阵 A 的压缩存储方式。数组 B 共有 n + ( n - 1 ) + + 1 = n*(n+1)/2 个元素。23下三角矩阵B a00 a10 a11 a20 a21 a22 a30 a31 a32 an-1n-1 0 1 2 3 4 5 6 7 8 n(n+1)/2-1若 i j, 数组元素Aij在数组B中

10、的存放位置为 1 + 2 + + i + j = (i + 1)* i / 2 + j前i行元素总数 第i行第j个元素前元素个数24 若 i j，数组元素 Aij 在矩阵的上三角部分, 在数组 B 中没有存放，可以找它的对称元素Aji：= j *(j +1) / 2 + i 若已知某矩阵元素位于数组 B 的第 k个位置，可寻找满足 i (i + 1) / 2 k (i + 1)*(i + 2) / 2的 i, 此即为该元素的行号。 j = k - i * (i + 1) / 2此即为该元素的列号。 例，当 k = 8, 3*4 / 2 = 6 k j，数组元素Aij在矩阵的下三角部分，在数组

11、B 中没有存放。因此，找它的对称元素Aji。 Aji在数组 B 的第 (2*n-j-1) * j / 2 + i 的位置中找到。27三对角矩阵的压缩存储B a00 a01 a10 a11 a12 a21 a22 a23 an-1n-2 an-1n-1 0 1 2 3 4 5 6 7 8 9 1028三对角矩阵中除主对角线及在主对角线上 下最临近的两条对角线上的元素外，所有其它元素均为0。总共有3n-2个非零元素。将三对角矩阵A中三条对角线上的元素按行存放在一维数组 B 中，且a00存放于B0。在三条对角线上的元素aij 满足 0 i n-1, i-1 j i+1在一维数组 B 中 Aij 在第

12、 i 行，它前面有 3*i-1 个非零元素, 在本行中第 j 列前面有 j-i+1 个，所以元素 Aij 在 B 中位置为 k = 2*i + j。29若已知三对角矩阵中某元素 Aij 在数组 B 存放于第 k 个位置，则有 i = (k + 1) / 3 j = k - 2 * i例如，当 k = 8 时， i = (8+1) / 3 = 3, j = 8 - 2*3 = 2 当 k = 10 时， i = (10+1) / 3 = 3, j = 10 - 2*3 = 430线性表 (Linear List)线性表的定义和特点 定义 n（ 0）个数据元素的有限序列，记作 （a1, a2, ,

13、 an） ai 是表中数据元素，n 是表长度。 遍历 逐项访问： 从前向后 从后向前 31线性表的特点除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。a1a2a3a4a5a632顺序表 (Sequential List)顺序表的定义和特点 定义 将线性表中的元素相继存放在一个连续的存储空间中。 可利用一维数组描述存储结构 特点 线性表的顺序存储方式 遍历 顺序访问或直接访问 25 34 57 16 48 09 0 1 2 3 4 5 data33顺序表(SeqList)类的定义const int defaultSize = 30

14、;template class SeqList Type *data; /顺序表存储数组 int MaxSize; /最大允许长度 int last; /当前最后元素下标public: SeqList ( int size = defaultSize ); SeqList ( ) delete data; int Length ( ) const return last+1; 34 int Find ( Type& x ) const; /查找 int Locate ( int i ) const; /定位 int Insert ( Type & x, int i ); /插入 int Rem

15、ove ( Type & x ); /删除 int Next ( Type & x ) ; /后继 int Prior ( Type & x ) ; /前驱 int IsEmpty ( ) return last =-1; int IsFull ( ) return last = MaxSize-1; Type Get ( int i ) /提取 return i last？NULL : datai; 35顺序表部分公共操作的实现 template /构造函数 SeqList : SeqList ( int size ) if ( size 0 ) MaxSize = size; last =

16、 -1; data = new TypeMaxSize; if ( data = NULL ) MaxSize = 0; return; 36template int SeqList : Find ( Type& x ) const /搜索函数：在顺序表中从头查找结点值等于/给定值x的结点 int i = 0; while ( i last ) return -1; else return i;37顺序搜索图示25 34 57 16 48 09 0 1 2 3 4 5 data搜索 16i25 34 57 16 48 09 i25 34 57 16 48 09 i25 34 57 16 48

17、09 i搜索成功3825 34 57 16 48 0 1 2 3 4data搜索 50i25 34 57 16 48 i25 34 57 16 48 i25 34 57 16 48 i25 34 57 16 48 i搜索失败39搜索成功的平均比较次数 若搜索概率相等，则搜索不成功 数据比较 n 次40表项的插入25 34 57 16 48 09 63 0 1 2 3 4 5 6 7data50插入 x25 34 57 50 16 48 09 63 0 1 2 3 4 5 6 7data50i41template int SeqList : Insert (Type& x, int i ) /在

18、表中第 i 个位置插入新元素 x if ( i last+1 | last = MaxSize-1 ) return 0; /插入不成功 else last+; for ( int j = last; j i; j- ) dataj = dataj -1; datai = x; return 1; /插入成功 42表项的删除25 34 57 50 16 48 09 63 0 1 2 3 4 5 6 7data16删除 x25 34 57 50 48 09 63 0 1 2 3 4 5 6 7data43 template int SeqList : Remove ( Type& x ) /在表

19、中删除已有元素 x int i = Find (x); /在表中搜索 x if ( i = 0 ) last- ;for ( int j = i; j = last; j+ ) dataj = dataj+1; return 1; /成功删除 return 0; /表中没有 x 44顺序表的应用：集合的“并”运算void Union ( SeqList & A, SeqList & B ) int n = A.Length ( ); int m = B.Length ( ); for ( int i = 0; i m; i+ ) int x = B.Get(i); /在B中取一元素 int k

20、 = A.Find (x); /在A中搜索它 if ( k = -1 ) /若未找到插入它 A.Insert ( x, n ); n+; 45 void Intersection ( SeqList & A, SeqList & B ) int n = A.Length ( ); int m = B.Length ( ); int i = 0; while ( i n ) int x = A.Get (i); /在A中取一元素 int k = B.Find (x); /在B中搜索它if ( k = -1 ) A.Remove ( x ); n-; else i+; /未找到在A中删除它 顺序表

21、的应用：集合的“交”运算46稀疏矩阵 (Sparse Matrix)非零元素个数远远少于矩阵元素个数47稀疏矩阵的定义设矩阵 Amn 中有 t 个非零元素，若 t 远远小于矩阵元素的总数 mn，且非零元素的分布无规律，则称矩阵A 为稀疏矩阵。为节省存储空间，应只存储非零元素。非零元素的分布一般没有规律，应在存储非零元素时，同时存储该非零元素的行下标 row、列下标 col、值 value。每一个非零元素由一个三元组唯一确定： ( 行号 row, 列号 col, 值 value )48稀疏矩阵的抽象数据类型template class SparseMatrix;template class Tr

22、ituple /三元组friend class SparseMatrix private: int row, col; /非零元素行号/列号 Type value; /非零元素的值template class SparseMatrix /稀疏矩阵类定义 49 int Rows, Cols, Terms; /行/列/非零元素数 Trituple smArrayMaxTerms; public: /三元组表 SparseMatrix (int MaxRow, int Maxcol); SparseMatrix& Transpose (SparseMatrix&); /转置 SparseMatrix

23、& Add (SparseMatrix a, SparseMatrix b); /相加 SparseMatrix& Multiply(SparseMatrix a, SparseMatrix b); /相乘 50稀疏矩阵的转置一个 mn 的矩阵 A，它的转置矩阵 B 是一个 nm 的矩阵，且 Aij = Bji。即矩阵 A 的行成为矩阵 B 的列，矩阵 A 的列成为矩阵 B 的行。在稀疏矩阵的三元组表中，非零矩阵元素按行存放。当行号相同时，按列号递增的顺序存放。稀疏矩阵的转置运算要转化为对应三元组表的转置。51稀疏矩阵52转置矩阵53用三元组表表示的稀疏矩阵及其转置54稀疏矩阵转置算法思想设矩

24、阵列数为 Cols，对矩阵三元组表扫描Cols 次。第 k 次检测列号为 k 的项。第 k 次扫描找寻所有列号为 k 的项，将其行号变列号、列号变行号，顺次存于转置矩阵三元组表。55稀疏矩阵的转置 template SparseMatrix& SparseMatrix : Transpose (SparseMatrix& a) SparseMatrix b (a.Cols, a.Rows); b.Rows = a.Cols; b.Cols = a.Rows; b.Terms = a.Terms; /转置矩阵的列数,行数和非零元素个数 if ( a.Terms 0 ) int CurrentB

25、= 0; /转置三元组表存放指针56 for ( int k = 0; k a.Cols; k+ ) /对所有列号处理一遍 for ( int i = 0; i a.Terms; i+ ) if ( a.smArrayi.col = k ) b.smArrayCurrentB.row = k; b.smArrayCurrentB.col = a.smArrayi.row; b.smArrayCurrentB.value= a.smArrayi.value; CurrentB+; 57 return b; 快速转置算法设矩阵三元组表总共有 t 项，上述算法的时间代价为 O ( n* t )。若矩

26、阵有 200 行，200 列，10,000 个非零元素，总共有 2,000,000 次处理。58为加速转置速度，建立辅助数组 rowSize 和 rowStart，记录矩阵转置后各行非零元素个数和各行元素在转置三元组表中开始存放位置。扫描矩阵三元组表，根据某项列号，确定它转置后的行号, 查 rowStart 表, 按查到的位置直接将该项存入转置三元组表中59 for ( int i = 0; i a.Cols; i+ ) rowSizei = 0; for ( i = 0; i a.Terms; i+ ) rowSizea.smArrayi.col+; rowStart0 = 0; for (

27、 i = 1; i Cols; i+ ) rowStarti = rowStarti-1+rowSizei-1;60稀疏矩阵的快速转置template SparseMatrix&SparseMatrix : FastTranspos (SparseMatrix& a) int *rowSize = new inta.Cols; int *rowStart = new inta.Cols; SparseMatrix b ( a.Cols, a.Rows ); b.Rows = a.Cols; b.Cols = a.Rows; b.Terms = a.Terms; if ( a.Terms 0 )

28、 for (int i = 0; i Cols; i+) rowSizei = 0; 61for ( i = 0; i Terms; i+ ) rowSizesmArrayi.col+; rowStart0 = 0; for ( i = 1; i a.Cols; i+ ) rowStarti = rowStarti-1+rowSizei-1;for ( i = 0; i a.Terms; i+ ) int j = rowStarta.smArrayi.col; b.smArrayj.row = a.smArrayi.col; b.smArrayj.col = a.smArrayi.row; b

29、.smArrayj.value = a.smArrayi.value; rowStarta.smArrayi.col+; 62 delete rowSize; delete rowStart; return b;设矩阵有 m 行，n 列，非零元素 t 个，则矩阵三元组表总共有 t 项，上述算法的时间代价为 O ( max(n, t ) )。若矩阵有 200 行，200 列，10,000 个非零元素，总共有 20,400 次处理。63字符串 (String)字符串是 n ( 0 ) 个字符的有限序列， 记作 S : “c1c2c3cn” 其中，S 是串名字 “c1c2c3cn”是串值 ci 是串

30、中字符 n 是串的长度。例如, S = “Tsinghua University” 64 const int maxLen = 128; class String int curLen; /串的当前长度 char *ch; /串的存储数组 public: String ( const String& ob ); String ( const char * init ); String ( ); String ( ) delete ch; 字符串抽象数据类型和类定义65 int Length ( ) const return curLen; /求当前串*this的实际长度 String &ope

31、rator ( ) ( int pos, int len ); /取*this从pos开始len个字符组成的子串 int operator = ( const String &ob ) return strcmp (ch, ob.ch) = 0; /判当前串*this与对象串ob是否相等 int operator != ( const String &ob ) const return strcmp (ch, ob.ch) != 0; /判当前串*this与对象串ob是否不等 66 int operator ! ( ) const return curLen = 0; /判当前串*this是否

32、空串 String &operator = (String &ob); /将串ob赋给当前串*this String &operator += (String &ob); /将串ob连接到当前串*this之后 char &operator ( int i ); /取当前串*this的第 i 个字符 int Find ( String& pat ) const;67 String : String ( const String& ob ) /复制构造函数：从已有串ob复制 ch = new charmaxLen+1; /创建串数组 if ( ch = NULL ) cerr “存储分配错! n”

33、; exit(1); curLen = ob.curLen; /复制串长度 strcpy ( ch, ob.ch ); /复制串值 字符串部分操作的实现68String : String ( const char *init ) /复制构造函数: 从已有字符数组*init复制 ch = new charmaxLen+1; /创建串数组 if ( ch = NULL ) cerr “存储分配错 ! n”; exit(1); curLen = strlen ( init ); /复制串长度 strcpy ( ch, init ); /复制串值 69String : String ( ) /构造函数

34、：创建一个空串 ch = new charmaxLen+1; /创建串数组 if ( ch = NULL ) cerr “存储分配错!n”; exit(1); curLen = 0; ch0 = 0; 70提取子串的算法示例pos+len -1 pos+len -1 curLen-1 curLeni n f i n i t yi n f i n i t ypos = 2, len = 3pos = 5, len = 4f i ni t y超出71String& String : operator ( ) (int pos, int len) /从串中第 pos 个位置起连续提取 len 个字符

35、/形成子串返回 String * temp = new String; /动态分配 if (pos= maxLen | lencurLen = 0; /返回空串 temp-ch0 = 0; else /提取子串if ( pos+len -1 = curLen ) len = curLen - pos; 72 temp-curLen = len; /子串长度 for ( int i = 0, j = pos; i chi = chj; /传送串数组 temp-chlen = 0; /子串结束 return * temp; 例：串 st = “university”, pos = 3, len = 4使用示例 subSt = st (3, 4)提取子串 subSt = “vers”73String& String : operator = ( String& ob ) /串赋值：从已有串ob复制 if ( &ob != this ) delete ch; ch