第四章 串和树组

1、 4.1.1 4.1.1 串的定义和基本运算串的定义和基本运算 串是字符串的简称。它是一种在数据元素的组成串是字符串的简称。它是一种在数据元素的组成 上具有一定约束条件的线性表，即要求组成线性表的上具有一定约束条件的线性表，即要求组成线性表的 所有数据元素都是字符，所以，人们经常又这样定义所有数据元素都是字符，所以，人们经常又这样定义 串：串：串串是一个有穷字符序列。是一个有穷字符序列。 串一般记作：串一般记作： s= “a1a2.an” (n 0) 其中，其中，s是串的名称，用双引号（是串的名称，用双引号（“”“”）括起来的字）括起来的字 符序列是串的值；符序列是串的值；ai可以是字母、数字

2、或其他字符；串可以是字母、数字或其他字符；串 中字符的数目中字符的数目n被称作串的被称作串的长度长度。当。当n=0时，串中没有任时，串中没有任 何字符，其串的长度为何字符，其串的长度为0，通常被称为，通常被称为空串空串。 s1= “” s2= “ ” s1中没有字符，是一个空串；而中没有字符，是一个空串；而s2中有两个空格字中有两个空格字 符，它的长度等于符，它的长度等于2，它是由空格字符组成的串，一般称，它是由空格字符组成的串，一般称 此为此为空格串空格串。 概念：概念： 子串子串、主串主串：串中任意连续的字符组成的子序列被：串中任意连续的字符组成的子序列被 称为该串的子串。包含子串的串又被

3、称为该子串的主串。称为该串的子串。包含子串的串又被称为该子串的主串。 例如，有下列四个串例如，有下列四个串a，b，c，d： a= “Welcome to Beijing” b= “Welcome” c= “Bei” d= “welcometo” 子串的位置：子串在主串中第一次出现的第一个子串的位置：子串在主串中第一次出现的第一个 字符的位置。字符的位置。 两个串相等两个串相等：两个串的长度相等，并且各个对应：两个串的长度相等，并且各个对应 的字符也都相同。的字符也都相同。 例如，有下列四个串例如，有下列四个串a，b，c，d： a= “program” b= “Program” c= “pro”

4、 d= “program ” 串的基本操作：串的基本操作： （1） 创建串创建串 StrAssign (s1,s2) （2）判断串是否为空）判断串是否为空 StrEmpty(s) （3）计算串长度）计算串长度StrLength(s) （4）串连接）串连接 StrConcat(s1,s2) （5）求子串）求子串 SubStr(s,i,len) （6）串的定位）串的定位 StrIndex(s1,t) 4.1.2 4.1.2 串的存储结构串的存储结构 1. 1. 顺序存储结构顺序存储结构 串的顺序存储结构与线性表的顺序存储类似，用串的顺序存储结构与线性表的顺序存储类似，用 一组连续的存储单元依次存储

5、串中的字符序列。在一组连续的存储单元依次存储串中的字符序列。在C 语言中，有两种实现方式：语言中，有两种实现方式： 第一种是事先定义字符串的最大长度，字符串存第一种是事先定义字符串的最大长度，字符串存 储在一个定长的存储区中。类型定义如下所示：储在一个定长的存储区中。类型定义如下所示： #define MAXSIZE 255 char sMAXSIZE; 第二种是在程序执行过程中，利用标准函数第二种是在程序执行过程中，利用标准函数malloc和和free动动 态地分配或释放存储字符串的存储单元，并以一个特殊的字态地分配或释放存储字符串的存储单元，并以一个特殊的字 符作为字符串的结束标志，它的好

6、处在于：可以根据具体情符作为字符串的结束标志，它的好处在于：可以根据具体情 况，灵活地申请适当数目的存储空间，从而提高存储资源的况，灵活地申请适当数目的存储空间，从而提高存储资源的 利用率。类型定义如下所示：利用率。类型定义如下所示： typedef struct char dataMAXSIZE; int curlen; SeqString; 定义一个串变量：定义一个串变量：SeqString s; 不同的定义形式，算法中的处理也略有不同。下面我们将给出在不同的定义形式，算法中的处理也略有不同。下面我们将给出在 第一种顺序存储方式下串的几个基本操作的算法。第一种顺序存储方式下串的几个基本操作

7、的算法。 (1)串联接：串联接：把两个串把两个串s1和和s2首尾连接成一个新串首尾连接成一个新串s ，即：，即： sMAXSIZE-1) return 0 ; /* s长度不够长度不够*/ j=0; while(s1j!=0) si=s1j;i+; j+; j=0; while(s2j!=0) si=s2j;i+; j+; si=0; return 1; (2)子串子串 int StrSub (char *t, char *s, int i, int len) /* 用用t返回串返回串s中第个中第个i字符开始的长度为字符开始的长度为len 的子串的子串1i串长串长*/ int slen; sl

8、en=StrLength(s); if ( islen | lenslen-i+1) printf(参数不对参数不对); return 0; for (j=0; jlen; j+) tj=si+j-1; tj=0; return 1; (3) 串比较串比较 int StrComp(char *s1, char *s2) int i=0; while (s1i=s2i return (s1i-s2i); 4.2.1 数组的定义和基本运算数组的定义和基本运算 数组的特点是每个数据元素可以又是一个线性表数组的特点是每个数据元素可以又是一个线性表 结构。因此，数组结构可以简单地定义为：若线性表结构。因

9、此，数组结构可以简单地定义为：若线性表 中的数据元素为非结构的简单元素，则称为一维数组，中的数据元素为非结构的简单元素，则称为一维数组， 即为即为向量向量；若一维数组中的数据元素又是一维数组结；若一维数组中的数据元素又是一维数组结 构，则称为二维数组；依次类推，若二维数组中的元构，则称为二维数组；依次类推，若二维数组中的元 素又是一个一维数组结构，则称作三维数组。素又是一个一维数组结构，则称作三维数组。 结论：线性表结构是数组结构的一个特例，而数结论：线性表结构是数组结构的一个特例，而数 组结构又是线性表结构的扩展。举例：组结构又是线性表结构的扩展。举例： 1, 11 , 10, 1 1, 1

10、1110 1,00100 . . . . nmmm n n nm aaa aaa aaa A 图图 4-3 其中，其中，A是数组结构的名称，整个数组元素可以看是数组结构的名称，整个数组元素可以看 成是由成是由m个行向量和个行向量和n个列向量组成，其元素总数为个列向量组成，其元素总数为 mn。在。在C语言中，二维数组中的数据元素可以表示语言中，二维数组中的数据元素可以表示 成成a表达式表达式1表达式表达式2，表达式，表达式1和表达式和表达式2被称为下被称为下 标表达式，比如，标表达式，比如，aij。 数组结构在创建时就确定了组成该结构的行向量数组结构在创建时就确定了组成该结构的行向量 数目和列向

11、量数目，因此，在数组结构中不存在插入、数目和列向量数目，因此，在数组结构中不存在插入、 删除元素的操作。删除元素的操作。 二维数组结构的基本操作：二维数组结构的基本操作： （1） 给定一组下标，修改该位置元素的内容给定一组下标，修改该位置元素的内容 Assign(A,item,index1,index2) （2）给定一组下标，返回该位置的元素内容）给定一组下标，返回该位置的元素内容 Value(A,item,index1,index2) 4.2.2 数组的存储结构数组的存储结构 从理论上讲，数组结构也可以使用两种存储结构，从理论上讲，数组结构也可以使用两种存储结构， 即顺序存储结构和链式存储结

12、构。然而，由于数组结即顺序存储结构和链式存储结构。然而，由于数组结 构没有插入、删除元素的操作，所以使用顺序存储结构没有插入、删除元素的操作，所以使用顺序存储结 构更为适宜。换句话说，一般的数组结构不使用链式构更为适宜。换句话说，一般的数组结构不使用链式 存储结构。存储结构。 组成数组结构的元素可以是多维的，但存储数据组成数组结构的元素可以是多维的，但存储数据 元素的内存单元地址是一维的，因此，在存储数组结元素的内存单元地址是一维的，因此，在存储数组结 构之前，需要解决将多维关系映射到一维关系的问题。构之前，需要解决将多维关系映射到一维关系的问题。 举例：举例： 图图 4-4 1, 11 ,

13、10 , 1 1, 11110 1, 00100 . . . . nmmm n n nm aaa aaa aaa A a00a01.a0,n- 1 a10a11.a1,n- 1 .am- 1,0 am- 1,1 .am-1,n- 1 第0行 第1行 第m-1行 图图 4-5 a0 0a1 0.am- 1 ,0 a0 1a1 1.am-1 ,1.a0 ,n -1a1 ,n -1.am- 1 ,n -1 第0列 第1列 第n-1列 图图 4-6 在在C语言中语言中 LOC(i,j)=LOC(0,0)+(n*i+j)*L 数组结构的定义：数组结构的定义： #define MAX_ROW_INDEX

14、10 #define MAX_COL_INDEX 10 typedef struct EnterType itemMAX_ROW_INDEXMAX_COL_INDEX ; ARRAY; 基本操作算法举例：基本操作算法举例： （1）给数组元素赋值）给数组元素赋值 void Assign(ARRAY *A,EnterType item,int index1,int index2) if (index1=MAX_ROW_INDEX| index2=MAX_COL_INDEX) exit(ERROR); else A-itemindex1index2=item; （2）返回给定位置的元素内容）返回给定

15、位置的元素内容 int Value(ARRAY A,EntryType *item,int index1,int index2) if (index1=MAX_ROW_INDEX| index2=MAX_COL_INDEX) return FALSE; else *item= A.itemindex1index2; return OK; 3 3矩阵的压缩存储矩阵的压缩存储 矩阵是在很多科学与工程计算中遇到的数学模型。矩阵是在很多科学与工程计算中遇到的数学模型。 在数学上，矩阵是这样定义的：它是一个由在数学上，矩阵是这样定义的：它是一个由sn个元个元 素排成的素排成的s行（横向）行（横向）n列（

16、纵向）的表。下面就是一列（纵向）的表。下面就是一 个矩阵：个矩阵： 1. 1. 特殊矩阵特殊矩阵 所谓所谓特殊矩特殊矩阵就是元素值的排列具有一定规律的阵就是元素值的排列具有一定规律的 矩阵。常见的这类矩阵有：对称矩阵、下（上）三角矩阵。常见的这类矩阵有：对称矩阵、下（上）三角 矩阵、对角线矩阵等等。矩阵、对角线矩阵等等。 对称矩阵的特点是对称矩阵的特点是aij=aji， 2. 2. 稀疏矩阵的压缩存储稀疏矩阵的压缩存储 若一个若一个mn的矩阵含有的矩阵含有t个非零元素，且个非零元素，且t远远小远远小 于于m*n，则我们将这个矩阵称为，则我们将这个矩阵称为稀疏矩阵稀疏矩阵。举例：。举例： 020

17、00 00000 00021 00100 70003 图图 4-14 稀疏矩阵的压缩存储方法稀疏矩阵的压缩存储方法三元组表示法。三元组表示法。 矩阵中的每个元素都是由行序号和列序号唯一确矩阵中的每个元素都是由行序号和列序号唯一确 定的。因此，我们需要用三项内容表示稀疏矩阵中的定的。因此，我们需要用三项内容表示稀疏矩阵中的 每个非零元素，即形式为：每个非零元素，即形式为： (i,j,value) 其中，其中，i表示行序号，表示行序号，j表示列序号，表示列序号，value表示非表示非 零元素的值，通常将它称为三元。我们将稀疏矩阵中零元素的值，通常将它称为三元。我们将稀疏矩阵中 的所有非零元素用这种

18、三元的形式表示，并将它们按的所有非零元素用这种三元的形式表示，并将它们按 以行为主的顺序存放在一个一维数组中，就形成了我以行为主的顺序存放在一个一维数组中，就形成了我 们所说的三元组表示法。举例：们所说的三元组表示法。举例： 图图 4-15 ij v a lu e 0 113 1 157 2 23 - 1 3 31 - 1 4 32 - 2 5 542 define SMAX 1024 /*一个足够大的数一个足够大的数*/ typedef struct int i,j; /*非零元素的行、列非零元素的行、列*/ datatype v; /*非零元素值非零元素值*/ SPNode; /*三元组类

19、型三元组类型*/ typedef struct int mu,nu,tu; /*矩阵的行、列及非零元素的个数矩阵的行、列及非零元素的个数*/ SPNode dataSMAX; /*三元组表三元组表*/ SPMatrix; /*三元组表的存储类型三元组表的存储类型*/ 4.3 应用举例应用举例 例例.1 .1 若矩阵Amn 中存在某个元素aij满足：aij是 第i行中最小值且是第j列中的最大值，则称该元素 为矩阵A的一个鞍点。试编写一个算法，找出A中 的所有鞍点。 基本思想：在矩阵A中求出每一行的最小值元素， 然后判断该元素它是否是它所在列中的最大值， 是则打印出，接着处理下一行。矩阵A用一个二维 数组表示 算法如下：算法如下： void saddle (int A ,int m, int n) /*m,n是矩阵是矩阵A的行和列的行和列*/ int i,j,min,k,p; for (i=0;im;i+) /*按行处理按行处理*/ min=Ai0 for (j=1; jn; j+) if (Aijmin ) min=Aij;/*找第找第i行最小值行最小值*/ for (j=0; jn;