数据结构：第4章 数组和字符串

第4章数组和字符串4.1

数组4.2

特殊矩阵4.3

稀疏矩阵4.4

字符串4.1数组

数组是非常有用的数据结构，几乎所有的高级程序设计语言中都提供了数组类型。本章从数据结构的角度介绍数组的概念、它的抽象数据类型和类的定义。在自然科学中，矩阵常被用于解决许多实际问题。由于稀疏矩阵在存储表示上的特点，本章也对它进行专门的讨论。

数组的定义数组是下标index和值value组成的序对的集合。(index,value)一维数组：A={(0,15),(1,24),(2,33),(3,21)}

4.1.1

数组ADT

数组抽象数据类型ADTArray{Data:

下标index和元素值value组成的数据对集合,其中任意两个数据对的下标index各不相同。Operations:Create():

建立一个数组。

Retrieve(i):返回下标为i的元素值。

Store(i,x):将下标为i的数据对的值置为x。};

一维数组的顺序表示二维数组的顺序表示多维数组的顺序表示4.1.2数组的顺序表示

一维数组的顺序表示

地址计算:设第一个数组元素a[0]的存储地址是loc(a[0])，若已知每个数组元素占k个存储单元，则下标为i的数组元素a[i]的存储地址loc(a[i])为

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

二维数组的顺序表示

二维数组a[m][n]映射到一维的存储空间时有两种顺序：行优先和列优先。大多数语言如PASCAL、BASIC、C、C++等都是按行优先顺序存储的，FORTRAN是按列优先顺序存储的。地址计算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

多维数组的顺序表示

推广到多维数组a[m1][m2]…[mn]，数组元素a[i1][i2]…[in]的存储地址为：loc(a[i1][i2]…[in])=loc(a[0]…[0])+(i1*m2*m3*…*mn

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

+in

)*k=

用C++的模板类定义的一维数组抽象数据类型。公有成员函数包括：构造函数析构函数重载下标操作符：[]

重载下标操作符用来返回指向第i个元素的引用重载数组赋值：＝

赋值操作符实现数组的整体赋值。4.1.3一维数组的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)//数组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;//采用缺省长度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特殊矩阵对称矩阵和三角矩阵在n×n的矩阵A中，若aij=aji(0<i,j<n)，则称其为n阶对称矩阵。对于对称矩阵，可以只存储上三角(或下三角)中的元素(包括对角线上的元素)。01

k4.2.1对称矩阵4.3稀疏矩阵

稀疏矩阵：

大多数元素为零的矩阵称为稀疏矩阵。4.3稀疏矩阵

1、稀疏矩阵的操作在稀疏矩阵上执行的操作本质上是普通矩阵的操作，ADT4.2定义了包括建立、加法、乘法和转置操作的抽象数据类型。ADTSparseMatrix{数据：绝大多数元素为零的矩阵。运算：

Create();建立一个稀疏矩阵。

Destroy():撤消一个稀疏矩阵。

Add(B,C):当前矩阵对象与B相加，C中返回相加和。

Mul(B,C):当前矩阵对象与B相乘，C中返回相乘积。

Transpose(B):B中返回当前矩阵对象的转置矩阵。}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稀疏矩阵的顺序表示

按照压缩存储的思想，稀疏矩阵Am

n中的每一个非零元素aij的行号、列号和值可以用一个三元式(i,j,v)表示。三元式可以按行或按列的顺序存储在一维数组中，形成三元组。为了节省空间，对于稀疏矩阵可只存非零元素。

三元组按行顺序存储

三元组按列顺序存储(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;//最大元素个数

intm,n,t;//行数、列数和非零元素个数

Term<T>*trip;//动态一维数组的指针};

矩阵转置普通矩阵转置：for(inti=0;i<m;i++)for(intj=0;j<n;j++)B[j][i]=A[i][j];

时间复杂度为O(m×n)。在三元组表示下实现矩阵转置

如果稀疏矩阵Am

n用行三元组A表示，转置矩阵保存在一维数组B中，则B应仍为行三元组。方法一:将三元组A中所有元素的行、列号交换后保存到B中；然后按B中的行号排序。这样，矩阵转置的时间就取决于选择的排序算法的时间。ABB方法二：对数组A扫描n遍，每扫描一遍找出B的一行元素，第i遍扫描得到B的第i行元素，依此存入B中。此方法的时间为O(n*t),t是A的长度。AB方法三：快速转置使用n个指针k[n](n是矩阵的列数)，指向A中每一列的第一个非零元素在B中的存放位置。BA

计算k[i]k[i]可以简单地由下式计算。for(inti=0;i<Cols;i++)num[i]=0；for(i=0;i<t;i++)

num[trip[i].col]++;计算num[i]template<classT>voidSeqTriple<T>::Transpose(SeqTriple<T>&B)const{//将this转置赋给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字符串的定义字符串(简称为串)是由n(

0)个字符组成的有限序列。S=“a0a1…an－1”(n≥0)其中，S是串名，单引号括起来的字符序列是串S的值。n是串中字符个数，又称串长度，n=0的串称为空串。要注意区分空串和空白串。

串中任意连续个字符组成的子序列称为该串的子串，包含子串的串称为主串。通常以子串的首字符在主串中的位置作为子串在主串中的位置。

S=‘abcabcaabcbcde’P=‘aabc’ADTString{数据：字符串是由n(≥0)个字符组成的有限序列S="a0a1…an-1"，0

i<n。

运算：

Create():建立一个空串。

Destroy():撤消一个串。

Length():返回当前串对象的长度。

Clear():置为空串。

ADT４.3字符串ADT

Assign(S):串S的值赋给当前串对象。

Concat(b):将串b连接在当前串对象之后。

Insert(P,i):将串P插在当前串对象的位置i处。

Delete(i,len):从当前串对象的位置i起删除len个字符。

Substr(i,len):返回当前串对象中，从位置i开始的len个字符组成的子串。

Find(i,P):返回子串P在当前串对象中的位置。若当前串对象不包含串P，则返回-1。}1.链接存储表示4.4.2

字符串的存储表示

2.顺序存储表示串的顺序表示可用C++的一维字符数组来描述。

#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;//当前串长

char*str;//动态一维字符数组的指针};String::String(constchar*p){n=strlen(p);

str=newchar[n+1];

strcpy(str,p);}4.4.3简单模式匹配算法

设有两个字符串s和p，在串s中找串p的过程被称为模式匹配

。这里s为主串，p为子串，又称为模式。模式匹配最普遍的应用是文本编辑器中查找串．如：WORD中的“Find”等命令．

模式匹配算法思想

１.从主串s中下标为i的字符与模式串p的第１个字符(下标为0)开始逐个比较，遇到不相等时，即到达失配点，该趟匹配失败．２.s回到i加１的位置（称为回溯），p回到第１个字符位置，开始下趟匹配．直到匹配成功返回p的第１个字符在s中的位置或者s中不存在p，匹配失败．简单模式匹配－匹配成功失配点简单模式匹配－匹配失败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个字符,为下趟匹配准备

t=str+(++i);//主串回到i+1的位置，为下趟匹配准备

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

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

return-1;

//匹配失败}

简单匹配算法的渐近时间复杂度：

设主串和模式串的长度为n和m，while循环最多进行n-m+1趟，每趟最多比较m次，这样总的比较次数最多是(n-m+1)×m。由于(n-m+1)×m≤(n-m+m)×m=n×m，因此简单模式匹配算法在最坏情况下的时间复杂度是O(n×m)。

S=‘abcabcaadbcbcdeP=‘aabc’

4.4.4模式匹配的KMP算法

简单匹配算法效率不高。原因：有回溯。KMP是一种无回溯匹配算法

KMP的时间复杂度是O(n+m)。效率高的主要原因是匹配失败时在主串中不需回朔，在子串（模式串）中也不一定要回朔到第一个字符的位置。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]处开始没有必要

因此确定下趟匹配开始时，模式串回朔到什么位置，是问题的关键。6

KMP算法的关键是确定模式串p中每个字符的最大k值，K是失配时j需向前回朔得最少的位置，即下趟匹配时，j的新值为k。于是下一趟应从si和pk开始比较。

设主串S=“s0,s1,s2,…,sn-1”，模式串P=“p0,p1,…,pm-1”,失配点为SiPj。如果发现在模式串P中有：p0p1…pk-1=pj-kpj-k+1…pj-1是串p0p1…pj-1中“最长的相等的前缀子串和后缀子串”，由于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”是“最长的相等的前缀子串和后缀子串”，因此，下趟匹配从s4和p1开始没有必要失配点前的串“abcabca”中，相同的前、后缀子串只有“a”、“abca”,其中“abca”是最长的相同的前、后缀子串，所以k为４，下一趟的匹配从s[7]和p[4]开始。

失败函数的定义

设有长度为m的模式串p＝p0p1…pm－1,，k为相同的前、后缀子串长，失败函数的定义为：此函数的含义为：当SiPj匹配失败时，j应当回朔的f(j)。当f(j)>=0时，下趟匹配从si和pf(j)开始当f(j)=-1时，下趟匹配从si和p0开始

（无相同的前、后缀子串）从定义计算失败函数KMP算法就容易实现。当SiPj时，只需使j=f[j]，即从P[f[j]]字符开始下一趟比较；主串无需回朔。

设有主串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);}时间分析算法中语句if(j==-1||str[i]==p.str[j])的执行次数最多，因此KMP算法的时间复杂度主要取决于该语句的执行次数。

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