数据结构

---

🌱 一些记录? 🌱

快捷导航

算法

• 算法: 对特定问题求解步骤的描述
• 算法特性: 有穷, 确定, 可行, 输入, 输出

---

• O(1) ＜ O(log2n) ＜ O(n) ＜ O(nlog2n) ＜ O(n2) ＜ O(n3) ＜ O(2^n) ＜ O(n!) ＜ O(n^n)

---

• 如何计算时间复杂度 T(n):
• 方法1: f(循环次数t) ~ 循环条件(直接的条件 | 需推导的条件注意取值范围) -> T(n)
• 方法2: 直接累计次数 -> T(n)
• 最后忽略高阶项系数和低阶项

---

• 如何计算空间复杂度 S(n):
• 注意空间是否随着n的增长而增长

时间复杂度

• 时间复杂度指算法中所有语句的频度(执行次数)之和
• T(n) = O(f(n)), 其中: n是问题的规模, f(n)是问题规模n的某个函数
• 最高阶数越小,说明算法的时间性能越好
• 时间复杂度计算忽略高阶项系数和低阶项
• 最坏,平均,最好

空间复杂度

• 算法运行过程中所使用的辅助空间的大小
• S(n) = O(f(n))
• 算法原地工作是指算法所需的辅助空间是常量, 即O(1)
• n个元素数组排序,不使用额外的空间(随着n的增长而增长的空间叫额外空间),空间复杂度就是O(1)

数据结构

• 数据项 < (相同性质)数据元素 < 数据对象 < 数据
• 数据类型: 原子类型, 结构类型, 抽象数据类型
• 抽象数据类型描述了数据的逻辑结构和抽象运算, 可以成一个完整的数据结构定义
• 数据结构三要素: 逻辑结构, 存储结构(物理结构), 数据的运算
• 结构: 数据元素(数据的基本单位)相互之间的关系; 在存储数据元素的值时也要存储数据元素之间的关系
• 数据的逻辑结构独立于其存储结构
• 逻辑结构分为线性结构和非线性结构
• 线性结构: 线性表, 栈, 队列
• 非线性结构: 集合, 树, 图
• 存储(物理)结构主要有: 顺序存储, 链式存储, 索引存储, 散列存储
• 顺序存储: 随机存取(读写), 最少空间, 整块存储, 较多碎片
• 链式存储: 只能顺序存取(读写), 额外空间, 没有碎片
• 数据的运算: 包括运算的定义(针对逻辑结构)和实现(针对存储结构)

---

• 链式存储设计时, 各个不同结点的存储空间可以不连续, 但结点内的存储单元地址必须连续
• 抽象数据类型(只表示逻辑结构): 线性表, 栈, 队列, 集合, 树, 图
• 数据结构: 顺序表, 链表, 索引表?, 哈希表, 循环队列(用顺序表表示的队列)

逻辑结构

• 数据元素之间的逻辑关系
• 抽象的
• 对人友好

集合结构	线性结构	树形结构	图形结构
无关系	一对一	一对多	多对多

存储结构

• 数据结构在计算机中的表示
• 具体的
• 对计算机友好

存储结构
顺序存储	可以实现随机存取,每个元素占用最少的空间;只能使用整块的存储单元,会产出较多的碎片
链式存储	充分利用所有存储单元,不会出现碎片现象;需要额外的存储空间用来存放下一结点的指针,只能实现顺序存取
索引存储	索引存取
散列存储	散列存取

线性表

• 线性表是具有相同数据类型的n(n≥0)个数据元素的有限序列

• 线性表中元素个数n,称为线性表的长度。当n=0时,为空表。

• a1是唯一的第一个数据元素, an是唯一的最后一个数据元素。

• ai-1为ai的直接前驱, ai+1为ai的直接后继

• 表中元素的个数是有限的

• 表中元素的数据类型都相同。意味着每一个元素占用相同大小的空间

• 表中元素具有逻辑上的顺序性, 在序列中各元素排序有其先后顺序

• 线性表: 数据元素同类型, 有限, 有序
• 注意顺序表的位序和数组下标
• 动态分配的数组属于顺序存储结构, 只是分配的空间大小可以在运行时动态决定
• 顺序表: 线性表的顺序表示
• 链表: 线性表的链式表示

---

• 假设在顺序表中L为结构体变量, 在带头结点的链表中L为头指针
• 顺序表: 随机存取(读写), 逻辑顺序与物理顺序相同; 判断是否为空: 0 == L.length; 记得判断位序是否有效, 存储空间是否已满
• 链表: 只能顺序存取(读写)
• 单链表: 判断是否为空: NULL == L -> next
• 双链表: 判断是否为空: NULL == L -> next
• 循环单链表: 判断是否为空: L->next==L
• 循环双链表: 判断是否为空: L->next==L && L->prior==L
• 静态链表: 判断是否为空: -1 == next
• 有关头指针和尾指针: 头指针方便头结点的删除操作和头结点前插入元素; 尾指针只方便尾结点后插入元素
• 对于循环单链表: 尾指针可以方便在头结点进行的操作, 方便在尾结点后插入元素
• 对于循环双链表: 头指针和尾指针均可方便在头结点和尾结点进行的操作

---

• 顺序表增删查时间复杂度: 最好 O(1), 平均和最坏 O(n)
• 增: 时间复杂度: 最好 O(1), 平均 n*(n+1)/2/(n+1) = n/2 -> O(n), 最坏 O(n)
• 删: 时间复杂度: 最好 O(1), 平均 (n-1)/2 -> O(n), 最坏 O(n)
• 查(按值查找): 时间复杂度: 最好 O(1), 平均 (n+1)/2 -> o(n), 最坏 O(n)

顺序表

• 顺序表采用数组来实现,因此逻辑上相邻的两个元素在物理位置上也相邻,从而能够实现随机存取

优点	缺点
可以随机存取(根据表头元素地址和元素序号)表中任意一个元素	插入和删除操作需要移动大量元素
存储密度高,每个结点只存储数据元素	线性表变化较大时,难以确定存储空间的容量
	存储分配需要一整段连续的存储空间,造成很多碎片, 不够灵活

• 静态分配
• 动态分配

#define MaxSize 6
typedef int ElemType;

typedef struct{
    ElemType data[MaxSize];
    int length;
}SqList;

#define InitSize 6
typedef int ElemType;

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

L.data = (ElemType *)malloc(sizeof(ElemType)*InitSize);

L.data = new ElemType[InitSize];

顺序表的增删查

• 查
• 增
• 删
• code
• debug

// 按值查找, 查找成功返回顺序表位序, 反之 0
int search_sqlist(SqList _SqList, ElemType _element) {
    for (int i=0; i<_SqList.length; i++) {
        if(_element == _SqList.data[i]) {
            return i+1;
        }
    }
    return 0;
}

// i: 顺序表位序
bool insert_sqlist(SqList &_SqList, int i, ElemType _element) {
    if (i<1 || i>_SqList.length+1) {
        return false;
    }
    if (_SqList.length == MaxSize) {
        return false;
    }
    for (int j=_SqList.length; j>=i; j--) {
        _SqList.data[j] = _SqList.data[j-1];
    }
    _SqList.data[i-1] = _element;
    _SqList.length++;
    return true;
}

// i: 顺序表位序
bool delete_sqlist(SqList &_SqList, int i, ElemType &_element) {
    if (i<1 || i>_SqList.length) {
        return false;
    }
    _element = _SqList.data[i-1];
    for (int j=i; j<_SqList.length; j++) {
        _SqList.data[j-1] = _SqList.data[j];
    }
    _SqList.length--;
    return true;
}

#include <stdio.h>

#define MaxSize 50
typedef int ElemType;
typedef struct{
    ElemType data[MaxSize];
    int length;
}SqList;



void print_sqlist(SqList _SqList) {
    for (int i=0; i<_SqList.length; i++) {
        printf("%3d", _SqList.data[i]);
    }
    printf("\n");
}



// i: 顺序表位序
bool insert_sqlist(SqList &_SqList, int i, ElemType _element) {
    if (i<1 || i>_SqList.length+1) {
        return false;
    }
    if (_SqList.length == MaxSize) {
        return false;
    }
    for (int j=_SqList.length; j>=i; j--) {
        _SqList.data[j] = _SqList.data[j-1];
    }
    _SqList.data[i-1] = _element;
    _SqList.length++;
    return true;
}

// i: 顺序表位序
bool delete_sqlist(SqList &_SqList, int i, ElemType &_element) {
    if (i<1 || i>_SqList.length) {
        return false;
    }
    _element = _SqList.data[i-1];
    for (int j=i; j<_SqList.length; j++) {
        _SqList.data[j-1] = _SqList.data[j];
    }
    _SqList.length--;
    return true;
}

// 按值查找, 查找成功返回顺序表位序, 反之 0
int search_sqlist(SqList _SqList, ElemType _element) {
    for (int i=0; i<_SqList.length; i++) {
        if(_element == _SqList.data[i]) {
            return i+1;
        }
    }
    return 0;
}



int main() {
    SqList slist;
    slist.data[0]=1;
    slist.data[1]=2;
    slist.data[2]=3;
    slist.length=3;

    bool ret;
    ret=insert_sqlist(slist,3,66);
    if (ret) {
        printf("insert SqList success\n");
        print_sqlist(slist);
    }else {
        printf("insert SqList fail\n");
    }
    printf("\n");

    ElemType del;//删除的元素存入del中
    ret=delete_sqlist(slist,1,del);
    if (ret) {
        printf("delete SqList success\n");
        printf("del element = %d\n",del);
        print_sqlist(slist);
    }else {
        printf("delete SqList fail\n");
    }
    printf("\n");

    int pos;//存储元素位置
    pos=search_sqlist(slist,66);
    if (pos) {
        printf("search element success\n");
        printf("pos = %d\n",pos);
    }else {
        printf("search element fail\n");
    }
    return 0;
}

insert seqlist success
  1  2 66  3

delete sqlist success
del element = 1
  2 66  3

search element success
pos = 2

链表

• 逻辑上相邻的两个元素在物理位置上不相邻

• 头指针：链表中第一个结点的存储位置,用来标识单链表

• 头结点：在单链表第一个结点之前附加的一个结点,为了操作上的方便

• 若链表有头结点,则头指针永远指向头结点

• 不论链表是否为空,头指针均不为空

• 头指针是链表的必须元素,他标识一个链表

• 头结点是为了操作的方便而设立的,其数据域一般为空,或者存放链表的长度

• 头结点不是必须的

优点	缺点
插入和删除操作不需要移动元素,只需要修改指针	单链表附加指针域,也存在浪费存储空间的缺点
不需要大量的连续存储空间	查找操作时需要从表头开始遍历,依次查找,不能随机存取

#define MaxSize 99
typedef int ElemType;
typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}LinkNode, *LinkList;

单链表的增删查

• 头插法新建链表
• 尾插法新建链表
• 查
• 增
• 删
• code
• debug

// 头插法新建链表
void head_insert(LinkNode *&_LinkNode) {
    // 申请头结点空间,头指针指向头结点
    _LinkNode = (LinkNode *)malloc(sizeof(LinkNode));
    _LinkNode -> next = NULL;

    ElemType e;
    scanf("%d", &e);
    LinkNode *new_node;
    while (e != MaxSize) {
        new_node = (LinkNode *)malloc(sizeof(LinkNode));
        new_node -> data = e;
        new_node -> next = _LinkNode -> next;
        _LinkNode -> next = new_node;
        scanf("%d", &e);
    };
    return;
}

// 尾插法新建链表
void tail_insert(LinkNode *&_LinkNode) {
    // 申请头结点空间,头指针指向头结点
    _LinkNode = (LinkList)malloc(sizeof(LinkNode));

    ElemType e;
    scanf("%d", &e);
    LinkNode *new_node;
    LinkNode *temp_node = _LinkNode;
    while (e != MaxSize) {
        new_node = (LinkNode *)malloc(sizeof(LinkNode));
        new_node -> data = e;
        temp_node -> next = new_node;
        temp_node = new_node; // 保存最后一个节点
        scanf("%d", &e);
    }
    new_node -> next = NULL; // 尾结点的next要为NULL
    return;
}

//按位置查找, _location: 链表位序
LinkNode* find_by_location(LinkNode *_LinkNode, int _location) {
    if (_location < 0) {
        return NULL;
    }
    int i = 0;
    while (_LinkNode&&i<_location) {
        _LinkNode = _LinkNode -> next;
        i++;
    }
    return _LinkNode;
}

//按值查找
LinkNode* find_by_value(LinkNode *_LinkNode, int _value) {
    while (_LinkNode) {
        if (_LinkNode->data == _value) {
            return _LinkNode;
        }else {
            _LinkNode = _LinkNode->next;
        }
    }
    return NULL;
}

// _location: 链表位序
bool insert_specified_location(LinkNode *_LinkNode, int _value, int _location) {
    LinkNode *new_node, *temp_node;
    temp_node = find_by_location(_LinkNode, _location-1);
    if (NULL == temp_node) {
        return false;
    }
    new_node = (LinkNode *)malloc(sizeof(LinkNode));
    new_node -> data = _value;
    new_node -> next = temp_node -> next;
    temp_node -> next = new_node;
    return true;
}

// _location: 链表位序
bool delete_specified_node(LinkNode *_LinkNode, int _location) {
    _LinkNode = find_by_location(_LinkNode, _location-1);
    if (NULL == _LinkNode) {
        return false;
    }
    LinkNode *delete_node;
    delete_node = _LinkNode -> next;
    _LinkNode -> next = delete_node -> next;
    free(delete_node);
    return true;
}

#include <stdio.h>
#include <stdlib.h>

#define MaxSize 99
typedef int ElemType;

// LinkNode*是结构体指针, 和LinkList完全等价
typedef struct LinkNode{
    ElemType data; // 数据域
    struct LinkNode *next; // 指针域
}LinkNode, *LinkList;



void print_LinkList(LinkList _LinkNode) {
    _LinkNode = _LinkNode->next; //去到第一个结点
    while (_LinkNode) {
        printf("%3d", _LinkNode -> data);
        _LinkNode = _LinkNode -> next;
    }
    printf("\n");
}

// 头插法新建链表
void head_insert(LinkNode *&_LinkNode) {
    // 申请头结点空间,头指针指向头结点
    _LinkNode = (LinkNode *)malloc(sizeof(LinkNode));
    _LinkNode -> next = NULL;

    ElemType e;
    scanf("%d", &e);
    LinkNode *new_node;
    while (e != MaxSize) {
        new_node = (LinkNode *)malloc(sizeof(LinkNode));
        new_node -> data = e;
        new_node -> next = _LinkNode -> next;
        _LinkNode -> next = new_node;
        scanf("%d", &e);
    };
    return;
}

// 尾插法新建链表
void tail_insert(LinkNode *&_LinkNode) {
    // 申请头结点空间,头指针指向头结点
    _LinkNode = (LinkList)malloc(sizeof(LinkNode));

    ElemType e;
    scanf("%d", &e);
    LinkNode *new_node;
    LinkNode *temp_node = _LinkNode;
    while (e != MaxSize) {
        new_node = (LinkNode *)malloc(sizeof(LinkNode));
        new_node -> data = e;
        temp_node -> next = new_node;
        temp_node = new_node; // 保存最后一个节点
        scanf("%d", &e);
    }
    new_node -> next = NULL; // 尾结点的next要为NULL
    return;
}

//按位置查找, _location: 链表位序
LinkNode* find_by_location(LinkNode *_LinkNode, int _location) {
    if (_location < 0) {
        return NULL;
    }
    int i = 0;
    while (_LinkNode&&i<_location) {
        _LinkNode = _LinkNode -> next;
        i++;
    }
    return _LinkNode;
}

//按值查找
LinkNode* find_by_value(LinkNode *_LinkNode, int _value) {
    while (_LinkNode) {
        if (_LinkNode->data == _value) {
            return _LinkNode;
        }else {
            _LinkNode = _LinkNode->next;
        }
    }
    return NULL;
}

// _location: 链表位序
bool insert_specified_location(LinkNode *_LinkNode, int _value, int _location) {
    LinkNode *new_node, *temp_node;
    temp_node = find_by_location(_LinkNode, _location-1);
    if (NULL == temp_node) {
        return false;
    }
    new_node = (LinkNode *)malloc(sizeof(LinkNode));
    new_node -> data = _value;
    new_node -> next = temp_node -> next;
    temp_node -> next = new_node;
    return true;
}

// _location: 链表位序
bool delete_specified_node(LinkNode *_LinkNode, int _location) {
    _LinkNode = find_by_location(_LinkNode, _location-1);
    if (NULL == _LinkNode) {
        return false;
    }
    LinkNode *delete_node;
    delete_node = _LinkNode -> next;
    _LinkNode -> next = delete_node -> next;
    free(delete_node);
    return true;
}



int main() {
    LinkNode *linklist; // 链表头指针,是结构体指针类型
    head_insert(linklist);
    print_LinkList(linklist);
    // free(linklist); // 防止内存泄露
    tail_insert(linklist);
    print_LinkList(linklist);

    LinkList result;
    result = find_by_location(linklist, 3);
    if (result) {
        printf("find_by_location of 3: %3d\n", result->data);
    }
    result = find_by_value(linklist, 5);
    if (result) {
        printf("find_by_value: %3d\n", result->data);
    }

    bool ret;
    ret = insert_specified_location(linklist, 66, 3);
    print_LinkList(linklist);
    ret = delete_specified_node(linklist, 3);
    print_LinkList(linklist);

    return 0;
}

1 2 3 4 5 99
  5  4  3  2  1
1 2 3 4 5 99
  1  2  3  4  5
find_by_location of 3:   3
find_by_value:   5
  1  2 66  3  4  5
  1  2  3  4  5

静态链表

#define MaxSize 50
typedef int ElemType;
typedef struct {
    ElemType data;
    int next;
} SLinkList[MaxSize];

栈

• stack: a pile of objects
• 又称为堆栈或堆叠, 先进后出(First In Last Out)
• 栈的特点是先进后出, 简称FILO,也可以称为后进先出
• 只允许在一端进行插入或删除操作的线性表
• 栈的基本操作:入栈, 出栈
• 栈可以进行压栈, 弹栈
• 压栈操作, 栈中元素变多, 弹栈操作, 栈中元素减少

• 栈: 先进后出(First In Last Out, FILO), 也可以称为后进先出
• 对于顺序栈:
• 初始化栈: S.top = -1; 栈长为: S.top + 1
• 判断栈空: -1 == S.top; 判断栈满: S.top == MaxSize-1
• n个不同元素进栈, 出栈元素不同排列的个数为(C n 2n)/(n+1)

顺序栈

#define MaxSize 99
typedef int ElemType;
typedef struct {
    ElemType data[MaxSize];
    int top;
} SqStack;

• 初始化栈
• 判断栈是否为空
• 入栈
• 出栈
• 获取栈顶元素
• code
• debug

void init_stack(SqStack &_SqStack) {
    _SqStack.top=-1;
}

bool is_stack_empty(SqStack _SqStack) {
    if (-1 == _SqStack.top) {
        return true;
    }else {
        return false;
    }
}

bool push_stack(SqStack &_SqStack, ElemType x) {
    if (_SqStack.top == MaxSize-1) {
        return false;
    }
    _SqStack.data[++_SqStack.top] = x;
    return true;
}

bool pop_stack(SqStack &_SqStack, ElemType &m) {
    if (is_stack_empty(_SqStack)) {
        return false;
    }
    m = _SqStack.data[_SqStack.top--];//出栈
    return true;
}

bool get_stack_top(SqStack _SqStack, ElemType &m) {
    if (is_stack_empty(_SqStack)) {
        return false;
    }
    m = _SqStack.data[_SqStack.top];
    return true;
}

#include <stdio.h>
#include <stdlib.h>

#define MaxSize 99
typedef int ElemType;
typedef struct {
    ElemType data[MaxSize];
    int top;//栈顶
} SqStack;


void init_stack(SqStack &_SqStack) {
    _SqStack.top=-1; //初始化栈,就是_seq_stack.top=-1,让栈为空
}

bool is_stack_empty(SqStack _SqStack) {
    if (-1 == _SqStack.top) {
        return true;
    }else {
        return false;
    }
}

//入栈
bool push_stack(SqStack &_SqStack, ElemType x) {
    //判断栈是否满了
    if (_SqStack.top == MaxSize-1) {
        return false;
    }
    _SqStack.data[++_SqStack.top] = x;
    //等价于_seq_stack.top=_SqStack.top+1; _SqStack.data[_SqStack.top]=x;
    return true;
}

bool get_stack_top(SqStack _SqStack, ElemType &m) {
    if (is_stack_empty(_SqStack)) {
        return false;
    }
    m = _SqStack.data[_SqStack.top];//拿栈顶元素
    return true;
}

//弹栈
bool pop_stack(SqStack &_SqStack, ElemType &m) {
    if (is_stack_empty(_SqStack)) {
        return false;
    }
    m = _SqStack.data[_SqStack.top--];//出栈
    //等价于m=_SqStack.data[_SqStack.top];_SqStack.top=_SqStack.top-1;
    return true;
}

int main() {
    SqStack a_seq_stack;
    init_stack(a_seq_stack);
    bool flag;
    flag=is_stack_empty(a_seq_stack);
    if (flag) {
        printf("a_seq_stack is empty\n");
    }
    push_stack(a_seq_stack,1);
    push_stack(a_seq_stack,2);
    push_stack(a_seq_stack,3);

    int m;
    flag=get_stack_top(a_seq_stack,m);
    if (flag) {
        printf("get_stack_top: %d\n",m);
    }

    push_stack(a_seq_stack,4);
    push_stack(a_seq_stack,5);
    flag=pop_stack(a_seq_stack,m);//弹出栈顶元素
    if (flag) {
        printf("pop_stack: %d\n",m);
    }
    return 0;
}

a_seq_stack is empty
get_stack_top: 3
pop_stack: 5

链栈

typedef int ElemType;
typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
} *LinkStack;

队列

• 队列(Queue)简称队,也是一种操作受限的线性表,只允许在表的一端进行插人而在表的另一端进行删除
• 向队列中插人元素称为入队或进队,删除元素称为出队或离队
• 队头 (Front): 允许删除的一端,又称队首
• 队尾 (Rear): 允许插人的一端
• 特性是先进先出(First ln First Out, FIFO)

• 队列: 先进先出(First ln First Out, FIFO)
• 对于顺序存储实现的队列: 队尾入队, 队头出队
• 初始化队列: Q.front = Q.rear = 0
• 在循环队列中约定队尾指针始终指向空元素
• 判断循环队列是否为空: Q.rear == Q.front
• 判断循环队列是否已满: (Q.rear + 1)%MaxSize == Q.front
• 循环队列中的元素个数: (Q.rear - Q.front + MaxSize)%MaxSize

---

• 输出受限的双端队列
• -> ——— <-
• a, b, c, …
• <- ———
• 出队序列必为: a, b, c, ... (有用)

---

• 输入受限的双端队列
• ——— <-
• a, b, c, …
• <- ——— ->
• 入队序列必为: a, b, c, ... (没什么用)

顺序存储实现循环队列

• 循环队列我们最多放置MaxSize-1个元素
• 循环队列入队时我们需要判断队列是否满了,出队时我们需要判断队列是否为空

#define MaxSize 6
typedef int ElemType;
typedef struct {
    ElemType data[MaxSize];
    int front, rear;
} SqQueue;

• 初始化队
• 判断队是否为空
• 入队
• 出队
• code
• debug

void init_queue(SqQueue &Q) {
    Q.front = Q.rear = 0;
}

bool is_queue_empty(SqQueue Q) {
    return Q.rear == Q.front;
}

bool ent_queue(SqQueue &Q, int x) {
    if ((Q.rear + 1)%MaxSize == Q.front) {
        return false;
    }
    Q.data[Q.rear] = x;
    Q.rear = (Q.rear + 1)%MaxSize;
    return true;
}

bool del_queue(SqQueue &Q, int &x) {
    if (Q.rear == Q.front) {
        return false;
    }
    x = Q.data[Q.front];
    Q.front = (Q.front + 1)%MaxSize;
    return true;
}

#include <stdio.h>
#include <stdlib.h>

#define MaxSize 5
typedef int ElemType;
typedef struct {
    ElemType data[MaxSize];//存储max_size-1个元素
    int front, rear;//队列头,队列尾
} SqQueue;

void init_queue(SqQueue &Q) {
    Q.front = Q.rear = 0;//初始化循环队列,就是让头和尾都指向零号
}

bool is_queue_empty(SqQueue Q) {
    return Q.rear == Q.front;
}

//入队
bool ent_queue(SqQueue &Q, int x) {
    if ((Q.rear + 1)%MaxSize == Q.front) {
        return false;
    }
    Q.data[Q.rear] = x;
    Q.rear = (Q.rear + 1)%MaxSize;
    return true;
}

//出队
bool del_queue(SqQueue &Q, int &x) {
    if (Q.rear == Q.front) {
        return false;
    }
    x = Q.data[Q.front];
    Q.front = (Q.front + 1)%MaxSize;
    return true;
}

int main() {
    SqQueue Q;
    init_queue(Q);
    bool ret;
    ret=is_queue_empty(Q);
    if (ret) {
        printf("SqQueue is empty\n");
    }else {
        printf("SqQueue is not empty\n");
    }

    ent_queue(Q,1);
    ent_queue(Q,2);
    ent_queue(Q,3);
    ret=ent_queue(Q,4);
    ret=ent_queue(Q,5);
    if (ret) {
        printf("ent_queue succeed\n");
    }else {
        printf("ent_queue fail\n");
    }

    int element;//存储出队元素
    ret=del_queue(Q,element);
    if (ret) {
        printf("del_queue succeed\n");
    }else {
        printf("del_queue fail\n");
    }

    ret=ent_queue(Q,6);
    if (ret) {
        printf("ent_queue succeed\n");
    }else {
        printf("ent_queue fail\n");
    }
    return 0;
}

seq_queue is empty
ent_queue fail
del_queue succeed
ent_queue succeed

链式存储实现循环队列

• code
• debug

#include <stdio.h>
#include <stdlib.h>

typedef struct LinkNode {
    int data;
    struct LinkNode* next;//指向下一个结点
}LinkNode, *LinkQueue;


void ent_queue(LinkQueue front, LinkQueue &rear, int _value) {
    if (rear->next == front) {//判断队列是不是满了
        LinkQueue p_new;
        p_new= (LinkQueue)malloc(sizeof(LinkNode));
        rear->data = _value;
        rear->next = p_new;
        p_new->next = front;
        rear = p_new;
    } else {//如果队列不满,直接放值,让rear后移一个结点
        rear->data = _value;
        rear = rear->next;
    }
}

void del_queue(LinkQueue& front, LinkQueue rear) {
    if (front == rear) {
        printf("queue is empty\n");
    }else {
        printf("del_queue: %d\n", front->data);
        front = front->next;
    }
}

int main() {
    LinkQueue front, rear;
    front = (LinkQueue)malloc(sizeof(LinkNode));
    rear = front;
    rear->next = front;//构造循环队列

    ent_queue(front, rear, 1);
    ent_queue(front, rear, 2);
    ent_queue(front, rear, 6);
    del_queue(front, rear);
    del_queue(front, rear);
    del_queue(front, rear);
    return 0;
}

del_queue: 1
del_queue: 2
del_queue: 6

链队列

• 队列的链式表示称为链队列,它实际上是一个同时带有队头指针和队尾指针的单链表
• 头指针指向队头结点,尾指针指向队尾结点,即单链表的最后一个结点

typedef int ElemType;
typedef struct LinkNode {
	ElemType data;
	struct LinkNode *next;
}LinkNode;
typedef struct {
	LinkNode *front,*rear;
}LinkQueue;

• 初始化队
• 入队
• 出队
• code
• debug

void init_queue(LinkQueue &Q) {
    Q.front=Q.rear=(LinkNode *)malloc(sizeof(LinkNode));
    Q.front->next=NULL;
}

void ent_queue(LinkQueue &Q, int x) {
    LinkNode *p_new=(LinkNode *)malloc(sizeof(LinkNode));
    p_new->data=x;
    p_new->next=NULL;
    Q.rear->next=p_new;
    Q.rear=p_new;
}

bool del_queue(LinkQueue &Q, int &x) {
    if (Q.rear==Q.front) {
        return false;
    }
    LinkNode* q=Q.front->next;
    x=q->data;
    Q.front->next=q->next;
    if (Q.rear==q) {
        Q.rear=Q.front;//链表只剩余一个结点时,被删除后,要改变rear
    }
    free(q);
    return true;
}

#include <stdio.h>
#include <stdlib.h>

typedef struct LinkNode{
	int data;
	struct LinkNode *next;
}LinkNode;

typedef struct{
	LinkNode *front,*rear;//链表头 链表尾,也可以称为队头,队尾
}LinkQueue;//先进先出


//队列的初始化,使用的是带头结点的链表来实现的
void init_queue(LinkQueue &Q) {
    Q.front=Q.rear=(LinkNode *)malloc(sizeof(LinkNode));
    Q.front->next=NULL;
}

//入队
void ent_queue(LinkQueue &Q, int x) {
    LinkNode *p_new=(LinkNode *)malloc(sizeof(LinkNode));
    p_new->data=x;
    p_new->next=NULL;
    Q.rear->next=p_new;
    Q.rear=p_new;
}

//出队
bool del_queue(LinkQueue &Q, int &x) {
    if (Q.rear==Q.front) {
        return false;
    }
    LinkNode* q=Q.front->next;
    x=q->data;
    Q.front->next=q->next;
    if (Q.rear==q) {
        Q.rear=Q.front;//链表只剩余一个结点时,被删除后,要改变rear
    }
    free(q);
    return true;
}

int main() {
    LinkQueue Q;
    init_queue(Q);
    ent_queue(Q,1);
    ent_queue(Q,2);

    int element;
    bool ret;
    ret=del_queue(Q,element);
    if (ret) {
        printf("del_queue: %d\n",element);
    }else {
        printf("del_queue fail\n");
    }

    del_queue(Q,element);
    ret=del_queue(Q,element);
    if (ret) {
        printf("del_queue: %d\n",element);
    }else {
        printf("del_queue fail\n");
    }
    return 0;
}

del_queue: 1
del_queue fail

双端队列

• 双端队列是指允许两端都可以进行入队和出队操作的队列

• 输入受限的双端队列

• 输出受限的双端队列

栈和队列的应用

• 所谓能算: 根据扫描的结果以及运算顺序进行判断
• 中缀表达式快速转化为后缀表达式: 括号括起两个直接操作数, 操作符提到括号后, 最后去掉括号, 按运算顺序依次进行
• 中缀表达式按步依次转化为后缀表达式: 按顺序扫描表达式, 只有操作符进栈, 能算时操作符就出栈
• 通过后缀表达示计算表达式的值: 顺序扫描表达式, 不能算就压栈, 能算就把算得的结果压栈, 之后继续扫描表达式

栈在括号匹配中的应用

• 中缀表达式转化为后缀表达式

栈在表达式求值中的应用

• 中缀表达式转化为后缀表达式
• 通过后缀表达示计算表达式的值

栈在递归中的应用

• 可以将递归算法转换为非递归算法，通常需要借助栈来实现这种转换

队列在层次遍历中的应用

• 层序遍历二叉树

队列在计算机系统中的应用

• 缓冲区
• CPU资源竞争

数组和特殊矩阵

• 描述矩阵元素时, 行、列号通常从 1 开始; 而描述数组时下标默认从0开始
• 注意上下三角矩阵?, 行优先?, 列优先?, 矩阵下标?, 数组下标?

数组的存储结构

• 一维数组: 数组数据类型 -> 顺序表
• 多维数组: 按行优先和按列优先存储
• 矩阵可用二维数组存储

特殊矩阵的压缩存储

• 压缩存储：指为多个值相同的元素只分配一个存储空间, 对零元素不分配存储空间, 其目的是节省存储空间
• 特殊矩阵: 对称矩阵、上(下)三角矩阵、三对角矩阵(带状矩阵); 稀疏矩阵
• 特殊矩阵的压缩存储方法：找出特殊矩阵中值相同的矩阵元素的分布规律, 把那些呈现规律性分布的、值相同的多个矩阵元素压缩存储到一个存储空间中

---

• 对称矩阵: 只存储主对角线 + 下三角区
• 数组大小为: n(n+1)/2
• 按行优先: 矩阵下标 -> 一维数组下标: a(i,j) -> i(i-1)/2 + j - 1

---

• 上(下)三角矩阵: 存储主对角线 + 三角区 + 常数
• 数组大小为: n(n+1)/2 + 1
• 数组最后一个元素下标: n(n+1)/2

---

• 三对角矩阵(带状矩阵): 只存储带状部分
• 数组大小为: 3n-2
• 按行优先: 矩阵下标 -> 一维数组下标: a(i,j) -> 2i + j - 3

---

• 稀疏矩阵: 非零元素远远少于矩阵元素的个数
• 顺序存储: 三元组(行列值)
• 链式存储: 十字链表法

串

• 空串

• 空袼串: 由一个或多个空格(空格是特殊字符)组成的串

• 空格串不是空串, 其长度为串中空格字符的个数

• 子串, 主串

• 串中任意多个连续的字符组成的子序列称为该串的子串, 包含子串的串称为主串

• 某个字符在串中的序号称为该字符在串中的位置

• 子串在主串中的位置以子串的第一个字符在主串中的位置来表示

• 当两个串的长度相等且每个对应位置的字符都相等时, 称这两个串是相等的

• 求next与nextval数组: 目测接下来将要匹配的位序(1开头的那个), 即next数组对应的值, 如果是nextval数组的话, 那再考虑将要匹配的是否肯定匹配不上

串的存储结构

• 定长顺序存储
• 堆分配存储
• 块链存储

#define MaxSize 99
typedef struct {
    char ch[MaxSize];
    int length;
} SqString;

#define MaxSize 99
typedef struct {
    char ch[MaxSize]; // must endswith(`\0`)
} SqString;

typedef struct {
    char *ch;
    int length;
} HeapString;

• 每个节点称为块, 整个链表称为块链结构

typedef struct LinkNode{
    char *ch;
    LinkNode *next;
} *LinkString;

串的模式匹配

• 子串的定位操作通常称为串的模式匹配, 它求的是子串(常称模式串)在主串中的位置

简单的模式匹配算法

• 暴力匹配算法
• 简单模式匹配算法的最坏时间复杂度为 O(nm), 其中 n 和 m 分别为主串和模式串的长度

#include <stdio.h>

#define MaxSize 99
typedef struct {
    char ch[MaxSize];
    int length;
} SqString;

// S: 主串, T: 模式串
int index_string (SqString _S, SqString _T) {
    int i = 1, 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;
    }

}

int main () {
    SqString S = {"000000001", 9};
    SqString T = {"00001", 5};
    int pos = index_string(S, T);
    printf("%d", pos); // 5
}

KMP算法

• 某年某月某日…

// T: 模式串
void get_next(SqString T, int next[]) {
    int i = 1;
    int j = 0;
    next[1] = 0;
    while (i < T.length) {
        if (0 == j || T.ch[i] == T.ch[j]) {
            ++i; ++j;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
}

// S: 主串, T: 模式串
int insex_kmp(SqString S, SqString T, int next[]) {
    int i = 1, j = 1;
    while (i<=S.length && j<=T.length) {
        if (0==j || S.ch[i] == T.ch[j]) {
            ++i; ++j;
        } else {
            j = next[j];
        }
    }
    if (j>T.length) {
        return i - T.length;
    } else {
        return 0;
    }
}

void get_nextval(SqString T, int nextval[]) {
    int i = 1, j = 0;
    nextval[1] = 0;
    while (i<T.length) {
        if (0 == j || T.ch[i] == T.ch[j]) {
            ++i; ++j;
            if (T.ch[i] != T.ch[j]) {
                nextval[i] = j;
            } else {
                nextval[i] = nextval[j];
            }
        } else {
            j = nextval[j];
        }
    }
}

• kmp算法时间复杂度为 O(m + n), 其优点为主串不回溯

树

• 树是n(n≥0)个结点的有限集,当n = 0时,称为空树

• 树是一种逻辑结构,同时也是一种分层结构

• 树的根结点没有前驱,除根结点外的所有结点有且只有一个前驱

• 树中所有结点可以有零个或多个后继

• 树中一个结点的孩子个数称为该结点的度, 树中结点的最大度数称为树的度

• 度大于 0 的结点称为分支结点(又称非终端结点), 度为 0 (没有子女结点)的结点称为叶结点(又称终端结点)

• 树的高度(或深度)是树中结点的最大层数

• 二叉树的子树有左右之分, 其次序不能任意颠倒

• 树中结点的各子树从左到右是有次序的, 不能互换, 称该树为有序树, 否则称为无序树

• 树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的, 而路径长度是路径上所经过的边的个数

• 森林是(m>=0)棵互不相交的树的集合, 只要把树的根结点删去就成了森林

• 对于树: 一棵有n个结点的树的所有结点的度数之和为n-1, 边的数量为n - 1
• 对与树: 总结点数 = 总分支数 + 1
• 对于二叉树: 叶结点数等于度为 2 的结点数加 1
• 对于二叉树: 若总结点数为n, 则其高的范围为: [log2 n] + 1 ~ n
• 对于二叉树: 若只有度为0和2的结点, 其深度为h, 则结点总数为2h - 1
• 对于二叉链表: 若总结点数为n, 则含有n + 1个空链域(空指针数)
• 对于完全二叉树: 有个编号为i的结点, 则左孩子编号为2i(2i<=n), 右孩子编号为2i+1(2i+1<=n), 深度为[log2 i] + 1, 最后一个分支结点序号[n/2](n为总结点数)

---

• 由遍历序列构造二叉树
• 唯一确定二叉树: 先序序列和中序序列, 中序序列和后序序列, 层序序列和中序序列
• 不能唯一确定二叉树: 先序序列和后序序列

---

• 线索二叉树是一种物理结构
• 线索二叉树只是为了方便遍历, 其中后序线索二叉树中求后序后继仍不能有效解决

---

• 快速写出遍历序列可以先关注最小单位的二叉树的遍历顺序再注意整体的遍历顺序
• 某某结点在某某结点的左方或右方和左兄弟或右兄弟不一样
• 最右结点和最右叶结点不一样
• 二叉树前序序列和中序序列的关系相当于以前序序列为入栈次序, 中序序列为出栈次序
• 树或森林转化为二叉树, 树或森林的分支结点数 + 1(根节点对应的) = 转化的二叉树的无右孩子结点数
• 树或森林与对应的二叉树相互转换, 其先序(根)遍历, 后序(根)遍历序列不变
• 树或森林转换为二叉树的本质: 只是用孩子兄弟表示法存储树或森林, 在形态上与二叉树类似

二叉树

• 二叉树是另一种树形结构,其特点是每个结点至多只有两棵子树(即二叉树中不存在度大于2的结点), 并且二叉树的子树有左右之分, 其次序不能任意颠倒

• 二叉树是n(n≥0)个结点的有限集合:

  • 或者为空二叉树,即 n = 0
  • 或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成,左子树和右子树又分别是一棵二叉树

• 满二叉树: 树的每层都含有最多结点, 即共含有2^h - 1(h为树的高度)个结点

• 完全二叉树: 若有度为 1 的结点, 则只可能有一个, 且该结点只有左孩子而无右孩子

• 二叉排序树: 左子树上所有结点的关键字均小于根结点的关键字, 右子树上的所有结点的关键字均大于根结点的关键字, 左子树和右子树又各是一棵二叉排序树

• 平衡二叉树: 树上任意一个结点的左子树和右子树的深度之差不超过 1

• calloc申请空间大小是其传入的两个参数相乘

• calloc申请空间和malloc的区别在于,申请空间后,会对申请的空间内容全部初始化为0

二叉树的遍历

• 二叉树的层次建树与前序, 中序, 后序, 层序遍历
• 二叉树层次建树需使用辅助队列
• 使用辅助队列进行二叉树层次建树时,队列中的结点值放置的是树中某结点的地址值
• 前序遍历是先打印当前结点, 再打印左子树, 再打印右子树, 前序遍历, 也叫先序遍历, 深度优先遍历
• 中序遍历是先打印左子树, 再打印当前结点, 再打印右子树
• 后序遍历是先打印左子树, 再打印右子树, 最后打印当前结点
• 层序遍历, 也叫层次遍历, 广度优先遍历

• 前序遍历
• 中序遍历
• 后序遍历
• 层序遍历
• code
• debug

//前序遍历,也叫先序遍历,也是深度优先遍历
void pre_order(bitree p) {
    if(p!=NULL)
    {
        printf("%c", p->c);
        pre_order(p->left);//打印左子树
        pre_order(p->right);//打印右子树
    }
}

//中序遍历
void in_order(bitree p) {
    if(p!=NULL)
    {
        in_order(p->left);//打印左子树
        printf("%c", p->c);
        in_order(p->right);//打印右子树
    }
}

//后序遍历
void post_order(bitree p) {
    if(p!=NULL)
    {
        post_order(p->left);//打印左子树
        post_order(p->right);//打印右子树
        printf("%c", p->c);
    }
}

//层次遍历,层序遍历,广度优先遍历
void level_order(bitree T) {
    link_queue Q;
    init_queue(Q);
    bitree p;//存储出队的结点
    ent_queue(Q,T);//把根入队
    while(!is_queue_empty(Q)) {
        del_queue(Q,p);
        putchar(p->c);//等价于printf("%c",c);
        if (p->left) {
            ent_queue(Q,p->left);//左孩子不为空,就入队左孩子
        }
        if (p->right) {
            ent_queue(Q,p->right);//右孩子不为空,就入队右孩子
        }
    }
}

#include <stdio.h>
#include <stdlib.h>

typedef char bitree_data_type;
typedef struct bitree_node{
    bitree_data_type c;
    struct bitree_node *left;
    struct bitree_node *right;
}bitree_node, *bitree;

typedef struct bitree_queue_node{
    bitree p;
    struct bitree_queue_node *next;
}bitree_queue_node, *bitree_queue;


//前序遍历,也叫先序遍历,也是深度优先遍历
void pre_order(bitree p) {
    if(p!=NULL)
    {
        printf("%c", p->c);
        pre_order(p->left);//打印左子树
        pre_order(p->right);//打印右子树
    }
}

//中序遍历
void in_order(bitree p) {
    if(p!=NULL)
    {
        in_order(p->left);//打印左子树
        printf("%c", p->c);
        in_order(p->right);//打印右子树
    }
}

//后序遍历
void post_order(bitree p) {
    if(p!=NULL)
    {
        post_order(p->left);//打印左子树
        post_order(p->right);//打印右子树
        printf("%c", p->c);
    }
}


typedef bitree queue_data_type;
typedef struct link_node{
	queue_data_type data;
	struct link_node *next;
}link_node;

typedef struct{
	link_node *front,*rear;//链表头 链表尾,也可以称为队头,队尾
}link_queue;//先进先出


bool is_queue_empty(link_queue Q) {
    return Q.rear==Q.front;
}

//队列的初始化,使用的是带头结点的链表来实现的
void init_queue(link_queue &Q) {
    Q.front=Q.rear=(link_node *)malloc(sizeof(link_node));
    Q.front->next=NULL;
}

//入队
void ent_queue(link_queue &Q,queue_data_type x) {
    link_node *p_new=(link_node *)malloc(sizeof(link_node));
    p_new->data=x;
    p_new->next=NULL;
    Q.rear->next=p_new;
    Q.rear=p_new;
}

//出队
bool del_queue(link_queue &Q,queue_data_type &x) {
    if (Q.rear==Q.front) {
        return false;
    }
    link_node* q=Q.front->next;
    x=q->data;
    Q.front->next=q->next;
    if (Q.rear==q) {
        Q.rear=Q.front;//链表只剩余一个结点时,被删除后,要改变rear
    }
    free(q);
    return true;
}

//层次遍历,层序遍历,广度优先遍历
void level_order(bitree T) {
    link_queue Q;
    init_queue(Q);
    bitree p;//存储出队的结点
    ent_queue(Q,T);//把根入队
    while(!is_queue_empty(Q)) {
        del_queue(Q,p);
        putchar(p->c);//等价于printf("%c",c);
        if (p->left) {
            ent_queue(Q,p->left);//左孩子不为空,就入队左孩子
        }
        if (p->right) {
            ent_queue(Q,p->right);//右孩子不为空,就入队右孩子
        }
    }
}

int main() {
    char c;
    bitree bitree_new;
    bitree tree_root=NULL;
    bitree_queue bitree_queue_new=NULL;
    bitree_queue bitree_queue_head=NULL, bitree_queue_tail=NULL;
    bitree_queue bitree_queue_cur;
    //abcdef
    while (scanf("%c",&c)) {
        if (c=='\n') {
            break;
        }
        bitree_new = (bitree)calloc(1, sizeof(bitree_node));
        bitree_new->c = c;
        bitree_queue_new = (bitree_queue)calloc(1, sizeof(bitree_queue_node));
        bitree_queue_new->p = bitree_new;
        if (NULL==tree_root) {
            tree_root = bitree_new;
            bitree_queue_head = bitree_queue_new;
            bitree_queue_tail = bitree_queue_new;
            bitree_queue_cur=bitree_queue_new;
        }else {
            bitree_queue_tail->next = bitree_queue_new;
            bitree_queue_tail=bitree_queue_new;
            if(NULL==bitree_queue_cur->p->left) {
                bitree_queue_cur->p->left = bitree_new;
            }else if (NULL==bitree_queue_cur->p->right) {
                bitree_queue_cur->p->right=bitree_new;
                bitree_queue_cur=bitree_queue_cur->next;
            }
        }
    }
    pre_order(tree_root);
    printf("\n");
    in_order(tree_root);
    printf("\n");
    post_order(tree_root);
    printf("\n");
    level_order(tree_root);
    printf("\n");
    return 0;
}

abcdef
abdecf
dbeafc
debfca
abcdef

线索二叉树

• 引入线索二叉树是为了加快查找结点直接前驱和直接后继的速度, 像遍历单链表那样方便遍历二叉树

• 规定: 若无左子树, 令 lchild 指向其前驱结点; 若无右子树, 令 rchild 指向其后继结点; 此外还需增加两个标志域标识指针域, 以指向左(右)孩子或前驱(后继)

• tag 为 0: 指向左孩子或右孩子; tag为1: 指向前驱或后继

• 其中指向结点前驱和后继的指针称为线索

• 二叉树的线索化是将二叉链表中的空指针改为指向前驱或后继的线索, 而前驱或后继的信息只有在遍历时才能得到, 因此线索化的实质就是遍历一次二叉树

typedef int ElemType;
typedef struct ThreadNode {
    ElemType data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag;
} ThreadNode, *ThreadTree;

树的存储结构

• 双亲表示法
• 孩子表示法
• 孩子兄弟表示法(二叉树表示法)

#define MaxSize 99
typedef int ElemType;
typedef struct {
    ElemType data;
    int parent;
} PNode;
typedef struct {
    PNode nodes[MaxSize];
    int n;
} PTree;

//

typedef struct CSNode {
    ElemType data;
    struct CSNode  *first_child, *next_sibling;
} CSNode, *CSTree;

树和森林与二叉树的转换

• 由于二叉树和树都可以用二叉链表作为存储结构, 因此以二叉链表作为媒介可以导出树与二叉树的一个对应关系, 即给定一棵树, 可以找到唯一的一棵二叉树与之对应

• 从物理结构上看, 它们的二叉链表是相同的, 只是解释不同而己

• 树转二叉树, 二叉树转树

• 森林转二叉树, 二叉树转森林

树和森林的遍历

• 树的遍历是指用某种方式访问树中的每个结点, 且仅访问一次
• 另外, 树也有层次遍历, 与二叉树的层次遍历思想基本相同, 即按层序依次访问各结点

先根遍历树	后根遍历树
1: 先访问根结点	1: 先依次遍历根结点的每棵子树(遍历子树时仍遵循先子树后根的规则), 其遍历序列与这棵树相应二叉树的中序序列相同
2: 再依次遍历根结点的每棵子树(遍历子树时仍遵循先根后子树的规则), 其遍历序列与这棵树相应二叉树的先序序列相同	2: 再访问根结点

---

• 邯分教材也森林的中序遍历称为后序遍历, 称中序遍历是相对其二叉树而言的, 称后序遍历是因为根确实最后才访问的

先序遍历森林	中序遍历森林
1: 访问森林中第一棵树的根结点	1: 中序遍历森林中第一棵树的根结点的子树森林
2: 先序遍历第一棵树中根结点的子树森林	2: 访问第一棵树的根结点
3: 先序遍历除去第一棵树之后剩余的树构成的森林	3: 中序遍历除去第一棵树之后剩余的树构成的森林

---

树	森林	二叉树
先根遍历	先序遍历	先序遍历
后根遍历	中序遍历	中序遍历

树与二叉树的应用

• 构造最优二叉树注意选权值最小的两个结点合并, 并让其作为一个新的结点(可能新结点的权值比较大, 这时先合并其它结点)
• 并查集是逻辑结构, 一种借由树和森林实现的集合

哈夫曼树和哈夫曼编码

• 结点的权: 有某种现实含义的数值
• 结点的带权路径长度: 从树的根到该结点的路径长度(经过的边数)与该结点上权值的乘积
• 树的带权路径长度(WPL, Weighted Path Length): 树中所有叶结点的带权路径长度之和
• 在含有n个带权叶结点的二叉树中, 其中带权路径长度 (WPL) 最小的二叉树称为哈夫曼树, 又称最优二叉树, 结点总数为 2n - 1
• 哈夫曼树中不存在度为 1 的结点
• 哈夫曼树并不唯一, 但 WPL 必然相同且为最优
• 构造哈夫曼树: 每次选两个根节点权值最小的树合并, 并将二者权值之和作为新的根节点的权值

---

• 将字符频次作为字符结点权值, 构造哈夫曼树, 即可得哈夫曼编码, 可用于数据压缩
• 固定长度编码: 每个字符用相等长度的二进制位表示
• 可变长度编码: 允许对不同字符用不等长的二进制位表示
• 前缀编码: 没有一个编码是另一个编码的前缀
• 可由哈夫曼树得到哈夫曼编码; 哈夫曼树不唯一, 因此哈夫曼编码不唯一

并查集

• 用互不相交的树, 表示多个集合
• 并查集（ Disjoint set) 是逻辑结构, 集合的一种具体实现, 只进行 “ 并 ” 和 “ 查 ” 两种基本操作
• Union 操作的优化: 在每次 Union 操作构建树的时候, 尽可能让树不长高高; 用根节点的绝对值表示树的结点总数, 让小树合并到大树
• Union 操作优化后, Find 操作最坏时间复杂度: O(log2 n)
• Find 操作的优化(压缩路径): 先找到根节点, 再将查找路径上所有结点都挂到根结点下

图

• 邻接矩阵有向图的方向: 列 -> 行; 于是出度看行, 入度看列

图的定义

• 图 G 由顶点集 V 和边集 E 组成

• |V| 表示图 G 中顶点的个数, 也称图 G 的阶, V一定是非空集, 即图不可以是空

• |E|表示图 G 中边的条数

• 无向图: E 是无向边 （ 简称边 ） 的有限集合; (a, b)

• 有向图: E 是有向边 （ 也称弧 ） 的有限集合; <a, b>: a -> b , 其中 a:弧头, b:弧尾

• 简单图: 不存在重复边, 不存在顶点到自身的边

• 多重图: 与简单图相反

---

点到点的关系

• 无向图顶点 v 的度 TD(v): 依附于该顶点的边的条数

• 无向图所有定点的度之和: 边数乘2 (即2|E|)

• 有向图顶点 v 的度 TD(v): 入度 ID(v) + 出度OD(v)

• 有向图: 入度总数等于出度总数

• 路径: 顶点与顶点之间的顶点序列

• 有向图的路径是有向的

• 顶点之间有可能不存在路径

• 回路: 第一个顶点和最后一个顶点相同的路径称为回路或环

• 简单路径: 在路径序列中, 顶点不重复出现的路径称为简单路径

• 简单回路: 除第一个顶点和最后一个顶点外, 其余顶点不重复出现的回路称为简单回路

• 路径长度: 路径上边的数目

• 顶点到顶点的距离: 它们之间的最短路径存在, 则最短路径的长度为点到点距离; 不存在路径, 则记该距离为无穷

• 无向图中, 若从顶点 v 到顶点 w 有路径存在, 则称 v 和 w 是连通的

• 有向图中, 若从顶点 v 到顶点 w 和从顶点 w 到顶点 v 之间都有路径, 则称这两个顶点是强连通的

• 若图 G 中任意两个顶点都是连通的, 则称图 G 为连通图, 否则称为非连通图

• 若图中任何一对顶点都是强连通的, 则称此图为强连通图

• 对于 n 个顶点的无向图 G, 若 G 是连通图, 则最少有 n-1 条边; 若 G 是非连通图, 则最多可能有 C n-1 2 条边

• 对于 n 个顶点的有向图 G, 若 G 是强连通图, 则最少有 n 条边 （ 即形成回路 ）

---

图的局部

• 子图: 取顶点集的子集和边集的子集, 并能符合图的定义

• 生成子图: 子图的顶点集包含所有顶点, 边集包含部分边

• 连通分量: 无向图中的极大连通子图称为连通分量

• 极大连通子图: 子图必须连通, 且包含尽可能多的顶点和边

• 强连通分量: 有向图中的极大强连通子图称为有向图的强连通分量

• 极大强连通子图: 子图必须强连通, 同时保留尽可能多的边

• 连通图的生成树是包含图中全部顶点的一个极小连通子图

• 极小连通子图: 边尽可能的少, 但要保持连通

• 若图中顶点数为 n , 则它的生成树含有 n-1 条边; 对生成树而言, 若砍去它的一条边, 则会变成非连通图, 若加上一条边则会形成一个回路

• 极小和极大是在满足连通的前提下, 针对边的数目而言的

• 极大连通子图包含连通分量的全部边

• 极小连通子图 （ 生成树 ） 包含连通图的全部顶点, 且使其连通的边数最少

• 在非连通图中, 连通分量的生成树构成了非连通图的生成森林

• 边的权: 在一个图中, 每条边都可以标上具有某种含义的数值, 该数值称为该边的权值

• 带权图 / 网: 边上带有权值的图称为带权图 , 也称网

• 带权路径长度: 当图是带权图时, 一条路径上所有边的权值之和, 称为该路径的带权路径长度

---

几种特殊的图

• 无向完全图: 无向图中任意两个顶点之间都存在边

• 有向完全图: 有向图中任意两个顶点之间都存在方向相反的两条弧

• 边数很少的图称为稀疏图, 反之称为稠密图

• 树: 不存在回路, 且连通的无向图

• n 个顶点的树, 必有 n-1 条边

• n 个顶点的图, 若 |E| > n - 1 , 则一定有回路

• 森林: 各个子图是极小连通的

• 有向树: 一个顶点的入度为 0, 其余顶点的入度均为 1 的有向图, 称为有向树

图的存储

邻接矩阵法

• 无向图: 第i个结点的度 = 第i行（或第i列）的非零元素个数
• 有向图: 第i个结点的出度 = 第i行的非零元素个数
• 有向图: 第i个结点的入度 = 第i列的非零元素个数
• 有向图: 第i个结点的度 = 第i行、第i列的非零元素个数之和
• 邻接矩阵法求顶点的度/出度/入度的时间复杂度为 O(|V|)
• 邻接矩阵法存储带权图（网）: 顶点 -> 自己: 0, 顶点 -> 无路径的顶点: ∞
• 空间复杂度：O(|V|2) ——只和顶点数相关，和实际的边数无关
• 数组实现的顺序存储，空间复杂度高，不适合存储稀疏图
• 无向图的邻接矩阵是对称矩阵，可以压缩存储（只存储上三角区/下三角区）
• 设图G的邻接矩阵为A（矩阵元素为0/1），则An的元素An[i][j]等于由顶点i到顶点j的长度为n的路径的数目
• 只要确定了顶点编号，图的邻接矩阵表示方式唯一

---

邻接表法 (顺序+链式存储)

• 无向图: 边结点的数量是2|E|，整体空间复杂度为 O(|V| + 2|E|)
• 有向图: 边结点的数量是|E|，整体空间复杂度为 O(|V| + |E|)
• 图的邻接表表示方式并不唯一

---

十字链表 (存储有向图)

• 空间复杂度：O(|V|+|E|)

---

邻接多重表 (存储无向图)

• 空间复杂度：O(|V|+|E|)

---

	邻接矩阵	邻接表	十字链表	邻接多重表
空间复杂度	O(|V|2)	无向图 O(|V| + 2|E|), 有向图O(|V| + |E|)	O(|V| + |E|)	O(|V| + |E|)
找相邻的边	遍历对应行或列, 时间复杂度为O(|V|)	找有向图的入边必须遍历整个邻接表	很方便	很方便
删除边或顶点	删除边很方便，删除顶点需要大量移动数据	无向图中删除边或顶点都不方便	很方便	很方便
适用于	稠密图	稀疏图和其他	只能存有向图	只能存无向图
表示方式	唯一	不唯一	不唯一	不唯一
计算度/出度/入度	必须遍历对应行或列	计算有向图的度、入度不方便，其余很方便

图的基本操作

• 这里只关注于邻接矩阵和邻接表

操作	无向图邻接矩阵	无向图邻接表	有向图邻接矩阵	有向图邻接表
判断是否存在边 <a,b> (a,b)	O(1)	O(1)~O(|V|)	O(1)	O(1)~O(|V|)
列出图G中与结点x邻接的边	O(|V|)	O(1)~O(|V|)	O(|V|)	出边:O(1)~O(|V|), 入边: O(|E|)
在图G中插入顶点x	O(1)	O(1)	O(1)	O(1)
从图G中删除顶点x	O(|V|)	O(1)~O(|E|)	O(|V|)	删出边: O(1)~O(|V|), 删入边: O(|E|)
若无向边(x, y)或有向边<x, y>不存在，则向图G中添加该边	O(1)	O(1)	O(1)	O(1)
若无向边(x, y)或有向边<x, y>存在，则从图G中删除该边	O(1)	O(1)~O(|V|)	O(1)	O(1)~O(|V|)
求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-1	O(1)~O(|V|)	O(1)	O(1)~O(|V|)	找出边邻接点：O(1), 找入边邻接点：O(1) ~O(|E|)
假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1	O(1)~O(|V|)	O(1)

图的遍历

⼴度优先遍历（Breadth-First-Search, BFS）

• 搜索相邻的顶点时，有可能搜到已经访问过的顶点

• 找到与⼀个顶点相邻的所有顶点, 标记哪些顶点被访问过, 需要⼀个辅助队列

• 同⼀个图的邻接矩阵表示⽅式唯⼀，因此⼴度优先遍历序列唯⼀

• 同⼀个图邻接表表示⽅式不唯⼀，因此⼴度优先遍历序列不唯⼀

• 如果是⾮连通图，则⽆法遍历完所有结点, 可采取多次调用BFS函数解决; 对于⽆向图，调⽤BFS函数的次数=连通分量数

• 空间复杂度：最坏情况，辅助队列⼤⼩为 O(|V|)

• 邻接矩阵存储的图：时间复杂度= O(|V|2)

• 邻接表存储的图：时间复杂度= O(|V|+|E|)

⼴度优先⽣成树, ⼴度优先⽣成森林

• ⼴度优先⽣成树由⼴度优先遍历过程确定。由于邻接表的表示⽅式不唯⼀，因此基于邻接表的⼴度优先⽣成树也不唯⼀
• 对⾮连通图的⼴度优先遍历，可得到⼴度优先⽣成森林

---

深度优先遍历

• 空间复杂度：来⾃函数调⽤栈，最坏情况，递归深度为O(|V|); 最好情况，O(1)
• 邻接矩阵存储的图：时间复杂度= O(|V|2)
• 邻接表存储的图：时间复杂度= O(|V|+|E|)
• 同⼀个图的邻接矩阵表示⽅式唯⼀，因此深度优先遍历序列唯⼀
• 同⼀个图邻接表表示⽅式不唯⼀，因此深度优先遍历序列不唯⼀

深度优先生成树, 深度优先⽣成森林

• 同⼀个图的邻接矩阵表示⽅式唯⼀，因此深度优先遍历序列唯⼀，深度优先⽣成树也唯⼀
• 同⼀个图邻接表表示⽅式不唯⼀，因此深度优先遍历序列不唯⼀，深度优先⽣成树也不唯⼀

---

图的遍历与图的连通性

• 对⽆向图进⾏BFS/DFS遍历调⽤BFS/DFS函数的次数=连通分量数

• 对于连通图，只需调⽤1次 BFS/DFS

• 对有向图进⾏BFS/DFS遍历, 调⽤BFS/DFS函数的次数要具体问题具体分析

• 若起始顶点到其他各顶点都有路径，则只需调⽤1次BFS/DFS 函数

• 对于强连通图，从任⼀结点出发都只需调⽤1次 BFS/DFS

• 时间复杂度=访问各结点所需时间+探索各条边所需时间

图的应用

• 最小生成树(连接所有顶点耗权最短): 在一个连通图中依靠权值最小的边依次重新构建极小连通子图, 边多就从顶点开始, 边少就从边开始

• Prim 算法(从顶点开始构造最小生成树):

  • is_join[n]存储各节点是否已加⼊树, low_cost[n]存储各节点加⼊树的最低代价
  • 循环遍历 n-1 轮，每轮 ( 循环遍历所有结点, 找到low_cost最低的且还没加⼊树的顶点, 和循环遍历所有结点, 更新还没加⼊的各个顶点的low_cost值 )
  • 时间复杂度：O(|V|2)

• Kruskal 算法(从边开始构造最小生成树):

  • 将各条边按权值排序, 循环遍历 e 轮，每轮判断两个顶点是否属于同⼀集合(并查集)
  • 时间复杂度：O( |E|log2|E| )

---

• 单源最短路径:

• BFS 算法: 广度优先遍历时, 修改最短路径长度(dist[n]), 路径上的前驱(path[n]), 标记各结点是否已被访问(visited[n])

  • 时间复杂度: O(\|V\|2)或O(\|V\|+\|E\|)

• Dijkstra 算法:

  • final[n]存储标记各顶点是否已找到最短路径, dist[n]存储最短路径长度, path[n]存储路径上的前驱
  • 循环遍历 n-1 轮, 每轮循环遍历所有顶点，找到还没确定最短路径且 dist 最⼩的顶点, 并检查所有邻接的顶点, 判断是否更新其它顶点的 dist和path
  • 时间复杂度: O(\|V\|2)

• 各顶点间的最短路径:

• Floyd 算法:

  • 矩阵A存储各顶点间最短路径, 矩阵path存储两个顶点之间的中转点
  • 循环遍历 n 个中转点, 每轮循环遍历整个矩阵A, 判断以此中转点的路径是否更短, 并更新矩阵A和矩阵path
  • 时间复杂度: O(\|V\|3)

---

• 有向无环图描述表达式: 优化树存储表达式可能浪费内存的缺点

---

• 括扑排序:

  • indegree[n]保存当前顶点入度, 用栈或队列保存入度为 0 的顶点, print[n]存储括扑序列
  • 先将indegree[n]入度为 0 的顶点进栈或队列, 循环 ( 出栈或队列, 更新print[n]和indegree[n], 将indegree[n]入度为 0 的顶点进栈或队列), 直到栈或队列为空
  • 寻找有向无环图入度为0的顶点, 假设删除此顶点和它相邻的边, 删除顶点的序列即括扑排序序列, 此序列包含图中全部顶点
  • 时间复杂度: O(|V|2)或O(|V|+|E|)

• DFS实现逆括扑排序: 在顶点退栈前输出

• 关键路径: 寻找带权有向图的带权路径长度最大的路径

---

• 邻接矩阵对角线以上元素全为 1, 以下全为 0 -> 括扑序列唯一
• 邻接矩阵对角线以上或下元素全为 0 -> 括扑序列不一定唯一
• 快速计算某活动的时间余量: 如果此活动不在关键路径上, 找到所有与此边形成的三角形, 并根据三角形为单位计算时间余量, 所得的最大的时间余量就是该活动的时间余量, 其它舍去; 如果此活动在关键路径上, 时间余量为 0

最小生成树

• 最⼩⽣成树（最⼩代价树）（Minimum-Spanning-Tree, MST）

• 连通图的生成树是包含图中全部顶点的一个极小连通子图。

• 若图中顶点数为n，则它的生成树含有 n-1 条边。对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。

• 对于⼀个带权连通⽆向图G = (V, E)，⽣成树不同，每棵树的权（即树中所有边上的权值之和）也可能不同。设R为G的所有⽣成树的集合，若T为R中边的权值之和最⼩的⽣成树，则T称为G的最⼩⽣成树（Minimum-Spanning-Tree, MST）。

• 最⼩⽣成树可能有多个，但边的权值之和(最小代价)总是唯⼀且最⼩的

• 最⼩⽣成树的边数 = 顶点数 - 1。砍掉⼀条则不连通，增加⼀条边则会出现回路

• 如果⼀个连通图本身就是⼀棵树，则其最⼩⽣成树就是它本身

• 只有连通图才有⽣成树，⾮连通图只有⽣成森林

• 只要无向连通图中没有权值相同的边, 则其最小生成树唯一

---

Prim 算法

• 每次将代价最⼩的新顶点纳⼊⽣成树，直到所有顶点都纳⼊为⽌
• 适合⽤于边稠密图

---

• 需要两个数组存储: 标记各节点是否已加⼊树(is_join[n]), 各节点加⼊树的最低代价(low_cost[n])
• 每⼀轮处理：循环遍历所有个结点，找到low_cost最低的，且还没加⼊树的顶点。再次循环遍历，更新还没加⼊的各个顶点的low_cost值
• 时间复杂度：O(|V|2) (每一轮 O(2n), 共 n-1 轮)

---

Kruskal 算法

• 每次选择⼀条权值最⼩的边，使这条边的两头连通（原本已经连通的就不选）直到所有结点都连通
• 适合⽤于边稀疏图

---

• 初始: 将各条边按权值排序 (并查集)
• 共执⾏ e 轮，每轮判断两个顶点是否属于同⼀集合，需要 O(log2e)
• 时间复杂度：O( |E|log2|E| )

最短路径

单源最短路径

BFS 算法 (无权图)

• ⽆权图可以视为⼀种特殊的带权图，只是每条边的权值都为1
• 需要用三个数组存储: 最短路径长度(dist[n]), 路径上的前驱(path[n]), 标记各结点是否已被访问(visited[n])
• 只是对BFS的⼩修改，在visit⼀个顶点时，修改其最短路径⻓度 dist[ ] 并在 path[ ] 记录前驱结点
• 其⼴度优先⽣成树⼀定是以某顶点为根的，⾼度最⼩的⽣成树
• BFS算法求单源最短路径只适⽤于⽆权图，或所有边的权值都相同的图

Dijkstra 算法 (带权图, 无权图)

• 需要用三个数组存储: 标记各顶点是否已找到最短路径(final[n]), 最短路径长度(dist[n]), 路径上的前驱(path[n])
• 时间复杂度：O(n2)即O(|V|2)
• Dijkstra 算法不适⽤于有负权值的带权图
• 可⽤ Dijkstra 算法求所有顶点间的最短路径，重复 |V| 次即可，总的时间复杂度是O(|V|3)

---

各顶点间的最短路径

Floyd 算法 (带权图, 无权图)

• 求出每⼀对顶点之间的最短路径, 依次增加顶点, 再计算是否更短
• 时间复杂度，O(|V|3)
• 空间复杂度，O(|V|2)
• 可以⽤于负权值带权图
• Floyd 算法不能解决带有“负权回路”的图（有负权值的边组成回路），这种图有可能没有最短路径

---

	BFS 算法	Dijkstra 算法	Floyd 算法
⽆权图	✔	✔	✔
带权图	❌	✔	✔
带负权值的图	❌	❌	✔
带负权回路的图	❌	❌	❌
时间复杂度	O(|V|2)或O(|V|+|E|)	O(|V|2)	O(|V|3)
通常⽤于	求⽆权图的单源最短路径	求带权图的单源最短路径	求带权图中各顶点间的最短路径

有向无环图描述表达式

• 有向⽆环图：若⼀个有向图中不存在环，则称为有向⽆环图，简称DAG图（Directed Acyclic Graph）

描述表达式

• 本来可以用树描述表达式的, 但某些运算重复了, 为了节省内存, 于是用有向无环图描述表达式

• 1. 把各个操作数不重复地排成⼀排
• 2. 标出各个运算符的⽣效顺序（先后顺序有点出⼊⽆所谓）
• 3. 按顺序加⼊运算符，注意“分层”
• 4. 从底向上逐层检查同层的运算符是否可以合体

括扑排序

拓扑排序

• AOV⽹(Activity On Vertex NetWork，⽤顶点表示活动的⽹)：

• ⽤DAG图（有向⽆环图）表示⼀个⼯程。顶点表示活动，有向边<Vi, Vj>表示活动Vi必须先于活动Vj进⾏

• 在图论中，由⼀个有向⽆环图的顶点组成的序列，当且仅当满⾜下列条件时，称为该图的⼀个拓扑排序：

  • 1. 每个顶点出现且只出现⼀次。
  • 2. 若顶点A在序列中排在顶点B的前⾯，则在图中不存在从顶点B到顶点A的路径。

• 拓扑排序是对有向⽆环图的顶点的⼀种排序，它使得若存在⼀条从顶点A到顶点B的路径，则在排序中顶点B出现在顶点A的后⾯。每个AOV⽹都有⼀个或多个拓扑排序序列。

• 拓扑排序：找到做事的先后顺序

• 拓扑排序的实现：

  • 1. 从AOV⽹中选择⼀个没有前驱（⼊度为0）的顶点并输出。
  • 2. 从⽹中删除该顶点和所有以它为起点的有向边。
  • 3. 重复1和2直到当前的AOV⽹为空或当前⽹中不存在⽆前驱的顶点为⽌。

• 当前所有顶点⼊度>0，说明原图存在回路

• 若采⽤邻接矩阵，时间复杂度: O(|V|2)

• 若采用邻接表, 时间复杂度：O(|V|+|E|)

---

逆拓扑排序

• 对⼀个AOV⽹，如果采⽤下列步骤进⾏排序，则称之为逆拓扑排序：

  • 1. 从AOV⽹中选择⼀个没有后继（出度为0）的顶点并输出。
  • 2. 从⽹中删除该顶点和所有以它为终点的有向边。
  • 3. 重复1和2直到当前的AOV⽹为空。

• 使用邻接矩阵比邻接表更好, 但如果用逆邻接表的话, 也可以

---

用 DFS 实现拓扑排序 / 逆拓扑排序

• DFS 实现逆拓扑排序: 在顶点退栈前输出
• 存在回路需要判断

关键路径

• 在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销（如完成活动所需的时间），称之为⽤边表示活动的⽹络，简称AOE⽹ (Activity On Edge NetWork)

• AOE⽹具有以下两个性质：

  • 1. 只有在某顶点所代表的事件发⽣后，从该顶点出发的各有向边所代表的活动才能开始；
  • 2. 只有在进⼊某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发⽣。
  • 另外，有些活动是可以并⾏进⾏的

• 在AOE⽹中仅有⼀个⼊度为0的顶点，称为开始顶点（源点），它表示整个⼯程的开始；也仅有⼀个出度为0的顶点，称为结束顶点（汇点），它表示整个⼯程的结束。

• 从源点到汇点的有向路径可能有多条，所有路径中，具有最⼤路径⻓度的路径称为关键路径，⽽把关键路径上的活动称为关键活动

• 完成整个⼯程的最短时间就是关键路径的⻓度，若关键活动不能按时完成，则整个⼯程的完成时间就会延⻓

• 事件vk的最早发⽣时间ve(k)——决定了所有从vk开始的活动能够开⼯的最早时间

• 活动ai的最早开始时间e(i)——指该活动弧的起点所表⽰的事件的最早发⽣时间

• 事件vk的最迟发⽣时间vl(k)——它是指在不推迟整个⼯程完成的前提下，该事件最迟必须发⽣的时间。

• 活动ai的最迟开始时间l(i)——它是指该活动弧的终点所表示事件的最迟发⽣时间与该活动所需时间之差。

• 活动ai的时间余量d(i)=l(i)-e(i)，表⽰在不增加完成整个⼯程所需总时间的情况下，活动ai可以拖延的时间

• 求关键路径的步骤

  • 1. 求所有事件的最早发⽣时间 ve( )
  • 2. 求所有事件的最迟发⽣时间 vl( )
  • 3. 求所有活动的最早发⽣时间 e( )
  • 4. 求所有活动的最迟发⽣时间 l( )
  • 5. 求所有活动的时间余量 d( )

关键活动, 关键路径特性

• 若⼀个活动的时间余量为零，则说明该活动必须要如期完成，d(i)=0即l(i) = e(i)的活动ai是关键活动

• 由关键活动组成的路径就是关键路径

• 若关键活动耗时增加，则整个⼯程的⼯期将增⻓

• 缩短关键活动的时间，可以缩短整个⼯程的⼯期

• 当缩短到⼀定程度时，关键活动可能会变成⾮关键活动

• 可能有多条关键路径，只提⾼⼀条关键路径上的关键活动速度并不能缩短整个⼯程的⼯期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短⼯期的⽬的。

查找算法

顺序查找

• 顺序查找又称线性查找, 它对于顺序表和链表都是适用的

• code
• debug

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef int seqlist_data_type;
typedef struct {
    seqlist_data_type *p;
    int len;
}seqlist;


void init_seqlist(seqlist &_seqlist, int _len) {
    _seqlist.len = _len;
    _seqlist.p = (seqlist_data_type *)malloc(
        sizeof(seqlist_data_type)*_seqlist.len
    );
    srand(time(NULL));
    for (int i=0;i<_seqlist.len;i++) {
        _seqlist.p[i] = rand()%100;
    }
}

void print_seqlist(seqlist _seqlist) {
    for (int i=0;i<_seqlist.len;i++) {
        printf("%3d", _seqlist.p[i]);
    }
    printf("\n");
}

int search_seqlist(seqlist _seqlist, seqlist_data_type _element) {
    int i;
    for (i=_seqlist.len-1;i>=0&&_seqlist.p[i]!=_element;i--);
    return i;
}

int main() {
    seqlist slist;
    init_seqlist(slist, 10);
    print_seqlist(slist);

    printf("input element\n");
    seqlist_data_type e;
    scanf("%d", &e);
    int pos;
    pos = search_seqlist(slist, e);
    if (pos>=0) {
        printf("pos = %d\n", pos);
    }else {
        printf("not find\n");
    }
}

 80 37 92 96 62 88 28 15 17 11
input element
80
pos = 0

  6 20 33 95 43 34 27 65 38 95
input element
95
pos = 9

 29 23 10 98  9 53 46 42 15 94
input element
0
not find

折半查找

• 有序顺序表的二分查找—折半查找
• 二分查找又称折半查找,它仅适用于有序的顺序表
• 时间复杂度: 最好O(1), 平均和最坏O(logn)

• code
• debug

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef int seqlist_data_type;
typedef struct {
    seqlist_data_type *p;
    int len;
}seqlist;


void init_seqlist(seqlist &_seqlist, int _len) {
    _seqlist.len = _len;
    _seqlist.p = (seqlist_data_type *)malloc(
        sizeof(seqlist_data_type)*_seqlist.len
    );
    srand(time(NULL));
    for (int i=0;i<_seqlist.len;i++) {
        _seqlist.p[i] = rand()%100;
    }
}

void print_seqlist(seqlist _seqlist) {
    for (int i=0;i<_seqlist.len;i++) {
        printf("%3d", _seqlist.p[i]);
    }
    printf("\n");
}

int binary_search(seqlist _seqlist, seqlist_data_type _element) {
    int low=0, hight=_seqlist.len-1;
    int middle;
    while (low<=hight) {
        middle = (low+hight)/2;
        if (_element<_seqlist.p[middle]) {
            hight = middle-1;
        }else if (_element>_seqlist.p[middle]) {
            low = middle+1;
        }else {
            return middle;
        }
    }
    return -1;
}

int qsort_compare(const void *left, const void *right) {
    return *(int*)left-*(int*)right;
}

int main() {
    seqlist slist;
    init_seqlist(slist, 10);
    print_seqlist(slist);
    qsort(slist.p, slist.len, sizeof(int), qsort_compare);
    print_seqlist(slist);

    printf("input element\n");
    seqlist_data_type e;
    scanf("%d", &e);
    int pos;
    pos = binary_search(slist, e);
    if (pos!=-1) {
        printf("pos = %d\n", pos);
    }else {
        printf("not find\n");
    }
    return 0;
}

 28 77 93 57 37 22 93 91 31  8
  8 22 28 31 37 57 77 91 93 93
input element
8
pos = 0

 51 80 70 60 35 41 12 68 40 39
 12 35 39 40 41 51 60 68 70 80
input element
0
not find

分块查找

树形查找

二叉排序树

• 二叉排序树的新建,中序遍历,查找,删除

• 二叉排序树,也称二叉查找树,或者是一棵空树,或者是具有下列特性的二叉树:

  • 若左子树非空,则左子树上所有结点的值均小于根结点的值
  • 若右子树非空,则右子树上所有结点的值均大于根结点的值
  • 左、右子树也分别是一棵二叉排序树

• 二叉排序树的最大查找次数是树的高度

• code
• debug

#include <stdio.h>
#include <stdlib.h>


typedef int bitree_data_type;
typedef struct bitree_node{
	bitree_data_type data;
	struct bitree_node *left, *right;
}bitree_node, *bitree;


void in_order(bitree p) {
    if(p!=NULL) {
        in_order(p->left);//打印左子树
        printf("%3d", p->data);
        in_order(p->right);//打印右子树
    }
}

//递归创建二叉排序树
int creat_recursion_search_bitree(bitree &_bitree, bitree_data_type _element){
    if (NULL==_bitree) {
        bitree tree_new=(bitree)calloc(1,sizeof(bitree_node));
        tree_new->data = _element;
        _bitree = tree_new;
        return 1;
    }
    if (_element==_bitree->data) {
        return 0;
    }else if (_element<_bitree->data) {
        return creat_recursion_search_bitree(_bitree->left, _element);
    }else {
        return creat_recursion_search_bitree(_bitree->right, _element);
    }
}

//非递归创建二叉排序树
int creat_search_bitree(bitree &_bitree, bitree_data_type _element) {
    bitree tree_new=(bitree)calloc(1,sizeof(bitree_node));
    tree_new->data = _element;

    if (NULL==_bitree) {
        _bitree = tree_new;
        return 1;
    }

    bitree tree_parent, p_now=_bitree;
    while (p_now) {
        tree_parent = p_now;
        if (_element>p_now->data) {
            p_now = p_now->right;
        }else if (_element<p_now->data) {
            p_now = p_now->left;
        }else {
            return 0;
        }
    }
    if (_element<tree_parent->data) {
        tree_parent->left = tree_new;
    }else if (_element>tree_parent->data) {
        tree_parent->right = tree_new;
    }
    return 1;
}

bitree search_bitree(bitree _bitree, bitree_data_type _element) {
    while (_bitree!=NULL&&_bitree->data!=_element) {
        if (_element>_bitree->data) {
            _bitree = _bitree->right;
        }else if (_element<_bitree->data) {
            _bitree = _bitree->left;
        }
    }
    return _bitree;
}

void del_search_bitree(bitree &_bitree, bitree_data_type _element) {
    if (NULL==_bitree) {
        return;
    }
    if (_element<_bitree->data) {
        return del_search_bitree(_bitree->left, _element);
    }else if (_element>_bitree->data) {
        return del_search_bitree(_bitree->right, _element);
    }else {
        if (NULL==_bitree->left) {
            bitree temp_tree=_bitree;
            _bitree = _bitree->right;
            free(temp_tree);
        }else if (NULL==_bitree->right) {
            bitree temp_tree=_bitree;
            _bitree = _bitree->left;
            free(temp_tree);
        }else {//左子树的最大数据或右子树的最小数据代替要删除的节点
            bitree temp_tree=_bitree->left;
            while (NULL!=temp_tree->right) {
                temp_tree = temp_tree->right;
            }
            _bitree->data = temp_tree->data;
            del_search_bitree(_bitree->left, temp_tree->data);
        }
    }
}


int main() {
    bitree tree_root=NULL;
    bitree_data_type data_list[9] = {66,33,88,44,77,99,11,22,55};
    for (int i=0;i<9;i++) {
        // creat_search_bitree(tree_root, data_list[i]);
        creat_recursion_search_bitree(tree_root, data_list[i]);
    }
    in_order(tree_root);
    printf("\n");

    bitree searched_tree;
    searched_tree = search_bitree(tree_root, 66);
    if (searched_tree) {
        printf("searched_tree = %d\n", searched_tree->data);
    }else {
        printf("not search\n");
    }
    del_search_bitree(tree_root, 66);
    in_order(tree_root);
    return 0;
}

 11 22 33 44 55 66 77 88 99
searched_tree = 66
 11 22 33 44 55 77 88 99

平衡二叉树

红黑树

B 树和 B+ 树

散列表

排序算法

• 排序算法分为交换类排序,插入类排序,选择类排序,归并类排序

交换类排序

• 交换排序分为冒泡排序, 快速排序

冒泡排序

• 时间复杂度为: 最好O(n), 平均和最坏O(n2)
• 空间复杂为O(1)

• code
• debug

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef int seqlist_data_type;
typedef struct {
    seqlist_data_type *p;
    int len;
}seqlist;


void init_seqlist(seqlist &_seqlist, int _len) {
    _seqlist.len = _len;
    _seqlist.p = (seqlist_data_type *)malloc(
        sizeof(seqlist_data_type)*_seqlist.len
    );
    srand(time(NULL));
    for (int i=0;i<_seqlist.len;i++) {
        _seqlist.p[i] = rand()%100;
    }
}

void print_seqlist(seqlist _seqlist) {
    for (int i=0;i<_seqlist.len;i++) {
        printf("%3d", _seqlist.p[i]);
    }
    printf("\n");
}

void swap(int &a, int &b) {
    int temp;
    temp = a;
    a = b;
    b = temp;
}

void bubble_sort(seqlist_data_type *_slist, int _len) {
    bool flag;
    for (int i=0;i<_len-1;i++) {
        flag = false;
        for (int j=_len-1;j>i;j--) {
            if (_slist[j-1]>_slist[j]) {
                swap(_slist[j-1],_slist[j]);
                flag = true;
            }
        }
        if (false == flag) {
            return;
        }
    }
}


int main() {
    seqlist slist;
    init_seqlist(slist, 10);
    print_seqlist(slist);

    bubble_sort(slist.p, 10);
    print_seqlist(slist);
    return 0;
}

95 84 55 20 97 77 39  7 63 66
 7 20 39 55 63 66 77 84 95 97

快速排序

• 快速排序的核心是分治思想
• 时间复杂度: 最好和平均O(nlogn),最坏O(n2)
• 空间复杂度是O(log2n)

• code
• debug

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

typedef int seqlist_data_type;
typedef struct {
    seqlist_data_type *p;
    int len;
}seqlist;


void init_seqlist(seqlist &_seqlist, int _len) {
    _seqlist.len = _len;
    _seqlist.p = (seqlist_data_type *)malloc(
        sizeof(seqlist_data_type)*_seqlist.len
    );
    srand(time(NULL));
    for (int i=0;i<_seqlist.len;i++) {
        _seqlist.p[i] = rand()%100;
    }
}

void print_seqlist(seqlist _seqlist) {
    for (int i=0;i<_seqlist.len;i++) {
        printf("%3d", _seqlist.p[i]);
    }
    printf("\n");
}

//快速排序核心函数,挖坑法
int partition(seqlist &_seqlist, int _low, int _hight) {
    int pivot = _seqlist.p[_low];
    while (_low<_hight) {
        //从右边找小于pivot的元素
        while (_low<_hight&&_seqlist.p[_hight]>=pivot) {
            _hight--;
        }
        _seqlist.p[_low] = _seqlist.p[_hight];
        //从左边找大于pivot的元素
        while (_low<_hight&&_seqlist.p[_low]<=pivot) {
            _low++;
        }
        _seqlist.p[_hight] = _seqlist.p[_low];
    }
    _seqlist.p[_low] = pivot;
    return _low;
}

void quick_sort(seqlist &_seqlist, int _low, int _hight) {
    if (_low<_hight) {
        int pivot_pos;
        pivot_pos = partition(_seqlist, _low, _hight);
        quick_sort(_seqlist, _low, pivot_pos-1);
        quick_sort(_seqlist, pivot_pos+1, _hight);
    }
}


int main() {
    seqlist slist;
    init_seqlist(slist, 10);

    int low = 0;
    int hight = slist.len - 1;
    print_seqlist(slist);
    quick_sort(slist, low, hight);
    print_seqlist(slist);

    return 0;
}

9 81 37  7 37 98 25  5 39 11
5  7  9 11 25 37 37 39 81 98

插入类排序

• 插入类排序分为直接插入排序, 折半插入排序, 希尔排序

直接插入排序

• 时间复杂度: 最好O(n),最坏和平均O(n2)
• 空间复杂度为O(1)

• code
• debug

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

typedef int seqlist_data_type;
typedef struct {
    seqlist_data_type *p;
    int len;
}seqlist;


void init_seqlist(seqlist &_seqlist, int _len) {
    _seqlist.len = _len;
    _seqlist.p = (seqlist_data_type *)malloc(
        sizeof(seqlist_data_type)*_seqlist.len
    );
    srand(time(NULL));
    for (int i=0;i<_seqlist.len;i++) {
        _seqlist.p[i] = rand()%100;
    }
}

void print_seqlist(seqlist _seqlist) {
    for (int i=0;i<_seqlist.len;i++) {
        printf("%3d", _seqlist.p[i]);
    }
    printf("\n");
}

void insert_sort(seqlist &_seqlist) {
    int len = _seqlist.len;
    for (int i=1;i<len;i++) {
        int insert_value = _seqlist.p[i];
        int j;
        for (j=i-1;j>=0&&_seqlist.p[j]>insert_value;j--) {
            _seqlist.p[j+1] = _seqlist.p[j];
        }
        _seqlist.p[j+1] = insert_value;
    }
}


int main() {
    seqlist slist;
    init_seqlist(slist, 10);

    print_seqlist(slist);
    insert_sort(slist);
    print_seqlist(slist);

    return 0;
}

74 20 69  2  2 96 15  8 48 41
 2  2  8 15 20 41 48 69 74 96

折半插入排序

希尔排序

选择类排序

• 选择类排序分为简单选择排序, 堆排序

简单选择排序

• 时间复杂度最坏,平均,最好都是O(n2)
• 空间复杂度为O(1)

• code
• debug

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

typedef int seqlist_data_type;
typedef struct {
    seqlist_data_type *p;
    int len;
}seqlist;


void init_seqlist(seqlist &_seqlist, int _len) {
    _seqlist.len = _len;
    _seqlist.p = (seqlist_data_type *)malloc(
        sizeof(seqlist_data_type)*_seqlist.len
    );
    srand(time(NULL));
    for (int i=0;i<_seqlist.len;i++) {
        _seqlist.p[i] = rand()%100;
    }
}

void print_seqlist(seqlist _seqlist) {
    for (int i=0;i<_seqlist.len;i++) {
        printf("%3d", _seqlist.p[i]);
    }
    printf("\n");
}

void swap(int &a, int &b) {
    int temp;
    temp = a;
    a = b;
    b = temp;
}

void select_sort(seqlist _seqlist) {
    int len = _seqlist.len;
    for (int i=0;i<len-1;i++) {
        int min = i;
        for (int j=i+1;j<len;j++) {
            if (_seqlist.p[j]<_seqlist.p[min]) {
                min = j;
            }
        }
        if (i != min) {
            swap(_seqlist.p[i], _seqlist.p[min]);
        }
    }
}


int main() {
    seqlist slist;
    init_seqlist(slist, 10);
    print_seqlist(slist);

    select_sort(slist);
    print_seqlist(slist);
    return 0;
}

92  0 20 28 47 15 32 20 39 92
 0 15 20 20 28 32 39 47 92 92

堆排序

• 堆(Heap)是计算机科学中的一种特殊的树状数据结构

• 若满足以下特性,则可称为堆:给定堆中任意结点P和C,若P是C的父结点,则P的值小于等于(或大于等于)C的值

• 若父结点的值恒小于等于子结点的值,则该堆称为最小堆(min heap)

• 若父结点的值恒大于等于子结点的值,则该堆称为最大堆(max heap)

• 堆中最顶端的那个结点称为根结点(root node),根结点本身没有父结点(parent node)

• 最小堆又称为小根堆或小顶堆,最大堆又称为大根堆或大顶堆

• 堆是用数组去表示二叉树的一种结构,而且表示的一定是完全二叉树

• 将二叉树中每个元素对应到数组下标的这种数据结构称为堆

• 最后一个父元素的下标是len/2-1

• 如果父结点的下标是dad,那么父结点对应的左子结点的下标值是2*dad+1

• 最好、最坏、平均时间复杂度都是O(nlog2n)

• 空间复杂度是O(1)

• code
• debug

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

typedef int seqlist_data_type;
typedef struct {
    seqlist_data_type *p;
    int len;
}seqlist;


void init_seqlist(seqlist &_seqlist, int _len) {
    _seqlist.len = _len;
    _seqlist.p = (seqlist_data_type *)malloc(
        sizeof(seqlist_data_type)*_seqlist.len
    );
    srand(time(NULL));
    for (int i=0;i<_seqlist.len;i++) {
        _seqlist.p[i] = rand()%100;
    }
}

void print_seqlist(seqlist _seqlist) {
    for (int i=0;i<_seqlist.len;i++) {
        printf("%3d", _seqlist.p[i]);
    }
    printf("\n");
}

void swap(int &a, int &b) {
    int temp;
    temp = a;
    a = b;
    b = temp;
}

void adjust_down(int _array[], int _dada, int _len) {
    int dada = _dada;
    int son = _dada*2 + 1;
    while (son<_len) {
        if (son+1<_len&&_array[son]<_array[son+1]) {
            son++;
        }
        if (_array[son]>_array[dada]) {
            swap(_array[dada], _array[son]);
            dada = son;
            son = dada*2 + 1;
        }else {
            break;
        }
    }
}

void heap_sort(int _array[], int _len) {
    for (int i=_len/2-1;i>=0;i--) {
        adjust_down(_array, i, _len);
    }
    swap(_array[0], _array[_len-1]);
    for (int j=_len-1;j>1;j--) {
        adjust_down(_array, 0, j);
        swap(_array[0], _array[j-1]);
    }
}


int main() {
    seqlist slist;
    init_seqlist(slist, 10);
    print_seqlist(slist);

    int len = slist.len;
    heap_sort(slist.p, len);
    print_seqlist(slist);
    return 0;
}

59 24 53 70 89 59  7 65  7 44
 7  7 24 44 53 59 59 65 70 89

归并类排序

• 归并排序是我们不断进行二分,最终各自剩余 1 个元素,自然有序,然后先将每两个元素进行合并,变为有序,然后再将两个小组合并,变为有序,循环往复,直到整个数组有序

两两归并排序

• 最好、最坏、平均时间复杂度都是O(nlog2n)
• 空间复杂度是O(n)

• code
• debug

#include <stdio.h>
#include <stdlib.h>


void merge_array(int _array[], int _low, int _mid, int _high) {
    static int array_new[9];
    int i,j,k;
    for (i=_low;i<=_high;i++) {
        array_new[i]=_array[i];
    }
    k=_low;
    for (i=_low,j=_mid+1;i<=_mid&&j<=_high;k++) {
        if (array_new[i]<_array[j]) {
            // _array[k] = array_new[i];
            // i++;
            _array[k] = array_new[i++];
        }else {
            // _array[k] = array_new[j];
            // j++;
            _array[k] = array_new[j++];
        }
    }
    while (i<=_mid) {
        // _array[k] = array_new[i];
        // i++;
        // k++;
        _array[k++] = array_new[i++];
    }
    while (j<=_high) {
        // _array[k] = array_new[j];
        // j++;
        // k++;
        _array[k++] = array_new[j++];
    }
}

void merge_sort(int _array[], int _low, int _high) {
    if (_low<_high) {
        int mid = (_low+_high)/2;
        merge_sort(_array, _low, mid);
        merge_sort(_array, mid+1, _high);
        merge_array(_array, _low, mid, _high);
    }
}

void print_array(int _array[], int _len) {
    for (int i=0;i<_len;i++) {
        printf("%3d", _array[i]);
    }
    printf("\n");
}


int main() {
    int array[9]={33,22,44,11,66,77,55,99,88};
    int len = 9;

    print_array(array, len);
    merge_sort(array, 0, len);
    print_array(array, len);
    return 0;
}

33 22 44 11 66 77 55 99 88
11 22 33 44 55 66 77 88 99

基数排序

内部排序算法的比较与应用

排序方式	时间复杂度			空间复杂度	稳定性
	平均情况	最坏情况	最好情况
插人排序	O(n2)	O(n2)	O(n)	O(1)	稳定
希尔排序	O(n1.3)			O(1)	不稳定
冒泡排序	O(n2)	O(n2)	O(n)	O(1)	稳定
快速排序	O(n log2 n)	O(n2)	O(n log2 n)	O(log2 n)	不稳定
选择排序	O(n2)	O(n2)	O(n2)	O(1)	不稳定
堆排序	O(n log2 n)	O(n log2 n)	O(n log2 n)	O(1)	不稳定
归并排序	O(n log2 n)	O(n log2 n)	O(n log2 n)	O(n)	稳定
基数排序	O(d(n+r))	O(d(n+r))	O(d(n+r))	O(r)	稳定

• 稳定性是指排序前后,相等的元素位置是否会被交换

外部排序