第4章數(shù)組和字符串4.1

數(shù)組4.2

特殊矩陣4.3

稀疏矩陣4.4

字符串4.1數(shù)組

數(shù)組是非常有用的數(shù)據(jù)結(jié)構(gòu)，幾乎所有的高級(jí)程序設(shè)計(jì)語言中都提供了數(shù)組類型。本章從數(shù)據(jù)結(jié)構(gòu)的角度介紹數(shù)組的概念、它的抽象數(shù)據(jù)類型和類的定義。在自然科學(xué)中，矩陣常被用于解決許多實(shí)際問題。由于稀疏矩陣在存儲(chǔ)表示上的特點(diǎn)，本章也對(duì)它進(jìn)行專門的討論。

數(shù)組的定義數(shù)組是下標(biāo)index和值value組成的序?qū)Φ募稀?index,value)一維數(shù)組：A={(0,15),(1,24),(2,33),(3,21)}

4.1.1

數(shù)組ADT

數(shù)組抽象數(shù)據(jù)類型ADTArray{Data:

下標(biāo)index和元素值value組成的數(shù)據(jù)對(duì)集合,其中任意兩個(gè)數(shù)據(jù)對(duì)的下標(biāo)index各不相同。Operations:Create():

建立一個(gè)數(shù)組。

Retrieve(i):返回下標(biāo)為i的元素值。

Store(i,x):將下標(biāo)為i的數(shù)據(jù)對(duì)的值置為x。};

一維數(shù)組的順序表示二維數(shù)組的順序表示多維數(shù)組的順序表示4.1.2數(shù)組的順序表示

一維數(shù)組的順序表示

地址計(jì)算:設(shè)第一個(gè)數(shù)組元素a[0]的存儲(chǔ)地址是loc(a[0])，若已知每個(gè)數(shù)組元素占k個(gè)存儲(chǔ)單元，則下標(biāo)為i的數(shù)組元素a[i]的存儲(chǔ)地址loc(a[i])為

loc(a[i])=loc(a[0])+i*ki=0,1,2,…,n-1。

二維數(shù)組的順序表示

二維數(shù)組a[m][n]映射到一維的存儲(chǔ)空間時(shí)有兩種順序：行優(yōu)先和列優(yōu)先。大多數(shù)語言如PASCAL、BASIC、C、C++等都是按行優(yōu)先順序存儲(chǔ)的，F(xiàn)ORTRAN是按列優(yōu)先順序存儲(chǔ)的。地址計(jì)算loc(a[i][j])=loc(a[0][0])+(i*n+j)*k

(0

i<m;0

j<n)loc(a[i][j])=loc(a[0][0])+(j*m+i)*k

多維數(shù)組的順序表示

推廣到多維數(shù)組a[m1][m2]…[mn]，數(shù)組元素a[i1][i2]…[in]的存儲(chǔ)地址為：loc(a[i1][i2]…[in])=loc(a[0]…[0])+(i1*m2*m3*…*mn

+i2*m3*m4*…*mn+…+in-1*mn

+in

)*k=

用C++的模板類定義的一維數(shù)組抽象數(shù)據(jù)類型。公有成員函數(shù)包括：構(gòu)造函數(shù)析構(gòu)函數(shù)重載下標(biāo)操作符：[]

重載下標(biāo)操作符用來返回指向第i個(gè)元素的引用重載數(shù)組賦值：＝

賦值操作符實(shí)現(xiàn)數(shù)組的整體賦值。4.1.3一維數(shù)組的C++類

#include<assert.h>template<classT>classArray1D{public:Array1D(intsz=0);~Array1D(){delete[]elements;}T&operator[](inti)const;Array1D<T>&operator=(constArray1D<T>&r);friendistream&operator>>(istream&in,Array1D<T>&r);friendostream&operator<<(ostream&out,constArray1D<T>&r);private:

intsize; T*elements;};template<classT>Array1D<T>::Array1D(intsz){

assert(sz>=0);//越界檢查

size=sz;elements=newT[sz];}

template<classT>T&Array1D<T>::operator[](inti)const{//越界檢查

assert(i>=0&&i<size); returnelements[i];}template<classT>Array1D<T>&Array1D<T>::operator=(constArray1D<T>&r)//數(shù)組r整體賦值給this{if(this!=&r){//防止自我賦值

size=r.size; delete[]elements;//釋放原空間

elements=newT[size];//重新分配空間

for(inti=0;i<size;i++)elements[i]=r.elements[i];}return*this;}例如：c=btemplate<classT>Istream&operator>>(istream&in,Array1D<T>&r){

cout<<"Intputarray\n";

for(inti=0;i<r.size;i++)in>>r.elements[i];returnin;}template<classT>ostream&operator<<(ostream&out,constArray1D<T>&r){

cout<<"Array=";

for(inti=0;i<r.size;i++)out<<r.elements[i]<<'';out<<endl;returnout;}#include"array1d.h"voidmain(){Array1D<int>a(5),b(8);Array1D<int>c;//采用缺省長(zhǎng)度0

cin>>a;cout<<"a"<<a;

cin>>b;cout<<"b"<<b;

cout<<"c"<<c;

cout<<"a[0]="<<a[0]<<“;“<<"b[5]="<<b[5]<<endl;c=b;cout<<"c=b,c"<<c;b=a;cout<<"b=a,b"<<b;}4.2特殊矩陣對(duì)稱矩陣和三角矩陣在n×n的矩陣A中，若aij=aji(0<i,j<n)，則稱其為n階對(duì)稱矩陣。對(duì)于對(duì)稱矩陣，可以只存儲(chǔ)上三角(或下三角)中的元素(包括對(duì)角線上的元素)。01

k4.2.1對(duì)稱矩陣4.3稀疏矩陣

稀疏矩陣：

大多數(shù)元素為零的矩陣稱為稀疏矩陣。4.3稀疏矩陣

1、稀疏矩陣的操作在稀疏矩陣上執(zhí)行的操作本質(zhì)上是普通矩陣的操作，ADT4.2定義了包括建立、加法、乘法和轉(zhuǎn)置操作的抽象數(shù)據(jù)類型。ADTSparseMatrix{數(shù)據(jù)：絕大多數(shù)元素為零的矩陣。運(yùn)算：

Create();建立一個(gè)稀疏矩陣。

Destroy():撤消一個(gè)稀疏矩陣。

Add(B,C):當(dāng)前矩陣對(duì)象與B相加，C中返回相加和。

Mul(B,C):當(dāng)前矩陣對(duì)象與B相乘，C中返回相乘積。

Transpose(B):B中返回當(dāng)前矩陣對(duì)象的轉(zhuǎn)置矩陣。}4.3.1稀疏矩陣ADT稀疏矩陣的C++類template<classT>classSparseMatrix{public:

SparseMatrix(int

maxRowSize,int

maxColSize){};~SparseMatrix(){};virtualvoidAdd(constSparseMatrix<T>&B,

SparseMatrix<T>&C)const;virtualvoidMul(const

SparseMatrix<T>&B,

SparseMatrix<T>&C)const;virtualvoidTranspose(SparseMatrix<T>&B)const;private:

int

maxRows,maxCols;};

三元組表示法4.3.2稀疏矩陣的順序表示

按照壓縮存儲(chǔ)的思想，稀疏矩陣Am

n中的每一個(gè)非零元素aij的行號(hào)、列號(hào)和值可以用一個(gè)三元式(i,j,v)表示。三元式可以按行或按列的順序存儲(chǔ)在一維數(shù)組中，形成三元組。為了節(jié)省空間，對(duì)于稀疏矩陣可只存非零元素。

三元組按行順序存儲(chǔ)

三元組按列順序存儲(chǔ)(a)稀疏矩陣M(b)M的列三元組三元組的Term類template<classT>structTerms{

int

row,col;Tvalue;};

行三元組表的C++類template<classT>classSeqTriple{public:

SeqTriple(int

mSize);~SeqTriple(){delete[]trip;};voidAdd(constSeqTriple<T>&B,

SeqTriple<T>&C)const;voidMul(const

SeqTriple<T>&B,

SeqTriple<T>&C)const;voidTranspose(SeqTriple<T>&B)const;friendistream&operator>>(istream&input,constSeqTriple<T>&);friendostream&operator<<(ostream&output,constSeqTriple<T>&);

private:

int

maxSize;//最大元素個(gè)數(shù)

intm,n,t;//行數(shù)、列數(shù)和非零元素個(gè)數(shù)

Term<T>*trip;//動(dòng)態(tài)一維數(shù)組的指針};

矩陣轉(zhuǎn)置普通矩陣轉(zhuǎn)置：for(inti=0;i<m;i++)for(intj=0;j<n;j++)B[j][i]=A[i][j];

時(shí)間復(fù)雜度為O(m×n)。在三元組表示下實(shí)現(xiàn)矩陣轉(zhuǎn)置

如果稀疏矩陣Am

n用行三元組A表示，轉(zhuǎn)置矩陣保存在一維數(shù)組B中，則B應(yīng)仍為行三元組。方法一:將三元組A中所有元素的行、列號(hào)交換后保存到B中；然后按B中的行號(hào)排序。這樣，矩陣轉(zhuǎn)置的時(shí)間就取決于選擇的排序算法的時(shí)間。ABB方法二：對(duì)數(shù)組A掃描n遍，每掃描一遍找出B的一行元素，第i遍掃描得到B的第i行元素，依此存入B中。此方法的時(shí)間為O(n*t),t是A的長(zhǎng)度。AB方法三：快速轉(zhuǎn)置使用n個(gè)指針k[n](n是矩陣的列數(shù))，指向A中每一列的第一個(gè)非零元素在B中的存放位置。BA

計(jì)算k[i]k[i]可以簡(jiǎn)單地由下式計(jì)算。for(inti=0;i<Cols;i++)num[i]=0；for(i=0;i<t;i++)

num[trip[i].col]++;計(jì)算num[i]template<classT>voidSeqTriple<T>::Transpose(SeqTriple<T>&B)const{//將this轉(zhuǎn)置賦給B

int*num=newint[n];int*k=newint[n];B.m=n;B.n=m;B.t=t;if(t>0){ for(inti=0;i<n;i++)num[i]=0;for(i=0;i<t;i++)num[trip[i].col]++; k[0]=0; for(i=1;i<n;i++)k[i]=k[i-1]+num[i-1];

for(i=0;i<t;i++){

intj=k[trip[i].col]++; B.trip[j].row=trip[i].col;

B.trip[j].col=trip[i].row;B.trip[j].value=trip[i].value;}}delete[]num;delete[]k;}

4.4字符串

4.4.1字符串ADT字符串的定義字符串(簡(jiǎn)稱為串)是由n(

0)個(gè)字符組成的有限序列。S=“a0a1…an－1”(n≥0)其中，S是串名，單引號(hào)括起來的字符序列是串S的值。n是串中字符個(gè)數(shù)，又稱串長(zhǎng)度，n=0的串稱為空串。要注意區(qū)分空串和空白串。

串中任意連續(xù)個(gè)字符組成的子序列稱為該串的子串，包含子串的串稱為主串。通常以子串的首字符在主串中的位置作為子串在主串中的位置。

S=‘a(chǎn)bcabcaabcbcde’P=‘a(chǎn)abc’ADTString{數(shù)據(jù)：字符串是由n(≥0)個(gè)字符組成的有限序列S="a0a1…an-1"，0

i<n。

運(yùn)算：

Create():建立一個(gè)空串。

Destroy():撤消一個(gè)串。

Length():返回當(dāng)前串對(duì)象的長(zhǎng)度。

Clear():置為空串。

ADT４.3字符串ADT

Assign(S):串S的值賦給當(dāng)前串對(duì)象。

Concat(b):將串b連接在當(dāng)前串對(duì)象之后。

Insert(P,i):將串P插在當(dāng)前串對(duì)象的位置i處。

Delete(i,len):從當(dāng)前串對(duì)象的位置i起刪除len個(gè)字符。

Substr(i,len):返回當(dāng)前串對(duì)象中，從位置i開始的len個(gè)字符組成的子串。

Find(i,P):返回子串P在當(dāng)前串對(duì)象中的位置。若當(dāng)前串對(duì)象不包含串P，則返回-1。}1.鏈接存儲(chǔ)表示4.4.2

字符串的存儲(chǔ)表示

2.順序存儲(chǔ)表示串的順序表示可用C++的一維字符數(shù)組來描述。

#include<string.h>chars[20]="cdabcde“；#include<string.h>classString{public:String();String(constchar*p);~String(){delete[]str;};

int

Find(inti,String&P);private:

intn;//當(dāng)前串長(zhǎng)

char*str;//動(dòng)態(tài)一維字符數(shù)組的指針};String::String(constchar*p){n=strlen(p);

str=newchar[n+1];

strcpy(str,p);}4.4.3簡(jiǎn)單模式匹配算法

設(shè)有兩個(gè)字符串s和p，在串s中找串p的過程被稱為模式匹配

。這里s為主串，p為子串，又稱為模式。模式匹配最普遍的應(yīng)用是文本編輯器中查找串．如：WORD中的“Find”等命令．

模式匹配算法思想

１.從主串s中下標(biāo)為i的字符與模式串p的第１個(gè)字符(下標(biāo)為0)開始逐個(gè)比較，遇到不相等時(shí)，即到達(dá)失配點(diǎn)，該趟匹配失?。?s回到i加１的位置（稱為回溯），p回到第１個(gè)字符位置，開始下趟匹配．直到匹配成功返回p的第１個(gè)字符在s中的位置或者s中不存在p，匹配失?。?jiǎn)單模式匹配－匹配成功失配點(diǎn)簡(jiǎn)單模式匹配－匹配失敗int

String::Find(inti,String&P){ if(i<0||i>n-1){//越界檢查

cout<<"Outofbounds!"<<endl;return-1;}

char*pp=P.str,//指針pp指向模式串

char*t=str+i;while(*pp!='\x0'&&i<=n-P.n) if(*pp++!=*t++){ pp=P.str;

//模式串回到第1個(gè)字符,為下趟匹配準(zhǔn)備

t=str+(++i);//主串回到i+1的位置，為下趟匹配準(zhǔn)備

}if(*pp==‘\0’)returni;

//串pp已到串尾，匹配成功

return-1;

//匹配失敗}

簡(jiǎn)單匹配算法的漸近時(shí)間復(fù)雜度：

設(shè)主串和模式串的長(zhǎng)度為n和m，while循環(huán)最多進(jìn)行n-m+1趟，每趟最多比較m次，這樣總的比較次數(shù)最多是(n-m+1)×m。由于(n-m+1)×m≤(n-m+m)×m=n×m，因此簡(jiǎn)單模式匹配算法在最壞情況下的時(shí)間復(fù)雜度是O(n×m)。

S=‘a(chǎn)bcabcaadbcbcdeP=‘a(chǎn)abc’

4.4.4模式匹配的KMP算法

簡(jiǎn)單匹配算法效率不高。原因：有回溯。KMP是一種無回溯匹配算法

KMP的時(shí)間復(fù)雜度是O(n+m)。效率高的主要原因是匹配失敗時(shí)在主串中不需回朔，在子串（模式串）中也不一定要回朔到第一個(gè)字符的位置。6第1趟，S[4]!=P[4]，匹配失敗

第2趟，回溯到S[1]、P[0]而S[1]=P[1]，P[0]!=P[1]第2趟沒有必要第3趟，回溯到S[2]、P[0]而S[2]=P[2]，P[0]!=P[2])第3趟沒有必要第4趟，沒有必要回溯到S[3]、P[0]而S[3]==P[3]，P[0]==P[3],所以S[3]==P[0]因此，可從S[4]與P[1]處開始沒有必要沒有必要第1趟，S[4]!=P[4]，匹配失敗

第2趟，回溯到S[1]、P[0]而S[1]=P[1]，P[0]!=P[1]第2趟沒有必要第3趟，回溯到S[2]、P[0]而S[2]=P[2]，P[0]!=P[2])第3趟沒有必要第4趟，沒有必要回溯到S[3]、P[0]而S[3]==P[3]，P[0]==P[3],所以S[3]==P[0]因此，可從S[4]與P[1]處開始沒有必要

因此確定下趟匹配開始時(shí)，模式串回朔到什么位置，是問題的關(guān)鍵。6

KMP算法的關(guān)鍵是確定模式串p中每個(gè)字符的最大k值，K是失配時(shí)j需向前回朔得最少的位置，即下趟匹配時(shí)，j的新值為k。于是下一趟應(yīng)從si和pk開始比較。

設(shè)主串S=“s0,s1,s2,…,sn-1”，模式串P=“p0,p1,…,pm-1”,失配點(diǎn)為SiPj。如果發(fā)現(xiàn)在模式串P中有：p0p1…pk-1=pj-kpj-k+1…pj-1是串p0p1…pj-1中“最長(zhǎng)的相等的前綴子串和后綴子串”，由于SiPj故有：pj-k…

pj-2pj-1=si-k

…

si-2si-1因此

p0…

pk-2pk-1=si-k

…

si-2si-1

下一趟就可從si

和pk

開始比較。6沒有必要第1趟，S[4]!=P[4]，匹配失敗

在串“abcaab”中,“a”是“最長(zhǎng)的相等的前綴子串和后綴子串”，因此，下趟匹配從s4和p1開始沒有必要失配點(diǎn)前的串“abcabca”中，相同的前、后綴子串只有“a”、“abca”,其中“abca”是最長(zhǎng)的相同的前、后綴子串，所以k為４，下一趟的匹配從s[7]和p[4]開始。

失敗函數(shù)的定義

設(shè)有長(zhǎng)度為m的模式串p＝p0p1…pm－1,，k為相同的前、后綴子串長(zhǎng)，失敗函數(shù)的定義為：此函數(shù)的含義為：當(dāng)SiPj匹配失敗時(shí)，j應(yīng)當(dāng)回朔的f(j)。當(dāng)f(j)>=0時(shí)，下趟匹配從si和pf(j)開始當(dāng)f(j)=-1時(shí)，下趟匹配從si和p0開始

（無相同的前、后綴子串）從定義計(jì)算失敗函數(shù)KMP算法就容易實(shí)現(xiàn)。當(dāng)SiPj時(shí)，只需使j=f[j]，即從P[f[j]]字符開始下一趟比較；主串無需回朔。

設(shè)有主串S=“abcabcaabcabacbbac”，模式串P=“abcabcabbac

”,KMP算法匹配過程如下： i=0

i=7

第S=abcabcaabcabacbbac一P=abcabcabbac趟

j=0

j=7S[7]

P[7]j=f[7]=4

i=7

第S=abcabcaabcabacbbac二P= abcabcabbac趟

j=4S[7]

P[4]j=f[4]=1 i=7

第S=ab cabcaabcabacbbac三P= abcabcabbac趟

j=1S[7]

P[1]j=f[1]=0 i=7

第S=abcabca abcabacbbac四P= abcabcabbac趟

j=0KMP匹配算法int

String::FindKMP(inti,String&P){if(i<0||i>n-1){

cout<<"Outofbounds!"<<endl;return-1;}

intj=0,m=P.n;while(i<n&&j<m)if(j==-1||str[i]==P.str[j]){i++;j++;}elsej=P.f[j];return((j==m)?i-m:-1);}時(shí)間分析算法中語句if(j==-1||str[i]==p.str[j])的執(zhí)行次數(shù)最多，因此KMP算法的時(shí)間復(fù)雜度主要取決于該語句的執(zhí)行次數(shù)。

if(j==-1||str[i]==p.str[j])