线性表与字符串-2

《线性表与字符串-2》由会员分享，可在线阅读，更多相关《线性表与字符串-2（57页珍藏版）》请在金锄头文库上搜索。

1、数组数组 线性表线性表 字符串字符串第二章 线性表和字符串数组数组 二元组二元组 的一个集合。的一个集合。uu存储于一个连续存储空间中的相同数据类型的数据元素存储于一个连续存储空间中的相同数据类型的数据元素 的集合；的集合；uu通过数组元素的下标，可以得到存放该数组元素的存储通过数组元素的下标，可以得到存放该数组元素的存储 地址，从而可以访问该数组元素的值。地址，从而可以访问该数组元素的值。 一维数组一维数组向量向量uu具有相同类型的具有相同类型的n n( (n n 0)0)个元素的有限序列。个元素的有限序列。FFn n为数组长度或数组大小；为数组长度或数组大小；FFn n=0=0为空数组。为

2、空数组。uu各数组元素处于一个线性聚集或线性表中。各数组元素处于一个线性聚集或线性表中。FF每个元素的数据类型相同；每个元素的数据类型相同；FF占有相同的存储空间；占有相同的存储空间；FF每个元素的开始位置到相邻元素的开始位置的距离相等每个元素的开始位置到相邻元素的开始位置的距离相等 。一维数组的特点一维数组的特点uu数组中的每一个元素在数组中的位置由下标唯一确数组中的每一个元素在数组中的位置由下标唯一确 定；定；uu除第一个元素外，其它元素有且仅有一个直接前驱除第一个元素外，其它元素有且仅有一个直接前驱 ，第一个元素没有前驱。，第一个元素没有前驱。uu除最后一个元素外，其它元素有且仅有一个直

3、接后除最后一个元素外，其它元素有且仅有一个直接后 继，最后一个元素没有后继。继，最后一个元素没有后继。 示例示例长度为长度为1010，每个元素占，每个元素占l l个存储字，起始地址为个存储字，起始地址为a a。数组的定义和初始化数组的定义和初始化 创建数组创建数组uu静态数组静态数组FF在声明数组对象时显式地定义了数组长度；在声明数组对象时显式地定义了数组长度；FF定义了数组的下标范围；定义了数组的下标范围；FF对数组各元素赋值；对数组各元素赋值；FF存储空间不随程序的执行而改变。存储空间不随程序的执行而改变。uu动态数组动态数组FF用指针声明数组；用指针声明数组；FF在指针中只存放数组第一个

4、元素的地址，所以仅占用一在指针中只存放数组第一个元素的地址，所以仅占用一 个存储空间；个存储空间；FF用用+和和- - -可访问数组下一个元素或前一个元素。可访问数组下一个元素或前一个元素。数组的标准操作数组的标准操作uu存储存储uu抽取抽取 示例示例uuPositionPosition i i=PositionPosition i i-1+-1+NumberNumber i i-1-1FF赋值符号右边表示按下标赋值符号右边表示按下标i i-1-1直接提取相应直接提取相应 数组元素的值；数组元素的值；FF赋值符号左边表示按下标赋值符号左边表示按下标i i把右边的计算结把右边的计算结 果直接存储

5、到相应数组元素中。果直接存储到相应数组元素中。二维数组二维数组矩阵矩阵uu由由n n个行向量个行向量mm个列向量所组成的向量。个列向量所组成的向量。FF共有共有n n* *mm个数组元素；个数组元素； 元素元素 j j k k 处于第处于第j j个行向量的第个行向量的第k k个列向量；个列向量；在行和列方向上各有一个直接前驱和直接后继。在行和列方向上各有一个直接前驱和直接后继。FF某一个数组元素在数组中的位置需由下标的某一个数组元素在数组中的位置需由下标的 二元组二元组 j j k k 唯一确定。唯一确定。 三维数组三维数组uu共有共有mm1 1* *mm2 2* *mm3 3个数组元素；个数

6、组元素；FF每个数组元素同时处于三个向量之中；每个数组元素同时处于三个向量之中； 最多有三个直接前驱和直接后继。最多有三个直接前驱和直接后继。FF某一个数组元素在数组中的位置需由下标的三元组某一个数组元素在数组中的位置需由下标的三元组 i i j j k k 唯一确定。唯一确定。二维数组二维数组 三维数组三维数组行向量行向量下标下标 i i 页向量页向量下标下标i i列向量列向量下标下标 j j 行向量行向量下标下标j j列向量列向量下标下标k kn n维数组维数组uua a mm1 1 mm2 2.mmn n FF总共有总共有mm1 1* *mm2 2*mmn n个数组元素；个数组元素；FF

7、每一个数组元素每一个数组元素a a i i1 1 i i2 2.i in n 处于处于n n个向量个向量 之中；之中；FF每一个数组元素的位置由下标的每一个数组元素的位置由下标的n n元组元组 i i1 1 i i2 2.i in n 唯一确定。唯一确定。 数组连续存储方式数组连续存储方式在实现数组存储时，通常是按各个数组元素的排列顺序，在实现数组存储时，通常是按各个数组元素的排列顺序， 顺次存放在一个连续的存储区域内，得到一个所有数组元顺次存放在一个连续的存储区域内，得到一个所有数组元 素的线性序列。素的线性序列。一维数组一维数组uu第一个元素的起始位置为第一个元素的起始位置为 ，每一个数，

8、每一个数 组元素的存储大小为组元素的存储大小为l l。uu任一数组元素的存储地址任一数组元素的存储地址LOCLOC( (i i) )：LOC(1) = LOC(0) + l =+ l LOC(2) = LOC(1) + l =+ 2*l， LOC(i) = LOC ( i -1 ) + l =+ i*l行优先顺序行优先顺序uu所有数组元素按行向量依次排列，第所有数组元素按行向量依次排列，第i i+1+1个行个行 向量紧跟在第向量紧跟在第i i个行向量后面。个行向量后面。 列优先顺序列优先顺序uu所有数组元素按列向量依次排列，第所有数组元素按列向量依次排列，第j j+1+1个列个列 向量紧跟在第

9、向量紧跟在第j j个列向量后面。个列向量后面。二维数组二维数组行优先行优先 LOC LOC ( ( j j, , k k ) ) = = LOC LOC ( ( j j, 0, 0 )+)+k k* *l l /第j行开始位置加k k* *l l= LOC = LOC ( ( j j-1, 0-1, 0 )+)+mm* *l l+ +k k * *l l/第j-1行开始位置加该行元素个数mm* *l l加k k * *l l= LOC = LOC ( ( j j-2, 0-2, 0 )+2*)+2*mm* *l l + +k k* *l l /前推到第j-2行= = = LOC = LOC (

10、0, 0(0, 0 )+)+j j* *mm* *l l + +k k* *l l /前推到第0行= = +( +( j * m + k j * m + k )*)*l l设二维数组设二维数组a a n n mm 第一个元素第一个元素a a0000在相应的一维数在相应的一维数 组中存放于第一个位置，其地址为组中存放于第一个位置，其地址为 ，每个元素占，每个元素占l l个个 元素的空间。元素的空间。 则任一数组元素则任一数组元素a a j j k k 在相应一维数组中的存放地址在相应一维数组中的存放地址 利用递推公式计算：利用递推公式计算：设三维数组设三维数组a a mm1 1 mm2 2 mm

11、3 3 中，对于任一数组元素中，对于任一数组元素a a i i j j k k 在一维数组中存放的位置为：在一维数组中存放的位置为：页优先页优先 LOC LOC ( ( i, ji, j, , k k ) ) = = LOC LOC ( ( i i, 0 , 0, 0 , 0 )+)+j j* *mm3 3* *l l+ +k k* *l l= LOC = LOC ( ( i i-1, 0, 0-1, 0, 0 )+)+mm2 2* *mm3 3* *l l+ +j j* *mm3 3* *l l+ +k k* *l l= LOC = LOC ( ( i i-2, 0, 0-2, 0, 0 )

12、+2*)+2*mm2 2* *mm3 3* *l l+ +j j* *mm3 3* *l l+ +k k* *l l= = = LOC = LOC (0, 0 , 0(0, 0 , 0 )+)+i i* *mm2 2* *mm3 3* *l l+ +j j* *mm3 3* *l l+ +k k* *l l= = +(+(i i* *mm2 2* *mm3 3+ +j j* *mm3 3+ +k k)*)*l l三维数组三维数组线性表线性表 线性聚集，一个存储线性聚集，一个存储n n( (n n 0 0) )个表项的序列。个表项的序列。uun n是表的长度，可以是任意整数。是表的长度，可以是任

13、意整数。FFn n=0=0为空表。为空表。FF表的长度随增加或删除某些表项而发生改变。表的长度随增加或删除某些表项而发生改变。uu每个表项都是单个对象，其数据类型相同。每个表项都是单个对象，其数据类型相同。FF各个表项通过其位置来访问；各个表项通过其位置来访问；FF第一个表项位于表的头部，最后一个表项位于第一个表项位于表的头部，最后一个表项位于 表的尾部。表的尾部。 除最后一个表项之外，其它每个表项有且仅有一除最后一个表项之外，其它每个表项有且仅有一 个直接后继。个直接后继。线性表的特点线性表的特点uu特点特点 顺序存取顺序存取FF为了得到顺序表中所要求的项，必须从表为了得到顺序表中所要求的项

14、，必须从表 的第一个表项开始，逐个访问表项，直到找的第一个表项开始，逐个访问表项，直到找 到满足要求的表项为止。到满足要求的表项为止。uu 遍历遍历 逐项访问逐项访问从前向后从前向后 从后向前从后向前 从两端向中间从两端向中间线性表上的基本运算线性表上的基本运算 InitList(L)InitList(L) 构造构造一一个空的顺序表个空的顺序表 Length(L)Length(L) 求顺序表求顺序表L L中的表元个数中的表元个数 GetNode(L, i)GetNode(L, i) 取顺序表取顺序表L L中的第中的第i i个表元个表元 LocateNode(L, x)LocateNode(L,

15、 x)在顺序表中找值为在顺序表中找值为x x的结点，返的结点，返 回该结点在回该结点在L L中的位置。中的位置。 InsertList(L, x, i)InsertList(L, x, i)在在L L的第的第i i个位置插入一个个位置插入一个 值为值为x x的新表元。的新表元。 DeleteList(L, i)DeleteList(L, i) 删除删除L L的第的第i i个表元。个表元。线性表线性表 的存储结构的存储结构常用的存储结构：常用的存储结构： 顺序存储顺序存储 链接存储链接存储 顺序存储（顺序表）顺序存储（顺序表） 设顺序表的每个表元的结构都相同，记设顺序表的每个表元的结构都相同，记 LOCLOC（ a ai i） 为存储为存储aiai的开始地址，则的开始地址，则LOCLOC（ a ai