1、數據結構與算法作為抽象數據類型的數組一維數組一維數組的示例一維數組的特點連續(xù)存儲的線性聚集（別名 向量）除第一個元素外，其他每一個元素有一個且僅有一個直接前驅。除最后一個元素外，其他每一個元素有一個且僅有一個直接后繼。數組的定義和初始化#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

2、_value ( ) “n”; /打印靜態(tài)數組 elem = &a1; for ( int i=0, i3, i+ ) cout elemget_value( ) “n”; /打印動態(tài)數組 elem+; return 0;一維數組(Array)類的定義 #include #include template class Array Type *elements; /數組存放空間 int ArraySize; /當前長度 void getArray ( ); /建立數組空間 public: Array(int Size=DefaultSize ); Array(const Array& x );

3、Array( ) delete elements; Array & operator = ( const Array & A ); Type& operato ( int i );operator Type * ( ) const return elements; int Length ( ) const return ArraySize; void ReSize ( int sz ); template void Array:getArray ( ) /私有函數：創(chuàng)建數組存儲空間 elements = new TypeArraySize; if ( elements = 0 ) cerr M

4、emory Allocation Error endl; 一維數組公共操作的實現 template void Array:Array ( int sz ) /構造函數 if ( sz = 0 ) cerr Invalid Array Size endl; return; ArraySize = sz; getArray ( ); template Array: Array ( const Array & x ) /復制構造函數 int; elements = new Typen; if ( elements = 0 ) cerr Memory Allocation Error endl; Ty

5、pe ; Type *destptr = 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 & sz !=

6、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; 二維數組 三維數組行向量 下標 i

7、 頁向量 下標 i列向量 下標 j 行向量 下標 j 列向量 下標 k數組的連續(xù)存儲方式一維數組LOC ( i ) = LOC ( i -1 ) + l =+ i*l 二維數組行優(yōu)先 LOC ( j, k ) = j * m + k n維數組各維元素個數為 m1, m2, m3, , mn下標為 i1, i2, i3, , in 的數組元素的存儲地址： 順序表 (Sequential List)順序表的定義和特點 定義 n（ 0）個表項的有限序列 （a1, a2, , an） ai是表項，n是表長度。 特點 順序存取 遍歷 逐項訪問 從前向后 從后向前 從兩端向中間順序表(SeqList)類的

8、定義template 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;int IsIn ( Type & x );int Insert ( Type & x, int i );int Remove ( Type & x );

9、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; 順序表部分公共操作的實現 template SeqList:SeqList ( int sz ) /構造函數 if ( sz 0 ) MaxSize = sz; last = -1; data = new TypeMaxSize; template int S

10、eqList:Find ( Type & x ) const /搜索函數：在表中從前向后順序查找 x int i = 0; while ( i last ) return -1; else return i;順序搜索圖示 x = 48 x = 50搜索成功 若搜索概率相等，則搜索不成功 數據比較 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=l

11、ast; ji; j- ) dataj = dataj -1; datai = x; return 1; /插入成功 表項的刪除 template int 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, Se

12、qList & LB ) int n = LA.Length ( ); int m = LB.Length ( ); for ( int i=1; i=m; i+ ) Type(i); /在LB中取一元素 int (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(

13、i); /在LA中取一元素 int (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 ( ); /構造函數 int operator ! ( ); /判是否零多項式 Coefficient Coef (Exponent e); Exponent LeadExp (

14、 ); /返回最大指數 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, int exp); double get_power ( ) return mul; ;創(chuàng)建power類，計算x的冪 power:power (double val, int exp)

15、/按val值計算乘冪 x = val; e = exp; mul; if (exp = 0 ) return; for ( ; exp0; exp-) mul = mul * x; main ( ) power pwr ( 1.5, 2 ); cout pwr.get_power ( ) “n”; 多項式的存儲表示第一種： private: (靜態(tài)數 int degree;組表示) float coef maxDegree+1; Pn(x)可以表示為： = n i = ai, 0 i n第二種：private: (動態(tài)數 int degree;組表示) float * coef; Polyno

16、mial:Polynomial (int sz) degree = sz; coef = new float degree + 1; 以上兩種存儲表示適用于指數連續(xù)排列的多項式。但對于指數不全的多項式如P101(x) = 3 + 5x50 - 14x101, 不經濟。第三種： class Polynomial;class term /多項式的項定義friend Polynomial;private: float coef; /系數 int exp; /指數;class Polynomial /多項式定義public: private: static term termArrayMaxTerms

17、; /項數組 static int free; /當前空閑位置指針 / term Polynomial:termArrayMaxTerms; / int Polynomial:free = 0; int start, finish; /多項式始末位置 A(xx1000 B(xx50 x101 兩個多項式存放在termArray中兩個多項式的相加結果多項式另存掃描兩個相加多項式，若都未檢測完： 若當前被檢測項指數相等，系數相加。若未變成 0，則將結果加到結果多項式。 若當前被檢測項指數不等，將指數小者加到結果多項式。若有一個多項式已檢測完，將另一個多項式剩余部分復制到結果多項式。Polynomi

18、al Polynomial:Add ( Polynomial B ) Polynomial C; int a = start; int ; C.start = free; float c; while ( a : NewTerm ( termArrayb.coef, termArrayb.exp ); b+; break; case : NewTerm ( termArraya.coef, termArraya.exp ); a+; for ( ; a= maxTerms ) cout Too many terms in polynomials” endl; return; termArray

19、free.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 ); SparseMatrix Transpose ( ); /轉置 Spar

20、seMatrix /相加 Add ( SparseMatrix b ); SparseMatrix /相乘 Multiply ( SparseMatrix b ); 三元組 (Trituple) 類的定義 template class SparseMatrix; template class Trituple friend class SparseMatrix private: int row, col;/非零元素所在行號/列號 Type value; /非零元素的值 稀疏矩陣轉置矩陣用三元組表表示的稀疏矩陣及其轉置稀疏矩陣轉置算法思想設矩陣列數為Cols，對矩陣三元組表掃描Cols次。第k次

21、檢測列號為k的項。第k次掃描找尋所有列號為k的項，將其行號變列號、列號變行號，順次存于轉置矩陣三元組表。設矩陣三元組表總共有Terms項，其時間代價為 O ( Cols* Terms )。若矩陣有200行，200列，10,000個非零元素，總共有2,000,000次處理。稀疏矩陣的轉置 template SparseMatrix SparseMatrix: Transpose ( ) SparseMatrix b; b.Rows = Cols; b.Cols = Rows; b.Terms = Terms; /轉置矩陣的列數,行數和非零元素個數 if ( Terms 0 ) int Curre

22、ntB = 0; /轉置三元組表存放指針 for ( int k=0; kCols; k+ ) for ( int i=0; iTerms; i+ ) if ( smArrayi.col = k ) CurrentB.row = k;CurrentB.col = smArrayi.row;CurrentB.value= smArrayi.value; CurrentB+; return b; 快速轉置算法建立輔助數組rowSize和rowStart，記錄矩陣轉置后各行非零元素個數和各行元素在轉置三元組表中開始存放位置。掃描矩陣三元組表，根據某項的列號，確定它轉置后的行號，查rowStart表，

23、按查到的位置直接將該項存入轉置三元組表中。轉置時間代價為 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+rowSizei-1;稀疏矩陣的快速轉置template SparseMatrixSparseMatrix:FastTranspos (

24、) 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+; rowStart0 = 0; for ( i=1; i Cols; i+ ) rowStarti = rowStarti-1+rowSizei-1;for

25、( i=0; iTerms; i+ ) int j = rowStartsmArrayi.col;j.row = smArrayi.col;j.col = smArrayi.row;j.value = smArrayi.value; rowStartsmArrayi.col+; delete rowSize; delete rowStart; return b;字符串 (String)字符串是n ( 0 ) 個字符的有限序列，記作 S : “c1c2c3cn” 其中，S是串名字 “c1c2c3cn”是串值 ci是串中字符 n是串的長度。 const int maxLen = 128; clas

26、s String int curLen; /串的當前長度 char *ch; /串的存儲數組 public: String ( const String & ob); String ( const char *init ); String ( ); String ( ) delete ch; int Length ( ) const return curLen; 字符串抽象數據類型和類定義 String &operator ( ) ( int pos, int len ); int operator = ( const String &ob ) const return strcmp (ch,

27、) = 0; int operator != ( const String &ob ) const return strcmp (ch,) != 0; int operator ! ( ) const return curLen = 0; String &operator = ( const String &ob ); String &operator += ( const String &ob ); char &operator ( int i ); int Find ( String pat ) const; String:String ( const String &ob ) /復制構造函數：從已有串ob復制 ch =