线性表／链表／栈／队列／串／数组（稀疏矩阵）

线性表

• 线性实现：{基址，size，长度}
• 链式实现：{头，尾，长度}
• 应用：
  - AB集合合并：遍历A，取A中a，在B中查找a是否存在，不存在则插入
  - B去重：构造空A，遍历B，取b，在A中查找b是否存在，不存在则插入
  - 有序AB合并：构造空C，依次对比AB起始元素，大者入C，指针移动，继续，至某一为空，另外一个剩余的元素全部转入C

单链表：

• {头}，头节点是空的，增删注意维护原结构。
• 静态链表：用数组实现链表：数组元素为一个含有next元素的数组索引的结构，等于用结构实现了指针，放在了数组里。
• 双向链表：{头}，head一头为空，操作注意维护原结构

栈

• push，pop
• 动态顺序栈：{top（int*），base地址，size}，动态一维数组，base[top]是空位
• 静态顺序栈：{数组，int的top}，一维数组，[top+1]是空位

队列

• enqueue，dequeue
• 链式：{fount，rear}，链表，空（fount=rear）满（不会满）判断
• 顺序：{数组；int：fount，rear，size}，++时记得模size（循环队列），空（fount==rear）满（（rear+1）%size=fount）判断
• 应用：还没看的：日程安排，请求处理

串

• 元素是字符的线性表
• 实现：（顺序存储=地址连续）
  - 一般都是定长顺序存储，属于静态存储，在程序内存空间的静态存储区域；
  - 堆分配顺序存储：在堆区
• 存储：8位（压缩）or32位（非压缩）存储一个字符

模式匹配问题：模式串

• 检测，定位，枚举，计数（你平时用的find就是这个，还有心电图之类的波形匹配）
• kmp：
  • 研究模式串的结构：每个前缀的最大相同前后缀——自匹配，长度记为x；next[i]记录i之前的前缀部分的特征，i是索引，记录的是长度；n[0]=-1；
  • 使下次匹配时主串中起始位置为pre position+n[i]（而不是+1）
  • n[i]生成算法：从1开始，递推，比较str[i+1]与str[n[i]]，同则n[i+1]=n[i]+1；异，在已匹配的n[i]的串中找结构：str[0:n[i]-1]的x，是n[n[i]]，比较str[x]与str[i+1]，同，则n[i+1]=x+1，异则继续，此次研究的是串str[ 0 : n[n[i]]-1 ]的x，是n[n[n[i]]]；到研究对象长度为1时，结束
  • next数组优化—nextval：next数组本质目的是记录比对失败时下一次比对主串和模式串的游标位置，暴力是i+1与0（i为此次比对起始在主串中的索引），next数组改进为了i+j与n[j]（j为此次匹配成功的长度）——再多想一步：比较模式串str[j]与str[n[j]]，若同（这也是生成next时直接n[j]=n[j-1]+1的条件，二者差为1也可以当作判断相同的条件（因为nextval是使用next生成的）），则下次匹配还是不成功，按目的看，n[j]可直接修改为n[n[j]]—因为nextval的所有位置的元素都有递归寻找一步的性质，则从0开始增长时，如果用nextval[j]=nv[nv[j]]（而不是n[n[j]]），可以一直递归到最底层，所以nextval就用了这种算法生成；

数组

• 集合（而不是线性表）；随机访问，直接访问；顺序存储，索引=指针（映射）；作为存储结构时，=顺序存储结构
• {base，dim，bounds，cis（用于寻址）}

特殊矩阵的压缩存储

• 稀疏矩阵：三元组线性表／行逻辑链接顺序表

三元组：

• 快速转置：M—T：instead of 行列遍历：遍历线性表，只需每次转置后确定其在T中的位置即可：两个辅助数组：num[col], cpot[col]，每列元素个数与该列元素转置后在T中开始存放的位置（列转为行，行优先排序，则他们连续，只需记一个总体起始位置）

• 生成算法：num通过遍历M计数，cpot[col]通过cpot[col-1]+num[clo-1]得出
• 使用方法（总体算法）：遍历M，每次确定col，转置，T中位置=cpot[col]，每次cpot[col]使用后自增

行逻辑链接顺序表：

• 快速相乘
• 相乘的关键时快速的存取：三元组的基础上加一个数组，记录每一行第一个非零元的在三元组中的位置，rpos

MxN=Q

• 三元表中矩阵最佳扫描方式：确定行后遍历列（行相同序数连续），而加了rpos数组的矩阵就更好定位

• 计算过程如下：
  // 1. 以M进行逐行的扫描。
  // 2. 使Q的此行逻辑表的序号等于其非零元个数Q.tu+1，以表示其行的首个元素的序号。
  // 3. 从行中找到M的非零元，并以它的列值为N的行号，对N进列列的扫描，依次计算它们，存在数组ctemp[ccol]中的不同各种，每次行确定后列遍历一遍，ctemp就各列累加更新一遍
  // 4. 在M的当前行完成扫描后，将ctemp[ccol]不为0的值，就是Q这行的非零元，压入到Q矩阵的三元组，累加++Q.tu，

• 复杂度是mn+tu1(tu2/m2)（就是平均的列数）

十字链表存储：若非零元的个数和位置在操作中变化较大

• node{row，col，rownext（right），colnext（down），value}

• 行列各成循环链表

• 十字链表相比三元组的优越性：处理矩阵加：
  - 三元组：线性表有序合并：滑动窗口：始末，作用主体
  - 十字链表：：本质也是滑动窗口，是一个每次对比判断的循环主体，一次一步，其实很繁琐

• 分析：十字链表强在定位和增删，定位是十字带来的，增删是链表带来的（如果三元组也是链表实现，那十字链表的唯一优越性就是定位）。一维结构的定位自然没有二维便利……