线性表说明

1. 一般线性表:也就是操作不受限、元素不受限的线性表
2. 操作受限的线性表：栈、队列
3. 元素受限的线性表：串
4. 一般线性表的实现

#include<stdio.h>
#define NodeType char
// 链表节点定义
typedef struct LinkedList{
   NodeType data;
   struct LinkedList* next;
}LinkedList;
// 创建一个链表
void CreateLinkedList(LinkedList* list){
  if(list==NULL)
    list = (LinkedList*)malloc(sizeof(LinkedList));
  LinkedList* point = list;
  while(c=getchar()!='#')
  {
     LinkedList* node = (LinkedList*)malloc(sizeof(LinkedList));
     point ->next = node;
     node->next = NULL;
     point = node;
  }
}

5. 栈：先进后出的线性表。只允许在栈顶操作数据
6. 前中后缀表达式

前缀计算：

1. 从右到左扫描中缀表达式，构建一个数据栈一个操作符栈
2. 遇到数据就压入数据栈，遇到操作符开始比对。如果当前操作符等级大于等于操作符栈顶元素。那么就入栈。如果小于栈顶操作符等级。那就从数据栈中弹出两个数据进行运算。运算结果压回数据栈
3. 当表达式全部读取完且两个栈空，说明前缀表达式计算完毕。数据栈顶元素为表达式值

后缀计算：

1. 从左到右扫描中缀表达式，构建一个数据栈一个操作符栈
2. 遇到数据就压入数据栈，遇到操作符开始比对。如果当前操作符等级大于等于操作符栈顶元素。那么就入栈。如果小于栈顶操作符等级。那就从数据栈中弹出两个数据进行运算。运算结果压回数据栈
3. 当表达式全部读取完且两个栈空，说明前缀表达式计算完毕。数据栈顶元素为表达式值

中缀表达式生成前后缀表达式：表达式树

中缀生成前缀表达式：中缀表达式生成表达式树。前序遍历生成树就是前缀表达式
中缀生成后缀表达式：中缀表达式生成表达式树。后序遍历生成树就是后缀表达式

后缀表达式生成中缀表达式：

1. 从左往右扫描后缀表达式，遇到操作数就压入栈中，遇到操作符就从栈中弹出两个数，与操作符组成一棵树
2. 进行中序遍历就是中缀表达式

前缀表达式生成中缀表达式：

1. 从右往左扫描后缀表达式，遇到操作数就压入栈中，遇到操作符就从栈中弹出两个数，与操作符组成一棵树
2. 进行中序遍历就是中缀表达式

利用两个栈模拟一个队列：A栈负责入队操作，A栈出栈元素入B栈。然后B栈出栈模拟出队列

栈解决的问题有：子程序调用、递归

队列：先进先出的线性表
队空：front＝＝rear
队满： (rear+1) mod maxsize ==front
队中元素个数n＝（rear-front+maxsize )mod maxsize
入队：rear=(rear+1) % maxsize ;
出队：front=(front+1) % maxsize ;

串：

1. 模式匹配：求子串在主串中的首地址
2. 模式匹配算法：当（0,k-1）不是子串时，那么就找(1,k)的元素。直到(n-k+1,n)
3. KMP算法：利用已经匹配完的元素确定下一次匹配该0去的位置
   1. 当主串与模式串进行第一次匹配之后发现不匹配，那么就会去找下一个长度为K的子串进行匹配。但是如果该子串与模式串的首元素就不同， 那么就无需比较，直接下一个。所以在我们找到一个可以进行匹配操作的子串时我们进行了很多不必要的操作。那么整个核心就转为了找到一个可以进行对比的子串位置。
      转化：每个长度为K的子串都进行匹配—>只匹配首元素与模式串匹配的子串
      但如何得知主串中元素与首元素相同的元素位置呢？
   2. 利用已经匹配过的数据去了解主串的信息。因为我们进行匹配的时候是直到第m个元素才知道整个长度为K的串不匹配的。也就是当匹配失败的时候我们已经知道了0–m-1个元素是匹配的。也就是主串与模式串的元素相同。如果此时这m个元素中存在与首元素相同的元素，那么我们是不是就知道了下一个该滑动到哪个地方去进行匹配呢？
      转化：利用已经匹配的模式串元素与主串元素相同的信息去了解主串的信息
   3. 那么如何得知模式串的哪些元素与首元素是相同的呢？–>对模式串进行匹配。对模式串进行遍历，假设point指向当前出现不匹配的元素。那么我们就需要对其【0–point-1】的元素进行判断。找元素与首元素相同的位置。
      转化：尽可能多的找相同
   4. 对于第3个操作中，我们既然已经知道了首元素匹配的位置，为什么不一起把剩下元素是否匹配的情况也找出来呢？因为如果只有首元素匹配，第二个元素又不匹配是不是就白忙活一场了？依次类推只要有一个元素不匹配，那么我们之前找到的那些相同元素就是白费了。那么我们干脆对整个【0,point-1】元素列表中前后进行匹配。也就是只要这些元素前缀与后缀相同的情况。
      转化：结果记录
   5. 我们把point从0到n都走一步，记录下每次前后缀匹配的个数。保存在一个数组内next[n]
   6. 整体思路：模式串T与主串S进行匹配，s_i指向当前进行对比的主串元素，t_i指向当前进行对比的模式串元素。当执行到第K个遇到不匹配的时候。我们需要知道此时我们该划去哪里才是当前的最优位置。因为Next数组内保存着[0,k-1]列表中前后缀匹配的个数。把这个数取出来。因为k-next[k]的元素一定是匹配的，因为前后next[k]个元素相同。那么我们直接从T的第next+1个元素与S的第k+1个元素进行比较。
      0010 0010 0010 1100 0010 0000 与 0010 0010 1100进行模式匹配
      当遇到第k=9个元素的时候发生不匹配。那么去next数组里找next[9] = 4。
      那么对比继续，用T的T[4+1]元素与S的k也就是S[9]进行比较。因为既然主串前8个元素中前4个与后4个元素相同。那么第二次匹配的时候，直接从主串的第5个元素开始与模式串进行匹配。但是又知道前4个一定相同。那么就直接模式串T从第next[k]+1个元素去与S的k+1个元素比较。