武汉理工大学：《数据结构》 第四章 串、数组与广义表

第4章串、数组与广义表 41串的定义与操作 定义:串( string)是由零个或多个字符组 成的有限序列,也称字符串 记为:s=” aaaa a 3 称为串的长度(即串中字符的个数),当n 为零时称为空串。 子串:串中任意连续的字符组成的子序列, 称为原串(主串)的子串 例如:a=”abcd”,b=”abc”,x=”d” 主串 武汉理子患华夏学院信息工串 系

武汉理工大学华夏学院-信息工程 系 第4章串、数组与广义表 4.1 串的定义与操作 定义：串（string）是由零个或多个字符组 成的有限序列，也称字符串。 记为：s＝”a0a1a2a3…an ” 其中s称为串名， a0a1a2a3…an称为串值，n 称为串的长度（即串中字符的个数），当n 为零时称为空串。 子串：串中任意连续的字符组成的子序列， 称为原串（主串）的子串。 例如：a＝”abcd”，b＝”abc”，x＝”d” 主串 子串 子串

串的比较运算 两串相等:两串的长度相等且对应位置的字符 都相同时,称为两串相等。 当两串不等时按字典序比较大小 注意:1串值必须用“”括起来 2.空串与空白串的区别:空串长度为0, 空白串的长度大于0; 常用的串操作有: 赋值:将一个串值赋给串变量s; 复制:将一个串s1赋给另一个串变量s; 连接:两个串首尾相连,形成另一个新串 以及判串相等、求串长、求子串、定位、插入、 删除、替换等操作。 武汉理工大学华夏学院-信息工程 系

武汉理工大学华夏学院-信息工程 系 串的比较运算 两串相等：两串的长度相等且对应位置的字符 都相同时，称为两串相等。 当两串不等时按字典序比较大小。 注意：1.串值必须用“”括起来； 2. 空串与空白串的区别：空串长度为0， 空白串的长度大于0； 常用的串操作有： 赋值：将一个串值t赋给串变量s； 复制：将一个串s1赋给另一个串变量s； 连接：两个串首尾相连，形成另一个新串； 以及判串相等、求串长、求子串、定位、插入、 删除、替换等操作

42串的存储结构 串的顺序存储 用一组地址连续的存储单元存储串值的字 符序列,c语言中用字符数组来实现。 例如 char sl (20), name(8) 二、串的堆分配存储 串变量的存储空间是在程序执行过程中动 态分配得到的,程序中出现的所有串变量的值 共享一个称为“堆”的存储空间 串的链式存储 用单链表来实现。 武汉理工大学华夏学院-信息工程 系

武汉理工大学华夏学院-信息工程 系 4.2 串的存储结构 一、串的顺序存储 用一组地址连续的存储单元存储串值的字 符序列，c语言中用字符数组来实现。 例如：char s1〔20〕，name〔8〕等 二、串的堆分配存储 串变量的存储空间是在程序执行过程中动 态分配得到的，程序中出现的所有串变量的值 共享一个称为“堆”的存储空间。 三、串的链式存储 用单链表来实现

4.5数组 、数组的概念:一组相同类型数据有序的 组合,其中每一个数据称为数组元素 设一个m行n列的矩阵A为: 11 a a21222 a2 n A= I amI am 2 °amn 武汉理工大学华夏学院-信息工程 系

武汉理工大学华夏学院-信息工程 系 4.5 数组 一、数组的概念：一组相同类型数据有序的 组合，其中每一个数据称为数组元素 设一个m行n列的矩阵A为： | a11 a12 · · · a1 n | | a21 a22 · · · a2 n | A=| · · · | | · · · | | am1 am 2 · · · am n |

二、二维数组的处理方法 1、矩阵的逻辑特点 设一个m行n列的矩阵A为: 11a 12 a In a21a22 a 2 n A= I amI am 2 am n 武汉理工大学华夏学院-信息工程 系

武汉理工大学华夏学院-信息工程 系 二、二维数组的处理方法 1、矩阵的逻辑特点 设一个m行n列的矩阵A为： | a11 a12 · · · a1 n | | a21 a22 · · · a2 n | A=| · · · | | · · · | | am1 am 2 · · · am n |

可以把矩阵A看成一个把每一行当成一个结点 的线性表B,则表B的结点个数(表B的长度) 为m;也可以把矩阵A看成一个把每一列当成 个结点的线性表C,则表C的结点个数(表C的 长度)为n。 2、矩阵的存储表示 在程序设计中,一个矩阵通常用一个二维数组 来表示,顺序存储在一个地址连续的存储区内, 具体实现分为: 武汉理工大学华夏学院-信息工程 系

武汉理工大学华夏学院-信息工程 系 2、矩阵的存储表示 在程序设计中，一个矩阵通常用一个二维数组 来表示，顺序存储在一个地址连续的存储区内， 具体实现分为： 可以把矩阵A看成一个把每一行当成一个结点 的线性表B，则表B的结点个数（表B的长度） 为m；也可以把矩阵A看成一个把每一列当成一 个结点的线性表C，则表C的结点个数（表C的 长度）为n

(1)按行序优先顺序存储 按行序优先顺序存储是从第一个元素a1开始,先存储 第一行;再存储第二行,以此类推,直到每一行存储 完。在存储各行时,又按第一列、第二列……的次序。 例矩阵A按行序优先顺序存储的结构图为图61( 所示。 (2)按列序优先顺序存储 按列序优先顺序存储是从第一个元素a1开始先存储第 列;再存储第二列,以此类推,直到每一列存储完。 在存储各列时,又按第一行、第二行.次序。 例矩阵A按列序优先顺序存储的结构图为图6-1(b)所示。 武汉理工大学华夏学院-信息工程 系

武汉理工大学华夏学院-信息工程 系 按列序优先顺序存储是从第一个元素a11开始,先存储第 一列；再存储第二列，以此类推，直到每一列存储完。 在存储各列时，又按第一行、第二行……的次序。 例矩阵A按列序优先顺序存储的结构图为图6-1(b)所示。 按行序优先顺序存储是从第一个元素a11开始，先存储 第一行；再存储第二行，以此类推，直到每一行存储 完。在存储各行时，又按第一列、第二列…… 的次序。 例矩阵A按行序优先顺序存储的结构图为图6-1 (a) 所示。 （1）按行序优先顺序存储 （2）按列序优先顺序存储

all a a12 21 a a a a 22 22 azn (a)按行序优先存储表 (b)按列序优先存储表 图4-1矩阵的存储结构表示图 武汉理工大学华夏学院-信息工程 系

武汉理工大学华夏学院-信息工程 系 amn …. am2 ... a22 a12 amn …. a2n ... a22 a21 (a)按行序优先存储表 (b)按列序优先存储表 图4-1矩阵的存储结构表示图 a1n ... a12 a11 am1 ... a21 a11

(3)矩阵中元素的寻址公式国心 设矩阵A的第一个元素a1的首地址为 (1,1,每一个元素占用的存储单元数为 则矩阵A的第珩行,第列的元素a1的首地址为: 若矩阵A按行序优先顺序存储,则 loc(Lj)=loc(1,1)+((I-1)×n+j)×s 若矩阵A按列序优先顺序存储,则 loc(Li)=loc(1,1)+((j-1)×m+i)×s 武汉理工大学华夏学院-信息工程 系

武汉理工大学华夏学院-信息工程 系 loc(I,j)＝loc(1,1)＋〔（I－1）×n＋j〕×s 若矩阵A按列序优先顺序存储，则 loc(I,j)＝loc(1,1)＋〔（j－1）×m＋i〕×s 若矩阵A按行序优先顺序存储，则 （3） 矩阵中元素的寻址公式 设矩阵A的第一个元素a11的首地址为 loc(1,1)，每一个元素占用的存储单元数为s， 则矩阵A的第I行，第j列的元素aij的首地址为：

46矩阵的压缩存储 特殊矩阵的压缩存储 1.压缩存储的概念 对数组中的零元素不分配存储单元,只对 非零元素分配存储单元进行存储的存储方 法称为压缩存储。 其目的是节省存储空间。 2.特殊矩阵 (1)定义 在矩阵中存在大量的零元素,且这些零元 素的分布是有规律的一类矩阵。 武汉理工大学华夏学院-信息工程 系

武汉理工大学华夏学院-信息工程 系 4.6 矩阵的压缩存储 一、特殊矩阵的压缩存储 1. 压缩存储的概念 对数组中的零元素不分配存储单元，只对 非零元素分配存储单元进行存储的存储方 法称为压缩存储。 其目的是节省存储空间。 2. 特殊矩阵 （1）定义 在矩阵中存在大量的零元素，且这些零元 素的分布是有规律的一类矩阵