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

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

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

3、 b2 a20 a21 a22 a23 二維數(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 例 float a34Loc(a12) = Loc(a00) +(in+j) C = Loc(a00) +(14+2) 4 = Loc(a00) +24多維數(shù)組元素在內(nèi)存中的排序順序?yàn)椋旱谝痪S的下標(biāo)變化最慢，最右邊的維

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

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

6、ze(int NewSize);/重新定義數(shù)組的大小; 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; int n=(newSize = Fsize?newSsize:Fsize); for(int i=0;in;i+) newArrayi=alisti;/保留原數(shù)組中元素 de

7、lete alist; alist=newArray; FSize=newSize; 例 編寫一個(gè)函數(shù)，要求輸入一個(gè)整數(shù)N，用動態(tài)數(shù)組A來存放2 N之間所有5或7的倍數(shù)，輸出該數(shù)組。#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時(shí)有M(i, j)=0 . 方陣M是下對角矩陣，當(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 0 0 015 10 0 035 20 30 0 25 60 10 40以下三角矩陣為例，討論其壓縮存儲方法?？紤]一個(gè)nn維下三角矩陣，其第一行有1個(gè)非零元素，第二行有2個(gè)非零元素，第n行有n個(gè)非零元素，非零元素共有(1+2+n) = n(n+1)/2個(gè)。可以用大小為n(n+1)/2的一維數(shù)組來存儲下三角矩陣，即把下三角矩陣M的非零元素映射到一個(gè)一維數(shù)組d中。映射次序可采用按行優(yōu)先或按列

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

10、大小為n(n+1)/2的一維數(shù)組來存儲，對于對稱矩陣中的下三角矩陣元素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的計(jì)算公式，即可實(shí)現(xiàn)對稱矩陣的壓縮存儲。 4、稀疏矩陣的壓縮存儲 定義：設(shè)矩陣Amn中非零元素的個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于零元素的個(gè)數(shù)，則稱 A 為稀疏矩陣。 特點(diǎn)：零元素的分布沒有規(guī)律。 作用：解決空間浪費(fèi)的問題。對于矩陣Amn 的每個(gè)元素aij，知道其行號i和列號j

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

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

13、m; template / 稀疏矩陣類的聲明public: / 建立一個(gè)稀疏矩陣 SparseMatrix( int Mrows,int Mcols); / 求轉(zhuǎn)置矩陣 SparseMatrix Transpose( ); /矩陣的其它運(yùn)算 / 求矩陣的和 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、轉(zhuǎn)置矩陣 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) 描述：假設(shè)稀疏矩陣存儲在一個(gè)三元組表 a 中, 且 A 的非零元素個(gè)數(shù)為count, Transpose求A的轉(zhuǎn)置矩陣并將其保存在三元組表b中. 算法的主要思想：針對每個(gè)列號k(k0, 1, , n1), 對a進(jìn)行掃描,

15、考察a中是否有列號為k的結(jié)點(diǎn), 若有記為au (假定au在a中的行號為i), 將au依次(可能列號為k的結(jié)點(diǎn)不止一個(gè))保存在b的bw中, 則row(bw)k, col(bw) i, val(bw) val(au). 算法Transpose (a, b) / 已知矩陣A存放在三元組表a中，求A的轉(zhuǎn)置矩陣并將其保存在三元組表b中 T1. 初始化 j0. / 首先考察三元組表b的第一個(gè)結(jié)點(diǎn)b0T2. a為空？ IF count 0 THEN/ 若a非空，開始確定bj中存放的非零元素的行號、列號、非零元素值 ( FOR k0 TO n-1 DO / 對每個(gè)列號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中的下一個(gè)結(jié)點(diǎn) 對于用三元組表存儲的稀疏矩陣Amn，若矩陣非零元素個(gè)數(shù)為t，求Amn的轉(zhuǎn)置矩陣的時(shí)間復(fù)雜性是多少呢？觀察Transpose函數(shù)不難發(fā)現(xiàn)，函數(shù)中包含雙重循環(huán)，第一重循

17、環(huán)是對轉(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è)） 3.2 矩陣3.2.1 特殊矩陣3.2.2 三元組表3.2.3 十字鏈表LEFTUPROWCOLVAL 十字鏈表矩陣的元素結(jié)構(gòu)如下：分別表示該元素的左鄰非零元素、上鄰非零元素、所在的行、所在的列和它的值。例：稀疏矩陣 矩陣的每一行、每一列都設(shè)置為由一個(gè)表頭結(jié)點(diǎn)引導(dǎo)的循環(huán)鏈表，并且各行和各列的表頭結(jié)點(diǎn)有如下特點(diǎn)： -1 = COL（Loc（BASEROWi） 0 -1

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

19、s a string B = is 子串B = is在主串中的位置是3 1、串的順序存儲：把一個(gè)串所包含的字符序列相繼存入連續(xù)的字節(jié)中 (1) 非緊縮格式 : 一個(gè)存儲單元存放一個(gè)字符 例 S a0a1 an-1 a0a1an-1Word0Word1Wordn-1字符串的存儲方式(2) 緊縮格式 : 一個(gè)存儲單元存放多個(gè)字符 例 S= a0a1 an-1 / 一個(gè)存儲單元存放4個(gè)字符 a1a4an-1Word0Word1a0a2a3a5a6a7an-2Word n/4 -12、串的鏈?zhǔn)酱鎯Γ捍逆溄哟鎯κ前芽捎玫拇鎯臻g分成一系列大小相同的結(jié)點(diǎn)，其中每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)為： （str, link）5

20、chinap 結(jié)點(diǎn)大小為4的鏈串Sc5hian 結(jié)點(diǎn)大小為1的鏈串class String private:char *str; / 指向動態(tài)申請的字符串首地址的指針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)算符重載String & operator = (const String & s); / 賦值運(yùn)算符

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

22、tring & 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 * s, int index); / 向當(dāng)前對象的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);3.3 字符串3.3.1字符串的定義和實(shí)現(xiàn)3.3.2 模式