数据结构-串、数组和广义表

串

串是内容受限的线性表（规定其内容只能是字符）。
（1）串：零个或多个任意字符组成的有限序列。
（2）子串：一个串中任意个连续字符组成的子序列（含空串）称为该串的子串。真子串是不包含自身的所有子串。
（3）子串位置：子串第一个字符在主串中的位置。
（4）串相等：当且仅当这两个串的长度相等并各个对应位置上的字符都相同时，这两个串才相等。所有空串都相等。
串也可分为链式存储结构（链串）和顺序存储结构（顺序串）。
串的顺序存储结构：元素的逻辑关系直接映射到存储位置，由逻辑关系的先后直接影响到存储位置的先后。

// 伪代码实现
#define MAXLEN 255
typedef struct{
  char ch[MAXLEN + 1]; // 存储串的一维数组（下标为0~255）
  int length;  // 串的当前长度
}SString // 将定义的串声明成SString这个名字

串的链式存储结构
（1）优点：操作方便；缺点：存储密度较低
（2）可以将多个字符存放在一个结点，以克服其缺点，即块链结构。

// 块链结构伪代码实现
#define CHUNKSIZE 80 // 块的大小可由用户定义
typedef struct Chunk{
  char ch[CHUNKSIZE];
  struct Chunk *next;
}Chunk;

typedef struct{
  Chunk *head,*tail; // 串的头指针和尾指针
  int curlen; // 串的当前长度
}LString; // 字符串的块链结构

由于实际情况中对串进行匹配、查找等操作较多，因此顺序串应用比较普遍。
串的模式匹配算法——BF算法
（1）模式匹配算法定义：确定主串中所含子串（模式串）第一次出现的位置（定位）。
（2）i为主串的指针，j为模式串指针。匹配失败：i=i-j+2（回溯），j=1（从头开始）；匹配成功：返回i-t.length。
（3）Index(S,T,pos)算法设计思想：将主串的第pos个字符和模式串的第一个字符比较，若相等，则继续逐个比较后续字符，若不相等，则从主串的下一字符开始，重新与模式串的第一个字符比较。直到主串的第一个连续子串字符与模式串相等，则返回值为S中与T匹配的子序列的第一个字符的序号，即匹配成功。否则匹配失败，返回值0。
（4）BF算法描述：

// 主串从pos位置开始匹配模式串
int Index_BF(SString S, SString T,int pos){
  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; // 模式匹配不成功
}

（5）算法时间复杂度
若n为主串长度，m为子串长度，算法复杂度为O(n*m)。

串的模式匹配算法——KMP算法
（1）优点：主串i的指针i不必回溯，使算法复杂度降低到O(n+m)。
（2）定义next[j]函数，表明当模式中第j个字符与主串中相应字符失配时，需要和主串中重新匹配的字符的位置。
其中next[j]的取值情况如下图：

image.png

（3）KMP算法描述

// KMP算法描述
int Index_KMP(SString S, SString T, int pos) {
  i=pos,j=1;
  while(i<=S.length && j<T.length) {
      if(j==0||s.ch[i]==t.ch[j]) {++i; ++j;} // 与BF一样，主串、子串依次匹配下一个字符
      else
          j=next[j];  // i不变，j后退，后退的值为用上图方法所求的next[j]
    }
  if(j>T.length) return i-T.length; // 匹配成功
   else return 0; // 匹配不成功返回0
}

（4）next函数的改进

image.png

数组

定义：
（1）数组：具有相同类型的数据元素按一定格式排列起来。
（2）一维数组：若线性表中的数据元素为非结构的简单元素，则成为一维数组。一维数组是定长的线性表。
（3） n维数组：若n-1维数组中的元素又是一个一维数组，则称作n维数组。
（4）结论：线性表结构是数组结构的一个特例，而数组结构又是线性表结构的扩展。
数组的顺序存储
（1）结构固定——维数和维界不变，一般不做插入和删除操作，故一般采用顺序存储结构来表示。
（2）二维数组的存储位置表示
以行列为主序：设数组开始存储位置LOC(0,0)，每行有n个元素，存储每个元素需要L个存储单元。则数组元素a[i][j]的存储位置是：LOC(i,j)=LOC(0,0)+(ni+j)L。
（3）n维数组的存储位置表示

image.png
特殊矩阵的压缩存储
（1）将矩阵描述为一个二维数组，可以对其进行随机存取，且存储的密度为1。但常规方法不适合某种特殊矩阵，比如有很多元素值相等的矩阵等。
（2）定义：
压缩矩阵：若多个数据元素的值都相等，则只分配一个元素值的存储空间，且零元素不占存储空间。
稀疏矩阵：矩阵中零元素的个数较少（一般小于5%）
（3）对称矩阵存储方法
①只存储下（上）三角（包括主对角线）的数据元素。共占用n(n+1)/2个元素空间。（元素空间用等差数列求和运算）
②以行序为主序将元素存放在一个一维数组SA[n(n+1)/2]中。

image.png

（4）三角矩阵存储方法
①三角矩阵定义：对角线以下（或者以上）的数据元素（不包括对角线）全部为常数C。
②存储方法：重复元素C共享一个元素存储空间，共占用n(n+1)/2+1个元素空间。

image.png

（5）对角矩阵存储方法
①对角矩阵定义：在n x n的方阵中，