数据结构-第4章-字符串、数组和矩阵

4.1串第4章字符串、数组和矩阵4.1.1串的基本概念和抽象数据类型串（string）是由零个或多个字符组成的有限序列。一般记为：s=’a1a2a3……ai……an’ (n≥0)其中s是串的名字；单引号是串的定界符，其本身不属于串；单引号中的字符序列a1a2a3……ai……an是串的值；ai（1≤i≤n）可以是字母、数字或其它字符；n为串的长度。具有0个字符的串称为空串，其长度为0，记为s=’’，一般用Φ表示。注意：空串与由空格组成的串不是一个概念，后者称为空格串，是有长度的，不是空串。串中任意个连续的字符组成的子序列称为串的子串，包含子串的串对应地称为主串。空串是任意串的子串。单个字符在序列中的序号称为该字符在串中的位置。子串在主串中的位置为其第一个字符在串中的位置。4.1串第4章字符串、数组和矩阵4.1.2串的静态存储和操作实现串作为一种计算机要处理的一种对象，在程序设计中，可以赋给它一个变量名，通过变量名访问值。对串的存储有静态和动态两种，所谓静态存储是指串值的存储分配在编译时完成，可以根据串名直接访问到串值；而动态存储是指串值的存储分配是在程序运行时完成的，在串名和串值之间有一个称之为存储映像的对照表，通过此对照表访问串值。本节介绍串的静态存储和基于此种存储方式的操作实现。4.1串第4章字符串、数组和矩阵串的静态存储结构是指用一段地址连续的存储单元存储串的字符序列。和线性表的顺序存储结构相类似，一般也称为串的顺序存储结构。一般描述如下：#define MAXLEN 255 /*串的最大长度*/typedef struct{ chardata[MAXLEN+1]; /*定义存储串的空间*/ int len; /*当前串的实际长度*/}sqString;4.1串第4章字符串、数组和矩阵1.串赋值把字符串常量（如“Data_Structure”）赋值给一个串。如果字符串常量的长度小于MAXLEN则返回OK；否则字符串被截断，并返回CUT。

StatusStrAssign(sqString*S,charchars[]) {

inti=0;

while(chars[i]!=‘\0’&&i<MAXLEN) /*把字符串常量赋值给串S*/ {

S->data[i]=chars[i];

i++; } S->data[i]=‘\0’; S->len=i; if(i==MAXLEN&&chars[i]!=‘\0’) /*字符串常量被截断*/

returnCUT; else

returnOK; }4.1串第4章字符串、数组和矩阵2.求串的长度

intStrLength(sqStringS) {

returnS.len;

}3.串比较串的比较实际是依次比较两个串（如S和T）中的对应字符。若串中的所有对应字符均相等，则两个串相等、返回0；若S中的字符大于T中的对应字符，则串S>T、返回正数；若S中的字符小于T中的对应字符，则串S<T、返回负数。intStrCmp(sqStringS,sqStringT){ inti; for(i=0;i<S.len&&i<T.len;i++)

if(S.data[i]!=T.data[i])returnS.data[i]-T.data[i];

returnS.len-T.len;}4.1串第4章字符串、数组和矩阵5.求子串从串S中第pos个字符开始，有Sub返回长度为len的子串。若len超出了从pos到S结尾的子串的长度，则Sub只包含S中从pos到结尾的部分，并返回OK。StatusSubStr(sqString*Sub,sqStringS,intpos,intlen){ inti; if(S.len==0||pos<1||pos>S.len||len<0) returnERROR; if(pos+len>S.len) len=S.len–pos+1; for(i=0;i<=len;i++) Sub->data[i]=S.data[i+pos-1]; Sub->data[len]=‘\0’;Sub->len=len; returnOK;}4.1串第4章字符串、数组和矩阵4.1.3串的动态存储和操作实现1.串的链式存储与线性表的链式存储结构相类似，串也可以采用链表的形式来存储。但是与线性表的链式存储不同的是，串的链式存储存在一个“结点大小”的问题，即每个结点可以存放一个字符，也可以存放多个字符。对于结点大小大于1的情况，由于串的长度不一定恰好是结点大小的整数倍，所以串链表的最后一个结点一般用“\0”填充至满。4.1串第4章字符串、数组和矩阵串的链式存储一般定义如下： #define NODE_SIZE 4 /*每个结点的大小*/typedef structstrNode{ chardata[NODE_SIZE]; structstrNode*next; }StrNode;typedefstruct{ StrNode*head; intlen;}nodeString;4.1串第4章字符串、数组和矩阵2.串的堆式存储在串的实际应用中，经常采用另外一种动态存储结构，即堆式存储结构。堆式存储结构是指系统开辟一个连续且足够大的空间用来存储串值，但存储地址是在程序执行的过程中动态分配的。在C语言中，一般用系统函数malloc（）和free（）来管理这个存储区域。当要建立新串时，系统用malloc（）函数为其分配一个和串长大小相同的空间来存储串值。如果分配成功，则返回一个指向该串的起始地址的指针，通过该指针可以访问到该串。当某个串不在被使用的时候，系统用free（）函数收回该串占用的存储空间，以备后续分配时使用。4.1串第4章字符串、数组和矩阵串的堆式存储一般定义如下：typedef struct{

char*data; /*定义存储串空间的指针*/

int len; /*当前串的实际长度*/}heapString;（1）串赋值

为串动态分配一存储空间，把字符串常量（如“Data_Structure”）赋值给该串。如果成功返回OK，否则返回失败。StatusStrAssign(heapString**S,charchars[]){intlen=0,i=0;while(chars[len]!='\0')/*计算字符串常量的长度*/len++;if(*S!=NULL)/*释放原串的内容*/free((*S)->data);else*S=(heapString*)malloc(sizeof(heapString));if(!*S)/*分配空间失败*/returnERROR;(*S)->data=(char*)malloc((len+1)*sizeof(char));if(!(*S)->data)/*分配空间失败*/returnERROR;(*S)->len=len;for(i=0;i<=(*S)->len;i++)(*S)->data[i]=chars[i];returnOK;}4.1串第4章字符串、数组和矩阵堆式存储的基本操作主要介绍以下几种：（2）求串的长度

intStrLength(heapStringS) {

returnS.len;

}（3）串比较比较两个串（如S和T）的大小。若两个串相等则返回0；若S>T则返回正数；若S<T则返回负数。intStrCmp(heapStringS,heapStringT){

inti;

for(i=0;i<S.len&&i<T.len;i++) if(S->data[i]!=T->data[i])returnS->data[i]-T->data[i]; returnS.len-T.len;}4.1串第4章字符串、数组和矩阵

（4）串连接把T连接到S的尾部，并由S返回新的串。StatusStrConcat(heapString*S,heapStringT){inti;S->data=(char*)realloc(S->data,(S->len+T.len+1)*sizeof(char));if(!S->data)/*分配空间失败*/ returnERROR;for(i=0;i<T.len;i++){S->data[S->len+i]=T.data[i];}S->len=S->len+i;S->data[S->len]='\0';returnOK;}4.1串第4章字符串、数组和矩阵

（5）求子串从串S中第pos个字符开始，有Sub返回长度为len的子串。若len超出了从pos到S结尾的子串的长度，则Sub只包含S中从pos到结尾的部分，并返回OK。StatusSubStr(heapString*Sub,heapStringS,intpos,intlen){ inti; if(S.len==0||pos<1||pos>S.len||len<0) returnERROR; if(pos+len>S.len) len=S.len–pos+1; if(S->len>0) /*释放原串的内容*/ free(S->data); Sub->data=(char*)malloc((len+1)*sizeof(char)); if(!Sub->data) /*分配空间失败*/ returnERROR; for(i=0;i<=len;i++) Sub->data[i]=S.data[i+pos-1]; Sub->data[len]=‘\0’;Sub->len=len; returnOK;}4.1串第4章字符串、数组和矩阵4.2串的模式匹配第4章字符串、数组和矩阵4.2.1Brute-Force算法1.基本思想Brute-Force算法的思想比较简单：首先将主串的第一个字符和模式串的第一个字符相比较，若相等，则比较二者的下一个字符；若不等，则将主串的下一个字符和模式串的第一个字符相比较。重复此过程，直至主串从某一个字符起，依次和模式串中的字符相等，则匹配成功；否则，匹配失败。从上述思想中可以看到，此算法的关键是主串和模式串中的字符比较和移动。可以设定两个指针i、j分别指向主串和模式串中的字符。首先i=1，j=1进行比较，若相等，则i、j分别自加1，继续进行比较；若不等，则i自加1，j重置为1，进行比较。重复此过程，直至匹配成功或失败。4.2串的模式匹配第4章字符串、数组和矩阵2.算法实现 基于顺序存储的Brute-Force算法描述如下，基于堆式存储的实现算法也类似。

intBFIndex(sqStringS,sqStringT) { /*在主串S中寻找子串T第一次出现的位置。若匹配失败，则返回-1*/ inti=0,j=0,k=-1; while(i<S.len&&j<T.len) { if(S.data[i]==T.data[j]) /*相等则继续比较*/ { i++; j++; } else { i=i–j+1; j=0; } /*不相等则回溯*/ } if(j>=T.len) /*全部匹配*/ k=i–T.len; returnk; }4.2串的模式匹配第4章字符串、数组和矩阵3.效率分析若主串的长度为n，模式串长度为m，则Brute-Force算法的比较次数分别为：最好的情况，主串的前m个字符刚好为模式串的m个字符，因此只需m次比较，所以时间复杂度为O(m)。最恶劣情况，每一趟匹配时，模式串的前m-1个字符序列与主串的相应字符序列比较总是相等，但模式串的第m个字符和主串的相应字符比较总是不等。此时i指针需回溯，总的比较趟数为n-m+1，每趟进行m次比较，所以总次数为m*(n-m+1)，因此其时间复杂度为O(n*m)。4.2串的模式匹配第4章字符串、数组和矩阵4.2.2KMP算法1.基本思想在4.4.1节中的例子中可以看到，每次发生主串和模式串不等的情况，指针都需回溯，以重新比较。如图4-2中，当i=3，j=3发生不等时，重新比较i=2，j=1；仍然不等，则回溯，重新比较i=3，j=1；仍然不等，继续回溯。4.2串的模式匹配第4章字符串、数组和矩阵2.算法实现

根据上述分析，KMP算法描述如下： intKMPIndex(sqStringS,sqStringT) { /*在主串S中寻找子串T第一次出现的位置。若匹配失败，则返回-1*/ inti=1,j=1,k=-1; while(i<=S.len&&j<=T.len) { if(j==0||S.data[i]==T.data[j]) { i++; j++; } else j=next[j]; /*不相等则模式串的指针回溯*/ } if(j>T.len) /*全部匹配*/ k=i–T.len; returnk; }4.2串的模式匹配第4章字符串、数组和矩阵3.效率分析

由于KMP算法不需要回溯主串的指针，所以总的时间复杂度为O(n+m)。GetNext函数的时间复杂度为O(m)，但通常模式串的长度要比主串的长度小的多，所以本算法所增加的时间相对整个KMP算法来说可以忽略。4.3数组第4章字符串、数组和矩阵4.3.1数组的定义组可以看作是线性表的推广，数组作为一种数据结构，其特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型，比如：一维数组可以看作一个线性表；二维数组Amn可视为由m个行向量组成的向量，或由n个列向量组成的向量，二维数组中的每个元素aij既属于第i行的行向量，又属于第j列的列向量。三维数组Amnp可视为以二维数组为数据元素的向量，三维数组中的每个元素aijk都属于三个向量。依此类推。一个n维数组可以定义为其数据元素为n-l维数组类型的一维数组类型。数组是一个具有固定格式和数量的数据有序集，每一个数据元素由惟一的一组下标来标识。对于数组，通常只有两种操作：(1)结定一组下标，存取相应的数据元素；(2)给定一组下标，修改相应数据元素中的某一个或几个数据项的值。4.3数组第4章字符串、数组和矩阵4.3.2数组的顺序存储及实现1.行优先顺序将数组元素按行向量排列，第i+1个行向量紧接在第i个行向量后面。例如：二维数组Amn按行优先存储的线性序列为：a11,a12,…,a1n,a21,a22,…,a2n,……，am1,am2,…，amn。应该注意的是，在C语言中，数组按行优先顺序存储；其次，行优先顺序推广到多维数组时，可规定为先排最右的下标。4.3数组第4章字符串、数组和矩阵2.列优先顺序将数组元素按列向量排列，第i+1个列向量紧接在第i个列向量后面。例如：二维数组Amn按列优先存储的线性序列为：a11,a21,…,am1,a12,a22,…,am2,……，a1n,a2n,…，amn。应该注意的是，FORTRAN语言中，数组按列优先顺序存储；列优先顺序推广到多维数组时，可规定为先排最左的下标。4.3数组第4章字符串、数组和矩阵3.数组元素的地址计算公式（1）按行优先顺序存储的二维数组Amn地址计算公式LOC(aij)=LOC(a11)+[(i-1)×n+j-1]×d其中：①LOC(a11)是开始结点的存放地址（即基地址）；②d为每个元素所占的存储单元数；③由地址计算公式可得，数组中任意一个元素可通过地址公式随机存取，即顺序存储的数组是随机存取结构；（2）按列优先顺序存储的二维数组Amn地址计算公式LOC(aij)=LOC(a11)+[(j-1)×m+i-1]×d4.3数组第4章字符串、数组和矩阵（3）按行优先顺序存储的三维数组Amnp地址计算公式LOC(aijk)=LOC(a111)+[(i-1)×n×p+(j-1)×p+k-1]×d（4）下界不为1的二维数组的地址计算公式①二维数组A[c1..d1][c2..d2]的地址计算公式LOC(aij)=LOC(ac1c2)+[(i-c1)×(d2-c2+1)+j-c2]×d②下界为0的二维数组的地址计算公式（C语言中使用）LOC(aij)=LOC(a00)+[i×(d2+1)+j]×d4.4矩阵的压缩存档第4章字符串、数组和矩阵4.4.1特殊矩阵的压缩存储所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。常见的有对称矩阵、三角矩阵和对角矩阵等。下面我们讨论这几种特殊矩阵的压缩存储。1．对称矩阵（1）对称矩阵在一个n阶方阵A中，若元素满足下述性质：aij=aji(0≤i，j≤n-1)则称A为对称矩阵。4.4矩阵的压缩存档第4章字符串、数组和矩阵（2）对称矩阵的压缩存储对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间。这样，能节约近一半的存储空间。①按"行优先顺序"存储主对角线(包括对角线)以下的元素图4-7对称矩阵的行优先存放4.4矩阵的压缩存档第4章字符串、数组和矩阵（3）对称矩阵的地址计算公式LOC(aij)=LOC(sa[k])=LOC(sa[0])+k×d=LOC(sa[0])+[I×(I+1)／2+J]×d通过下标变换公式，对于任意给定一组下标(i，j)，均可在sa[k]中找到矩阵元素aij。例如，a21和a12均存储在sa[4]中，反之，对所有的k＝0，1，…，n×(n+1)/2-1，都能确定sa[k]中的元素在矩阵中的位置(i，j)。由此，称sa[n×(n+1)/2]为n阶对称矩阵A的压缩存储，如图4-8所示，这种压缩存储也是随机存取结构。图4-8对称矩阵的压组存储4.4矩阵的压缩存档第4章字符串、数组和矩阵2．三角矩阵（1）三角矩阵的划分以主对角线划分，三角矩阵有上三角矩阵和下三角矩阵两种，如图4-9所示。图4-9(a)所示为上三角矩阵，它的下三角(不包括主角线)中的元素均为常数c；图4-9(b)所示为下三角矩阵，与上三角矩阵相反，主对角线上方均为常数c。图4-9三角矩阵4.4矩阵的压缩存档第4章字符串、数组和矩阵3．对角矩阵对角矩阵也称为带状矩阵。在这种矩阵中，所有的非零元素集中在以主对角线为中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零。我们把非零元素集中的带状区域中对角线的条数称为带状矩阵的带宽。如图4-11给出了一个三对角矩阵。图4-11三对角矩阵4.4矩阵的压缩存档第4章字符串、数组和矩阵4.4.2稀疏矩阵的压缩存储设矩阵Amn中有s个非零元素，若s远远小于矩阵元素的总数(即s<<m×n)，且非零元素分布没有一定规律，称A为稀疏矩阵。1．稀疏矩阵的压缩存储为了节省存储单元，可只存储非零元素。由于非零元素的分布一般是没有规律的，为了能找到相应的元素，所以仅存储非零元素的值是不够的，还必须存储非零元素所在的行号、列号，才能确定一个非零元素是矩阵中的哪一个元素。其中每一个非零元素所在的行号、列号和值组成一个三元组(i，j，aij)，并由此三元组惟一确定。稀疏矩阵的压缩存储会失去随机存取功能。稀疏矩阵进行压缩存储通常有两类方法：顺序存储和链式存储。4.4矩阵的压缩存档第4章字符串、数组和矩阵2．三元组顺序表将表示稀疏矩阵的非零元素的三元组按行优先(或列优先)的顺序排列(跳过零元素)，并依次存放在向量中，这种稀疏矩阵的顺序存储结构称为三元组顺序表。在下述讨论中，均假设三元组是按行优先顺序排列的。3．带行表的三元组表为了方便某些矩阵运算，在按行优先存储的三元组表中，加