第4章 串和数组 本章主要介绍下列内容： 串的定义、存储结构和基本运算 数组的定义、基本运算和存储结构 特殊矩阵的压缩存储.

Presentation on theme: "第4章 串和数组 本章主要介绍下列内容： 串的定义、存储结构和基本运算 数组的定义、基本运算和存储结构 特殊矩阵的压缩存储."— Presentation transcript:

1 第4章 串和数组 本章主要介绍下列内容： 串的定义、存储结构和基本运算 数组的定义、基本运算和存储结构 特殊矩阵的压缩存储

2 4.1 串 4.2 数组

3 4.1 串 4.1.1 串的定义和基本运算 串是字符串的简称。它是一种在数据元素的组成上具有一定约束条件的线性表，即要求组成线性表的所有数据元素都是字符，所以，人们经常又这样定义串：串是一个有穷字符序列。

4 s1中没有字符，是一个空串；而s2中有两个空格字符，它的长度等于2，它是由空格字符组成的串，一般称此为空格串。
串一般记作： s= “a1a2...an” (n0) 其中，s是串的名称，用双引号（“”）括起来的字符序列是串的值；ai可以是字母、数字或其他字符；串中字符的数目n被称作串的长度。当n=0时，串中没有任何字符，其串的长度为0，通常被称为空串。 s1= “” s2= “ ” s1中没有字符，是一个空串；而s2中有两个空格字符，它的长度等于2，它是由空格字符组成的串，一般称此为空格串。 概念： 子串、主串：串中任意连续的字符组成的子序列被称为该串的子串。包含子串的串又被称为该子串的主串。

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

6 串的基本操作： （1） 创建串 StringAssign (s,string_constant) （2）判断串是否为空 StringEmpty(s) （3）计算串长度 Length(s) （4）串连接 Concat(s1,s2) （5）求子串 SubStr(s1,s2start,len) （6）串的定位 Index(s1,s2)

7 例如1：将s2串插入到串s1的第i个字符后面。
SubStr(s3,s1,1,i); SubStr(s4,s1,i+1,Length(s1)-i); Concat(s3,s2); Concat(s3,s4); StringAssign (s1,s3); 例如2：删除串s中第i个字符开始的连续j个字符。 SubStr(s1,s,1,i-1); SubStr(s2,s,i+j,Length(s)-i-j+1); Concat(s1,s2); StringAssign(s,s1);

8 串的存储结构 1. 顺序存储结构 串的顺序存储结构与线性表的顺序存储类似，用一组连续的存储单元依次存储串中的字符序列。在C语言中，有两种实现方式： 第一种是事先定义字符串的最大长度，字符串存储在一个定长的存储区中。类型定义如下所示： #define MAX_STRING 255 //0号单元存放串的长度，字符从1号单元开始存放 type unsigned char String[MAX_STRING];

9 第二种是在程序执行过程中，利用标准函数 malloc和free动态地分配或释放存储字符串的存储单元， 并以一个特殊的字符作为字符串的结束标志，它的好 处在于：可以根据具体情况，灵活地申请适当数目的 存储空间，从而提高存储资源的利用率。类型定义如 下所示： typedef struct{ char *str; int length; }STRING; 不同的定义形式，算法中的处理也略有不同。下 面我们将给出在第二种顺序存储方式下串的几个基本 操作的算法。

10 （1） 串的赋值 int StringAssign(STRING*s,char *string_constant) { if (s->str) free(s->str); //若s已经存在，将它占据的空间释放掉 for (len=0,ch=string_constant;ch;len++,ch++); //求string_constant串的长度 if (!len) { s->str=(char*)malloc(sizeof(char));s->str[0]=’\0’; s->length=0; } //空串

11 else { s->str=(char*)malloc((len+1)*sizeof(char)); //分配空间 if (!s->str) return ERROR; s->str[0..len]=string_constant[0..len]; //对应的字符赋值 s->length=len; //赋予字符串长度 } return OK;

12 （2）判断串是否为空 int StringEmpty(STRING s) { if (!s.length) return TRUE; else return FALSE; } （3）求串的长度 int Length(STRING s) return s.length;

13 （4）串连接 int Concat(STRING *s1,STRING s2) { STRING s; StringAssign(&s,s1->str); //将s1原来的内容保留在s中 len=Length(s1)+Length(s2); //计算s1和s2的长度之和 free(s1->str); //释放s1原来占据的空间 s1->str=(char*)malloc((len+1)*sizeof(char)); //重新为s1分配空间

14 if (!s1) return ERROR; else { //连接两个串的内容 s1->str[0..Length(s)-1]=s.str[0..Length(s)-1)]; s1->str[Length(s)..len+1]=s2.str[0..Length(s2)]; s1->length=len; free(s->str); //释放为临时串s分配的空间 return OK; }

15 （5）求子串 int SubStr(STRING *s1,STRING s2,int start,int len) { len2=Length(s2); //计算s2的长度 if (start<1||start>len2||len2<=0||len>len2-start+1) { //判断start和len的合理性 s1->str=(char*)malloc(sizoef(char));s1->str[0]=’\0’;s1->length=0;return ERROR;} s1->str=(char*)malloc((len+1)*sizeof(char)); if (!s1.str) return ERROR; s1->str[0..len-1]=s2.str[start-1..start+len -2]; s1->str[len]=’\0’; s1->length=len; return OK; }

16 （6）串的定位 int Index(STRING s1,STRING s2) { len1=Length(s1); len2=Length(s2); //计算s1和s2的长度 i=0; j=0; //设置两个扫描指针 while (i<len1&&j<len2) { if (s1.str[i]==s2.str[j]) { i++; j++; } else {i=i-j+1; j=0;} //对应字符不相等时，重新比较 } if (j==len2) return i-len2+1; else return 0;

17 2. 链式存储结构 由于串结构中每个数据元素为一个字符，所以最直接的链式存储结构是每个结点的数据域存放一个字符。举例： s t r i n g ^ S 图 4-1

18 S s t r i n g # # # # ^ 优点是操作方便；不足之处是存储密度较低。所谓存储密度为：
若要将多个字符存放在一个结点中，就可以缓解这个问题。举例： S s t r i n g # # # # ^ 图 4-2

19 由于串中的字符个数不一定是每个结点存放字符个数的整倍数，所以，需要在最后一个结点的空缺位置上填充特殊的字符。
这种存储形式优点是存储密度高于结点大小为1 的存储形式；不足之处是做插入、删除字符的操作时，可能会引起结点之间字符的移动，算法实现起来比较复杂。

20 4.2 数组 数组的定义和基本运算 数组的特点是每个数据元素可以又是一个线性表 结构。因此，数组结构可以简单地定义为：若线性表 中的数据元素为非结构的简单元素，则称为一维数组， 即为向量；若一维数组中的数据元素又是一维数组结 构，则称为二维数组；依次类推，若二维数组中的元 素又是一个一维数组结构，则称作三维数组。 结论：线性表结构是数组结构的一个特例，而数 组结构又是线性表结构的扩展。举例：

21 图 4-3

22 其中，A是数组结构的名称，整个数组元素可以看成是由m个行向量和n个列向量组成，其元素总数为m×n。在C语言中，二维数组中的数据元素可以表示成a[表达式1][表达式2]，表达式1和表达式2被称为下标表达式，比如，a[i][j]。 数组结构在创建时就确定了组成该结构的行向量数目和列向量数目，因此，在数组结构中不存在插入、删除元素的操作。 二维数组结构的基本操作： （1） 给定一组下标，修改该位置元素的内容 Assign(A,item,index1,index2) （2）给定一组下标，返回该位置的元素内容 Value(A,item,index1,index2)

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

24 图 4-4

25 第0行 第1行 第m-1行 图 4-5 第0列 第1列 第m-1列 图 4-6

26 LOC(i,j)=LOC(0,0)+(n*i+j)*L
数组结构的定义： #define MAX_ROW_INDEX 10 #define MAX_COL_INDEX 10 typedef struct { EnterType item[MAX_ROW_INDEX][MAX_COL_INDEX] ; } ARRAY;

27 基本操作算法举例： （1）给数组元素赋值 void Assign(ARRAY *A,EnterType item,int index1,int index2) { if (index1<0||index1>=MAX_ROW_INDEX|| index2<0||index2>=MAX_COL_INDEX) exit(ERROR); else A->item[index1][index2]=item; }

28 （2）返回给定位置的元素内容 int Value(ARRAY A,EntryType *item,int index1,int index2) { if (index1<0||index1>=MAX_ROW_INDEX|| index2<0||index2>=MAX_COL_INDEX) return FALSE; else { *item= A.item[index1][index2]; return OK; }

29 3．矩阵的压缩存储 矩阵是在很多科学与工程计算中遇到的数学模型。在数学上，矩阵是这样定义的：它是一个由s×n个元素排成的s行（横向）n列（纵向）的表。下面就是一个矩阵：

30 图4-7 s×n的矩阵 它是一个s×n的矩阵。

31 1. 特殊矩阵 所谓特殊矩阵就是元素值的排列具有一定规律的矩阵。常见的这类矩阵有：对称矩阵、下（上）三角矩阵、对角线矩阵等等。 对称矩阵的特点是aij=aji，比如，下面就是一个对称矩阵：

32 图 4-8

33 下（上）三角矩阵的特点是以主对角线为界的上（下）半部分是一个固定的值，下（上）半部分的元素值没有任何规律。比如，下面是一个下三角矩阵：
图 4-9

34 对角矩阵的特点是所有的非零元素都集中在以主对角线为中心的带状区域中。比如，下面就是一个3阶对角矩阵：
图 4-10

35 对于这些特殊矩阵，应该充分利用元素值的分布规律，将其进行压缩存储。选择压缩存储的方法应遵循两条原则：一是尽可能地压缩数据量，二是压缩后仍然可以比较容易地进行各项基本操作。
三种特殊矩阵的压缩方法：。 （1）对称矩阵 对称矩阵的特点是aij=aji。一个n×n的方阵，共有n2个元素，而实际上在对称矩阵中有n(n-1)/2个元素可以通过其他元素获得。

36 压缩的方法是首先将二维关系映射成一维关系，并只存储其中必要的n(n+1)/2个（主对角线和下三角）元素内容，这些元素的存储顺序以行为主序。举例：
假设定义一个数组型变量：int A[10]; 图 4-11

37 k是对称矩阵位于（i，j）位置的元素在一维数组中的存放位置。

38 操作算法的实现： int Value(int A[],EntryType *item,int i,int j) { if (i<1||i>MAX_ROW_INDEX|| j<1||j>MAX_COL_INDEX) return FALSE; else { if (i>=j) k=i*(i-1)/2+j-1; else k=j*(j-1)/2+i-1; *item=A[k]; return TRUE; }

39 （2）下（上）三角矩阵 下三角矩阵的压缩存储与上面讲述的对称矩阵的压缩存储一样，只是将上三角部分的常量值存储在0单元，下三角和主对角上的元素从1号单元开始存放。 举例： 图 4-12 对于任意的（i，j），在一维数组中的存放位置可利用下列公式求得：

40 操作算法的实现： int Value(int A[],EntryType *item,int i,int j) { if (i<1||i>MAX_ROW_INDEX||j<1||j>MAX_COL_INDEX) return FALSE; else { if (i>=j) k=i*(i-1)/2+j; else k=0; *item=A[k]; return TRUE; }

41 （3）对角矩阵 我们以三阶对角矩阵为例讨论一下它的压缩存储方法。对于对角矩阵，压缩存储的主要思路是只存储非零元素。这些非零元素按以行为主序的顺序，从下标为1 的位置开始依次存放在一维数组中，而0位置存放数值0。 图 4-13

42 下面我们讨论一下对于任意给定的（i，j），求得在一维数组中存储位置k的方法。

43 操作算法的实现： int Value(int A[ ],EntryType *item,int i,int j) { if (i<1||i>MAX_ROW_INDEX||j<1||j>MAX_COL_INDEX) return FALSE; else { if (j>=(i-1)&&j<=(i+1)) k=3*(i-1)+j-i+1; else k=0; *item=A[k]; return TRUE; }

44 2. 稀疏矩阵的压缩存储 若一个m×n的矩阵含有t个非零元素，且t远远小于m*n，则我们将这个矩阵称为稀疏矩阵。举例： 图 4-14

45 稀疏矩阵的压缩存储方法——三元组表示法。
矩阵中的每个元素都是由行序号和列序号唯一确定的。因此，我们需要用三项内容表示稀疏矩阵中的每个非零元素，即形式为： (i,j,value) 其中，i表示行序号，j表示列序号，value表示非零元素的值，通常将它称为三元。我们将稀疏矩阵中的所有非零元素用这种三元的形式表示，并将它们按以行为主的顺序存放在一个一维数组中，就形成了我们所说的三元组表示法。举例：

46 图 4-15

47 类型定义： #define MAX_SIZE 最大的非零元素个数 typedef struct{ int i,j; //行序号、列序号 EntryType value; //非零元素值 }Three_Item; typedef struct { Three_Item Item[MAXSIZE]; //存储非零元素的一维数组 int rows,cols,tu; //稀疏矩阵的总行数、列数及非零元素个数 }Matrix;

48 操作算法的实现： （1）返回元素内容 int Value(Matrix M,EntryType *item,int i,int j) { if (i<1||i>rows||j<1||j>cols) exit(ERROR); else { for (p=0;p<M.tu;p++) if (M.item[p].i==i&&M.item[p].j==j) { *item=M.item[p].value; return OK; } else if (M.item[p].i>i||M.item[p].i==i&&M.Item[p].j>j) break; *item=0; return OK; }

49 （2）输出三元组表示的稀疏矩阵 void Print(Matrix M) { for (p=0,i=1;i<=M.rows;i++) { for (j=1;j<=M.cols;j++) if (p<M.tu&&M.item[p].i==i&&M.item[p].j==j) printf(“%4d”,M.item[p++].value;); else printf(“%4d”,0); printf(“\n”); }