3.6 其他线线性结结构串(String)是由零个或多个字符组成的有限序列。一般记为:S=a1 a2 . an(n0)其中，S是串的名，用单引号括起来的字符序列是串的值；ai(1in)可以是字母、数字或其它字符，串中字符的数目n称为串的长度。n=0的串称为空串(null string)。3.6.1 串的定义义和串的存储储方式概念串中任意个连续连续 的字符组组成的子序列称为该为该串的子串。包含子串的串相应应地称为为主串。通常称字符在序列中的序号为该为该 字符在串中的位置。子串在主串中的位置则则以子串的第一个字符在主串中的位置来表示。当两个串的长度相等，并且各个对应位置上的字符都相等时，称两个串相等。3.6.1 串的定义义和串的存储储方式概念l例：串名为为A、B、C、D的四个串如下：l A=very good；长长度为为9，是D的主串；l B= ；长长度为为3；l C=；长长度为为0（空串）；l D=good；长长度为为4，是A的子串。lD在A中的位置是6。3.6.1 串的定义义和串的存储储方式概念(1) 赋值操作：StrAssign(S，chars)初始条件：chars是字符串常量；操作结果：生成一个值等于chars的字符串S；(2) 插入操作：StrInsert(S，pos，T)初始条件：字符串S、T存在，1pos StrLength(S)+1；操作结果：在字符串S的第pos个字符之前插 入串T。3.6.1 串的定义义和串的存储储方式基本操作(3) 删删除操作：StrDelete(S，pos，len) 初始条件：字符串S存在， 1pos StrLength(S)-len+1； 操作结结果：从字符串S中删删除第pos个字符 起长长度为为len的子串。(4) 复制操作：StrCopy(S，T) 初始条件：字符串S存在； 操作结结果：将字符串S的内容复制到串T。3.6.1 串的定义义和串的存储储方式基本操作(5) 判空操作：StrEmpty(S)初始条件：字符串S存在；操作结结果：若S为为空串，则则返回TRUE，否 则则返回FALSE。(6) 比较较操作：StrCompare(S，T)初始条件：字符串S、T存在；操作结结果：若ST，则则返回值值0；若S=T， 则则返回值值=0；若SMaxlen，且pos+LCMaxlen，且pos+LCMaxlen；3.6.2 定长顺长顺 序串运算插入算法分析/* 在串s中序号为pos的字符之前插入串t */int StrInsert(SString *s, int pos, SString t) int i;if(poss-len) return(0); /* 插入位置不合法 */if(s-len+t.lenlen+t.len-1; i=t.len+pos; i-)s-chi=s-chi-t.len;for(i=0; ichi+pos=t.chi;s-len=s-len+t.len;3.6.2 定长顺长顺 序串运算插入算法实现实现else if(pos+t.lenMaxlen，但串t的字符序列可以全部插入 */for(i=Maxlen-1; i=t.len+pos; i-)s-chi=s-chi-t.len;for(i=0; ichi+pos=t.chi;s-len=Maxlen; else /* 串t的部分字符序列要舍弃 */for(i=0; ichi+pos=t.chi;s-len=Maxlen; return(1);3.6.2 定长顺长顺 序串运算插入算法实现实现int StrDelete(SString *s, int pos, int len) if(pos(s-len-len) return(0);for(i=pos+len; ilen; i+)s-chi-len=s-chi;s-len=s-len-len;return(1);3.6.2 定长顺长顺 序串运算删删除算法实现实现在进行串的连接时：假设原字符串为A，长度为LA；待连接串假设为B，其长度为LB；连接过程可能出现下列三种情况：1) 连接后串的总长度为LA+LB Maxlen；2) 连接后串的总长度Maxlen，且LAMaxlen，LA=Maxlen；3.6.2 定长顺长顺 序串运算连连接算法分析/* 将串t连接在串s的后面 */int StrCat(SString *s, SString t) int i, flag;if(s-len+t.lenlen; ilen+t.len; i+)s-chi=t.chi-s-len;s-len=s-len+t.len;flag=1;3.6.2 定长顺长顺 序串运算连连接算法实现实现else if(s-lenMaxlen，但串s的长度len; ichi=t.chi-s-len;s-len=Maxlen;flag=0;else flag=0; /* 串s的长度=Maxlen，串t不被连接 */return(flag);3.6.2 定长顺长顺 序串运算连连接算法实现实现数组组(array)可看成是线线性表的推广，是最常用的数据结结构之一。数组组是有限个数组组元素的集合，元素数目固定；数组组的每个元素与一组组下标标相对应对应 ，数组组元素的下标标关系具有上下界的约约束且下标标有序；数组组中所有数组组元素的数据类类型必须须一致；数组组的两种基本运算：1. 给给定下标标，存取相应应的数据元素；2. 给给定下标标，修改相应应的数据元素。3.6.3 二维维数组组的结结构特点和存储储方式定义义一个m行n列的二维维数组组(也称为为矩阵阵)，记记作Am, n。3.6.3 二维维数组组的结结构特点和存储储方式定义义A=a11 a12 . a1n a21 a22 . a2n am1 am2 . amn 按行优优先顺顺序存储储对对于上述二维维数组组A而言，可以将其看成是由m个行向量组组成的向量，即：Amn =(a11，.，a1n)，(a21，.，a2n)，.，(am1，.，amn)这这种行向量表相当于一个线线性表。行优优先顺顺序存储储就是数组组元素按行向量表次序进进行存储储，即第i+1个行表紧紧跟在第i个行表后面进进行存储储。3.6.3 二维维数组组的结结构特点和存储储方式存储结储结 构当把n维维数组组的元素按行优优先顺顺序地存放在存储储器里，则则每个元素的存储储地址可以用公式计计算出来。这这个计计算公式称为为“地址公式”。假设设每个数据元素占c个存储单储单 元，则则上述二维维数组组Amn的地址公式为为：Loc(aij)= Loc(a11)+ (i-1)* n +(j-1) * c(1im，1jn)3.6.3 二维维数组组的结结构特点和存储储方式存储结储结 构按列优优先顺顺序存储储对对于上述二维维数组组A而言，也可以将其看成是由n个列向量组组成的向量，即：Amn =(a11，.，am1)，(a12，.，am2)，.，(a1n，.，amn)这这种列向量表也相当于一个线线性表。列优优先顺顺序存储储就是数组组元素按列向量表次序进进行存储储，即第i+1个列表紧紧跟在第i个列表后面进进行存储储。3.6.3 二维维数组组的结结构特点和存储储方式存储结储结 构当把n维维数组组的元素按列优优先顺顺序地存放在存储储器里，并假设设每个数据元素占c个存储单储单 元，则则上述二维维数组组Amn的地址公式为为：Loc(aij)= Loc(a11)+ (j-1)* m +(i-1) * c(1im，1jn)3.6.3 二维维数组组的结结构特点和存储储方式存储结储结 构根据二维维数组组的特性可以推出：一个三维维数组组可以用其数据元素为为二维维数组组的线线性表来定义义；依次类类推，n维维数组组是由数据元素为为n-1维维数组组的线线性表构成。因此，对对n维维数组组也有上述两种不同顺顺序分配的存储结储结 构。当把n维维数组组的元素这样顺这样顺 序地存放在存储储器里，则则每个元素的存储储地址都可以用“地址公式”计计算出来。3.6.3 二维维数组组的结结构特点和存储储方式存储结储结 构在C语语言中，可以把一个二维维数组组看作是一种特殊的一维维数组组，该该一维维数组组的元素又是一个一维维数组组。例如定义义： int a34；其中，可以把a看作是一个一维维数组组，它有3个元素：a0、a1、a2，每个元素又是一个包含4个元素的一维维数组组。3.6.3 二维维数组组的结结构特点和存储储方式示例通常在实际计算中经常出现一些阶数很高的矩阵，且矩阵中有许多值相同的元素或者零元素。为了节省存储空间，可以对这类矩阵进行压缩存储。所谓压缩存储是指：为多个值相同的元素只分配一个存储空间；对零元素不分配空间。3.6.3 二维维数组组的结结构特点特殊矩阵阵的存储储方式下三角矩阵阵的存储储方式：设设下三角矩阵为阵为 Ann，满满足： 3.6.3 二维维数组组的结结构特点特殊矩阵阵的存储储方式A=a11 0 0 a21 a22 0 an1 an2 ann 若将其中的非零元素按行优优先顺顺序存放为为：则则一维维数组组Sak和矩阵阵元素aij之间间存在着一一对应对应 关系：(1ji n)3.6.3 二维维数组组的结结构特点特殊矩阵阵的存储储方式k=+jl假设每个数据元素占用一个字节的存储单元，则下三角矩阵的地址公式为：3.6.3 二维维数组组的结结构特点特殊矩阵阵的存储储方式Loc(aij) = Loc(a11)+ i(i1)/ 2 +(j1)三对对角矩阵阵的存储储方式：设设三对对角矩阵为阵为 Ann，满满足： 3.6.3 二维维数组组的结结构特点特殊矩阵阵的存储储方式A=a11 a12 0 0 a21 a22 a23 0 00 a32 a33 a34 0 0 0 0 an-1,n-2 an-1,n-1 an-1,n 0 0 0 an,n-1 ann 若将其中的非零元素按行优优先顺顺序存放，假设每个数据元素占用一个字节的存储单元，则三对角矩阵的地址公式为：3.6.3 二维维数组组的结结构特点特殊矩阵阵的存储储方式Loc(aij) = Loc(a11)+2(i1)+(j1)其中：i=1, j=1, 2或：i=n, j=n-1, n或：1data 和b-data中结结点序号； col指示*a的列号，即*b的行号 */pmatrix *b; /* 存放转转置后的矩阵阵 */b=malloc(sizeof(spmatrix); b-m=a-n; b-n=a-m; /*行列数交换换*/b-t=a-t;3.6.3 二维维数组组的结结构特点特殊矩阵阵的存储储方式if (b-t0) /* 有非零元素，则转则转 置 */ bno=0;for(col=0; coln; col+) /*按*a的列序转转