数据结构与算法

《数据结构与算法》由会员分享，可在线阅读，更多相关《数据结构与算法（67页珍藏版）》请在金锄头文库上搜索。

1、数据结构与算法 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life, there is hope。有生命必有希望。有生命必有希望作为抽象数据类型的数组一维数组一维数组一维数组的示例一维数组的示例一维数组的特点连续存储的线性聚集（别名连续存储的线性聚集（别名 向量向量）除第一个元素外，其他每一个元素有除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。一个且仅有一个直接前驱。除最后一个元素外，其他每一个元素除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。有一个且仅有一个直接后继。数组的定义和初始化数组的定义和初始化

2、#include class szcl int e; public: szcl ( ) e = 0; szcl ( int value ) e = value; int get_value ( ) return e; main ( ) szcl a13 = 3, 5, 7 , *elem; for ( int i=0, i3, i+ ) cout a1i.get_value ( ) “n”; /打印静态数组打印静态数组 elem = &a1; for ( int i=0, i3, i+ ) cout elemget_value( ) “n”; /打印动态数组打印动态数组 elem+; retu

3、rn 0;一维数组(Array)类的定义 #include #include template class Array Type *elements; /数组存放空间数组存放空间 int ArraySize; /当前长度当前长度 void getArray ( ); /建立数组空间建立数组空间 public: Array(int Size=DefaultSize ); Array(const Array& x ); Array( ) delete elements; Array & operator = ( const Array & A ); Type& operato ( int i );

4、operator Type * ( ) const return elements; int Length ( ) const return ArraySize; void ReSize ( int sz ); template void Array:getArray ( ) /私有函数：创建数组存储空间私有函数：创建数组存储空间 elements = new TypeArraySize; if ( elements = 0 ) cerr Memory Allocation Error endl; 一维数组公共操作的实现 template void Array:Array ( int sz )

5、 /构造函数构造函数 if ( sz = 0 ) cerr Invalid Array Size endl; return; ArraySize = sz; getArray ( ); template Array: Array ( const Array & x ) /复制构造函数复制构造函数 int n = ArraySize = x.ArraySize; elements = new Typen; if ( elements = 0 ) cerr Memory Allocation Error endl; Type *srcptr = x.elements; Type *destptr

6、= elements; while ( n- ) * destptr+ = * srcptr+; template Type & Array:operator ( int i ) /按数组名及下标按数组名及下标i，取数组元素的值，取数组元素的值 if ( i ArraySize-1 ) cerr Index out of Range endl; return elementi; 使用该函数于赋值语句使用该函数于赋值语句 Positioni = Positioni -1 + Numberi -1 template void Array:Resize (int sz) if ( sz = 0 &

7、sz != ArraySize ) Type * newarray = new Typesz; if ( newarray = 0 ) cerr Memory Allocation Error endl; int n = ( sz = ArraySize ) ? sz : ArraySize; Type *srcptr = elements; Type *destptr = newarray; while ( n- ) * destptr+ = * srcptr+; delete elements; elements = newarray; ArraySize = sz; 二维数组二维数组 三

8、维数组三维数组行向量行向量 下标下标 i 页向量页向量 下标下标 i列向量列向量 下标下标 j 行向量行向量 下标下标 j 列向量列向量 下标下标 k数组的连续存储方式一维数组一维数组LOC ( i ) = LOC ( i - -1 ) + l =+ i*l 二维数组二维数组行优先行优先 LOC ( j, k ) = j * m + k n维数组各维元素个数为各维元素个数为 m1, m2, m3, , mn下标为下标为 i1, i2, i3, , in 的数组元素的的数组元素的存储地址：存储地址： 顺序表 (Sequential List)顺序表的定义和特点顺序表的定义和特点 定义定义 n（

9、0）个表项的有限序列个表项的有限序列 （a1, a2, , an） ai是表项，是表项，n是表长度。是表长度。 特点特点 顺序存取顺序存取 遍历遍历 逐项访问逐项访问 从前向后从前向后 从后向前从后向前 从两端向中间从两端向中间顺序表(SeqList)类的定义template class SeqList Type *data; /顺序表存储数组顺序表存储数组 int MaxSize; /最大允许长度最大允许长度 int last; /当前最后元素下标当前最后元素下标public: SeqList ( int MaxSize = defaultSize ); SeqList ( ) delete

10、 data; int Length ( ) const return last+1; int Find ( Type & x ) const;int IsIn ( Type & x );int Insert ( Type & x, int i );int Remove ( 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

11、last？NULL : datai; 顺序表部分公共操作的实现 template SeqList:SeqList ( int sz ) /构造函数构造函数 if ( sz 0 ) MaxSize = sz; last = -1; data = new TypeMaxSize; template int SeqList:Find ( Type & x ) const /搜索函数：在表中从前向后顺序查找搜索函数：在表中从前向后顺序查找 x int i = 0; while ( i last ) return -1; else return i;顺序搜索图示 x = 48 x = 50搜索成功搜索成

12、功 若搜索概率相等，则若搜索概率相等，则搜索不成功搜索不成功 数据比较数据比较 n 次次表项的插入表项的插入template int SeqList:Insert ( Type & x, int i )/在表中第在表中第 i 个位置插入新元素个位置插入新元素 x if ( i last+1 | last = MaxSize- -1 ) return 0; /插入不成功插入不成功 else last+; for ( int j=last; ji; j- ) dataj = dataj -1; datai = x; return 1; /插入成功插入成功 表项的删除表项的删除 template i

13、nt SeqList:Remove ( Type & x ) /在表中删除已有元素在表中删除已有元素 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 顺序表的应用：顺序表的应用：集合的集合的“并并”运运算算 template void Union ( SeqList & LA, SeqList & LB ) int n = LA.Length ( ); int

14、m = LB.Length ( ); for ( int i=1; i=m; i+ ) Type x = LB.Get(i); /在在LB中取一元素中取一元素 int k = LA.Find (x); /在在LA中搜索它中搜索它 if ( k = -1 ) /若未找到插入它若未找到插入它 LA.Insert (n+1, x); n+; template void Intersection ( SeqList & LA, SeqList & LB ) int n = LA.Length ( ); int m = LB.Length ( ); int i=1; while ( i n ) Type

15、 x = LA.Get(i); /在在LA中取一元中取一元素素 int k = LB.Find (x); /在在LB中搜索它中搜索它 if ( k = -1 ) LA.Remove (i); n-; else i+; /未找到在未找到在LA中删除中删除它它 顺序表的应用：顺序表的应用：集合的集合的“交交”运算运算多项式 (Polynomial)n阶多项式阶多项式Pn(x)有有n+1项。项。 系数系数 a0, a1, a2, , an 指数指数 0, 1, 2, , n。按升幂排列。按升幂排列class Polynomial public: Polynomial ( ); /构造函数构造函数 i

16、nt operator ! ( ); /判是否零多项判是否零多项式式 Coefficient Coef (Exponent e); Exponent LeadExp ( ); /返回最大指返回最大指数数 Polynomial Add (Polynomial poly); Polynomial Mult (Polynomial poly); float Eval ( float x); /求值求值多项式(Polynomial)的抽象数据类型 #include class power double x; int e; double mul; public: power (double val, i

17、nt exp); double get_power ( ) return mul; ;创建power类，计算x的幂 power:power (double val, int exp) /按按val值计算乘幂值计算乘幂 x = val; e = exp; mul = 1.0; if (exp = 0 ) return; for ( ; exp0; exp-) mul = mul * x; main ( ) power pwr ( 1.5, 2 ); cout pwr.get_power ( ) “n”; 多项式的存储表示第一种：第一种： private: ( (静态数静态数 int degree

18、;组表示组表示) float coef maxDegree+1; Pn(x)可以表示为可以表示为： pl.degree = n pl.coefi = ai, 0 i n第二种：第二种：private: (动态数动态数 int degree;组表示组表示) float * coef; Polynomial:Polynomial (int sz) degree = sz; coef = new float degree + 1; 以上两种存储表示适用于指数连续排列以上两种存储表示适用于指数连续排列的多项式。但对于指数不全的多项式如的多项式。但对于指数不全的多项式如P101(x) = 3 + 5x5

19、0 - - 14x101, 不经济。不经济。第三种第三种： class Polynomial;class term /多项式的项定义多项式的项定义friend Polynomial;private: float coef; /系数系数 int exp; /指数指数;class Polynomial /多项式定义多项式定义public: private: static term termArrayMaxTerms; /项数项数组组 static int free; /当前空闲位置指当前空闲位置指针针 / term Polynomial:termArrayMaxTerms; / int Polyn

20、omial:free = 0; int start, finish; /多项式始末位置多项式始末位置 A(x) = 2.0x1000+1.8 B(x) = 1.2 + 51.3x50 + 3.7x101 两个多项式存放在两个多项式存放在termArray中中两个多项式的相加结果多项式另存结果多项式另存扫描两个相加多项式，若都未检测完：扫描两个相加多项式，若都未检测完： 若当前被检测项指数相等，系数相加。若未若当前被检测项指数相等，系数相加。若未若当前被检测项指数相等，系数相加。若未若当前被检测项指数相等，系数相加。若未变成变成变成变成 0 0，则将结果加到结果多项式。，则将结果加到结果多项式。

21、，则将结果加到结果多项式。，则将结果加到结果多项式。 若当前被检测项指数不等，将指数小者加到若当前被检测项指数不等，将指数小者加到若当前被检测项指数不等，将指数小者加到若当前被检测项指数不等，将指数小者加到结果多项式。结果多项式。结果多项式。结果多项式。若有一个多项式已检测完，将另一个多项若有一个多项式已检测完，将另一个多项式剩余部分复制到结果多项式。式剩余部分复制到结果多项式。Polynomial Polynomial:Add ( Polynomial B ) Polynomial C; int a = start; int b = B.start; C.start = free; floa

22、t c; while ( a = finish & b : NewTerm ( termArrayb.coef, termArrayb.exp ); b+; break; case : NewTerm ( termArraya.coef, termArraya.exp ); a+; for ( ; a=finish; a+ ) /a未检测完未检测完时时 NewTerm ( termArraya.coef, termArraya.exp ); for ( ; b= maxTerms ) cout Too many terms in polynomials” endl; return; termA

23、rrayfree.coef = c; termArrayfree.exp = e; free+; 稀疏矩阵 (Sparse Matrix)行数行数m = 6, 列数列数n = 7, 非零元素个数非零元素个数t = 6 稀疏矩阵稀疏矩阵(SparseMatrix)的抽象数据类型的抽象数据类型 template class SparseMatrix int Rows, Cols, Terms; /行行/列列/非零元素数非零元素数 Trituple smArrayMaxTerms; public: /三元组表三元组表 SparseMatrix ( int MaxRow, int Maxcol );

24、SparseMatrix Transpose ( ); /转置转置 SparseMatrix /相加相加 Add ( SparseMatrix b ); SparseMatrix /相乘相乘 Multiply ( SparseMatrix b ); 三元组三元组 (Trituple) 类的定义类的定义 template class SparseMatrix; template class Trituple friend class SparseMatrix private: int row, col;/非零元素所在行号非零元素所在行号/列号列号 Type value; /非零元素的值非零元素的

25、值 稀疏矩阵稀疏矩阵转置矩阵转置矩阵用三元组表表示的稀疏矩阵及其转置稀疏矩阵转置算法思想设矩阵列数为设矩阵列数为Cols，对矩阵三元组表扫，对矩阵三元组表扫描描Cols次。第次。第k次检测列号为次检测列号为k的项。的项。第第k次扫描找寻所有列号为次扫描找寻所有列号为k的项，将其的项，将其行号变列号、列号变行号，顺次存于转行号变列号、列号变行号，顺次存于转置矩阵三元组表。置矩阵三元组表。设矩阵三元组表总共有设矩阵三元组表总共有Terms项，其时项，其时间代价为间代价为 O ( Cols* Terms )。若矩阵有若矩阵有200行，行，200列，列，10,000个非零个非零元素，总共有元素，总共有

26、2,000,000次处理。次处理。稀疏矩阵的转置稀疏矩阵的转置 template SparseMatrix SparseMatrix: Transpose ( ) SparseMatrix b; b.Rows = Cols; b.Cols = Rows; b.Terms = Terms; /转置矩阵的列数转置矩阵的列数, ,行数和非零元素个数行数和非零元素个数 if ( Terms 0 ) int CurrentB = 0; /转置三元组表存放指针转置三元组表存放指针 for ( int k=0; kCols; k+ ) for ( int i=0; iTerms; i+ ) if ( smA

27、rrayi.col = k ) b.smArrayCurrentB.row = k; b.smArrayCurrentB.col = smArrayi.row; b.smArrayCurrentB.value= smArrayi.value; CurrentB+; return b; 快速转置算法建立辅助数组建立辅助数组rowSize和和rowStart，记录矩阵，记录矩阵转置后转置后各行非零元素个数各行非零元素个数和和各行元素在转置各行元素在转置三元组表中开始存放位置三元组表中开始存放位置。扫描矩阵三元组表，根据某项的列号，确定扫描矩阵三元组表，根据某项的列号，确定它转置后的行号，查它转置后

28、的行号，查rowStart表，按查到的表，按查到的位置直接将该项存入转置三元组表中。位置直接将该项存入转置三元组表中。转置时间代价为转置时间代价为 O(max(Terms, Cols)。若矩。若矩阵有阵有200列，列，10000个非零元素，总共需个非零元素，总共需10000次处理。次处理。 for ( int i=0; iCols; i+ ) rowSizei = 0; for ( i=0; iTerms; i+ ) rowSizesmArrayi.col+; rowStart0 = 0; for ( i=1; i Cols; i+ ) rowStarti = rowStarti-1+rowS

29、izei-1;稀疏矩阵的快速转置稀疏矩阵的快速转置template SparseMatrixSparseMatrix:FastTranspos ( ) int *rowSize = new intCols; int *rowStart = new intCols; SparseMatrix b; b.Rows = Cols; b.Cols = Rows; b.Terms = Terms; if ( Terms 0 ) for (int i=0; iCols; i+) rowSizei = 0; for ( i=0; iTerms; i+ ) rowSizesmArrayi.col+; rowS

30、tart0 = 0; for ( i=1; i Cols; i+ ) rowStarti = rowStarti-1+rowSizei-1;for ( i=0; iTerms; i+ ) int j = rowStartsmArrayi.col; b.smArrayj.row = smArrayi.col; b.smArrayj.col = smArrayi.row; b.smArrayj.value = smArrayi.value; rowStartsmArrayi.col+; delete rowSize; delete rowStart; return b;字符串 (String)字符

31、串是字符串是n ( 0 ) 个字符的有限序个字符的有限序列，记作列，记作 S : “c1c2c3cn” 其中，其中，S是串名字是串名字 “c1c2c3cn”是串值是串值 ci是串中字符是串中字符 n是串的长度。是串的长度。 const int maxLen = 128; class String int curLen; /串的当前长度串的当前长度 char *ch; /串的存储数组串的存储数组 public: String ( const String & ob); String ( const char *init ); String ( ); String ( ) delete ch; i

32、nt Length ( ) const return curLen; 字符串抽象数据类型和类定义 String &operator ( ) ( int pos, int len ); int operator = ( const String &ob ) const return strcmp (ch, ob.ch) = 0; int operator != ( const String &ob ) const return strcmp (ch, ob.ch) != 0; int operator ! ( ) const return curLen = 0; String &operator

33、 = ( const String &ob ); String &operator += ( const String &ob ); char &operator ( int i ); int Find ( String pat ) const; String:String ( const String &ob ) /复制构造函数：复制构造函数：从已有串从已有串ob复制复制 ch = new charmaxLen+1; if ( !ch ) cout “Allocation Errorn”; exit(1); curLen = ob.curLen; strcpy ( ch, ob.ch );

34、字符串部分操作的实现字符串部分操作的实现String:String ( const char *init ) /复制构造函数复制构造函数: 从已有字符数组从已有字符数组* *init复复制制 ch = new charmaxLen+1; if ( !ch ) cout “Allocation Errorn”; exit(1); curLen = strlen (init); strcpy ( ch, init ); String:String ( ) /构造函数：创建一个空串构造函数：创建一个空串 ch = new charmaxLen+1; if ( !ch ) cout “Allocati

35、on Errorn”; exit(1); curLen = 0; ch0 = 0; 提取子串的算法示例pos+len - -1 pos+len - -1 curLen- -1 curLen String &String: operator ( ) ( int pos, int len ) /从串中第从串中第pos个位置起连续提取个位置起连续提取len个字符个字符 /形成子串返回形成子串返回 if ( pos = maxLen | len = curLen ) len = curLen - pos; tempcurLen = len; /子串长度子串长度 for ( int i=0, j=pos

36、; ilen; i+, j+ ) tempchi = chj; /传送串数传送串数组组 tempchlen = 0; /子串结子串结束束 return temp; String &String:operator = ( const String &ob ) /串赋值：从已有串串赋值：从已有串ob复制复制 if ( &ob != this ) delete ch; ch = new char maxLen+1; /重新分重新分配配 if ( ! ch ) cerr “Out Of Memory!n ”; exit (1); curLen = ob.curLen; /串复制串复制 strcpy (

37、 ch, ob.ch ); else cout “Attempted assignment of a String to itself!n”; return *this; char &String:operator ( int i ) /按串名提取串中第按串名提取串中第i个字符个字符 if ( i = curLen ) cout “Out Of Boundary!n ”; exit (1) ; return chi;String &String: /串连接串连接operator += ( const String &ob ) char * temp =ch; /暂存原串数暂存原串数组组 curLen += ob.curLen; /串长度累加串长度累加 ch = new char maxLen+1; if ( ! ch ) cerr “Out Of Memory!n ”; exit (1) ; strcpy ( ch, temp );/拷贝原串数组拷贝原串数组 strcat ( ch, ob.ch );/连接连接ob串数组串数组 delete temp; return *this;