1.表

1.1 线性表

线性表的特点是

· 表中元素个数有限

· 元素具有逻辑上的顺序性

· 表中元素的数据类型相同（即每个元素具有相同存储空间）

· 线性表是一种逻辑结构

· 线性表有9中操作：初始化空表； 销毁； 按值查找；按位查找；插入（前插）；删除（删除i位置元素并返回删除的元素值）；输出；判空；求表长

线性表 按 存储结构 分为链表和顺序表
其中python中list和tuple用的是顺序表.

这是C语言版的，写一点后面的就不写了

    #include<stdio.h>
    #include<stdlib.h>
    typedef int ElemType;       //定义元素类型
    struct List{
    ElemType *list;         //存储空间基址
    int size;               //当前长度
    int MaxSize;            //当前分配的存储容量，即存储线性表的最大长度
    };
    
    //1、初始化线性表L，即进行动态存储空间分配并置L为一个空表(分配一个固定的list)
    void init_list(struct List *L, int ms)
    {
        printf("线性表正在初始化!\n");
        if (ms < 0) //检查ms是否有效
        {
            printf("ms值非法！\n");
            exit(1);
        }
        L->MaxSize = ms; //置线性表初始存储容量为ms
        // malloc分配的内存大小至少为参数所指定的字节数
        L->list = (ElemType *)malloc(ms*sizeof(ElemType)); //动态存储空间分配
        if (!L->list)
        {
            printf("动态存储分配失败！\n");
            exit(1);
        }
        L->size = 0; //初始置线性表为空
    }
    
    //2、清除线性表L中的所有元素，释放动态存储空间，使之成为一个空表
    void clear_list(struct List *L)
    {
        printf("线性表释放动态存储空间!\n");
        if (L->list != NULL)
        {
            free(L->list);
            L->list = 0;  // 将内存块释放掉
            L->size = L->MaxSize = 0;
        }
    }

1.2 顺序表

顺序表的元素是逻辑地址相邻，物理地址也相邻，且每个元素的物理内存相同（只能存放同一种数据对象）。每个元素存放数据和当前的表长度
python 的 list tuple是顺序表

1.3 单链表

单链表的元素逻辑地址相邻，物理地址不一定相邻，是任意存放在物理地址上的。每个元素存放数据本身和下一个数据元素的地址

1.4 栈

只允许在一端进行插入或删除操作的线性表，定义能插入删除的一端是顶部。
栈是后进先出的数据结构
栈的实现是有一个指向栈顶的指针，即top指针始终指向最新进栈的元素。

S.top = -1就是空栈；栈长S.top+1；栈满条件S.top == MaxSize-1（S.top指向数组，数组从0开始，栈从1开始）

1.5 队列

只允许在表的一端进行插入，另一端进行删除的线性表，队头进行删除，队尾进行插入。

出队：删除队头元素；入队：队尾进行插入元素

1.6 栈与队列的应用

1. 栈的应用：括号匹配问题
   对于一组括号[{[][]]，
   设置一个栈，然后将括号按顺序入栈，若遇到匹配括号，则弹出；遍历完括号列表，若为空栈，则是匹配的括号。

2 串

1. 两个串长度相同且对应位置都相等则是相等的串
2. 字符串结尾处有个/0表示字符串的结束
3. 串的存储结构，定长存储，即划分连续的存储空间只能存储定长；
   堆分配存储，即动态申请与释放空间，需要用到malloc和free函数；
   块链存储，即可以在每个链中存放多个字符
   4.基本操作：赋值，比较，求串长，求子串

2.1 简单的模式匹配算法

匹配定长的子串，lenth是子串长度。即初始化di=0， dj=0+lenth；然后在字符串上逐个遍历，直到找到。

2.2 KMP算法

两个指针di=0 dj=0.di指向串头，dj指向子串头，lenth是子串长度；
开始遍历，若di的字符与dj的字符相同，di+=1 dj+=1；
若出现不等，则di += 1 dj=0；
若dj = lenth-1 则成功匹配。若di遍历完，dj != lenth-1，则匹配失败。

3 树

3.1 二叉树

常用的二叉树存储结构：

1.顺序存储

顺序存储是用一个数组对二叉树每个节点的元素依次进行存储，其中。

这种存储方式适合完全二叉树，因为如果是非完全二叉树的话，比较浪费存储空间。

2.连输存储

这种存储就是创建一个节点类，有个左孩子有个右孩子，分别指向他们的指针域

3.二叉树的遍历

前序
先访问父节点，再左子树右子树

中序
先访问左子树再访问父节点，再访问右子树

后序
先访问左子树再右子树，再访问父节点

4.查找

4.1顺序查找

按照顺序进行查找

4.2折半查找

折半查找 仅适用于有序的顺序表

4.3B树

又叫多叉平衡查找树

1.若根结点不是叶子结点，则 2 <= 根结点的孩子数 <= m；（根结点至少包含一个关键字）

2.除根结点和叶子结点外，ceil(m/2) <= 其它结点的孩子数 <= m，其包含的关键字数 = 它的孩子数-1；（ceil(x)：返回大于或者等于x的最小整数）

3.所有叶子结点都出现在同一层，ceil(m/2)-1 <= 结点包含的关键字数目 <= m - 1；
每个结点中的关键字从小到大排列，并且非叶子结点的k-1个关键字，正好是它k个孩子包含的关键字的值域分划（即，父结点中的第i个关键字（如果存在的话） < 第i个孩子中的所有关键字 < 父结点中的第i+1个关键字（如果存在的话）。