线性表

线性表的程序示意

动态调配

#define MaxSize 10 // 定义最大长度 

typedef struct {int data[MaxSize]; // ElemType = int, * 用动态的“数组”存访数据元素 
    int length; // 程序表的以后长度 
} SqList;

动态分配

#define InitSize 10 // 程序表的初始长度
typedef struct {
    int * data; // ElemType = int, * 申明动态分配数组的指针 
    int MaxSize; // 程序表的最大容量
    int length; // 程序表的以后长度 
} SqList;

// 初始化程序表 
void InitList(SqList &L) {
    // 用 malloc 函数申请一片间断的存储空间 
    L.data = (int *)malloc(InitSize * sizeof(int));
    L.length = 0;
    L.MaxSize = InitSize;
}

特点：

• 可随机拜访，查找元素所需工夫复杂度为 O(1)。
• 存储密度高，每个节点只存储数据元素。
• 拓展容量不不便（即便应用动态分配的形式实现，拓展长度的工夫复杂度也比拟高，因为须要把数据复制到新的区域）。
• 插入删除操作不不便，需挪动大量元素：O(n)。

线性表的链式示意

单链表

struct LNode{            // 定义单链表节点类型  LNode: 结点
    ElemType data;       // 每个结点寄存一个数据元素 data: 数据域
    struct LNode *next;  // 指针指向下一个结点 next: 指针域
};

双链表

typedef struct DNode{            // 定义双链表结点类型
    ElemType data;               // 数据域
    struct DNode *prior, *next;  // 前驱和后继指针
}DNode, *DLinklist;

循环单链表

最初一个结点的指针不是 NULL, 而是指向头结点

循环双链表

表头结点的 prior 指向表尾结点，表尾结点的 next 指向头结点

动态链表

#define MaxSize 10        // 动态链表的最大长度

typedef struct{           // 动态链表构造类型的定义
    ELemType data;        // 存储数据元素
    int next;             // 下一个元素的数组下标
}SLinkList[MaxSize];

void testSLinkList(){SLinkList a;}

栈 (stack)

栈是非凡的线性表 ：只容许在一端进行插入或删除操作，其逻辑构造与一般线性表雷同
栈顶：容许进行插入和删除的一端（最下面的为栈顶元素）
栈底：不容许进行插入和删除的一端（最上面的为栈底元素）
空栈：不含任何元素的空表
特点：后进先出（后进栈的元素先出栈）
毛病：栈的大小不可变，解决办法——共享栈

栈的顺序存储

#define MaxSize 10         // 定义栈中元素的最大个数

typedef struct{ElemType data[MaxSize];       // 动态数组寄存栈中元素
    int top;                      // 栈顶元素
}SqStack;

void testStack(){SqStack S;       // 申明一个程序栈(调配空间)
                     // 间断的存储空间大小为 MaxSize*sizeof(ElemType)
}

栈的链式存储构造

因而，链栈实际上就是一个只能采纳头插法插入或删除数据的链表

typedef struct Linknode{
    ElemType data;              // 数据域
    struct Linknode *next;      // 指针域
}*LiStack;                      // 栈类型的定义

利用

• 栈在括号匹配中的利用
• 中断表达式 (须要界线符)
• 后缀表达式 (逆波兰表达式)
• 栈在递归中的利用

队列(Queue)

• 队列是操作受限的 线性表，只容许在一端进行插入 (入队)，另一端进行删除 (出队)
• 操作个性：先进先出 FIFO
• 队头：容许删除的一端
• 队尾：容许插入的一端
• 空队列：不含任何元素的空表

# define MaxSize 10;     // 定义队列中元素的最大个数
typedef struct{ElemType data[MaxSize];   // 用动态数组寄存队列元素
                              // 间断的存储空间，大小为——MaxSize*sizeof(ElemType)
    int front, rear;          // 队头指针和队尾指针
}SqQueue;

• 队头指针：指向队头元素；
• 队尾指针：指向队尾元素的后一个地位（下一个应该插入的地位）

循环队列（判满）

计划一: 就义一个单元来辨别队空和队满

队尾指针的再下一个地位就是队头，即 (Q.rear+1)%MaxSize == Q.front

• 循环队列——入队：只能从队尾插入（判满应用计划一）

bool EnQueue(SqQueue &Q, ElemType x){if((Q.rear+1)%MaxSize == Q.front)        // 队满
        return false;
    Q.data[Q.rear] = x;                      // 将 x 插入队尾
    Q.rear = (Q.rear + 1) % MaxSize;         // 队尾指针加 1 取模

    return true;
}

• 循环队列——出队：只能让队头元素出队

// 出队，删除一个队头元素，用 x 返回
bool DeQueue(SqQueue &Q, ElemType &x){if(Q.rear == Q.front)              // 队空报错
        return false;  

    x = Q.data[Q.front];
    Q.front = (Q.front + 1) % MaxSize; // 队头指针后挪动

    return true;
}

• 循环队列——取得队头元素

bool GetHead(SqQueue &Q, ElemType &x){if(Q.rear == Q.front)              // 队空报错
        return false;  

    x = Q.data[Q.front];
    return true;
}

计划二: 不就义存储空间，设置 size

定义一个变量 size用于记录队列此时记录了几个数据元素，初始化 size = 0，进队胜利 size++，出队胜利size--，依据 size 的值判断队满与队空

队满条件：size == MaxSize

队空条件：size == 0

计划三: 不就义存储空间，设置 tag

定义一个变量 tag，tag = 0 – 最近进行的是删除操作；tag = 1 – 最近进行的是插入操作；

每次删除操作胜利时，都令 tag = 0；只有删除操作，才可能导致队空；
每次插入操作胜利时，都令 tag = 1；只有插入操作，才可能导致队满；

队满条件：Q.front == Q.rear && tag == 1

队空条件：Q.front == Q.rear && tag == 0

队列的链式存储构造

typedef struct LinkNode{      // 链式队列结点
    ElemType data;
    struct LinkNode *next;
}

typedef struct{               // 链式队列
    LinkNode *front, *rear;   // 队列的队头和队尾指针
}LinkQueue;

双端队列

• 双端队列容许从 两端插入 、 两端删除 的线性表；
• 如果只应用其中一端的插入、删除操作，则等同于栈；
• 输出受限的双端队列：容许 一端插入 ， 两端删除 的线性表；
• 输入受限的双端队列：容许 两端插入 ， 一端删除 的线性表；

串

程序表

#define MAXLEN 255   // 预约义最大串长为 255

typedef struct{char ch[MAXLEN];   // 动态数组实现（定长顺序存储）// 每个重量存储一个字符
                       // 每个 char 字符占 1B
    int length;        // 串的理论长度
}SString;

堆调配

// 动静数组实现
typedef struct{
    char *ch;           // 按串长调配存储区，ch 指向串的基地址
    int length;         // 串的长度
}HString;

HString S；S.ch = (char *) malloc(MAXLINE * sizeof(char)); // 基地址指针指向间断空间的起始地位
                                                //malloc()须要手动 free()
S.length;

链式存储

typedef struct StringNode{
    char ch;           // 每个结点存 1 个字符
    struct StringNode *next;
}StringNode, * String;

树

顺序存储

#define MaxSize 100

struct TreeNode{
   ElemType value; // 结点中的数据元素
   bool isEmpty;   // 结点是否为空
}

链式存储

// 二叉树的结点

struct ElemType{int value;};

typedef struct BiTnode{
   ElemType data;          // 数据域
   struct BiTNode *lchild, *rchild; // 左、右孩子指针
}BiTNode, *BiTree;

计算机科学中的树

二叉查找树

中序有序

笛卡尔树

范畴 最值 查问与最低公共先人（间隔两个节点最近的独特先人）

AVL 树

实质上还是一棵二叉搜寻树，它的特点是：

1. 自身首先是一棵二叉搜寻树。

2. 带有 平衡条件：每个结点的左右子树的高度之差的绝对值（均衡因子）最多为 1。

也就是说，AVL 树，实质上是带了 均衡性能的二叉查找树（二叉排序树，二叉搜寻树）。

红黑树

是一种特化的 AVL 树 ，它能够在 O(log n) 工夫内做查找，插入和删除

在二叉查找树强制个别要求以外，对于任何无效的红黑树咱们减少了如下的额定要求:

性质 1. 结点是红色或彩色。

性质 2. 根结点是彩色。

性质 3. 所有叶子都是彩色。（叶子是 NIL 结点）

性质 4. 每个红色结点的两个子结点都是彩色。（从每个叶子到根的所有门路上不能有两个间断的红色结点）

性质 5. 从任一节结点其每个叶子的所有门路都蕴含雷同数目的彩色结点。

这些束缚强制了红黑树的要害性质:

从根到叶子的最长的可能门路不多于最短的可能门路的两倍长。

后果是这个树大抵上是均衡的。因为操作比方插入、删除和查找某个值的最坏状况工夫都要求与树的高度成比例。

这个在高度上的实践下限容许红黑树在最坏状况下都是 高效 的，而不同于一般的二叉查找树。

B 树（B-）

而 B - 树查问工夫复杂度 不固定，与 key 在树中的地位无关，最好为 O(1)。

B- 树，这里的 B 示意 balance(均衡的意思)，B- 树是一种 多路 自均衡的搜寻树

B- 树有如下特点:

1. 所有键值散布在整颗树中（索引值和具体 data 都在每个节点里）；
2. 任何一个关键字呈现且只呈现在一个结点中；
3. 搜寻有可能在非叶子结点完结（最好状况 O(1)就能找到数据）；
4. 在关键字选集内做一次查找, 性能迫近二分查找；

B- 树是专门为内部存储器设计的，如磁盘，它对于读取和写入大块数据有良好的性能，所以个别被用在文件系统及数据库中。

B+ 树

工夫复杂度 固定 为 log n

算法

冒泡排序

对一个列表多次重复遍历。它要比拟相邻的两项，并且替换程序

抉择排序

每遍历一次列表只替换一次数据将它换到正确的地位。

一共须要 n-1 次 遍从来排好 n 个数据。

插入排序

每一个新的数据项被 插入 到前边的子表里

希尔排序

放大距离排序

它以 插入排序 为根底，将原来要排序的列表划分为一些子列表，再对每一个子列表执行插入排序。

归并排序

把两个排序好了的列表联合在一起组合成一个繁多的有序的新列表

归并排序是一种 递归算法，它继续地将一个列表分成两半

如果列表是空的或者 只有一个元素，那么依据定义，它就被排序好了（最根本的状况）

如果列表里的元素超过一个，咱们就把列表拆分，而后别离对两个局部调用递归排序。

<img src=”https://pic3.zhimg.com/v2-cdda3f11c6efbc01577f5c29a9066772_b.webp” style=”zoom: 100%” />

疾速排序

基数排序

堆排序

参考链接

B+ 树和 B 树的区别 – 简书 (jianshu.com)