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

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