作為抽象數(shù)據(jù)類型的數(shù)組順序表稀疏矩陣字符串.ppt

作為抽象數(shù)據(jù)類型的數(shù)組 順序表 稀疏矩陣 字符串,第二章 數(shù)組,作為抽象數(shù)據(jù)類型的數(shù)組,一維數(shù)組 一維數(shù)組的示例,35 27 49 18 60 54 77 83 41 02,0 1 2 3 4 5 6 7 8 9,一維數(shù)組的特點,連續(xù)存儲的線性表（別名 向量）,數(shù)組的定義和初始化,#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; i get_value( ) “n”; /動態(tài) elem+; return 0; ,一維數(shù)組(Array)類的定義,#include #include template class Array Type *elements; /數(shù)組存放空間 int ArraySize; /當前長度 void getArray ( ); /建立數(shù)組空間 public: Array( int Size=DefaultSize ); Array( const Array,Array( ) delete elements; Array /擴充數(shù)組 ,template void Array : getArray ( ) /私有函數(shù)：創(chuàng)建數(shù)組存儲空間 elements = new TypeArraySize; if ( elements = NULL ) arraySize = 0; cerr “存儲分配錯！“ endl; return; ,一維數(shù)組公共操作的實現(xiàn),template Array : Array ( int sz ) /構造函數(shù) if ( sz = 0 ) arraySize = 0; cerr “非法數(shù)組大小” endl; return; ArraySize = sz; getArray ( ); ,template Array : Array ( Array ,template Type 使用該函數(shù)于賦值語句 Pos = Positioni -1 + Numberi -1,template void Array : Resize ( int sz ) if ( sz = 0 /按新的大小確定傳送元素個數(shù),Type *srcptr = elements; /源數(shù)組指針 Type *destptr = newarray; /目標數(shù)組指針 while ( n- ) * destptr+ = * srcptr+; /從源數(shù)組向目標數(shù)組傳送 delete elements; elements = newarray; ArraySize = sz; ,二維數(shù)組 三維數(shù)組,行向量 下標 i 頁向量 下標 i 列向量 下標 j 行向量 下標 j 列向量 下標 k,數(shù)組的連續(xù)存儲方式,一維數(shù)組,35 27 49 18 60 54 77 83 41 02,0 1 2 3 4 5 6 7 8 9,l l l l l l l l l l,LOC(i) = LOC(i-1)+l = a+i*l,LOC(i) =,LOC(i-1)+l = a+i*l, i 0,a, i = 0,a+i*l,a,二維數(shù)組,行優(yōu)先 LOC ( j, k ) = = a + ( j * m + k ) * l,三維數(shù)組,各維元素個數(shù)為 m1, m2, m3 下標為 i1, i2, i3的數(shù)組元素的存儲地址： （按頁/行/列存放）,LOC ( i1, i2, i3 ) = a + ( i1* m2 * m3 + i2* m3 + i3 ) * l,前i1頁總 元素個數(shù),第i1頁的 前i2行總元素個數(shù),n 維數(shù)組,各維元素個數(shù)為 m1, m2, m3, , mn 下標為 i1, i2, i3, , in 的數(shù)組元素的存儲地址：,LOC ( i1, i2, , in ) = a + ( i1*m2*m3*mn + i2*m3*m4*mn+ + + in-1*mn + in ) * l,線性表 (Linear List),線性表的定義和特點 定義 n（ 0）個數(shù)據(jù)元素的有限序列，記作 （a1, a2, , an） ai 是表中數(shù)據(jù)元素，n 是表長度。 遍歷 逐項訪問： 從前向后 從后向前,線性表的特點,除第一個元素外，其他每一個元素有且僅有一個直接前驅。 除最后一個元素外，其他每一個元素有且僅有一個直接后繼。,順序表 (Sequential List),順序表的定義和特點 定義 將線性表中的元素相繼存放在一個連續(xù)的存儲空間中 可利用一維數(shù)組描述存儲結構 特點 線性表的順序存儲方式 遍歷 順序訪問,25 34 57 16 48 09,0 1 2 3 4 5,data,順序表(SeqList)類的定義,template class SeqList Type *data; /順序表存儲數(shù)組 int MaxSize; /最大允許長度 int last; /當前最后元素下標 public: SeqList ( int MaxSize = defaultSize ); SeqList ( ) delete data; int Length ( ) const return last+1; ,int Find ( Type ,順序表部分公共操作的實現(xiàn),template /構造函數(shù) SeqList : SeqList ( int sz ) if ( sz 0 ) MaxSize = sz; last = -1; data = new TypeMaxSize; if ( data = NULL ) MaxSize = 0; last = -1; return; ,template int SeqList : Find ( Type ,順序搜索圖示,25 34 57 16 48 09,0 1 2 3 4 5,data,搜索 16,i,25 34 57 16 48 09,i,25 34 57 16 48 09,i,25 34 57 16 48 09,i,搜索成功,25 34 57 16 48,0 1 2 3 4,data,搜索 50,i,25 34 57 16 48,i,25 34 57 16 48,i,25 34 57 16 48,i,25 34 57 16 48,i,搜索失敗,搜索成功 若搜索概率相等，則 搜索不成功 數(shù)據(jù)比較 n 次,表項的插入,25 34 57 16 48 09 63 ,0 1 2 3 4 5 6 7,data,50,插入 x,25 34 57 50 16 48 09 63 ,0 1 2 3 4 5 6 7,data,50,i,template int SeqList : Insert (Type /插入成功 ,表項的刪除,25 34 57 50 16 48 09 63 ,0 1 2 3 4 5 6 7,data,16,刪除 x,25 34 57 50 48 09 63 ,0 1 2 3 4 5 6 7,data,template int SeqList : Remove ( Type /表中沒有 x ,順序表的應用：集合的“并”運算,void Union ( SeqList ,void Intersection ( SeqList /未找到在A中刪除它 ,順序表的應用：集合的“交”運算,稀疏矩陣 (Sparse Matrix),非零元素個數(shù)遠遠少于矩陣元素個數(shù),稀疏矩陣的抽象數(shù)據(jù)類型 template class SparseMatrix; template class Trituple /三元組 friend class SparseMatrix private: int row, col; /非零元素行號/列號 Type value; /非零元素的值 template class SparseMatrix /稀疏矩陣類定義,int Rows, Cols, Terms; /行/列/非零元素數(shù) Trituple smArrayMaxTerms; public: /三元組表 SparseMatrix (int MaxRow, int Maxcol); SparseMatrix /相乘 ,稀疏矩陣,轉置矩陣,用三元組表表示的稀疏矩陣及其轉置,稀疏矩陣轉置算法思想,設矩陣列數(shù)為 Cols，對矩陣三元組表掃描Cols 次。第 k 次檢測列號為 k 的項。 第 k 次掃描找尋所有列號為 k 的項，將其行號變列號、列號變行號，順次存于轉置矩陣三元組表。,稀疏矩陣的轉置 template SparseMatrix /轉置三元組表存放指針,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+; , return b; ,快速轉置算法,建立輔助數(shù)組 rowSize 和 rowStart，記錄矩陣轉置后各行非零元素個數(shù)和各行元素在轉置三元組表中開始存放的位置。,掃描矩陣三元組表，根據(jù)某項的列號，確定它轉置后的行號，查 rowStart 表，按查到的位置直接將該項存入轉置三元組表中。,for ( int i = 0; i a.Cols; i+ ) rowSizei = 0; for ( i = 0; i a.Terms; i+ ) rowSizea.smArrayi.col+; rowStart0 = 0; for ( i = 1; i Cols; i+ ) rowStarti = rowStarti-1+rowSizei-1;,稀疏矩陣的快速轉置 template SparseMatrix,for ( 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.smArrayj.value = a.smArrayi.value; rowStarta.smArrayi.col+; , delete rowSize; delete rowStart; return b; ,字符串 (String),字符串是 n ( 0 ) 個字符的有限序列， 記作 S : “c1c2c3cn” 其中，S 是串名字 “c1c2c3cn”是串值 ci 是串中字符 n 是串的長度。 例如, S = “Tsinghua University”,const int maxLen = 128; class String int curLen; /串的當前長度 char *ch; /串的存儲數(shù)組 public: String ( const String ,字符串抽象數(shù)據(jù)類型和類定義,int Length ( ) const return curLen; /求當前串*this的實際長度 String /判當前串*this與對象串ob是否不等,int operator ! ( ) const return curLen = 0; /判當前串*this是否空串 String ,String : String ( const String /復制串值 ,字符串部分操作的實現(xiàn),String : String ( const char *init ) /復制構造函數(shù): 從已有字符數(shù)組*init復制 ch = new charmaxLen+1; /創(chuàng)建串數(shù)組 if ( ch = NULL ) cerr “存儲分配錯 ! n”; exit(1); curLen = strlen ( init ); /復制串長度 strcpy ( ch, init ); /復制串值 ,String : String ( ) /構造函數(shù)：創(chuàng)建一個空串 ch = new charmaxLen+1; /創(chuàng)建串數(shù)組 if ( ch = NULL ) cerr “存儲分配錯!n”; exit(1); curLen = 0; ch0 = 0; ,提取子串的算法示例,pos+len -1 pos+len -1 curLen-1 curLen,i n f i n i t y,i n f i n i t y,pos = 2, len = 3,pos = 5, len = 4,f i n,i t y,超出,String,temp-curLe