数据结构【数组、串、广义表】-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构【数组、串、广义表】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

第四章数组、串、广义表

一、数组
1.概念：线性表是通过数组实现的，数组是线性表的推广，数组只有存取元素和修改元素的操作（除了初始化和销毁）；
2.数组的存储结构：一个数组的所有元素在内存中占用一段连续的存储空间（顺序存储）；

以行为主顺序优先存储；
以列为主顺序优先存储。

3.矩阵的压缩存储（节约空间）

对称矩阵：元素关于主对角线对称，利于节约空间，n*(n+1)/2；
三角矩阵：上三角或者下三角均为同一个常量，n*(n+1)/2+1；
三对角矩阵：第一行和最后一行有2非0数字，其余都是3个非0数字，3n-2；转化为一维数组的话，下标是k=2i+j-1（i是这个元素的纵坐标，j是横坐标）；
稀疏矩阵：三元组（i,j,v）记录了非零元素的行号i、列号j以及非零的元素v（一般压缩存储方法有三元组顺序表和十字链表）；

二、串
1.概念：特殊的线性表，数据元素是仅是一个字符组成，所以串是由0个或多个字符组成的有限序列；无元素叫空串（空格串不是空串），包含子串的叫主串，默认以1开头；
2.基本存储方式：顺序存储和链式存储；
3.子串：串中任意连续字符组成的子序列，空串是任意串的子串，任意串是其自身的子串；

长度为n的字符串的子串个数:
- 有n(n+1)/2 +1个子串;
- 非空子串:n(n+1)/2;
- 非空真子串:n(n+1)/2-1。

4.串相等：两串串值相等（相同），但两串长度相等时，各个对应位置的字符都相等才相等；
5.串的模式匹配算法：简单说就是在文本中查找某字符；

简单匹配：时间复杂度O(n*m)，n和m分别是主串和模式串（子串）的长度；
KMP算法：相对比较方便
前缀：第一个字母开头，不包括全部；如：absd，前缀是a、ab、ads;
后缀：最后一个字母开头，不包括全部；如：absd，后缀是d、sd、bsd;
求next：next[1]=0，前后缀重合时加1，否则就是1；

三、广义表
1.概念：简称表，一种递归的数据结构，通常使用链式存储结构；时线性表的推广，由于有两种数据元素，所以需要两种结构的结点，表结点和原子结点；
数据结构【数组、串、广义表】,数据结构,数据结构
2.特征：文章来源地址https://www.toymoban.com/news/detail-606246.html

广度：定义最外层包含的元素个数，把最外层的括号去掉就很明显了；
深度：定义所含弧的重数；原子深度为0，空表为1；
任何一个非空广义表GL可分解为表头head(GL)=al和表尾tail(GL)=(a2,…,an)两部分；
小写字母表示原子，大写字母表示广义表表名；
例子：A=()
B=(e)
C=(a,(bcd))
D=(A,B,C)=((),(e),(a,(b,cd)) E=((a,(a,b),((a,b),c)))
A是一个空表，其长度为0,其深度为1;
B是只含有单个原子e的表，其长度为1其深度为1:
C有两个元素，一个是原子a，另一个是子表，其长度为2，其深度为2;
D有三个元素，每个元素都是一个表，其长度为3,其深度为3;
E中只含有一个元素，是一个表，它的长度为1,其深度为4；
表结点的三个域：标志域、指示表头的指针的指针域、指示表尾的指针的指针域，tag=1;
原子域：两个域，标志域和值域，tag=0；

3.广义表中的head和tail的运算
表头：表中第一个元素，可以是原子、子表；
表尾：必定时子表
操作：取出
- 例题：已知广义表LS=((a,b,c),(d,e,f))，取出e，使用tail和head如何取出来？tail(LS)=((d,e,f))
  head(tail(LS))=(def) tail(head(tail(LS)))=(e,f) //无论如何都会加上这个()括号
  head(tail(head(tail(Ls)))=e //head可以去除单个元素