數(shù)據(jù)結(jié)構(gòu)課件：04 第三章 數(shù)組和字符串[新]

1、第三章 數(shù)組和字符串3.1 數(shù)組3.2 矩陣3.3 字符串13.1 數(shù)組3.1.1 數(shù)組的存儲(chǔ)和尋址3.1.2 自定義數(shù)組類3.1.3 動(dòng)態(tài)數(shù)組2一維數(shù)組是若干個(gè)元素的有限序列。元素本身就是一個(gè)數(shù)據(jù)結(jié)構(gòu)。一維數(shù)組的元素必須具有相同的類型，每個(gè)數(shù)組元素都占據(jù)相同大小的存儲(chǔ)空間。3一維數(shù)組采用順序存儲(chǔ)結(jié)構(gòu)。每個(gè)元素都通過一個(gè)下標(biāo)來指定，故一個(gè)一維數(shù)組對(duì)應(yīng)一個(gè)下標(biāo)函數(shù)。一維數(shù)組An ，每個(gè)數(shù)組元素占一個(gè)存儲(chǔ)單元（不妨設(shè)為C個(gè)連續(xù)字節(jié)）. 數(shù)組元素A0的首地址Loc(A0)，則對(duì)于0i n-1，有：Loc(Ai)=Loc(A0)+i*C 4高維數(shù)組可轉(zhuǎn)化為一維數(shù)組計(jì)算元素的地址。高維數(shù)組有兩種存放次序

2、：按行優(yōu)先順序和按列優(yōu)先順序。BASIC、PASCAL、C/C+等程序設(shè)計(jì)語言中，數(shù)組按行優(yōu)先順序存放；FORTRAN語言、Matlab語言中，數(shù)組則按列優(yōu)先順序存放。5按行優(yōu)先順序，就是將數(shù)組元素按行向量的順序存儲(chǔ)，第i+1個(gè)行向量存儲(chǔ)在第i個(gè)行向量之后。二維數(shù)組的行優(yōu)先存儲(chǔ) 例 int x23 /*有23個(gè)數(shù)組元素*/ x00 x01 x02 x10 x11 x126按行優(yōu)先順序存放存儲(chǔ)分配順序?yàn)椋?x00 x01 x02 x10 x11 x12x00 x01x02x10 x11x127二維數(shù)組可以看作是一種特殊的一維數(shù)組。例 float a34; b0 a00 a01 a02 a03 b

3、- b1 a10 a11 a12 a13 b2 a20 a21 a22 a23 8二維數(shù)組amn中元素aij的地址：Loc(aij) = Loc(bi) +jCLoc(bi)=Loc(b0)+iC / C=nCLoc(aij)=Loc(a00)+inC+jC = Loc(a00) + (in+j) C b0 a00 a01 a02 a03 b- b1 a10 a11 a12 a13 b2 a20 a21 a22 a23 9例 float a34Loc(a12) = Loc(a00) +(in+j) C = Loc(a00) +(14+2) 4 = Loc(a00) +2410多維數(shù)組元素在內(nèi)存

4、中的排序順序?yàn)椋旱谝痪S的下標(biāo)變化最慢，最右邊的維下標(biāo)變化最快。 例 float a234三維數(shù)組a000a001a002a003a010a011a012a013a020a021a022a023a100a101a102a103 a110a111a112a113 a120a121a122a123 11三維數(shù)組amnp中元素aijk地址計(jì)算公式為： Loc(aijk)=Loc(a000)+(inp+jp+k)C12例 float D334Loc(D122) = Loc(D000)+(inp+jp+k)C = Loc(D000)+ (134+24+2)4 = Loc(D000)+ 8813 多維數(shù)組a

5、m1m2mn中ai1i2in的存儲(chǔ)地址 14按列優(yōu)先順序，就是將數(shù)組元素按列向量的順序存儲(chǔ)，第i+1個(gè)列向量存儲(chǔ)在第i個(gè)列向量之后。二維數(shù)組x23的按列優(yōu)先存儲(chǔ) x00 x01 x02 x10 x11 x12x00 x10 x01x11x02x1215如果計(jì)算按列優(yōu)先順序存儲(chǔ)的數(shù)組元素地址？請(qǐng)同學(xué)們自己推導(dǎo)。163.1 數(shù)組3.1.1 數(shù)組的存儲(chǔ)和尋址3.1.2 自定義一維數(shù)組類3.1.3 動(dòng)態(tài)數(shù)組17自定義一維數(shù)組類 數(shù)組類型是高級(jí)程序設(shè)計(jì)語言所提供的基本數(shù)據(jù)類型之一，可定義一組相同類型的元素。但是直接創(chuàng)建的數(shù)組存在著一些問題，諸如： 無法執(zhí)行一些基本數(shù)組運(yùn)算，如數(shù)組加法和數(shù)組減法等操作；

6、越界索引保護(hù)問題，即檢查數(shù)組的下標(biāo)索引值是否在0到arraysize-1范圍內(nèi)。一些高級(jí)程序設(shè)計(jì)語言對(duì)越界索引訪問并不一定會(huì)產(chǎn)生異常，沒有越界索引保護(hù)會(huì)直接給程序調(diào)試帶來難以預(yù)料的困難。為了彌補(bǔ)這些缺陷，可以自定義一個(gè)數(shù)組類。18一維數(shù)組類Array的類定義template class Array private:int size ; / 數(shù)組的規(guī)模T *alist ; / 指向數(shù)組的第一個(gè)元素的指針public:Array ( int size = 0 ) ;/ 初始構(gòu)造函數(shù)Array ( const Array & v ) ;/ 復(fù)制構(gòu)造函數(shù)Array ( ) delete alist ;

7、 ;/ 析構(gòu)函數(shù)19 int ArraySize ( ) return size ; / 返回?cái)?shù)組大小T & operator ( int i ) const ;/ 重載下標(biāo)符號(hào)Array & operator = ( const Array & v )/ 重載賦值運(yùn)算符=Array operator + ( ) const ;/ 重載一元加法運(yùn)算符+Array operator + ( const Array & v ) const ; / 重載二元加法運(yùn)算符+Array operator - ( ) const ;/ 重載一元減法運(yùn)算符-Array operator - ( const A

8、rray & v ) const ; / 重載二元減法運(yùn)算符-；203.1 數(shù)組3.1.1 數(shù)組的存儲(chǔ)和尋址3.1.2 自定義數(shù)組類3.1.3 動(dòng)態(tài)數(shù)組21動(dòng)態(tài)數(shù)組動(dòng)態(tài)數(shù)組類 Array 的定義 template class Array private： int FSize; /數(shù)組的大小 T* alist; /指向數(shù)組的第一個(gè)元素的指針22 public： Array( int sz=50 ); Array( const Array & x ); /復(fù)制構(gòu)造函數(shù) Array( ) delete alist; int ListSize(void) const return Fsize; Arr

9、ay& operator= (const Array& x); T& operator (int i); void Resize(int NewSize); /重定義數(shù)組大小，保留原來元素;23 template / 修改數(shù)組的大小 void ArrayReSize(int newSize) if (newSize = 0) cerr“數(shù)組大小無效.”endl; return; if (newSize != Fsize) newArray = new TnewSize; if (newArray=0) cerr“內(nèi)存分配異常.” endl; return; 24 int n=(newSize

10、= Fsize?newSsize:Fsize); for(int i=0;in;i+) newArrayi=alisti;/保留原數(shù)組中元素 delete alist; alist=newArray; FSize=newSize; 25例 編寫一個(gè)函數(shù)，要求輸入一個(gè)整數(shù)N，用動(dòng)態(tài)數(shù)組A來存放2 N之間所有5或7的倍數(shù)，輸出該數(shù)組。#include #include “array.h”void main( ) Array A(10); int N,count = 0; cinN; 26 for(int i=5;i=N;i+) if (i%5= =0|i%7= =0) Acount+=i; if

11、(count=A.ListSize( ) A.ReSize(count+10); for(int j=0;jcount;j+) coutAj“ ”; out : 5 7 10 14 15 20 21 25 28 3035 40 42 45 4950 out :N？ in: 5227第三章 數(shù)組和字符串3.1 數(shù)組3.2 矩陣3.3 字符串283.2 矩陣3.2.1 矩陣類3.2.2 特殊矩陣3.2.3 三元組表3.2.4 十字鏈表29 矩 陣 矩陣是常用的數(shù)據(jù)組織方式。計(jì)算機(jī)工作者關(guān)心的是矩陣在計(jì)算機(jī)中如何存儲(chǔ)，以及如何實(shí)現(xiàn)矩陣的基本操作。 用二維數(shù)組存放矩陣，或者利用自定義的二維數(shù)組類聲明矩

12、陣對(duì)象，存在以下問題：數(shù)組的基本操作是數(shù)組加減，而矩陣的基本操作還有矩陣相乘、矩陣轉(zhuǎn)置等；數(shù)組的下標(biāo)從0開始, 而矩陣的下標(biāo)一般從1開始；數(shù)組元素用aij表示, 而矩陣元素通常用a(i,j)表示。 因此，用二維數(shù)組類型或者自定義的二維數(shù)組類所創(chuàng)建的矩陣實(shí)用性不強(qiáng)，鑒于此，有必要自定義一個(gè)矩陣類。303.2.1 矩陣的類定義和實(shí)現(xiàn) templateclass Matrixprivate:int rows, cols; / 矩陣的行數(shù)和列數(shù)T *element; / 矩陣的元素public:Matrix(int r = 0, int c = 0); / 構(gòu)造函數(shù)Matrix(const Matri

13、x& m); / 復(fù)制構(gòu)造函數(shù) Matrix() delete element; / 析構(gòu)函數(shù)int Rows() const return rows; / 返回矩陣行數(shù)int Columns() const return cols; / 返回矩陣列數(shù)31T & operator() (int i, int j) const; / 重載下標(biāo)操作符Matrix& operator = (const Matrix& m); / 重載賦值運(yùn)算符Matrix operator + ( ) const; / 重載一元加法運(yùn)算符Matrix operator + (const Matrix & m) co

14、nst; / 重載二元加法運(yùn)算符Matrix operator - ( ) const; / 重載一元減法運(yùn)算符Matrix operator - (const Matrix & m) const; / 重載二元減法運(yùn)算符Matrix operator * (const Matrix & m) const; / 重載乘法運(yùn)算符；32算法Multi-1(A, B, C, m, p, n) / 求矩陣的乘積FOR i=1 TO m DO FOR j=1 TO n DO ( cij 0 . FOR k=1 TO p DO . ) 重載乘法操作符對(duì)于矩陣Amp和Bpn的乘積Cmn ，其第i行第j列元素

15、cij的計(jì)算公式為33 用一維數(shù)組存放矩陣，隨著矩陣元素行號(hào)或列號(hào)的變化，其在對(duì)應(yīng)的一維數(shù)組的下標(biāo)也要進(jìn)行相應(yīng)變換。設(shè)矩陣A和B分別按行優(yōu)先存放在一維數(shù)組s和t中，aik是矩陣A中第i行第k列的元素，bkj是矩陣B中第k行第j列的元素，則ai(k+1)在s中的下標(biāo)比aik在s中的下標(biāo)多1，b(k+1)j在t中的下標(biāo)比bkj在t中的下標(biāo)多n .34算法Multi-2(s, t, w, m, p, n)/* Amp用一維數(shù)組s存放，Bpn用一維數(shù)組t存放，求A與B的乘積Cmn并用一維數(shù)組w存放 */M1. 初始化 cw0 . / 初始時(shí)cw是c11在一維數(shù)組w中的下標(biāo)M2. 循環(huán) FOR i=1

16、TO m DO / 第一層循環(huán) (cs(i-1)p. / cs為ai1在一維數(shù)組s中的下標(biāo)35FOR j1 TO n DO / 第二層循環(huán) ( ctj-1. / 令ct為b1j在t中的下標(biāo) wcw0 . FOR k1 TO p DO / 第三層循環(huán)，疊加aikbkj 并存于wcw中，cw為cij在w中的下標(biāo) ( wcwwcwscstct. cscs1. / cs為A中本行下一列元素在s中的下標(biāo) ctctn.) / ct為B中本列下一行元素在t中的下標(biāo) cwcw1. ) ) 36分析：矩陣乘法算法中包含三層循環(huán)，所以其時(shí)間復(fù)雜性為O(mnp) . 373.2 矩陣3.2.1 矩陣類3.2.2 特

17、殊矩陣3.2.3 三元組表3.2.4 十字鏈表381、對(duì)角矩陣的壓縮存儲(chǔ)nn維方陣M是對(duì)角矩陣，則對(duì) i j (1 i , j n)，都有M(i, j)=0，即非對(duì)角線上的元素均為0 . 對(duì)于一個(gè)nn維對(duì)角矩陣，至多只有n個(gè)非零元素，因此只需存儲(chǔ)其n個(gè)對(duì)角元素的信息。采用一維數(shù)組dn來壓縮存儲(chǔ)對(duì)角矩陣，其中di存儲(chǔ)Mi,i的值。 392、三角矩陣的壓縮存儲(chǔ)三角矩陣分為上三角矩陣和下三角矩陣。方陣M是上對(duì)角矩陣，當(dāng)且僅當(dāng)ij時(shí)有M(i, j)=0 . 方陣M是下對(duì)角矩陣，當(dāng)且僅當(dāng)ij時(shí)有M(i, j)=0 . 50 15 35 25 0 10 20 60 0 0 30 10 0 0 0 4050

18、 0 0 015 10 0 035 20 30 0 25 60 10 4040以下三角矩陣為例，討論其壓縮存儲(chǔ)方法。考慮一個(gè)nn維下三角矩陣，其第一行有1個(gè)非零元素，第二行有2個(gè)非零元素，第n行有n個(gè)非零元素，非零元素共有(1+2+n) = n(n+1)/2個(gè)?？梢杂么笮閚(n+1)/2的一維數(shù)組來存儲(chǔ)下三角矩陣，即把下三角矩陣M的非零元素映射到一個(gè)一維數(shù)組d中。映射次序可采用按行優(yōu)先或按列優(yōu)先。假設(shè)映射采取按行優(yōu)先，非零元素M(i,j)會(huì)映射到一維數(shù)組d中的哪個(gè)元素？41設(shè)元素M(i,j)前面有k個(gè)元素，可以計(jì)算出 k =1+2+ (i-1) + (j-1)= i(i-1)/2 + (j-

19、1)設(shè)一維數(shù)組d的下標(biāo)是從0開始，則M(i,j)映射到d中所對(duì)應(yīng)的元素是dk . 有了k的計(jì)算公式，可以很容易實(shí)現(xiàn)下三角矩陣的壓縮存儲(chǔ)。 423、對(duì)稱矩陣的壓縮存儲(chǔ)方陣Mnn是對(duì)稱矩陣，當(dāng)且僅當(dāng)對(duì)于任何1 i, j n，均有M(i, j) = M(j, i) . 因?yàn)閷?duì)稱矩陣中M(i, j)與M(j, i)的信息相同，所以只需存儲(chǔ)M的上三角部分或下三角部分的元素信息。43參照下三角矩陣的壓縮存儲(chǔ)方法，即用大小為n(n+1)/2的一維數(shù)組來存儲(chǔ)，對(duì)于對(duì)稱矩陣中的下三角矩陣元素M(i, j) (ij) ，和下三角矩陣壓縮存儲(chǔ)的映射公式一樣，映射到dk (其中k = i(i-1)/2+(j-1) )

20、；對(duì)稱矩陣中的上三角矩陣元素M(i, j)， 因其元素值與下三角中的M(j,i)相同，故映射到dq (其中q=j(j-1)/2+(i-1). 有了k和q的計(jì)算公式，即可實(shí)現(xiàn)對(duì)稱矩陣的壓縮存儲(chǔ)。 444、稀疏矩陣的壓縮存儲(chǔ) 定義：設(shè)矩陣Amn中非零元素的個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于零元素的個(gè)數(shù)，則稱 A 為稀疏矩陣。 特點(diǎn)：零元素的分布沒有規(guī)律。 作用：解決空間浪費(fèi)的問題。45對(duì)于矩陣Amn 的每個(gè)元素aij，知道其行號(hào)i和列號(hào)j，就可以確定該元素在矩陣中的位置。因此，如果用一個(gè)結(jié)點(diǎn)來存儲(chǔ)一個(gè)非零元素的話，那么該結(jié)點(diǎn)可以設(shè)計(jì)如下： ijaij46由三個(gè)域（行號(hào)、列號(hào)和元素值）構(gòu)成的結(jié)點(diǎn)被稱為三元組結(jié)點(diǎn)：矩陣的每

21、個(gè)非零元素可由一個(gè)三元組結(jié)點(diǎn)（i，j，aij）唯一確定。如何在三元組結(jié)點(diǎn)的基礎(chǔ)上實(shí)現(xiàn)對(duì)整個(gè)稀疏矩陣的存儲(chǔ)？用順序存儲(chǔ)方式實(shí)現(xiàn)的三元組表鏈接存儲(chǔ)方式實(shí)現(xiàn)的十字鏈表。 473.2 矩陣3.2.1 矩陣類3.2.2 特殊矩陣3.2.3 三元組表3.2.4 十字鏈表48三元組表將表示稀疏矩陣的非零元素的三元組結(jié)點(diǎn)按行優(yōu)先的順序排列，得到一個(gè)線性表，將此線性表用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)起來，稱之為三元組表。 49 50 0 0 0 10 0 20 0 0 0 0 0 30 0 60 5AB0B1B2B3B4B50021501333-6020-301035020例 稀疏矩陣三元組表50 template / 三元

22、組的結(jié)點(diǎn)類 class Trituple firend class SparseMatrix; private: int row,col; / 非零元素的行號(hào)、列號(hào) T value; / 非零元素的值 ; 稀疏矩陣類的聲明51 class SparseMatrix private: / 稀疏矩陣的行數(shù)、列數(shù)及非零元素個(gè)數(shù) int Rows,Cols,Count; int MaxTerm; / 存儲(chǔ)三元組表的數(shù)組 Trituple smArrayMaxTerm; template / 稀疏矩陣類的聲明52public: / 建立一個(gè)稀疏矩陣 SparseMatrix( int Mrows,int

23、 Mcols); / 求轉(zhuǎn)置矩陣 SparseMatrix Transpose( ); /矩陣的其它運(yùn)算 / 求矩陣的和 SparseMatrix Add (SparseMatrix b); / 求矩陣的乘積 SparseMatrix Multiply (SparseMatrix b); ; 53 50 10 0 -30 0 0 0 0 0 20 0 -60 0 0 0 5A例 稀疏矩陣 50 0 0 0 10 0 20 0 0 0 0 0 -30 0 -60 5A轉(zhuǎn)置矩陣54 50 10 0 -30 0 0 0 0 0 20 0 -60 0 0 0 5A例 稀疏矩陣的三元組表示 50 0 0

24、 0 10 0 20 0 0 0 0 0 -30 0 -60 5Aa0a1a2a3a4a500502120011033523-6003-30b0b1b2b3b4b5005030-30101033532-60122055算法Transpose (a, b) / 已知矩陣A存放在三元組表a中，求A的轉(zhuǎn)置矩陣并將其保存在三元組表b中 T1. 初始化 j0. / 首先考察三元組表b的第一個(gè)結(jié)點(diǎn)b0T2. a為空？ IF count 0 THEN/ 若a非空，開始確定bj中存放的非零元素的行號(hào)、列號(hào)、非零元素值 ( FOR k0 TO n-1 DO / 對(duì)每個(gè)列號(hào)k FOR i0 TO count-1

25、DO /依次掃描a中列號(hào)為k的元素 56 b0b1b2b3b4b5005030-30101033532-601220a0a1a2a3a4a500502120011033523-6003-30IF (col( ai )k THEN ( row(bj)k. / 該元素在b中的行號(hào)為k col(bj)row(ai). /在b中的列號(hào)為其在a中的行號(hào) value( bj )value( ai ).) jj1. ) / 考察三元組表b中的下一個(gè)結(jié)點(diǎn) 57對(duì)于用三元組表存儲(chǔ)的稀疏矩陣Amn，若矩陣非零元素個(gè)數(shù)為t，求Amn的轉(zhuǎn)置矩陣的時(shí)間復(fù)雜性是多少呢？觀察Transpose函數(shù)不難發(fā)現(xiàn)，函數(shù)中包含雙重循

26、環(huán)，第一重循環(huán)是對(duì)轉(zhuǎn)置矩陣A按行優(yōu)先依次確認(rèn)非零元素，故循環(huán)次數(shù)為A的行數(shù)n；第二重循環(huán)是掃描原矩陣的三元組表，執(zhí)行次數(shù)是矩陣非零元素個(gè)數(shù)t，顯然，求轉(zhuǎn)置矩陣的時(shí)間復(fù)雜性為O(nt) .能否找到時(shí)間復(fù)雜性為O(n+t)的算法呢？（課后作業(yè)） 583.2 矩陣3.2.1 矩陣類3.2.2 特殊矩陣3.2.3 三元組表3.2.4 十字鏈表59LEFTUPROWCOLVAL 800070900004060043214321十字鏈表矩陣的元素結(jié)構(gòu)如下：分別表示該元素的左鄰非零元素、上鄰非零元素、所在的行、所在的列和它的值。例：稀疏矩陣60 矩陣的每一行、每一列都設(shè)置為由一個(gè)表頭結(jié)點(diǎn)引導(dǎo)的循環(huán)鏈表，并且

27、各行和各列的表頭結(jié)點(diǎn)有如下特點(diǎn)： -1 = COL（Loc（BASEROWi） 0 -1 = ROW（Loc（BASECOLj）s1和couts2等。71class String private:char *str; / 指向動(dòng)態(tài)申請(qǐng)的字符串首地址的指針int size; / 字符串的長度+1，多出一個(gè)字節(jié)以存放字符串尾部的結(jié)束符 0public:String ( char *s = “” ); / 構(gòu)造函數(shù)String ( const String &s ); / 復(fù)制構(gòu)造函數(shù)String (void); / 析構(gòu)函數(shù)char & operator (int n); / 下標(biāo)運(yùn)算符重載Str

28、ing & operator = (const String & s); / 賦值運(yùn)算符重載把String對(duì)象賦值給當(dāng)前對(duì)象String & operator = (const char * s); / 賦值運(yùn)算符重載把一個(gè)C+串賦值給當(dāng)前對(duì)象/ 各種關(guān)系運(yùn)算符的重載，如“= =”, “!=”, “”等 自定義字符串類String72/ 串拼接運(yùn)算符重載String & operator + (const String & s) const; / 將當(dāng)前對(duì)象與一個(gè)String拼接String & operator + (const char * s) const; / 將當(dāng)前對(duì)象與一個(gè)C+串拼

29、接friend String operator + (char * str, const String & s); / 將C+串與String串拼接/ 串函數(shù)int Find (char c, int start) const; / 從start位置開始找字符cint FindLast (char c) const; / 返回字符c最后出現(xiàn)的位置String Substr (int index, int count); / 取子串 void Insert (const String & s, int index); / 在index位置插入一個(gè)String串void Insert ( char

30、 * s, int index); / 向當(dāng)前對(duì)象的index位置插入一個(gè)C+串void Remove ( int index, int count);/ 刪除子串operator char * (void) const; / 將String串轉(zhuǎn)換成C+串friend ostream & operator (istream & istr, String & s); / 輸入運(yùn)算符重載intLength (void) const;int IsEmpty (void) const;void Clear (void);73(1) 構(gòu)造函數(shù)，申請(qǐng)內(nèi)存并將一個(gè)C+串復(fù)制給當(dāng)前對(duì)象String:Strin

31、g ( char * s)size = strlen(s); / 串的長度str = new char size+1; / 為串申請(qǐng)空間if (str = = NULL) / 若申請(qǐng)失敗，退出程序 cout“outofMemory” endl; exit(1); strcpy(str, s); / 將c+串s復(fù)制到str;字符串類部分函數(shù)的實(shí)現(xiàn)74(2)賦值運(yùn)算符重載把一個(gè)String對(duì)象賦值給當(dāng)前對(duì)象String & String: operator = (const String & s)/*若s的長度與當(dāng)前對(duì)象長度不符，則刪除當(dāng)前對(duì)象所占空間，重新申請(qǐng)內(nèi)存空間*/if (s.size !

32、= size)delete str;str = new chars.size+1;if (str = = NULL) / 若申請(qǐng)空間失敗，則退出 cout“outofMemory” endl; exit(1); size = s.size;strcpy(str, s.str); / 將s復(fù)制到當(dāng)前對(duì)象return *this;75(3)拼接運(yùn)算符重載string+stringString String: operator + (const String & s) const String temp; / 創(chuàng)建一個(gè)臨時(shí)串tempdelete temp.str; / 釋放創(chuàng)建temp時(shí)所申請(qǐng)的空間

33、int len = size + s.size;temp.str = new charlen+1; / 為存放拼接串申請(qǐng)空間if (temp.str = = NULL) / 若申請(qǐng)空間失敗，則退出 cout“outofMemory” = size ) / 若index大于串長return temp; / 返回空串if ( count charleft ) / 若count大于剩下的字符數(shù)，則子串取剩下的字符count = charleft;delete temp.str; / 釋放創(chuàng)建temp時(shí)產(chǎn)生的空串temp.str = new charcount + 1; / 為子串動(dòng)態(tài)申請(qǐng)空間if (

34、 temp.str = = NULL)/ 若申請(qǐng)失敗，則返回 cout“outofMemory” endl; exit(1); 77 char *p = temp.str; / 令字符指針p指向暫無內(nèi)容的字符數(shù)組temp.str的首字符處char *q = &strindex; / 令字符指針q指向當(dāng)前對(duì)象的str數(shù)組下標(biāo)index處for ( int i =0; i = size ) / start超過串長 cout“start位置無效” endl; exit(1); int i = start;while ( stri != 0 & stri != c ) i +; / 查找字符c，若當(dāng)前

35、對(duì)象中沒有字符c，則循環(huán)在串尾結(jié)束if ( stri = = 0 ) / 未找到字符c，則返回-1return -1;return i; / 否則，返回字符c在當(dāng)前對(duì)象中的位置792、串的鏈?zhǔn)酱鎯?chǔ)：串的鏈接存儲(chǔ)是把可用的存儲(chǔ)空間分成一系列大小相同的結(jié)點(diǎn)，其中每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)為： （str, link）5chinap 結(jié)點(diǎn)大小為4的鏈串Sc5hian 結(jié)點(diǎn)大小為1的鏈串80算法SI（S , T, i . S)/*S和T是兩個(gè)鏈?zhǔn)酱?算法SI將串T插到串S的第 i 個(gè)字符之后;串S和T之元素有兩個(gè)域sym和link，sym域之值為字符， link域存放指向下一結(jié)點(diǎn)的指針，串S和T之首結(jié)點(diǎn)的sym域之

36、值為串長 */SI1.初始化L1STR(S). L2 STR(T). IF (iL1) THEN (PRINTString Length error. RETURN )IF L2=0 THEN RETURN. IF L1=0 THEN ( S T. RETURN )81STRI2尋找插入位置 P S. j 0.WHILE ( j i ) DO( P LINK(P). j j+1 )STRI3插入 T1 LINK(T). SAVE LINK(P).LINK(P) T1.WHILE LINK(T1) =NULL DOT1 LINK(T1). /*T1指向串的尾部結(jié)點(diǎn)*/LINK(T1) SAVE.STR(S) L1+L2. 823.3 字符串3.3.1字符串的定義和實(shí)現(xiàn)3.3.2 模式匹配算法83在目標(biāo)串中尋找模式串出現(xiàn)的首位置； 給定兩個(gè)字符串S和P，其中目標(biāo)S有n個(gè)字符，模式P有m個(gè)字符，m=n。從S的第一個(gè)字符開始，搜索模式P，如果找到，返回模式P的第一個(gè)字符在S中的位置；如果沒找到（即S中不包含P），則返回-1 。 例：S= “abaaabab”, P = “abab” 1、 模式匹配問題定義84模式匹配的應(yīng)用 - 文本編輯器中常用的“查找”、“替換” - 搜索引擎中的關(guān)鍵