1、第三章 數組和字符串3.1 數組3.2 矩陣3.3 字符串3.1 數組3.1.1 數組的存儲和尋址3.1.2 動態數組一維數組是若干個元素的有限序列。元素本身就是一個數據結構。一維數組的元素必須具有相同的類型，每個數組元素都占據相同大小的存儲空間。一維數組采用順序存儲結構。每個元素都通過一個下標來指定，故一個一維數組對應一個下標函數。一維數組An ，設每個數組元素的長度為C（不妨設為C個連續字節）. 數組元素A0的首地址Loc(A0)，則對于0i n-1，有：Loc(Ai)=Loc(A0)+i*C 高維數組可轉化為一維數組計算元素的地址。高維數組有兩種存放次序：按行優先順序和按列優先順序。BA

2、SIC、PASCAL、C/C+等程序設計語言中，數組按行優先順序存放；FORTRAN語言、Matlab語言中，數組則按列優先順序存放。按行優先順序，就是將數組元素按行向量的順序存儲，第i+1個行向量存儲在第i個行向量之后。二維數組的行優先存儲 例 int x23 /*有23個數組元素*/ x00 x01 x02 x10 x11 x12按行優先順序存放存儲分配順序為： x00 x01 x02 x10 x11 x12x00 x01x02x10 x11x12二維數組可以看作是一種特殊的一維數組。例 float a34; b0 a00 a01 a02 a03 b- b1 a10 a11 a12 a13

3、 b2 a20 a21 a22 a23 二維數組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 例 float a34Loc(a12) = Loc(a00) +(in+j) C = Loc(a00) +(14+2) 4 = Loc(a00) +24多維數組元素在內存中的排序順序為：第一維的下標變化最慢，最右邊的維

4、下標變化最快。 例 float a234三維數組a000a001a002a003a010a011a012a013a020a021a022a023a100a101a102a103 a110a111a112a113 a120a121a122a123 三維數組Amnp中數組元素aijk地址計算公式為： Loc(aijk)=Loc(a000)+i*n*p*C+j*p*C+k*C按列優先順序，就是將數組元素按列向量的順序存儲，第i+1個列向量存儲在第i個列向量之后。二維數組x23的按列優先存儲 x00 x01 x02 x10 x11 x12x00 x10 x01x11x02x123.1 數組3.1.1

5、數組的存儲和尋址3.1.2 動態數組動態數組動態數組類 Array 的定義 template class Array private： int FSize; /數組的大小 T* alist; /指向數組的第一個元素的指針 public： Array( int sz=50 ); Array( const Array & x ); /復制構造函數 Array( ) delete alist; int ListSize(void) const return Fsize; Array& operator= (const Array& x); T& operator (int i); void Resi

6、ze(int NewSize);/重新定義數組的大小; template / 修改數組的大小 void ArrayReSize(int newSize) if (newSize = 0) cerr“數組大小無效.”endl; return; if (newSize != Fsize) newArray = new TnewSize; if (newArray=0) cerr“內存分配異常.” endl; return; int n=(newSize = Fsize?newSsize:Fsize); for(int i=0;in;i+) newArrayi=alisti;/保留原數組中元素 de

7、lete alist; alist=newArray; FSize=newSize; 例 編寫一個函數，要求輸入一個整數N，用動態數組A來存放2 N之間所有5或7的倍數，輸出該數組。#include #include “array.h”void main( ) Array A(10); int N,count = 0; cinN; for(int i=5;i=N;i+) if (i%5= =0|i%7= =0) Acount+=i; if (count=A.ListSize( ) A.ReSize(count+10); for(int j=0;jcount;j+) coutAj“ ”; if(

8、j+1) % 5=0) coutj時有M(i, j)=0 . 方陣M是下對角矩陣，當且僅當ij時有M(i, j)=0 . 50 15 35 25 0 10 20 60 0 0 30 10 0 0 0 4050 0 0 015 10 0 035 20 30 0 25 60 10 40以下三角矩陣為例，討論其壓縮存儲方法。考慮一個nn維下三角矩陣，其第一行有1個非零元素，第二行有2個非零元素，第n行有n個非零元素，非零元素共有(1+2+n) = n(n+1)/2個。可以用大小為n(n+1)/2的一維數組來存儲下三角矩陣，即把下三角矩陣M的非零元素映射到一個一維數組d中。映射次序可采用按行優先或按列

9、優先。假設映射采取按行優先，非零元素M(i,j)會映射到一維數組d中的哪個元素？設元素M(i,j)前面有k個元素，可以計算出 k =1+2+ (i-1) + (j-1)= i(i-1)/2 + (j-1)設一維數組d的下標是從0開始，則M(i,j)映射到d中所對應的元素是dk . 有了k的計算公式，可以很容易實現下三角矩陣的壓縮存儲。 3、對稱矩陣的壓縮存儲方陣Mnn是對稱矩陣，當且僅當對于任何1 i, j n，均有M(i, j) = M(j, i) . 因為對稱矩陣中M(i, j)與M(j, i)的信息相同，所以只需存儲M的上三角部分或下三角部分的元素信息。參照下三角矩陣的壓縮存儲方法，即用

10、大小為n(n+1)/2的一維數組來存儲，對于對稱矩陣中的下三角矩陣元素M(i, j) (ij) ，和下三角矩陣壓縮存儲的映射公式一樣，映射到dk (其中k = i(i-1)/2+(j-1) )；對稱矩陣中的上三角矩陣元素M(i, j)， 因其元素值與下三角中的M(j,i)相同，故映射到dq (其中q=j(j-1)/2+(i-1). 有了k和q的計算公式，即可實現對稱矩陣的壓縮存儲。 4、稀疏矩陣的壓縮存儲 定義：設矩陣Amn中非零元素的個數遠遠小于零元素的個數，則稱 A 為稀疏矩陣。 特點：零元素的分布沒有規律。 作用：解決空間浪費的問題。對于矩陣Amn 的每個元素aij，知道其行號i和列號j

11、，就可以確定該元素在矩陣中的位置。因此，如果用一個結點來存儲一個非零元素的話，那么該結點可以設計如下： ijaij由三個域（行號、列號和元素值）構成的結點被稱為三元組結點：矩陣的每個非零元素可由一個三元組結點（i，j，aij）唯一確定。如何在三元組結點的基礎上實現對整個稀疏矩陣的存儲？用順序存儲方式實現的三元組表鏈接存儲方式實現的十字鏈表。 3.2 矩陣3.2.1 特殊矩陣3.2.2 三元組表3.2.3 十字鏈表三元組表將表示稀疏矩陣的非零元素的三元組結點按行優先的順序排列，得到一個線性表，將此線性表用順序存儲結構存儲起來，稱之為三元組表。 50 0 0 0 10 0 20 0 0 0 0 0

12、 30 0 60 5AB0B1B2B3B4B50021501333-6020-301035020例 稀疏矩陣三元組表 template / 三元組的結點類 class Trituple firend class SparseMatrix; private: int row,col; / 非零元素的行號、列號 T value; / 非零元素的值 ; 稀疏矩陣類的聲明 class SparseMatrix private: / 稀疏矩陣的行數、列數及非零元素個數 int Rows,Cols,Count; int MaxTerm; / 存儲三元組表的數組 Trituple smArrayMaxTer

13、m; template / 稀疏矩陣類的聲明public: / 建立一個稀疏矩陣 SparseMatrix( int Mrows,int Mcols); / 求轉置矩陣 SparseMatrix Transpose( ); /矩陣的其它運算 / 求矩陣的和 SparseMatrix Add (SparseMatrix b); / 求矩陣的乘積 SparseMatrix Multiply (SparseMatrix b); ; 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

14、轉置矩陣 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 5Aa0a1a2a3a4a500502120011033523-6003-30b0b1b2b3b4b5005030-30101033532-601220算法Transpose (a, b) 描述：假設稀疏矩陣存儲在一個三元組表 a 中, 且 A 的非零元素個數為count, Transpose求A的轉置矩陣并將其保存在三元組表b中. 算法的主要思想：針對每個列號k(k0, 1, , n1), 對a進行掃描,

15、考察a中是否有列號為k的結點, 若有記為au (假定au在a中的行號為i), 將au依次(可能列號為k的結點不止一個)保存在b的bw中, 則row(bw)k, col(bw) i, val(bw) val(au). 算法Transpose (a, b) / 已知矩陣A存放在三元組表a中，求A的轉置矩陣并將其保存在三元組表b中 T1. 初始化 j0. / 首先考察三元組表b的第一個結點b0T2. a為空？ IF count 0 THEN/ 若a非空，開始確定bj中存放的非零元素的行號、列號、非零元素值 ( FOR k0 TO n-1 DO / 對每個列號k FOR i0 TO count-1 D

16、O /依次掃描a中列號為k的元素 b0b1b2b3b4b5005030-30101033532-601220a0a1a2a3a4a500502120011033523-6003-30IF (col( ai )k THEN ( row(bj)k. / 該元素在b中的行號為k col(bj)row(ai). /在b中的列號為其在a中的行號 value( bj )value( ai ).) jj1. ) / 考察三元組表b中的下一個結點 對于用三元組表存儲的稀疏矩陣Amn，若矩陣非零元素個數為t，求Amn的轉置矩陣的時間復雜性是多少呢？觀察Transpose函數不難發現，函數中包含雙重循環，第一重循

17、環是對轉置矩陣A按行優先依次確認非零元素，故循環次數為A的行數n；第二重循環是掃描原矩陣的三元組表，執行次數是矩陣非零元素個數t，顯然，求轉置矩陣的時間復雜性為O(nt) .能否找到時間復雜性為O(n+t)的算法呢？（課后作業） 3.2 矩陣3.2.1 特殊矩陣3.2.2 三元組表3.2.3 十字鏈表LEFTUPROWCOLVAL 十字鏈表矩陣的元素結構如下：分別表示該元素的左鄰非零元素、上鄰非零元素、所在的行、所在的列和它的值。例：稀疏矩陣 矩陣的每一行、每一列都設置為由一個表頭結點引導的循環鏈表，并且各行和各列的表頭結點有如下特點： -1 = COL（Loc（BASEROWi） 0 -1

18、= ROW（Loc（BASECOLj） 0第三章 數組和字符串3.1 數組3.2 矩陣3.3 字符串3.3 字符串3.3.1字符串的定義和實現3.3.2 模式匹配算法串的定義：串是由零個或多個字符順序排列組成的有限序列。如字符串 S 可記作： Sa0a1 an-1S是串名，引號中的字符序列是串值，字符個數n是串長度。 空串：長度為零的串稱為空串。 空白串：由一個或多個空格組成的串稱為空白串。 3.3.1 字符串的定義和實現子串：若把某個串稱為主串，則主串中任意個連續的字符組成的子序列被稱為子串。子串在主串中第一次出現時，其首字符在主串中的序號被稱為該子串在主串中的位置。例 A = This i

19、s a string B = is 子串B = is在主串中的位置是3 1、串的順序存儲：把一個串所包含的字符序列相繼存入連續的字節中 (1) 非緊縮格式 : 一個存儲單元存放一個字符 例 S a0a1 an-1 a0a1an-1Word0Word1Wordn-1字符串的存儲方式(2) 緊縮格式 : 一個存儲單元存放多個字符 例 S= a0a1 an-1 / 一個存儲單元存放4個字符 a1a4an-1Word0Word1a0a2a3a5a6a7an-2Word n/4 -12、串的鏈式存儲：串的鏈接存儲是把可用的存儲空間分成一系列大小相同的結點，其中每個結點的結構為： （str, link）5

20、chinap 結點大小為4的鏈串Sc5hian 結點大小為1的鏈串class String private:char *str; / 指向動態申請的字符串首地址的指針int size; / 字符串的長度+1，多出一個字節以存放字符串尾部的結束符 0public:String ( char *s = “” ); / 構造函數String ( const String &s ); / 復制構造函數String (void); / 析構函數char & operator (int n); / 下標運算符重載String & operator = (const String & s); / 賦值運算符

21、重載把String對象賦值給當前對象String & operator = (const char * s); / 賦值運算符重載把一個C+串賦值給當前對象/ 各種關系運算符的重載，如“= =”, “!=”, “”等 自定義字符串類String/ 串拼接運算符重載String & operator + (const String & s) const; / 將當前對象與一個String拼接String & operator + (const char * s) const; / 將當前對象與一個C+串拼接friend String operator + (char * str, const S

22、tring & s); / 將C+串與String串拼接/ 串函數int Find (char c, int start) const; / 從start位置開始找字符cint FindLast (char c) const; / 返回字符c最后出現的位置String Substr (int index, int count); / 取子串 void Insert (const String & s, int index); / 在index位置插入一個String串void Insert ( char * s, int index); / 向當前對象的index位置插入一個C+串void Remove ( int index, int count);/ 刪除子串operator char * (void) const; / 將String串轉換成C+串friend ostream & operator (istream & istr, String & s); / 輸入運算符重載intLength (void) const;int IsEmpty (void) const;void Clear (void);3.3 字符串3.3.1字符串的定義和實現3.3.2 模式