1、串

KaTeX parse error: Undefined control sequence: \qquadd at position 1: \̲q̲q̲u̲a̲d̲d̲串(string)是零个或者多个任意字符组成的有限序列。

子串：一个串中任意个连续字符组成的子序列(含空串)称为该串的子串。

真子串：指不包含自身的所有子串。

主串：包含子串的串相应地称为主串。

字符位置：字符在序列中的序号为该字符在串中的位置。

子串位置：子串第一个字符在主串中的位置。

空格串：有一个或者多个空格组成的串，与空串不同。

串相等：当且仅当两个串的长度相等，并且各个对应位置上的字符都相同时，这两个串才是相等的。所有的空串都是相等的。

串的应用非常广泛，计算机上的非数值处理的对象大部分是字符串数据，例如：文字编辑，符号处理，各种信息处理系统等。字符串匹配等。

1.1 串的类型定义，存储结构及运算

串的抽象数据类型定义如下所示：

串中元素逻辑关系与线性表的相同，串可以采用与线性表相同的存储结构。串可以使用顺序存储结构或者链式存储结构来实现。

1.1.1 串的顺序存储结构

串的顺序存储结构

#define MAXLEN 255
class SString
{
  char ch[MAXLEN+1];  //存储串的一维数组
  int length;     //串的当前长度
};

串的链式存储结构

在进行串的链式存储时，可以多个字符放在一个结点中，克服链式存储存储密度低的缺点。

#define CHUNKSIZE 80
class Chunk
{//块链中的块定义
  char ch[CHUNKSIZE];
  Chunk *next;
};
class LString
{
  Chunk *head, *tail; //串的头指针和尾指针
  int curLen;     //串的当前长度  
};

1.1.2 串的模式匹配算法

算法目的： 确定主串中所含的子串(模式串)第一次出现的位置(定位)。

算法应用： 搜索引擎，拼写检查，语言翻译，数据压缩等

算法种类：

BF算法(Brute-Force)，又称古典的，经典的，朴素的，穷举的，即暴力破解法 \qquad KMP算法，算法速度快，但是逻辑较复杂

1.1.2.1 BF算法

BF算法的思路为穷举思路，算法从主串的每一个字符开始依次与子串的字符进行匹配，直到匹配到子串或者主串结束为止。

int Index_BF(SString S, SString T, int pos = 1)
{
  int i = pos,  j = 1;  //假设字符串第一个字符不放置元素
  while(i < S.length && j < T.length)
  {
    if(S.ch[i] == T.ch[j]){++i;++j}
    else
    {//主串回溯到下一个为止，子串置为初始位置
      i = i - j + 2;
      j = 1;
    }
    if(j >= T.length) return i - T.length;
    else return 0;
  }
}

BF算法的时间复杂度：

假设主串长度为n，子串长度为m，则最好情况下需要比较m次，即主串第一个子串即为目标子串 O(m)；最坏情况下，主串最后一个子串才为目标子串，则前面n-m各个主串元素均需要比较m次，则O(m∗(n−m)+m)，若m<<n，则算法的时间复杂度为：O(n∗m)。

1.1.2.2 KMP算法

KMP算法时由D.E.Knuth，J.H.Morris和V.R.Pratt共同提出的，简称KMP算法。该算法较BF算法有较大的改进，从而使算法效率有较大提高。

KMP算法的设计思想： 利用已经部分匹配的结果来加快模式串的滑动速度，并且主串S的指针i不需要回溯，子串T中的指针j可以不回到初始位置，可以提速到 O(m+n)。

为了衡量子串T中的指针j回到的位置，定义一个next[j]函数，表名当模式中的第j个字符与珠串中相应字符“失配”时，在模式中需要重新确定和主串中该字符进行比较的字符的位置。

next的例子如下图所示：

使用next[j]表的KMP算法如下所示：

int Index_KMP(SString S, SString T, int pos = 1)
{
  i = pos, j = 1;
  while(i < S.length && j < T.length)
  {
    if(j==0 || S.ch[i] == T.ch[j]){++i;++j}
    else
      j = next[j];    //i的位置不变
  }
  if(j >= T.length) return i - T.lenght;  //匹配成功
  else return 0;              //匹配失败
}
//获取next[j]
void Get_next(SString T, int &next[])
{
  int i = 1, j = 0;
  next[1]=0;
  while(i < T.length)
  {
    if(j == 0 || T.ch[i]==T.ch[j])
    {
      ++i; ++j;
      next[i]=j;  
    }
    else
      j = next[j];
  }
}

next的值还可以进行一定的修正，修正方法如下所示：

修正版求next值的代码如下所示：

void Get_next(SString T, int &nextVal[])
{
  int i = 1, j = 0;
  nextVal[1]=0;
  while(i < T.length)
  {
    if(j == 0 || T.ch[i]==T.ch[j])
    {
      ++i; ++j;
      if(T.ch[i]!=T.ch[j])nextVal[i]=j;
      else nextVal[i]=nextVal[j];
      nextVal[i]=j; 
    }
    else
      j = nextVal[j];
  }
}

2、数组

按照一定格式排列起来的，具有相同类型的数据元素的集合。

一维数组：若线性表中的数据元素为非结构的简单元素，则称为一维数组；一维数组的逻辑结构为线性结构，是一个定长的线性表。

声明格式： 数据类型，变量名称[长度]

int num[5] = {0,1,2,3,4};

二维数组： 若一维数组中的数据元素又是一维数据结构，则称为二维数组。

声明格式： 数据类型 变量名称[行数][列数]

int num[5][8];

三维数组： 若二维数组中的元素又是一个一维数组，则称作三维数组；

n维数组： 若n-1维数组中的元素又是一个一维数组结构，则称为n为数组。

线性表结构是数组结构的一个特例，而数组结构又是线性表结构的拓展。 数组特点 是结构固定，定义后，维数和维界不再改变。

数组的基本操作：除了结构的初始化和销毁外，只有取元素和修改元素值的操作。

2.1 数组的抽象数据类型定义

 以二维数组为例，定义数组的抽象数据类型：

2.2 数组的顺序存储结构

由于数组的结构固定，维数和维界不变，所以数组一般都是采用顺序存储结构的。数组可以是多维的，但存储数据元素的内存单元地址是一维的，因此，在存储数组结构之前，需要解决将多维关系映射到一维关系的问题。

2.2.1 二维数组

二维数组可以有两种顺序存储方式，一种是以行序为主体，低下标优先进行存储(C和Java中使用这种存储方式)；另外一种是以列序为主体，高下标优先进行存储。

以行序为主序，设数组开始存储的位置为LOC(0,0)，数组每行有n个元素，存储每个元素需要 L L L个存储单元，数组元素  a[i][j]的存储为止为： Loc(i,j)=Loc(0,0)+(i∗n+j)∗L。

2.2.2 三维数组

三维数组可以按页/行/列进行存放，页优先的顺序存储，每一页在按照行优先的顺序进行存储。如三维数组  a[m1][m2][m3]各维的元素个数为：  m1,m2,m3，则 a[i1][i2][i3]元素的存储位置为：Loc(i1,i2,i3)=a+i1∗m2∗m3+i2∗m3+i3。

2.2.3 n维数组

2.3 特殊矩阵的压缩存储

矩阵： 表示一个由 m×n个元素排成m行n列的表；矩阵的常规存储：将矩阵描述为一个二维数组，矩阵常规存储可以对其元素进行随机存取，矩阵运算非常简单，存储的密度为1。不适宜常规存储的矩阵：值相同的元素很多且呈现某种规律分布；零元素特别多。矩阵的压缩存储：为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。

特殊矩阵的例子：如对称矩阵，对角矩阵，三角矩阵，稀疏矩阵等。稀疏矩阵指：矩阵中非零元素的个数较少，一般小于5%。

2.3.1 对称矩阵

特点：在n×n的矩阵a中，满足如下性质： aij=aji(1≤i,j≤n)。对称矩阵的存储方法为：只存储下三角(包括主对角线)的数据元素。共占用 n(n+1)/2个元素空间。

对称矩阵中某个元素 ai,j的存储位置为： Loc(0,0)+(2i(i−1)+j)∗L，其中 L L L表示每一个元素所占用的内存空间。

2.3.2 三角矩阵

特点：对角线以下(或者以上)的数据元素(不包括对角线)全部为常数c。

存储方法：重复元素c共享一个元素存储单元，共占用 n(n+1)/2+1个元素空间。

2.3.3 对角矩阵

特点：在n×n的方阵中，所有非零元素都集中在以主对角线为中心的带状区域中，区域外的值全为0，则称为对角矩阵。常见的有三对角矩阵，五对角矩阵和七对角矩阵。

存储方法为：以对角线的顺序进行存储，如下所示：

2.3.4 稀疏矩阵的存储

设在m×n的矩阵中有t个非零元素，令 δ = t / ( m ∗ n ) \delta=t/(m*n) δ=t/(m∗n)，当 t ≤ 0.05 t \leq 0.05 t≤0.05时，称为稀疏矩阵。

2.3.4.1 三元组法

可以使用三元组法来存储稀疏矩阵，三元组 < i , j , a i , j > <i,j,a_{i,j}> <i,j,ai,j>来表示元素所在的行索引，列索引和元素值，之后还需要记录矩阵的总共和行数和列数和矩阵中总共元素的个数。三元组的不同表示方法可以决定稀疏矩阵不同的压缩存储方法。

三元组法又称为有序的双下标法，其优点是：非零元素在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算；其缺点是：不能随机存取。若按照行号存取某一行中的非零元，则需从头开始进行查找。

2.3.4.2 十字链表法

十字链表法的优点是：他能够灵活地插入因为运算而产生的新的非零元素，删除因运算而产生的新的零元素，实现矩阵的各种运算。

在十字链表中，矩阵的每一个非零元素用一个结点表示，该节点的成员包括：行索引，列索引，元素值，链接同一行中下一个非零元素的指针，链接同一列中下一个非零元素的指针，十字链表的结点结构示意图如下所示：

十字链表法的实现还需要一个行的头指针，指向每一行中第一个非零元素；一个列的头指针，指向每一列中第一个非零元素。

3、 广义表

广义表是 n ≥ 0 n \geq0 n≥0个元素 a 0 , a 1 , . . . , a n − 1 a_0,a_1,...,a_{n-1} a0,a1,...,an−1的有限序列，其中每一个 a i a_i ai或者是原子，或者是一个广义表。

广义表的表头是广义表中的第一个元素；广义表的表尾不是广义表的最后一个元素，而是广义表除表头之外的其余元素组成的子表。

3.1 广义表的性质

广义表中数据元素有相对次序，一个直接前驱和一个直接后继；

广义表的长度定义为最外层所包含的元素的个数，如C=(a,(b,c))是长度为2的广义表；

广义表的深度定义为，该广义表展开之后所包含的括号的重数，原子的深度为0，空表的深度为1；

广义表可以为其他广义表所共享；如上述广义表B就共享广义表A。

广义表可以是一个递归的表，如  F=(a,F)，递归表的长度为2，深度为无穷。

广义表是多层次结构，广义表的元素可以是单元素，也可以是子表，可以用树型结构来形象地进行表示。

3.2 广义表和线性表的区别

广义表可以看成线性表的推广，线性表是广义表的特例。

当二维数组的每行或者每列作为子表处理时，二维数组即为一个广义表；

树和图也可以用广义表来表示；

广义表的结构相当灵活，在某种前提下，特可以兼容线性表，数组，树和有向图等各种常用的数据结构。

3.3 广义表的基本运算

求表头，即非空广义表的第一个元素，可以是一个原子，也可以是一个子表；

求表尾，非空广义表出去表头元素以外其他元素构成的表，表尾一定是一个表。