资源预览内容
第1页 / 共29页
第2页 / 共29页
第3页 / 共29页
第4页 / 共29页
第5页 / 共29页
第6页 / 共29页
第7页 / 共29页
第8页 / 共29页
第9页 / 共29页
第10页 / 共29页
亲,该文档总共29页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
第4章 串和数组,本章主要介绍下列内容: 串的定义、存储结构和基本运算 数组的定义、基本运算和存储结构 特殊矩阵的压缩存储,退出,诚昊工作室,4.1 串 4.2 数组 4.3 应用举例,4.1 串,4.1.1 串的定义和基本运算 串是字符串的简称。它是一种在数据元素的组成上具有一定约束条件的线性表,即要求组成线性表的所有数据元素都是字符,所以,人们经常又这样定义串:串是一个有穷字符序列。,串一般记作: s= “a1a2.an” (n0) 其中,s是串的名称,用双引号(“”)括起来的字符序列是串的值;ai可以是字母、数字或其他字符;串中字符的数目n被称作串的长度。当n=0时,串中没有任何字符,其串的长度为0,通常被称为空串。 s1= “” s2= “ ” s1中没有字符,是一个空串;而s2中有两个空格字符,它的长度等于2,它是由空格字符组成的串,一般称此为空格串。 概念: 子串、主串:串中任意连续的字符组成的子序列被称为该串的子串。包含子串的串又被称为该子串的主串。,例如,有下列四个串a,b,c,d: a= “Welcome to Beijing” b= “Welcome” c= “Bei” d= “welcometo” 子串的位置:子串在主串中第一次出现的第一个字符的位置。 两个串相等:两个串的长度相等,并且各个对应的字符也都相同。 例如,有下列四个串a,b,c,d: a= “program” b= “Program” c= “pro” 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 串的存储结构 1. 顺序存储结构 串的顺序存储结构与线性表的顺序存储类似,用一组连续的存储单元依次存储串中的字符序列。在C语言中,有两种实现方式: 第一种是事先定义字符串的最大长度,字符串存储在一个定长的存储区中。类型定义如下所示: #define MAXSIZE 255 char sMAXSIZE;,第二种是在程序执行过程中,利用标准函数malloc和free动态地分配或释放存储字符串的存储单元,并以一个特殊的字符作为字符串的结束标志,它的好处在于:可以根据具体情况,灵活地申请适当数目的存储空间,从而提高存储资源的利用率。类型定义如下所示: typedef struct char dataMAXSIZE; int curlen; SeqString; 定义一个串变量:SeqString s; 不同的定义形式,算法中的处理也略有不同。下面我们将给出在第一种顺序存储方式下串的几个基本操作的算法。,(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; slen=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 ,4.2 数组,4.2.1 数组的定义和基本运算 数组的特点是每个数据元素可以又是一个线性表结构。因此,数组结构可以简单地定义为:若线性表中的数据元素为非结构的简单元素,则称为一维数组,即为向量;若一维数组中的数据元素又是一维数组结构,则称为二维数组;依次类推,若二维数组中的元素又是一个一维数组结构,则称作三维数组。 结论:线性表结构是数组结构的一个特例,而数组结构又是线性表结构的扩展。举例:,图 4-3,其中,A是数组结构的名称,整个数组元素可以看成是由m个行向量和n个列向量组成,其元素总数为mn。在C语言中,二维数组中的数据元素可以表示成a表达式1表达式2,表达式1和表达式2被称为下标表达式,比如,aij。 数组结构在创建时就确定了组成该结构的行向量数目和列向量数目,因此,在数组结构中不存在插入、删除元素的操作。 二维数组结构的基本操作: (1) 赋值操作。给定一组下标,存储或修改与之对应的数据元素。 (2)取值操作。给定一组下标,读其对应的数据元素元素。,4.2.2 数组的存储结构 从理论上讲,数组结构也可以使用两种存储结构,即顺序存储结构和链式存储结构。然而,由于数组结构没有插入、删除元素的操作,所以使用顺序存储结构更为适宜。换句话说,一般的数组结构不使用链式存储结构。 组成数组结构的元素可以是多维的,但存储数据元素的内存单元地址是一维的,因此,在存储数组结构之前,需要解决将多维关系映射到一维关系的问题。举例:,图 4-4,图 4-5,图 4-6,在C语言中 LOC(i,j)=LOC(0,0)+(n*i+j)*L,4.2.3矩阵的压缩存储 矩阵是在很多科学与工程计算中遇到的数学模型。在数学上,矩阵是这样定义的:它是一个由sn个元素排成的s行(横向)n列(纵向)的表。下面就是一个矩阵:,1. 特殊矩阵 所谓特殊矩阵就是元素值的排列具有一定规律的矩阵。常见的这类矩阵有:对称矩阵、下(上)三角矩阵、对角线矩阵等等。 对称矩阵的特点是aij=aji,,2. 稀疏矩阵的压缩存储 若一个mn的矩阵含有t个非零元素,且t远远小于m*n,则我们将这个矩阵称为稀疏矩阵。举例:,图 4-14,稀疏矩阵的压缩存储方法三元组表示法。 矩阵中的每个元素都是由行序号和列序号唯一确定的。因此,我们需要用三项内容表示稀疏矩阵中的每个非零元素,即形式为: (i,j,value) 其中,i表示行序号,j表示列序号,value表示非零元素的值,通常将它称为三元。我们将稀疏矩阵中的所有非零元素用这种三元的形式表示,并将它们按以行为主的顺序存放在一个一维数组中,就形成了我们所说的三元组表示法。举例:,图 4-15,define SMAX 1024 /*一个足够大的数*/ typedef struct int i,j; /*非零元素的行、列*/ datatype v; /*非零元素值*/ SPNode; /*三元组类型*/ typedef struct int mu,nu,tu; /*矩阵的行、列及非零元素的个数*/ SPNode dataSMAX; /*三元组表*/ SPMatrix; /*三元组表的存储类型*/,4.3 应用举例,例.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;i=m) printf (%d,%d,%dn, i ,k,min); /* if */ /*for i*/ ,例4.2 在串的堆分配存储结构上实现求子串函数SUBSTR(S,i,j) 详见课本。 例4.3 已知一个二维数组A,行下标0i7,列下标0j9,每个元素的长度为3字节,从首地址200开始连续存放在内存中,该数组元素按行优先存放,问:元素A7,4的起地址是多少? 该二维数组是用顺序存储结构存放元素,可用前面介绍的计算公式进行计算。A数组的行号数是8,列号数是10。题中给出的存放形式和C语言中一致,数组下标的下界是0,因此地址的计算公式是:LOC(ai,j)LOC(a0,0)+(i*n+j)*b,套用此公式,求得结果:200+(710+4)3422。 补充例题(06下程序员考试题),小结 基本学习要点如下: (1) 了解串的基本操作,掌握串的基本运算。 (2)重点掌握数组的顺序存储结构和元素地址计算方法。 (3)掌握稀疏矩阵的定义及其数组实现,稀疏矩阵的转置。,作业,方法,作业,4.5 4.6 复习巩固稀疏矩阵的转置运算。,
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号