《数据结构与算法应用教程 教学课件 ppt 作者高佳琴 第5章完 字符串与多维数组》由会员分享，可在线阅读，更多相关《数据结构与算法应用教程 教学课件 ppt 作者高佳琴 第5章完 字符串与多维数组（31页珍藏版）》请在金锄头文库上搜索。
1、数据结构与算法实用教程,主编 高佳琴,第5章 字符串与多维数组,本章要点： 1)字符串的基本概念与基本运算。 2)字符串的存储和基本运算的实现。 3)数组的存储结构。 4)特殊矩阵的压缩存储及运算。 本章难点： 稀疏矩阵的压缩存储及转置运算。,第5章 字符串与多维数组,5.1 串 5.2 数组,5.1 串,5.1.1 串的基本概念 5.1.2 串的存储结构 5.1.3 串基本操作的实现算法 5.1.4 串的应用,5.1.1 串的基本概念,1.串的定义 串是一个有穷字符序列，记为：s=a1a2an (n0)。 其中，s是串的名称，用双引号括起来的字符序列是串的值。ai可以是字母、数字或其他字符，
2、串中字符的个数n被称作串的长度。当n=0时，串中没有任何字符，串的长度为0，通常被称为空串。,2.相关概念,(1) 子串与主串 串中任意连续的字符组成的子序列被称为该串的子串。包含子串的串又被称为该子串的主串。 (2）子串的位置 子串在主串中第一次出现时其第一个字符的位置。例如上面b在a中出现的位置是1,c在a中出现的位置是12。 (3）串相等 两个串的长度相等，并且各个对应的字符也都相同。,3串的基本操作,在C语言中讲过，普通数组不能作为整体进行操作（如赋值、输入、输出）。串有别于其他线性表的最大区别是串作为整体进行操作。串的基本操作较多，重点介绍如下五种操作，其他重要的操作还有子串的替换、
3、插入、删除等。 (1)判断串是否为空 StrEmpty(s) (2)计算串长度 StrLength(s) (3)串连接 StrConcat(s1,s2) (4)求子串 SubStr(s,i,len) (5)串的定位 StrIndex(s1,t),5.1.2 串的存储结构,1. 顺序存储结构 2.链式存储结构,1. 顺序存储结构,串的顺序存储结构与线性表的顺序存储一样，用一组连续的存储单元依次存储串中的字符序列。在C 语言中，有两种实现方式。第一种是事先定义字符串的最大长度，字符串存储在一个定长的存储区中。 第二种是在程序执行过程中，利用标准函数malloc和free动态地分配或释放存储字符串的
4、存储单元，并以一个特殊的字符0作为字符串的结束标志。,2.链式存储结构,图5-1 链串的存储结构,用带头结点的单链表来存储串，这就是链串。链串的一个结点可以存储多个字符，通常将链串中每个结点存储的字符个数称为结点大小。如图5-1a所示为结点大小为4的链串，图5-1b所示为结点大小为1的链串。,5.1.3 串基本操作的实现算法,表格,5.1.3 串基本操作的实现算法,图5-3 串连接操作算法流程图,5.1.3 串基本操作的实现算法,图5-4 求子串函数算法流程图,5.1.3 串基本操作的实现算法,表格,5.1.4 串的应用,设计一个算法，求串s中出现的第1个最长重复子串及其位置。重复子串是指一个
5、或多个连续相同的字符组成的子串。若s=“abaacsssda”， 则其最大重复子串是sss， 起始位置5， 长度3。算法思路：返回最大重复子串只需确定其起始位置和长度即可。用index表示最大重复子串的起始位置序号， 用max表示其长度， 并分别设其初值为0。通过扫描串s并依次与最大子串的长度进行比较的方法来实现。,5.2 数组,5.2.1 数组的定义 5.2.2 数组的存储结构 5.2.3 特殊矩阵的压缩存储 5.2.4 稀疏矩阵的压缩存储 5.2.5 数组的应用,5.2.1 数组的定义,数组是n个具有相同类型的数据元素构成的有限序列。若线性表中的数据元素为非结构的简单元素， 则称为一维数组
6、， 又称为向量； 若一维数组中的数据元素又是一维数组结构， 则称为二维数组； 依次类推， 若二维数组中的元素又是一个一维数组结构， 则称为三维数组。,5.2.2 数组的存储结构,1.顺序存放规则 2.顺序存储数组的性质,1.顺序存放规则,1) 先行后列顺序， 或者称为行优先顺序， 先分配第一行， 再分配第二行， 最后分配第m行。 2) 先列后行顺序， 或者称为列优先顺序， 先分配第一列， 再分配第二列， 最后分配第n列。,2.顺序存储数组的性质,表格,2.顺序存储数组的性质,表格,2.顺序存储数组的性质,解题思路：该二维数组用顺序存储结构存放元素， 而且是行优先存放。A数组的行数是8， 列数是
7、10。其存储形式和C语言中一致， 数组下标的下界是0， 因此地址的计算公式是：LOC(aij)= LOC(a00)+(i*n + j)*L， 将相关参数代入公式中， 求得结果：200+(710+4)4 =496。,5.2.3 特殊矩阵的压缩存储,1.对称矩阵的压缩存储 2.n阶上(下)三角矩阵,1.对称矩阵的压缩存储,(1) 对称矩阵的定义 若一个n阶方阵Ann中的数据元素满足aij=aji(0i,jn-1),则称其为对称矩阵。 (2) 对称矩阵压缩存储分析 由于对称矩阵关于主对角线对称， 因此存储数据元素的值时， 只需要存储对称矩阵中上三角部分或下三角部分， 使对称的元素共用一个存储空间。,2.n阶上(下)三角矩阵,(1) n阶上(下)三角矩阵的定义 矩阵的上(下)三角中的元素(不包括对角线)均为常数c或0的n阶方阵。 (2) n阶上(下)三角矩阵的压缩存储分析 基本思路与对称矩阵相似， 借用一维数组bt存储其上(下)三角非常数c或0的部分元素。,5.2.4 稀疏矩阵的压缩存储,1.稀疏矩阵的三元组表示 2.转置算法,1.稀疏矩阵的三元组表示,表格,2.转置算法,(1) 矩阵转置方法描述,表格,2.转置算法,(2) 示例分析 (3) 转置算法的实现,表格,5.2.5 数组的应用,习题,1.简答题 2.算法设计题 1. 实验目的 2. 实验内容,
