408-数据结构

2022-11-15 10:14:25 浏览数 (1)

模板

线性表

顺序存储

代码语言：javascript复制
#include "head.h" 

#define OK 1
#define ERROR 0
#define SeqList_SIZE 20
typedef int ElementType;
typedef int Status;

typedef struct SeqList{
    ElementType* data;
    int length;
    int MaxSize;
}SeqList;

Status InitSeqList(SeqList& a){
    ElementType* q;
    a.data = (ElementType*)malloc(SeqList_SIZE * sizeof (ElementType));
    q = a.data;
    a.length = 0;
    a.MaxSize = SeqList_SIZE;
    int i = 0;
    for(i = 0; i < 10; i   )
    {
        *q = i;
        a.length    ;
        q    ;
    }

    return OK;

}

Status CleaSeqList(SeqList& a){
    if(!a.length)
        return ERROR;
    a.length = 0;
    return OK;
}

Status PrintSeqList(SeqList & a){
    if(!a.length)
    {
        printf("SeqList is emptyn");
        return false;
    }
    int i;
    for(i = 0; i < a.length; i   )
        printf("%d ", *(a.data   i)); 

    puts("");
    return OK;

}

Status Add(SeqList& a, int idx, int value){
    if(idx < 1 || idx > a.length)
        return ERROR;
    int i;
    for(i = a.length; i > idx; i --)
        a.data[i] = a.data[i - 1];
    a.length    ; 
    a.data[i] = value;
    return OK;
}

Status Del(SeqList& a, int idx){
    if(idx < 1 || idx > a.length)
        return ERROR;
    int i;
    for(i = idx; i < a.length; i   )
        a.data[i] = a.data[i   1];
    a.length -- ;
    return OK;
}

链式存储

代码语言：javascript复制
#include "head.h"

#define mal_list  (List)malloc(sizeof (struct ListNode))
#define OK 1
#define ERROR 0
typedef int ElementType;
typedef int Status;


typedef struct ListNode{
    ElementType val;
    ListNode* next;
}ListNode, *List;


Status InitList(List& list){

    list = mal_list ;
    list->next = NULL;
    return OK;
}

Status InsertToTail(List& list, int value){
    List p, s;
    p = list;
    while(p->next)
        p = p->next;
    s = mal_list ;
    s->next = NULL;
    s->val = value;
    p->next = s;
    return OK;
}

Status InsertToHead(List& list, int value){
    List p = mal_list ;
    p->val = value;
    p->next = list->next;
    list->next = p;
    
    return OK;
}
Status RemoveIndex(List& list, int idx){
    List p = list;
    while(--idx && p)
        p = p->next;
    if(idx)
        return ERROR;
    List temp = p->next;
    p->next = p->next->next;
    free(temp);
    return OK;
}

Status RemoveValue(List& _list, int value){
    List list = _list;
    while(list->next)
    {
        if(list->next->val == value)
        {
            list->next = list->next->next;
            return OK;
        }
        else 
            list = list->next;
    }

    return ERROR;
}
// 在第idx个点后面插入value
Status Insert(List& list, int idx, int value){
    List p = list;
    while(idx --)
        p = p->next;
    if(idx ^ -1)
        return ERROR;
    List temp = mal_list ;
    temp->val = value;
    temp->next = p->next;
    p->next = temp;
    return OK;
}


Status ReverseList(List& list){
    List a, b, c;
    if(!list->next || !list->next->next)
        return OK;
    a = NULL, b = list->next;
    while(b)
    {
        c = b->next;
        b->next = a;
        a = b; b = c;
    }
    list->next = a;
    return OK;
}

List ReverseListCreateNew(List head){
    if(!head || !head->next)
        return head; 
    List res = ReverseListCreateNew(head->next);
    head->next->next = head; 
    head->next = NULL;
    return res;
}


List CreateList(int* arr, int len){
    List phead, p, s;
    phead = mal_list ;
    phead->next = NULL;
    p = phead;
    int i = 0; 
    for(; i < len; i   )
    {
        s = mal_list ;
        s->next = NULL;
        s->val = *(arr   i);
        p->next = s;
        p = p->next;

    }
    return phead;
}


Status PrintList(List list){
    while(list->next)
    {
        list = list->next;
        printf("%d ", list->val);
    }
    puts("");
    return OK;
}

栈、队列和数组

栈

代码语言：javascript复制
#include "head.h"

#define OK 1
#define ERROR 0
#define SeqStack_SIZE 10
#define SIZE_DELTA 2
const int Inf = 0x3f3f3f3f;
typedef int ElementType;
typedef int Status;

typedef struct SeqStack{
    ElementType* top;
    ElementType* base;
    int size;
}SeqStack; 

Status InitSeqStack(SeqStack& stack){
    stack.base = (ElementType*)malloc(SeqStack_SIZE  * sizeof (ElementType));
    if(!stack.base)
        return ERROR;
    stack.size = SeqStack_SIZE ;
    
    stack.top = stack.base;

    return OK;

} 

Status IsEmpty(SeqStack& stack){
    if(stack.top == stack.base)
        return true;
    return false;

}

Status Push(SeqStack& stack, int val){
    if(stack.top - stack.base >= stack.size - 2)
    {
        stack.base = (ElementType*)realloc(stack.base, (stack.size * SIZE_DELTA) * sizeof(SeqStack));
        if(!stack.base)
            return ERROR;
        stack.top = stack.base   stack.size - 2;
        stack.size *= SIZE_DELTA;
    }
    * stack.top    = val;

    return OK;
}

ElementType Pop(SeqStack& stack){
    if(stack.base == stack.top)
        return Inf;
    return *( -- stack.top);
}

Status Converstion(ElementType x){
    ElementType res = 0;
    SeqStack stack;
    InitSeqStack(stack);
    while(x)
    {
        Push(stack, x % 2);
        x >>= 1;
    }
    while(!IsEmpty(stack))
        printf("%d", Pop(stack));
    puts("");
    return OK;
}

ZUST_homework

h01

题目描述:

  1. 建立两个顺序表(通过随机函数生成)
  2. 排序(升序)，输出合并前的结果
  3. 对这两个顺序表进行合并（保持升序）
  4. 输出合并结果
  5. 分析算法复杂度
代码语言：javascript复制
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <string.h>


#define OK 1
#define ERROR 0
#define SeqList_SIZE 20
typedef int ElementType;
typedef int Status;

#define stl srand((int)time(NULL)) 


typedef struct SeqList{
    ElementType* data;
    int length;
    int MaxSize;
}SeqList;


void quick_sort(SeqList& s, int l, int r){
    if(l >= r) return;
    int x = s.data[(l   l) / 2], i = l - 1, j = r   1;
    while(i < j)
    {
        do i    ; while(s.data[i] < x);
        do j -- ; while(s.data[j] > x); 
        if(i < j)
        {
            s.data[i] ^= s.data[j];
            s.data[j] ^= s.data[i];
            s.data[i] ^= s.data[j];
        }
        else 
            quick_sort(s, l, j), quick_sort(s, j   1, r);

    }
}

SeqList merge_SeqList(SeqList& s1, SeqList& s2){
    int i = 0, j = 0;
    int n = s1.length, m = s2.length;
    SeqList t;
    t.length = 0, t.MaxSize = n   m   2;
    t.data = (ElementType*)malloc((n   m   2) * sizeof (ElementType));
    ElementType* q = t.data;
    while(i < n && j < m)
    {
        if(s1.data[i] <= s2.data[j])
            *(q    ) = s1.data[i   ], t.length    ;
        else 
            *(q    ) = s2.data[j   ], t.length    ;
    }
    while(i < n)*(q    ) = s1.data[i    ], t.length    ;
    while(j < m)*(q    ) = s2.data[j    ], t.length    ;
    return t;
    
}


Status InitSeqList(SeqList& a){
    ElementType* q;
    a.data = (ElementType*)malloc(SeqList_SIZE * sizeof (ElementType));
    q = a.data;
    a.length = 0;
    a.MaxSize = SeqList_SIZE;
    int i = 0;
    for(i = 0; i < 10; i   )
    {
        *(q   ) = rand() % 100;
        a.length    ;
        
    }

    return OK;

}

Status CleaSeqList(SeqList& a){
    if(!a.length)
        return ERROR;
    a.length = 0;
    return OK;
}

Status PrintSeqList(SeqList & a){
    if(!a.length)
    {
        printf("SeqList is emptyn");
        return false;
    }
    int i;
    for(i = 0; i < a.length; i   )
        printf("%d ", *(a.data   i)); 

    puts("");
    return OK;

}

Status Add(SeqList& a, int idx, int value){
    if(idx < 1 || idx > a.length)
        return ERROR;
    int i;
    for(i = a.length; i > idx; i --)
        a.data[i] = a.data[i - 1];
    a.length    ; 
    a.data[i] = value;
    return OK;
}

Status Del(SeqList& a, int idx){
    if(idx < 1 || idx > a.length)
        return ERROR;
    int i;
    for(i = idx; i < a.length; i   )
        a.data[i] = a.data[i   1];
    a.length -- ;
    return OK;
}


void solve(){
    SeqList L1, L2;
    InitSeqList(L1), InitSeqList(L2);
    PrintSeqList(L1), PrintSeqList(L2);
    quick_sort(L1, 0, L1.length - 1), quick_sort(L2, 0, L2.length - 1);
    SeqList res = merge_SeqList(L1, L2);
    PrintSeqList(res);

}

int main(){
    stl;
    solve();

    return 0;
}

h02

题目描述:

  1. 建立两个递增有序链表（带表头，用头插法）
  2. 输出两个链表合并前的结果
  3. 将两个单链表合并，并保持递增有序
  4. 输出合并结果
代码语言：javascript复制
#include <stdio.h>
#include <stdlib.h>
#include <string.h>



#define mal_list (List)malloc(sizeof (struct LinkList))
#define OK 1
#define ERROR 0
#define SIZE 20
typedef int ElementType;
typedef int Status;


typedef struct LinkList{
    ElementType val;
    LinkList* next;
}LinkList, *List;


Status InitList(List& l){
    l = mal_list;
    l->next = NULL;
    return OK;
}

Status InsertToHead(List& head, int val){
    List p = mal_list;
    p->val = val;
    p->next = head->next;
    head->next = p;

    return OK;

}

Status PrintList(List list){
    while(list->next)
    {
        list = list->next;
        printf("%d ",list->val);
    }

    puts("");
    return OK;
}

List merge_List(List l1, List l2){
    List p = mal_list;
    p->next = NULL;
    List res = p;
    while(l1 && l2)
    {
        if(l1->val <= l2->val)
            p->next = l1, l1 = l1->next;
        else
            p->next = l2, l2 = l2->next;
        p = p->next;
    }
    while(l1)
        p->next = l1, l1 = l1->next, p = p->next;
    while(l2)
        p->next = l2, l2 = l2->next, p = p->next;
    p->next = NULL;
    return res;
}

void solve(){
    List l1, l2;
    InitList(l1), InitList(l2);
    int i = 9;
    for(; i >= 1; i -= 2)
        InsertToHead(l1, i);
    for(i = 10; i >= 2; i -= 2)
        InsertToHead(l2, i);
    PrintList(l1);
    PrintList(l2);
    List res = merge_List(l1->next, l2->next);
    PrintList(res);

}


int main (){
    solve();

    return 0;
}

考纲

一、线性表

（一）线性表的定义和基本操作

（二）线性表的实现

顺序存储

链式存储

线性表的应用

二、栈、队列和数组

栈和队列的基本概念

栈和队列的顺序存储结构

栈和队列的链式存储结构

栈和队列的应用

特殊矩阵的存储和压缩

三、树与二叉树

（一）树的基本概念

（二）二叉树

二叉树的定义及其主要特征

二叉树的顺序存储结构和链式存储结构

二叉树的遍历

线索二叉树的基本概念和构造

（三）树、森林

树的存储结构

森林与二叉树的转换

树和森林的遍历

（四）树与二叉树的应用

二叉排序树

平衡二叉树

哈夫曼（Huffman）树的哈弗曼编码

四、图

（一）图的基本概念

（二）图的存储及基本操作

邻接矩阵法

邻接表法

邻接多重表、十字链表

（三）图的遍历

深度优先搜索

广度优先搜索

四）图的基本应用

最小（代价）生成树

最短路径

拓扑排序

关键路径

五、查找

查找的基本概念

顺序查找法

分块查找法

折半查找法

B树及其基本操作、B 树及其基本概念

散列（Hash）表

字符串模式匹配（KMP）

查找算法的分析及应用

六、排序

（一）排序的基本概念

（二）插入排序

直接插入排序

折半插入排序

（三）起泡排序（bubble sort）

（四）简单选择排序

（五）希尔排序（shell sort）

（六）快速排序

（七）堆排序

（八）二路归并排序（merge sort）

（九）基数排序

（十）外部排序

（十一）各种内部排序算法的比较

（十二）排序算法的应用

上机题目

题目清单

  • 时间复杂度、矩阵展开；排序、进位制.
  • 线性表;日期问题
  • 栈与队列
  • 树的基本概念、二叉树、树和森林
  • 二叉排序树、平衡树、表达式树
  • Huffman编码和Huffman树
  • 图的基本概念、存储、遍历、拓扑排序
  • 最小生成树、最短路、关键路径
  • 基本概念、顺序、折半、分块查找法、B/B 树
  • 散列（Hash）表、字符串模式匹配（KMP）
  • 基本概念、插入、冒泡、选择、希尔、快速、堆、归并排序
  • 桶排序、基数排序、外部排序
  • 2021年笔试真题、DFS
  • 模拟、递推和BFS
  • 字符串处理、递归和背包问题
  • 高精度和因式分解
  • 枚举和位运算
  • 矩阵、计算几何和前缀和
  • 推公式、最短路、思维题
  • 哈希表、双指针、序列性DP
  • 红黑树、并查集

讲义

第1讲 时间复杂度、矩阵展开 一、时间、空间复杂度 只考虑次数，不考虑常数。常见复杂度有：O(1)、O(n)、O(sqrt(n))、O(n^k)、O(logn)、O(nlogn) 考题：2011-1、2012-1、2013-1、2014-1、2017-1、2019-1 二、矩阵展开 矩阵的按行展开、按列展开，展开后下标从0开始。 考题：2016-4、2018-3、2020-1

第2讲 线性表

  1. 将具有线性关系的数据存储到计算机中所使用的存储结构称为线性表。
  2. 对于线性表中的数据来说，位于当前数据之前的数据统称为“前趋元素”，前边紧挨着的数据称为“直接前趋”；同样，后边的数据统称为“后继元素”，后边紧挨着的数据称为“直接后继”。
  3. 线性表的分类 (1) 数据元素在内存中集中存储，采用顺序表示结构，简称“顺序存储”； 例如：数组 (2) 数据元素在内存中分散存储，采用链式表示结构，简称“链式存储”。 例如：单链表、双链表、循环单（双）链表
  4. 不同实现方式的时间复杂度（不要硬背结论、要从实现方式入手分情况讨论，下述为特定情况下的时间复杂度） (1) 数组：随机索引O(1)、插入O(n)、删除O(n) (2) 单链表：查找某一元素O(n)、插入O(1)、删除O(n) (3) 双链表：查找某一元素O(n)、插入O(1)、删除O(1)
  5. 考题：2016-1、2016-2、2012-42、2015-41、2019-41
  6. 押题：AcWing 34、AcWing 1451

第3讲 栈与队列

  1. 栈和队列的基本概念
  2. 栈和队列的顺序存储结构 (1) 栈：栈顶元素位置：指向最后一个元素、指向最后一个元素的下一个位置 (2) 队列：一般采用循环队列。 (a) 队头元素位置：指向第一个元素、指向第一个元素的前一个位置。 (b) 队尾元素位置：指向队尾元素、指向队尾元素的下一个位置。
  3. 栈和队列的链式存储结构
  4. 栈和队列的应用 (1) 栈的应用：表达式求值（中缀表达式转后缀表达式、括号匹配）、DFS (2) 队列的应用：BFS
  5. 考题：2011-2、2011-3、2012-2、2013-2、2014-2、2014-3、2015-1、2016-3、2017-2、2018-1、2018-2、2019-42、2020-2
  6. 押题：AcWing 3302

第4讲 树的基本概念、二叉树、树和森林

  1. 树的基本概念 (1) 树是由根节点和若干颗子树构成的。树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的节点，所定义的关系称为父子关系。父子关系在树的节点之间建立了一个层次结构。在这种层次结构中有一个节点具有特殊的地位，这个节点称为该树的根节点，或称为树根。 (2) 空集合也是树，称为空树。空树中没有节点； (3) 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； (4) 节点的度：一个节点含有的子节点的个数称为该节点的度； (5) 叶节点或终端节点：度为0的节点称为叶节点； (6) 非终端节点或分支节点：度不为0的节点； (7) 双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； (8) 兄弟节点：具有相同父节点的节点互称为兄弟节点； (9) 树的度：一棵树中，最大的节点的度称为树的度； (10) 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推； (11) 树的高度或深度：树中节点的最大层次； (12) 节点的祖先：从根到该节点所经分支上的所有节点； (13) 子孙：以某节点为根的子树中任一节点都称为该节点的子孙； (14) 森林：由棵互不相交的树的集合称为森林。
  2. 二叉树 (1) 二叉树的定义及其主要特征 a. 二叉树的基本形态：空二叉树、单节点二叉树、左子树、右子树 b. 性质： [1] 在非空二叉树中，第i层上至多有2^(i-1) 个结点。 [2] 深度为k的二叉树至多有2^k - 1个结点 [3] 对任何一棵二叉树，若其叶子结点数为n0，度为2的结点数为n2，则n0 = n2 1。 [4] n个结点的完全二叉树深度为：log2(n)向下取整 1 [5] 二叉树的堆式存储: 节点p的左儿子：2x，右儿子：2x 1 c. 两种特殊的二叉树 [1] 满二叉树：一颗深度为k且有2^k-1个结点的二叉树 [2] 如果深度为k,有n个结点的二叉树，当且仅当其每个结点都与深度为k的满二叉树中编号从1到n的结点一一对应，该二叉树称为完全二叉树 (2) 二叉树的顺序存储结构和链式存储结构 (3) 二叉树的遍历 a. 前序遍历 b. 中序遍历 c. 后序遍历 d. 根据前序 中序重建二叉树（AcWing 18) (4) 线索二叉树的基本概念和构造 对二叉树节点的指针域做如下规定： a. 若节点有左孩子，则Lchild指向左孩子，否则指向直接前驱；右孩子同理； b. 增加两个标志域，Ltag表示指向的是子节点还是前驱；Rtag同理 c. 指向前驱和后继的指针叫做线索。按照某种次序遍历，加上线索的二叉树称之为线索二叉树
  3. 树、森林 (1) 树的存储结构 a. 只存父节点 b. 邻接表存储所有子节点 c. 左儿子右兄弟 (2) 森林F与二叉树T的转换 a. 原树中叶子节点数 = 转换后的树中有右儿子的节点数 1 b. F的前序遍历就是T的前序遍历 c. F的后序遍历就是T的中序遍历 (3) 树和森林的遍历 a. 前序遍历 b. 后序遍历
  4. 考题：2011-4、2011-5、2011-6、2012-3、2013-5、2014-4、2014-5、2014-41、2015-2、2016-5、2016-42、2017-4、2017-5、2018-4、2019-2、2020-3、2020-4
  5. 押题：AcWing 18、AcWing 19

第5讲 二叉排序树、平衡树、表达式树

  1. 二叉排序树
  2. 平衡树——AVL (1) 定义：满足如下条件的树： a. 是二叉查找树 b. 每个节点的左子树和右子树的高度差最多为1 (2) 平衡因子：一个结点的左子树的高度减去右子树的高度，可取-1、0、1三种值 (3) 平衡操作
  3. 表达式树
  4. 考题：2011-7、2012-4、2013-3(PDF中的分析有误，以上课讲解为准)、2013-6、2015-4、2018-6、2019-4、2019-6、2020-5、2017-41

第6讲 Huffman编码和Huffman树

  1. Huffman编码和Huffman树 (1) Huffman编码 a. 前缀编码: 是指对字符集进行编码时，要求字符集中任一字符的编码都不是其它字符的编码的前缀。 b. 树的带权路径长度(WPL) c. 构造过程 (2) Huffman树 (3) 应用
  2. 考题：2012-41、2013-4、2014-6、2015-3、2017-6、2018-5、2019-3、2020-42

第7讲 图的基本概念、存储、遍历、拓扑排序

  1. 图的基本概念 (1) 有向图、无向图 (2) 度数（出度、入度） (3) 简单图：不存在顶点到其自身的边，且同一条边不重复出现 (4) 路径、环、简单路径 (5) 无向完全图：任意两个顶点之间都存在边，有n个顶点的无向完全图有 n × (n - 1) / 2条边 (6) 有向完全图：任意两个顶点之间都存在方向护卫相反的两条弧，有n个顶点的无向完全图有 n × (n - 1) 条弧 (7) 稀疏图&稠密图：有很少条边或弧的图称为稀疏图，反之称为稠密图，相对的概念。
  2. 图的存储及基本操作 (1) 邻接矩阵：适用于稠密图，可存有向图、无向图。常用。空间复杂度：O(n^2)。无法存重边。 (2) 邻接表：适用于稀疏图，可存有向图、无向图。常用。空间复杂度：O(n m)。可存重边。 (3) 邻接多重表，适用于稀疏图，可存无向图。不常用。空间复杂度：O(n m)。可存重边。 (4) 十字链表，适用于稀疏图，可存有向图、无向图。不常用。空间复杂度：O(n m)。无法存重边 (5) 三元组表，适用于稀疏图，可存有向图，无向图。常用于Bellman-Ford算法、Kruskal算法。空间复杂度：O(m)。可存重边。
  3. 图的遍历 (1) 深度优先搜索。邻接表存储的时间复杂度：O(n m)。邻接矩阵存储的时间复杂度：O(n^2) (2) 广度优先搜索。邻接表存储的时间复杂度：O(n m)。邻接矩阵存储的时间复杂度：O(n^2)
  4. 拓扑排序
  5. 考题：2011-8、2012-5、2012-6、2013-7、2013-8、2014-7、2015-5、2016-6、2016-7、2017-3、2017-7、2018-7、2020-6

第8讲 最小生成树、最短路、关键路径

  1. 最小生成树 (1) Prim (2) Kruskal
  2. 最短路 (1) 单源最短路 Dijkstra (2) 多源汇最短路 Floyd
  3. 关键路径 关键路径就是找最长路
  4. 考题：2011-41、2012-7、2012-8、2013-9、2015-6、2015-42、2016-8、2017-42、2018-42、2019-5、2020-7、2020-8

第9讲 基本概念、顺序、折半、分块查找法、B/B 树

  1. 查找的基本概念 (1) 平均查找长度 ASL = 每个元素 查找概率 * 找到第i个元素需要进行的比较次数 的和。 (2) 决策树(判定树):
  2. 顺序查找法 (1) 一般线性表的顺序查找 a. 若每个元素查找概率相同，则 ASL(成功) = (1 2 ... n) / n = (n 1) / 2 b. ASL(失败) = n或n 1，取决于代码写法。 (2) 有序表的顺序查找 a. 若每个元素查找概率相同，则 ASL(成功) = (1 2 ... n) / n = (n 1) / 2 b. ASL(失败) = (1 2 ... n n) / (n 1) = n / 2 n / (n 1)
  3. 折半查找法 (1) ASL = log(n 1) - 1
  4. 分块查找法 设共n个元素，每块s个元素，共b = n / s块。块内无序，块间有序。 (1) 顺序查找确定块：ASL(成功) = (s^2 2s n) / (2s)，s = sqrt(n)时取最小值 (2) 二分查找确定块：log(n/s 1) (s - 1)/2
  5. B树及其基本操作、B 树及其基本概念 (1) B树 [1] m阶B树，每个节点最多有m个孩子。 [2] 每个节点最多有m-1个关键字（可以存有的键值对）。 [3] 根节点最少可以只有1个关键字。 [4] 非根节点至少有m/2个关键字。 [5] 每个节点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。 [6] 所有叶子节点都位于同一层，或者说根节点到每个叶子节点的长度都相同。 [7] 每个节点都存有索引和数据，也就是对应的key和value。 [8] 所以，根节点的关键字数量范围：1 <= k <= m-1，非根节点的关键字数量范围：m/2 <= k <= m-1。 (2) B 树 [1] B 跟B树不同B 树的非叶子节点不保存关键字记录的指针，只进行数据索引，这样使得B 树每个非叶子节点所能保存的关键字大大增加； [2] B 树叶子节点保存了父节点的所有关键字记录的指针，所有数据地址必须要到叶子节点才能获取到。所以每次数据查询的次数都一样； [3] B 树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针。 (3) 参考链接：https://blog.csdn.net/Fmuma/article/details/80287924
  6. 考题：2011-42、2012-9、2013-10、2013-42、2014-9、2015-7、2016-9、2016-10、2017-8、2017-9、2018-8、2020-10

第10讲 散列（Hash）表、字符串模式匹配（KMP）

  1. 散列（Hash）表 (1) 负载因子 = ${Large frac{已有元素}{数组长度} }$ (2) 哈希函数 [1] 除余法 h(x) = x % M [2] 乘余取整法 h(x) = floor(n * (A * x的小数部分)) 0 < A < 1 [3] 平方取中法 先平方，然后取中间几位 [4] 基数转换法 换成其他进制，然后取其中几位 [5] ELFhash字符串 (3) 解决冲突的方式 [1] 开散列方法（拉链法） [2] 闭散列方法（开放寻址法） 聚集和二级聚集 a. 线性探查法 d(i) = (d(0) i * c) % M。易产生聚集问题。 b. 二次探查法。易产生二级聚集问题。 d(2i - 1) = (d(0) i^2) % M d(2i) = (d(0) - d ^2) % M c. 随机探查法。易产生二级聚集问题。 d. 双散列探查法
  2. 字符串模式匹配（KMP）
  3. 考题：2011-9、2014-8、2015-8、2018-9、2018-41、2019-8、2019-9

第11讲 基本概念、插入、冒泡、选择、希尔、快速、堆、归并排序

  1. 排序的基本概念 (1) 内排序和外排序 (2) 算法的稳定性
  2. 插入排序 (1) 直接插入排序 a. 时间复杂度 [1] 最好情况：O(n) [2] 平均情况：O(n^2) [3] 最坏情况：O(n^2) b. 辅助空间复杂度 O(1) c. 稳定 (2) 折半插入排序 a. 时间复杂度 [1] 最好情况：O(n) [2] 平均情况：O(n^2) [3] 最坏情况：O(n^2) b. 辅助空间复杂度 O(1) c. 稳定
  3. 冒泡排序（bubble sort） (1) 时间复杂度 a. 最好情况：O(n) b. 平均情况：O(n^2) c. 最坏情况：O(n^2) (2) 空间复杂度 O(1) (3) 稳定
  4. 简单选择排序 (1) 时间复杂度 a. 最好情况：O(n^2) b. 平均情况：O(n^2) c. 最坏情况：O(n^2) (2) 空间复杂度 O(1) (3) 不稳定
  5. 希尔排序（shell sort） (1) 时间复杂度 O(n^(3/2)) (2) 空间复杂度 O(1) (3) 不稳定
  6. 快速排序 (1) 时间复杂度 a. 最好情况：O(nlogn) b. 平均情况：O(nlogn) c. 最坏情况：O(n^2) (2) 空间复杂度 O(logn) (3) 不稳定
  7. 堆排序 (1) 时间复杂度 a. 最好情况：O(nlogn) b. 平均情况：O(nlogn) c. 最坏情况：O(nlogn) (2) 空间复杂度 O(logn) (3) 不稳定
  8. 二路归并排序（merge sort） (1) 时间复杂度 a. 最好情况：O(nlogn) b. 平均情况：O(nlogn) c. 最坏情况：O(nlogn) (2) 空间复杂度 O(n) (3) 稳定

第12讲 桶排序、基数排序、外部排序

  1. 桶排序 (1) 时间复杂度 a. 最好情况：O(n m) b. 平均情况：O(n m) c. 最坏情况：O(n m) (2) 空间复杂度 O(n m) (3) 稳定
  2. 基数排序 (1) 时间复杂度 a. 最好情况：O(d(n r)) b. 平均情况：O(d(n r)) c. 最坏情况：O(d(n r)) (2) 空间复杂度 O(n r) (3) 稳定
  3. 外部排序 (1) 置换选择排序 (2) 归并排序 a. 胜者树 b. 败者树 c. huffman树
  4. 考题：2011-10、2011-11、2012-10、2012-11、2013-11、2014-10、2014-11、2015-9、2015-10、2015-11、2016-11、2016-43、2017-10、2017-11、2018-10、2018-11、2019-7、2019-10、2019-11、2020-9、2020-11、2020-41

第21讲 红黑树和并查集

  1. 红黑树 1.1 定义 (1) 结点是红色或黑色。 (2) 根结点是黑色。 (3) 所有叶子都是黑色。（叶子是NIL结点） (4) 每个红色结点的两个子结点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色结点） (5) 从任一节结点其每个叶子的所有路径都包含相同数目的黑色结点。 1.2 性质 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。 1.3 平衡操作 1.3.1 插入 1.3.1.1 被插入的节点是根节点。 直接把此节点涂为黑色。 1.3.1.2 被插入的节点的父节点是黑色。 什么也不需要做。 1.3.1.3 被插入的节点的父节点是红色。 [1] 当前节点的祖父节点的另一个子节点（叔叔节点）也是红色。 (1) 将“父节点”设为黑色。 (2) 将“叔叔节点”设为黑色。 (3) 将“祖父节点”设为“红色”。 (4) 将“祖父节点”设为“当前节点”(红色节点)；即，之后继续对“当前节点”进行操作。 [2] 叔叔节点是黑色，且当前节点是其父节点的右孩子 (1) 将“父节点”作为“新的当前节点”。 (2) 以“新的当前节点”为支点进行左旋。 [3] 叔叔节点是黑色，且当前节点是其父节点的左孩子 (1) 将“父节点”设为“黑色”。 (2) 将“祖父节点”设为“红色”。 (3) 以“祖父节点”为支点进行右旋。 1.3.2 删除 1.3.2.1 x指向一个"红 黑"节点。 将x设为一个"黑"节点即可。 1.3.2.2 x指向根。 将x设为一个"黑"节点即可。 1.3.2.3 [1] x的兄弟节点是红色。 (1) 将x的兄弟节点设为“黑色”。 (2) 将x的父节点设为“红色”。 (3) 对x的父节点进行左旋。 (4) 左旋后，重新设置x的兄弟节点。 [2] x的兄弟节点是黑色，x的兄弟节点的两个孩子都是黑色。 (1) 将x的兄弟节点设为“红色”。 (2) 设置“x的父节点”为“新的x节点”。 [3] x的兄弟节点是黑色；x的兄弟节点的左孩子是红色，右孩子是黑色的。 (1) 将x兄弟节点的左孩子设为“黑色”。 (2) 将x兄弟节点设为“红色”。 (3) 对x的兄弟节点进行右旋。 (4) 右旋后，重新设置x的兄弟节点。 [4] x的兄弟节点是黑色；x的兄弟节点的右孩子是红色的，x的兄弟节点的左孩子任意颜色。 (1) 将x父节点颜色 赋值给 x的兄弟节点。 (2) 将x父节点设为“黑色”。 (3) 将x兄弟节点的右子节设为“黑色”。 (4) 对x的父节点进行左旋。

​

  1. 并查集 2.1 定义 用森林维护集合关系，支持合并、查询等操作。 2.2 优化 (1) 路径压缩 (2) 按秩合并

题目列表:

第一讲 排序与进位制

成绩排序

成绩排序

给定学生的成绩单，成绩单中包含每个学生的姓名和分数，请按照要求将成绩单按成绩从高到低或从低到高的顺序进行重新排列。

对于成绩相同的学生，无论以哪种顺序排列，都要按照原始成绩单中靠前的学生排列在前的规则处理。

输入格式

第一行包含整数 $N$，表示学生个数。

第二行包含一个整数 $0$ 或 $1$，表示排序规则，$0$ 表示从高到低，$1$ 表示从低到高。

接下来 $N$ 行，每行描述一个学生的信息，包含一个长度不超过 $10$的小写字母构成的字符串表示姓名以及一个范围在 $0 sim 100$ 的整数表示分数。

输出格式

输出重新排序后的成绩单。

每行输出一个学生的姓名和成绩，用单个空格隔开。

数据范围

$1 le N le 1000$

输入样例1：

代码语言：javascript复制
4
0
jack 70
peter 96
Tom 70
smith 67

输出样例1：

代码语言：javascript复制
peter 96
jack 70
Tom 70
smith 67

输入样例2：

代码语言：javascript复制
4
1
jack 70
peter 96
Tom 70
smith 67

输出样例2：

代码语言：javascript复制
smith 67
jack 70
Tom 70
peter 96
题解:
  • code 1
  • code 2
代码语言：javascript复制
#include <bits/stdc  .h>

using namespace std;
#define fi first
#define se second


const int N = 1010;

struct Stu{
    string name;
    int score, id;
    bool operator<(const Stu& s)const{
        return score ^ s.score ? score < s.score : id < s.id;
    }
    bool operator>(const Stu& s)const{
        return score > s.score ? score > s.score : id < s.id;
    }
}p[N];

int main(){
    int n; cin >> n;
    bool flg; cin >> flg;
    for(int i = 0; i < n; i   )
    {
        string name;
        int score;
        cin >> name >> score;
        p[i] = {name, score, i};
    }
    if(flg)
        stable_sort(p, p   n);
    else 
        stable_sort(p, p   n, greater<Stu>());
    for(int i = 0; i < n; i   )
        cout << p[i].name << " " << p[i].score << endl;
    return 0;
}
代码语言：javascript复制
#include <bits/stdc  .h>

using namespace std;
#define fi first
#define se second


const int N = 1010;

struct Stu{
    string name;
    int score, id;
}p[N];

int main(){
    int n; cin >> n;
    bool flg; cin >> flg;
    for(int i = 0; i < n; i   )
    {
        string name;
        int score;
        cin >> name >> score;
        p[i] = {name, score, i};
    }
    if(flg)
        sort(p, p   n, [=](Stu& p1, Stu& p2){
            return p1.score ^ p2.score ? p1.score < p2.score : p1.id < p2.id;
        });
    else 
        sort(p, p   n, [=](Stu& p1, Stu& p2){
            return p1.score ^ p2.score ? p1.score > p2.score : p1.id < p2.id;
        });
    for(int i = 0; i < n; i   )
        cout << p[i].name << " " << p[i].score << endl;
    return 0;
}

第二讲 链表、日期问题

第三讲 表达式求值

第四讲 树的遍历

第五讲 二叉搜索树与表达式树

第六讲 Huffman树

第七讲 拓扑排序

第八讲 最小生成树、最短路

第十讲 哈希表和KMP

第十一讲 排序

第十二讲 排序、多路归并和摩尔投票法

第十三讲 DFS

第十四讲 模拟、递推、BFS

第十五讲 字符串处理、递归和背包问题

第十六讲 高精度和因式分解

第十七讲 枚举和位运算

第十八讲 矩阵、计算几何和前缀和

第十九讲 推公式、最短路、思维题

第二十讲 哈希表、双指针、序列型DP

第二十一讲 红黑树和并查集

二叉树 编程算法 存储

0 人点赞