数据结构c++ ( 三 )

第4章 字符串和多维数组

• 字符串存储
• 模式匹配
• 多维数组

字符串存储

       
串的逻辑结构
       
       
串: 零个或多个字符组成的有限序列.

串长度: 串中所包含的字符个数.

空串: 长度为0的串 , 记为: " “.
       
非空串 通常记为：
S=” s₁ s₂ …… s_n "
其中：S是串名，双引号是 定界符 , 双引号引起来的部分是串值 ，s_i（1≤i≤n）是一个任意字符.

子串: 串中任意个连续的字符组成的子序列.

主串: 包含子串的串.

子串的位置: 子串的第一个字符在主串中的序号.

S1="ab12cd "
S2=“ab12”
S3=“ab13”

       
       
串的存储结构

       
顺序串: 用数组来存储串中的字符序列.

       
链接串: 用链接存储结构来存储串.

       
       
       
       

模式匹配

       
模式匹配:

          给定主串 S = "s₁s₂…s_n"和模式 T= “t₁t₂…t_m”,
在S中寻找T的过程称为模式匹配.
       
          模式匹配的应用包括 生物信息学 (基因表达分析，基因配对)、信息检索、拼写检查、语言翻译、数据压缩、网络入侵检测.
       
       
模式匹配—BF算法、KMP算法
       
       
       
       
       

多维数组

       
       


数组的定义: 数组是由一组 类型相同 的数据元素构成的 有序集合，每个元素受n ( n≥1)个线性关系的约束，并称该数组为 n 维数组.

              
数组的特点
       

• 元素本身可以具有某种结构，属于同一数据类型；

• 数组是一个具有固定格式和数量的数据集合.
         
         
  二维数组是数据元素为线性表的线性表.        
                

数组的存储结构与寻址—一维数组
       
设一维数组的下标的范围为闭区间[l,h],每个数组元素占用 c 个存储单元，则其任一元素 a_i的存储地址可由下式确定：
Loc(a_i)＝Loc(a_l)＋(i－l)×c

数组的存储结构与寻址—一维数组

常用的映射方法有两种：

• 按行优先: 先行后列,先存储行号较小的元素,行号相同者先存储列号较小的元素.
• 按列优先: 先列后行,先存储列号较小的元素,列号相同者先存储行号较小的元素.

       
       
按行优先存储的寻址

a_ij前面的元素个数
=整行数×每行元素个数+本行中aij前面的元素个数
=(i -l₁)×(h₂ -l₂＋1)＋(j -l₂)

另一种是按列序存储，如高级语言中的FORTRAN语言就是以列序为主
a₀₀,a₁₀, …,a_n-11,a₀₁,a₁₁, …,a_n-11,…,a_0m-1, a_1m-1, …,a_n-1m-1

设数组开始存放位置 LOC( 0, 0 ) = a,
每个元素占用 l 个存储单元
则a[i][j]的存储地址：
LOC ( i, j ) = a + ( j *n +i ) * l
       
       
三维数组
       
       

• 各维元素个数为 m1, m2, m3
• 下标为 i1, i2, i3的数组元素的存储地址：
• 按页/行/列存放
• 说明：各维的下标从0开始

       
       
       
n维数组
       
各维元素个数为 m₁, m₂, m₃, …, m_n
下标为 i₁, i₂, i₃, …, i_n 的数组元素的存储地址: