數(shù)據(jù)結(jié)構(gòu)課件老師chapter

1、 第2章 數(shù)組1. 數(shù)組及其抽象數(shù)據(jù)類型 1)一維數(shù)組 2) 一維數(shù)組的抽象數(shù)據(jù)類型的類聲明 3)二維數(shù)組（矩陣） 4)特殊矩陣2.順序表(sequential List) 1)順序表定義和特點(diǎn) 2) 順序表的類定義 3)順序表的查找 插入 刪除 4) 使用順序表的例子(用抽象數(shù)據(jù)類型）3.多項(xiàng)式抽象數(shù)據(jù)類型 1)如何表達(dá)多項(xiàng)式：系數(shù)，階數(shù) 2)多項(xiàng)式相加 4. 稀疏矩陣 5.字符串（String） 1) 字符串（簡稱串）的定義以及一些術(shù)語 2)串的基本操作 3)串的類定義以及串操作的實(shí)現(xiàn) 4)字符串的模式匹配（pattern matching） 樸素的匹配算法 改進(jìn)的模式匹配算法：KMP第2

2、章 數(shù)組數(shù)組：具有相同數(shù)據(jù)類型的數(shù)據(jù)元素的集合。 一般存儲于一個(gè)連續(xù)存儲空間中。 通過數(shù)組元素的下標(biāo)來存取該元素。1. 數(shù)組及其抽象數(shù)據(jù)類型 1)一維數(shù)組：具有相同數(shù)據(jù)類型的n（n=0）個(gè)元素的有限序列。例如： 0 1 2 3 4 5 6 7 8 9 a： i 下標(biāo)i為數(shù)組元素到數(shù)組開始的偏移量 Loc(ai)=loc(a0)+i*l35274918605477834102 2 ) 一維數(shù)組的抽象數(shù)據(jù)類型的類聲明 對數(shù)組的操作主要有：對數(shù)組元素的存與取。 3 ) 二維數(shù)組（矩陣） 由n個(gè)行向量和m個(gè)列向量所組成的向量 a00 a01 a02 a0,m-1 Anm = a10 a11 a12 a

3、 1,m-1 an-1,0an-1,1an-1,2an-1,m-1a00a01a0m-1a10a11a1m-1對二維數(shù)組的順序存儲：1）按行優(yōu)先順序存放 a00 , a01 ,a02, ,a0m-1 ,a10 如ALGOL,PASCAL,C+,BASIC,Ada等都是按行優(yōu)先順序存放的。2) 按列優(yōu)先順序存放 a00 , a10 , a20 ,a n-10 ,a01 如Fortran語言 如果按行優(yōu)先存放，其下標(biāo)元素的映射公式為： Loc(i, j)=Loc(0,0)+i*m+j*L 如果按列優(yōu)先存放，其下標(biāo)元素的映射公式為： Loc (i,j) = Loc (0, 0)+j*n+i*L 同理

4、對三維數(shù)組am1m2m3 其下標(biāo)元素aijk Loc(i, j, k)=Loc(0,0,0)+i*m2*m3+j*m3+k 0120m2-1m1-1 4)特殊矩陣(1)下三角矩陣（對于對稱矩陣的壓縮存儲） a11a21 a22a31 a32 a33an1 an2 ann 按行序存放a11a21a22 Loc(i,j)=Loc(1,1)+(1+2+3+i-1)+j-1*L =Loc(1,1)+(i*(i-1)/2 +j-1)*L 上三角矩陣 a11 a12 a1n a11 a22 a2n 按行序存放 a12 a33 a1n a22 . ann . . Loc(i,j)=Loc(1,1)+(n+(

5、n-1)+(n-i+2)+j-i*L =loc(1,1)+(n-k+1)+j-i*L K=1i-1 (2) 三對角線矩陣 a11a12 a21a22a23 a32a33a34 按行序存放 an-1,n-2an-1,n-1an-1,n an,n-1 an,n Loc(i,j)=Loc(1,1)+(i-1)*3-1+(j-i+1)*La11a12a21a22a232.順序表(sequential List) 1)順序表定義和特點(diǎn) 定義：是一個(gè)順序存儲的n（n=0）個(gè)表項(xiàng)的序列。 n=0叫做空表。每個(gè)表項(xiàng)是單個(gè)對象，其數(shù)據(jù)類型 相同。表長度因隨插入，刪除而改變。 線性表（a0,a1,a2,an-1)

6、可以線性存儲， 也可拉鏈存儲 特點(diǎn)：查找某一表項(xiàng)，必須從表的第一個(gè)表項(xiàng)開始查找， 直到找到為止。 數(shù)組可以方便的隨機(jī)存取，但不可任意插，刪元 素。a0a1an-12） 順序表的類定義順序表的實(shí)現(xiàn)：用數(shù)組。 datalast 0 1 2 MaxSize-1 有三個(gè)量來表示數(shù)組： data-存放數(shù)組 MaxSize-順序表的最大項(xiàng)數(shù) last-當(dāng)前已存項(xiàng)數(shù)的下標(biāo) 這三個(gè)向量都是封裝在私有域中 順序表的操作常用的操作是:查找，插入，刪除。 下面是順序表的類聲明：templateclass SeqList public: SeqList(int MaxSize=defaultSize); SeqLis

7、t( )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); int Next(Type& x); int Prior(Type& x); int IsEmpty( )return last= =-1; int IsFull( ) return last= = MaxSize-1; Type & Get(int i) return ilast? NULL:datai;

8、private: Type * data; int MaxSize; int last; 構(gòu)造函數(shù) templateSeqlist:Seqlist(int sz) if(sz0) Maxsize=sz; last=-1; data=new TypeMaxsize; 3) 順序表的查找 插入 刪除 (1)查找：i從0號位置開始找， 找到則返回x在data數(shù)組中的位 置，否則返回-1 算法分析：假設(shè)表中有n項(xiàng) ACN=(1+2+n)/n 等概率 =(1+n)*n/2n=(n+1)/2 不成功的比較次數(shù)為n次 (2）插入 把x插入到i位置,則必須把i到n-1的表項(xiàng)成塊向后移一個(gè)位置 插入成功返回1，

9、否則返回0 算法分析：插入運(yùn)算主要在移動元素的時(shí)間上 如果有n個(gè)元素，在每個(gè)位置上插入元素的概率相等，則datalast 0 1 2 n-1 MaxSize-1 0位置，1位置,n位置,一共有n+1情況 AMN=(n-i)/(n+1)=(n+n-1+1+0)/(n+1)=n/2 ni=0 （3） 刪除 01ilast(i+1至last 向前移動)n-1算法分析 AMN=(n-i-1)/n=(n-1+n-2+1+0)/n=(n-1)/2i=04)使用順序表的例子(用抽象數(shù)據(jù)類型）(1)將兩個(gè)順序表LA,LB當(dāng)集合來使用, 實(shí)現(xiàn)并的運(yùn)算。 即兩表中如有相同元素只保留一個(gè)。 算法：從LB中取一個(gè)元素

10、， 在LA中查找這一元素，如果未 找到則插入到LA中。templatevoid union(seglist&LA,seglist&LB) int n=LA.length( ); int m=LB.length( ); for (int i=0; i=m-1; i+) type x=LB.get(i); int k=LA.find(x); if(k=-1)LA.insert(x,n); n+; (2) 實(shí)現(xiàn)兩個(gè)順序表la和lb的交的運(yùn)算 即求兩個(gè)表的公共元素。 以表la為基準(zhǔn)，每取表la中一個(gè)元素，看是否在lb中出現(xiàn)， 如果沒有出現(xiàn)則在la中刪除Templatevoid intersection

11、(seglist&la,seglisttype&lb) int n=la.length( ); int m=lb.length( ); int i=0; while( i非零元素個(gè)數(shù)且非零元素是無規(guī)則 分佈的。例子： 0 0 0 22 0 0 15 0 11 0 0 0 17 0 0 0 0 6 0 0 0 A6x7 = 0 0 0 0 0 39 0 91 0 0 0 0 0 0 0 0 28 0 0 0 0分析：首先把非零元素表示出來，一般用三元組（稀疏矩陣 的壓縮表示）：行號，列號，值。如上例 稀疏矩陣的抽象數(shù)據(jù)類型SmArray01234567rowcolValue03220615111

12、1151723-6353940915228*對于稀疏矩陣應(yīng)該有哪些數(shù)據(jù)成員？ （1）矩陣行數(shù)（Rows） （2）列數(shù)（Cols） （3）非零元素個(gè)數(shù)（Terms） （4）非零元素的三元組（SmArray）*對于稀疏矩陣的操作 （1）實(shí)現(xiàn)轉(zhuǎn)置矩陣 （2）行數(shù)、列數(shù)相同的兩個(gè)稀疏矩陣a與b相加 （3）稀疏矩陣a與b相乘 template class SparseMatrix;template class Trituplefriend class SparseMatrixprivate: int row,col; Type value;template class SparseMatrixpubli

13、c: SparseMatrix(int MaxRow,int MaxCol);/構(gòu)造函數(shù) SparseMatrix Transpose(); SparseMatrix Add (SparseMatrix b); SparseMatrix Multiply (SparseMatrix b);Private: int Rows,Cols,Terms; Trituple SmArray MaxTerms; 5.字符串（String）1) 字符串（簡稱串）的定義以及一些術(shù)語 *串：是n（n=0）個(gè)字符的一個(gè)有限序列，開頭結(jié)尾用單 引號 或雙引號“ ”括起來。 例如： B=“structure” （B為

14、串名） *串的長度：串中所包含的字符個(gè)數(shù)n（不包括分界符，也不 包括串的結(jié)束符0） *空串：長度為0的串?；蛘哒f只包含串結(jié)束符0的串。 注意 0 不等于 0 , 空串不等于空白串 *子串：串中任一連續(xù)子序列 例子：B=peking 則 空串、ki、peking都是B的 子串但pk不是B的子串2)串的基本操作： *構(gòu)造一個(gè)空串；*求串長；*兩個(gè)串的連接（并置）； *取子串；*求一個(gè)子串在串中第一次出現(xiàn)的位置等。3)串的類定義以及串操作的實(shí)現(xiàn)： (1)串的類定義： 0 1 2 3 4 curlen-1 ch D a t a S t r . maxlen作為類外全局變量說明 const int ma

15、xlen=128;class String 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, ob.ch)= =0; int operator !=(const String &ob) cons

16、t return strcmp(ch, ob.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; private: int curLen; char * ch; (2)部分串操作的實(shí)現(xiàn)： maxlen-1 *取子串： 0 1 2 3 4 5 String B: ch: P e

17、k i n g curlen-1 *串賦值： String a(),b(); . a=b; 1、如果對賦值號“=”不重載，則實(shí)現(xiàn)淺拷貝.2、只有對“=”重載了，才能實(shí)現(xiàn)深拷貝.具體賦值過程：（1）先刪除原a中的ch數(shù)組 （2）為對象a再重分配ch數(shù)組 （3）再把b.ch復(fù)制到a.ch中achbch *連接操作 String a(),b(); .; a+=b; 4)字符串的模式匹配（pattern matching）問題：目標(biāo)串 Target: KxABDABCEFABC模式 pattern:ABC找模式（子串）ABC在目標(biāo)串KxABDABCEFABC中第一次出現(xiàn)的起始位置，稱為模式匹配。 (1

18、)樸素的匹配算法*思想：T: a b b a b a P: a b a從頭開始比，若對應(yīng)字符相等，則繼續(xù)下一對字符， 一旦不等，則T從剛剛開始比的下一個(gè)字符，P從第 一個(gè)字符再開始一輪比較。要么匹配成功，要么沒有。 *算法： *算法分析：該算法是帶有回溯的，在最壞情況下，假設(shè)每 趟的比較都在最后出現(xiàn)不等，則比較趟數(shù) n- m+1，每趟比較次數(shù)為m, 所以總次數(shù)=m*(n-m+1) O(m*n) (2)改進(jìn)的模式匹配算法：KMP(Knuth等人) O(m+n) *目的：克服不必要的回溯例子： T:.abcaxc. P:abcad 為什么：從模式P出發(fā)。因?yàn)閎a,而b與T中b已匹配，所以T中的b與

19、P的第一個(gè)a肯定不匹配，不必比較，同理c不等于a，所以T中的c也不必與P中的a相比，. 。 *問題： 當(dāng)前面i-1個(gè)字符匹配，而PiTj，為使j不回退，Tj應(yīng)與P?比 較. 假設(shè)Tj應(yīng)與Pk比，即 Text: “.Tj-i+1.Tj-k+1.Tj-1Tj.” pattern: “P1.Pk-1 Pk.Pi-k+1.Pi-1 Pi.”稱：P1P2.Pk-1 = Pi-k+1.Pi-1 前綴子串 后綴子串 注意：pattern：前綴子串與后綴子串可能重復(fù)（真子串） 例如：aaaab (3）書中的模式匹配改進(jìn)算法： 用的是失效函數(shù)Text: T0 T1 . .Ti.Tn-1 Pattern: P0 P1 .Pj Pj+1 .Pm-1失效函數(shù)f(j)=k text: t0 t1 t2 . .ti ti+1. pattern: p0 p1 pk pk+1pj-k pj-k+1pj pj+1.pm-1 kF(j) = k-為pj+1匹配失效時(shí)用的，當(dāng)pj+1!=ti+1時(shí)t的指針不動，p以pf(j)+1 = pk+1作為回退位置 *失效函數(shù)的定義： P=P0 P1 .Pm-2 Pm-1 f(j)= k 當(dāng)0=k0（即除第1位外）則目標(biāo)串指針不動，模式P的 開始位置為P f(j-1)+1例如：T:a c a b a a b a a b c a c a a b cP:a b a a b c a