四、串、数组和广义表

（一）串

零个或多个任意字符组成的有限序列

子串；空串；主串；字符位置；子串位置（第一个字符）；空格串！=空串；串相等 ······略 KMP算法

（二）数组

定义：n维同类型元素组成的序列，且连续存储 ElemType array[m][n]

1.数组抽象数据类型

略

2.数组的存储结构

1）静态存储

行主次序+列主次序

数组元素地址计算：（起始地址b，每个元素占L个字节）

  1. 一维数组 $Loc(e)=b+i*L$
  2. 二维数组 $Loc(e)=b+(in+j)L$
  3. 三维数组 $Loc(e)=b+(inp+jp+k)L$
  4. n维数组 $Local(e)=b+ \left( \sum_{j=1}^{n-1} i_j \cdot \prod_{k=j+1}^{n} u_k + i_n \right) \cdot L$

2）动态存储

n维数组映射到一维数组

3.特殊矩阵的压缩存储

1）常规存储：二维存储

2）对称矩阵：$a_{ij}=a_{ji}$ -> 只存上三角或下三角 -> $n*(n+1)/2$

存放在一个一维数组，算存储位置$a_{ij}$

3）三角矩阵:只存上三角或下三角

image-20250114114854644

4）对角矩阵（三对角矩阵、五对角矩阵······）

二维矩阵存储

image-20250114115458096

5）稀疏矩阵（只存储非零元素）

用三元组表

image-20250114120323764

4.三元组表

存储非零元素，i（行）,j,（列）v（数值），在第三元组表0行存矩阵总行数、总列数、非零元素总个数

5.十字链表

优点：灵活的插入、删除、进行矩阵运算

image-20250114141506773

image-20250114133726590

（三）广义表

定义：n>=0个元素的有限序列，每一个元素或是原子，或是广义表，可以表中套表 ，计作$LS=(a_1,a_2,\ldots,a_n)$，

  • 表头为$a_1$，表尾除了$a_1$外组成的表，
  • 长度：最外层所含元素个数
  • 深度：展开后所含括号的重数
  • 共享：$B=(A)$
  • 基本运算：GetHead(L),GetTail(L)
  • 链式结构存储