绪论

算法设计的目标:

正确性
可读性
健壮性
高效率与低存储量需求

一个特定算法的工作量只依赖于问题的规模 (用 n 表示), 或者是问题规模的函数, 记为 $f(n)$ , 算法执行的时间复杂度称为 $O(f(n))$

算法时间与空间复杂度

算法时间复杂度

算法的运行工作量 $f(n)$ 用执行基本操作次数来度量

运行工作量 $f(n)$ 的低阶部分不会影响比较结果, 高阶部分的常数项也可以省略掉, 举个栗子

O(f(n)) = O(\frac{1}{2}n^2-n) = O(n^2)

所以算法的时间复杂度也称为渐进时间复杂度

Case 1

惩罚操作, 操作次数 $n^3$

void mult(int a[], int b[], int& c[])
{
	for(i=1; i<=n; ++i)
	{
		c[i, j]=0;
		for (k=1; k<=n; ++k)
		{
			c[i, j] += a[i, k]*b[k, j];
		}
	}
}

Case 2

冒泡排序算法, 进行基本的交换操作, 最大操作次数 $(n-1)+(n-2)+\cdots+1 = \frac{n(n-1)}{2}$

void bubble_sort(int& a[], int n)
{
	for (i=n-1; i>0; -i)
	{
		for(j=0; j<i; ++j)
		{
			if(a[j]>a[j+1])
			{
				tmp = a[j];
				a[j] = a[j+1];
				a[j+1] = tmp;
			}
		}
	}
}

算法空间复杂度

算法的空间复杂度:

S(n) = O(g(n))

算法存储量包括

输入数据所占空间
程序本身所占空间
辅助变量所占空间

定理:

如果存在正的常数 $C$ 和自然数 $N_0$ , 使得 $N\geq N_0$ 时有 $f(N) \leq Cg(N)$ , 则称函数 $f(N)$ 当 $N$ 充分大时上有界, 且 $g(N)$ 是它的一个上界, 记为 $f(N) = O(g(N))$

例如, 对所有的 $N\geq 1, 有 3\mathrm{log}N \leq 4\mathrm{log}N, 则有 3\mathrm{log}N = O(\mathrm{log}N)$

再例如, 对 $N\geq 1$ , $N + 1024\leq 1025N$ , 有 $N + 1024 = O(N)$

复杂度的计算规则

O(Cf(N)) = O(f(N)), C是一个正常数

f \in O(f)

2n^2+2n+1\in O(n^2)$

常见复杂度:

常数阶: $O(1)$
对数阶: $O(log_2n)$
线性阶: $O(n)$
线性对数阶: $O(nlog_2n)$
多项式阶: $O(n^2)$
指数阶: $O(2^n)$

线性表

线性表: $n$ 个同类型数据元素的有限序列

直接先驱, 直接后继, 序号 $i$ 也称在线性表中的位序

线性表分为顺序表 (数组) 和链表

顺序表

顺序表以数组的形式存储, 逻辑地址和物理地址都相邻

线性表的静态定义

#define MaxSize 100
typeof struct{
	int data[MaxSize];
    int length;
}SqlList;

线性表的静态初始化

void InitList(Sqlist &L){
	for(int i; i<MaxSize; ++i){
		L.data = 0		// 防止脏数据
	}
	L.length = 0;
}

线性表的插入

bool ListInsert(SqlList &L, int i, int e){
	if(i<1 || i>MaxSize)
    {
        return false;
    }
    if(L.length>L.MaxSize)
    {
        return false;
    }
    for(int j=L.MaxSize; j>i; j++)
    {
        L.data[j] = L.data[j-1]
    }
    L.data[i] = i
    L.length++;
    return true;
}

线性表的删除

bool ListDelete(SqlList &L, int i, int &e){
	if(i<1 || i>L.length)
    {
        return false;
    }
    e = L.data[i]
    for(j=i; j<MaxSize; j++)
    {
        L.data[j] = L.data[j+1]
    }
    L.length--;
}

线性表的按索引查找

1
2
3

int GetElem(SqlList L, int i){
	return L.data[i-1];
}

线性表的按值查找

int LocateElem(SqlList L, ElemType e){
	for(int i=0; i<MaxSize; i++)
	{
		if(L.data[i] == e)
		{
			return i+1;
		}
	}
	return 0;
}

动态增长内存

void IncreaseSize(SqlList $L, int len){
    int *p = L.data
	L.data = (int *)malloc(L.MaxSize+len * sizeof(int));
    for(int i=0; i<p.length; i++)
    {
        L.data[i] = p.data[i]
    }
    L.MaxSize = L.MaxSize + len;
    free(p);
}

链表

逻辑地址上相邻, 物理地址上不一定相邻, 由指针指向下一个数据元素

空链表: 空链表的头结点的指针域为空

单向链表

单链表的定义

typedef struct node_t{
	int data;
	struct node_t *next;
}LinkNode_t;

或者

LinkNode_t *createLinkList()
{
	LinkNode_t* node = (LinkNode_t*)malloc(sizeof(LinkNode_t));
    node->next = NULL;
    return node;
}

// 创建头结点
LinkNode_t* head = createLinkList();

判断链表是否为空

int emptyLinkList(LinkNode_t* p)
{
	return p->next == NULL;
}

计算链表中除空头节点外的结点个数

int lengthLinkList(LinkLIst_t* p)
{
    int count = 0;
    LinkNode_t* t = p->next;
    while(t!=NULL)
    {
        count++;
        t = t->next;
    }
    return count;
}

note:这里 LinkNode_t* t = p->next; 定义了一个新的节点, 是头结点指向的结点, 我们通过一个额外的结点来顺着

插入新结点

先让插入结点的指针域指向后一个结点; 再找到待插入位置的前一个结点, 使前一个结点的指针域指向待插入的结点

int insertLinkList(LinkListNode_t* p, int pos, int x)
{
	if(pos<0||pos>lenthLinkList(p)){
        return -1;
    }
    
    // 创建新结点并赋值
    LinkNode_t* newNode = (LinkNode_t*)malloc(sizeof(LinkNode_t));
    newNode->data = x;
    newNode->next = NULL;
    
    LinkNode_t* t = p;
    int i;
    for(i=0; i<pos; i++)
    {
        t = t->next;
    }
    
    newNode->next = t->next;
    t->next = newNode;
    return 0;
    
    
    
}

获得某位置结点的值

int getLinkList(LinkNode_t* p, int pos)
{
    if(pos<0||pos>lengthLinkList(p))
    {
        return -1;
    }
    int i;
    LinkNode* t = p->next;
    for(i=0; i<pos; i++)
    {
        t = t->next;
    }
    return t->data;
}

删除链表中的结点

将被删除结点的前一个结点的指针域指向被删除节点的下一个结点

int deleteLinkList(LinkNode_t* p, int pos)
{
    if(pos<0||pos>lengthLinkList(p))
    {
        return -1;
    }
    LinkNode* t = p;
    for(int i=0; i<pos; i++)
    {
        t = t->next;
    }
    LinkNode* s = t->next;
    t->next = t->next->next;
    free(s);
    return 0;
}

清空链表

void clearLinkList(LinkNode_t* p)
{
	while(p!NULL)
    {
        LinkNode_t* t = p;
        p = p->next;
        free(t);
    }
}

双向链表

每一个结点由一个数据域和两个指针域组成, 数据域用于存储数据, 指针域用于指向上一个节点和下一个结点. 尾结点的 next 指针域指向头结点 (不指向第一个结点)

双链表的定义

typedef int LTDataType

typedef struct ListNode
{
	struct ListNode* prev;
    LTDataType Data;
    struct ListNode* next;
}

双向链表的初始化

双向链表的头结点, 初始化时两个指针域都指向自身

ListNode* ListInit()
{
    ListNode* guard = (ListNode*)malloc(sizeof(ListNode));
    if(guard == NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    guard->prev = guard;
    guard->next = guard;
    return guard;
}

双向链表创建一个新结点

ListNode* BuyListNode(ListDataType x)
{
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
	newNode->Data = x;
    newNode->next = x;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

双向链表的打印

void ListPrint(ListNode* phead)
{
    assert(phead!=NULL);
       
    ListNode* t = phead->next;
    print("guard<=>");
    while(cur != guard)
    {
        print("%d<=>", t->data);
        t = t->next;
    }
    print("\n");
}

双向链表的尾插

void ListPushBack(ListNode* phead, LTDataType x)
{
	assert(phead!=NULL);
        
    ListNode* newNode = BuyListNode(x);
    phead->prev->next = newNode;
    nexNode->prev = phead->prev;
    phead->prev = newNode;
    newNode->next = phead
}

双向链表的尾删

void ListPopOut(ListNode* phead)
{
	assert(phead!=NULL);
        
    tail = phead->prev;
    phead->prev->next = phead;
    phead->prev = tail->prev;
    free(tail);
}

双向链表的头插

累了, 和前面的大差不差吧

双链表的判空

void ListEmpty(ListNode* phead)
{
    assert(phead!=NULL);
    return phead->next == phead;
}

求双链表的长度

int ListSize(ListNode* phead)
{
    assert(phead!=NULL);
    int count = 0;
    
    ListNode* t = phead->next;
    while(t!=phead)
    {
        count++;
        t = t->next;
    }
    free(t);
    return count;
}

求双向链表的查找某个值

ListNode* ListFind(ListNode* phead, LTDataType x)
{
    assert(phead!=NULL);
    
    ListNode* t = phead->next;
    while(t!=phead)
    {
        if(t->Data == x)
        {
            return t;
        }
        t = t->next;
    }
    return NULL;
}

双向链表在 pos 前插入

双向链表删除 pos 位置

双向链表的销毁

void ListDestroy(ListNode* phead)
{
	assert(phead!=NULL);
    ListNode* t = phead->next;
    while(t!=phead)
    {
        ListNode* next = t->next;
        free(t);
        t = next;
    }
    free(phead);
}

线性表的优缺点

顺序表 (数组) 的优缺点

优点:
1. 查询的时间复杂度为 $O(1)$
2. 元素在内存中按顺序存储
缺点:
1. 建表时需要预先知道存储区的大小
2. 插入的时间复杂度为 $O(n)$

链表的优缺点

优点:
1. 插入的时间复杂度为 $O(1)$
2. 内存可以在不连续的存储区
3. 实现不用知道需要多少存储, 使用时新增即可
缺点
1. 查询的时间复杂度为 $O(n)$
2. 学习较为复杂

栈

线性结构, 先进先出, 后进后出, 入栈, 出栈

下面以数组来模拟栈, 由于所需大小难以估计, 所以可以给栈一个基本容量, 空间不够时再追加

栈的定义

typedef struct{
    SDataType *base;
    SDataType *top;
    int StackSize;		// 当前已经分配的存储空间, 以元素为单位
}SqStack;

栈的初始化

栈为空时, s.top = s.base

Status InitStack(SqStack &S){
    S.base = (SDataType *)malloc{Stack_INIT_SIZE*sizeof(SDataType)};
    if(!S.base)
    {
        return OVERFLOW;
    }
    S.top = S.base
        S.StackSize = STACK_INIT_SIZE;
}

判断是否为空栈

void judgeNULL(SqStack &s)
{
    if(s.top == s.base)
    {
        printf("此栈为空栈!\n");
    }else:
    {
        printf("此栈不是空栈!\n");
    }
}

判断是否为满栈

void judgeFULL(SqStack &s)
{
    if(s.top-s.base == s.SqSize)
    {
        printf("栈满!\n");
    }else{
        printf("栈未满!\n")
    }
}

入栈

先判断是否为满栈, 如满则追加存储空间, 然后将元素入栈

void *realloc(void *ptr, size t, new_size)用法: 分配一个大小为 new_size 字节的新内存块, 并赋值大小等于新旧大小中较小者的内存区域, 然后释放旧内存块

Status Push(SqStack &s, SDataType e)
{
    SDataType = *p;
    if(s.top==s.base)
    {
        // 追加空间
        p = (SDataType *)realloc(s.base, (s.StackSize + STACKINCREMENT * sizeof(SDataType)));
        if(!p)
        {
            return OVERFLOW;
        }
        s.base = p;
        s.top = s.base + s.StackSize;
        s.Stacksize += STACKINCREMENT;
    }
    *(s.top) = e;
    s.top++;
    return OK;
}

出栈

Status Pop(SqStack &s, SDataType &e)
{
    if(s.top!=s.base)
    {
        s.top--;
        e = *(s.top);
    }else{
        return 0;
    }
    return e;
}

队列

顺序存储

队列:先进先出, 存储结构分为顺序存储和链式存储

顺序队列

note: 当第一个元素出队时, 不会有后续元素顶上出队位置的元素

顺序队列的定义

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

顺序队列的初始化

int InitQueue(SqQueue* Q)
{
    Q->front = 0;
    Q->rear = 0;
    return 1;
}

使用时, SqQueue Q; InitQueue(&Q);

求顺序队列的长度

note: 特别注意, Q.rear 指的是最后的一个元素的 index, 而不是下一个空的位置的 index

int QueueLength(SqQueue)
{
    return Q.rear - Q.front;
}

顺序队列的入队

int EnQueue(SqQueue Q, int e)
{
    if(Q.rear == Maxsize)
    {
        return 0;
    }
    Q->data[Q->rear] = e;
    Q.rear++;
    return 1;
}

顺序队列的出队

int DeQueue(SqQueue* Q, int* e)
{
    if(Q.rear==Q.front)
    {
        return 0;
    }
    *e = Q->data[Q->front];
    Q->front++;
    return 1;
}

问题: 当队列满的时候, 无法从队尾插入新元素, 存在假溢出问题

循环队列

头尾相接的顺序存储结构

note: 此时 rear = front 不一定是空

解决判空的问题:

剩余一个空闲位置用来判断队列已满. 假定队列最大元素个数为 maxSize, 判满条件为 $(rear+1) \% maxSize == front$

循环队列的判空和判满

1 2	队列为空: rear == front 队列为满: (rear + 1) % maxSize == front

循环队列的入队

int EnQueue(SqQueue* Q, int e)
{
    if((Q->rear+1)%maxSize == Q->front)
    {
        return 0;
    }
    Q->data[Q->rear] = e;
    Q->rear++;
    return 1;
}

链式队列

链式队列中只允许单链表的表头删除, 表尾插入

链式队列分为头结点和普通结点

数据结点类型 DataNode

typedef int ElemType;
    
typedef struct Node
{
    ElemType data;
    struct Node *next;
}DataNode;

链式队列头结点类型

typedef struct
{
    DataNode *front;
    DataNode *rear;
}LinkQueue;

链式队列的初始化

LinkQueue *InitQueue()
{
    LinkQueue *q;
    q = (LinkNode *)malloc(sizeof(LinkQueue));
    q->front = NULL;
    q->next = NULL;
    return q;
}

1	LInkQueue lq = *InitQueue()

链式队列的判空

1	if(q->front==NULL && q->next==NULL)

链式队列的入队

void EnQueue(LinkQueue *q, ElemType e)
{
    DataNode *t;
    t = (DataNode *)malloc(sizeof(DataNode));
    t->data = e;
    t->next = NULL;
    
    if(q->front!=NULL && q->next!=NULL)
    {
        q->rear->next = t;
        q->rear = t;
    }else{
        q->front = t;
        q->next = t;
    }
}

链式队列的出队

int deQueue(LinkQueue *q, ElemType *e)
{
    DataNode *t;
    
    if(q->front!=NULL && Q->next!=NULL)
    {
        t = q->front;
        *e = t->data;
        
        if(q->front->next == NULL)
        {
            q->front = NULL;
            q->next = NULL;
        }else{
            q->front = t->next;
        }
        free(T);
        return 1;
    }else{
        printf("队列为空, 不能出队!\n");
        return 0;
    }
}

求链式队列长度

int lengthLinkQueue(LinkQueue *q)
{
    int len = 0;
    LinkNode* t;
    if(QueueEmpty(&q))
    {
        len = 0;
        return len;
    }
    
    t = (LinkNode*)malloc(sizeof(LinkNode));
    t = q->front;
    while(t->next!=NULL)
    {
        t = t->next;
        len++;
    }
    free(t);
    prntf("队列长度为%d\n");
    return len;
    
}

打印链式队列中的元素

void DisQueue(LinkQueue)
{
    DataNode *p;
    p = q->front;
    printf("队列元素为: ");
    while(p!=NULL)
    {
        printf("%d ", p->data);
    }
    print("\n");
}

销毁链式队列

void DestroyQueue(LinkQueue *q)
{
    int deQueue(LinkQueue *q, ElemType *e);
    ElemType m;
    while(q->front!=NULL &&q->next!=NULL)
    {
        deQueue(q, &m)
    }
    free(q);
}

字符串

空串: 不包含任何字符的串

子串: 串中任意连续的字符组成的子序列

空格串: 全是空格, 空格字符

串的基本操作以子串为操作对象, 如查找, 插入, 删除一个子串

串的存储形式:

字符串的存储形式

顺序存储

定义顺序存储结构

#define MAXSIZE 255

typedef struct string{
	char ch[MAXSIZE];
    int length;
} String;

初始化

note: 默认\0 为空字符

void initString(String &string)
{
    for(int i=0; i<MAXSIZE; i++)
    {
        string.ch[i] = '\0';
    }
    string.length = 0;
}

复制操作

String StrCopy(String &string, String str)
{
    int i, j;
    for(i=0; i<strlen(str.ch); i++)
    {
        string.ch[i] = str.ch[i];
    }
    for(j=i; i<strlen(string.ch); j++)
    {
        str.ch[i] = '\0';
    }
    string.length = str.length;
    return string.
}

字符串的判空

bool strIsEmpty(String string)
{
    if(string.length == 0)
    {
        return true;
    }else{
        return false;+
    }
}

字符串的比较

首先比较同位序的字母大小, 然后比较字符串的长度大小

例如, ab<ac, ab<abc

int strCompare(String string, String str)
{
    for(int i=0; i<string.length && i<str.length; ++i)
    {
        if(string.ch[i] != stc.ch[i])
        {
            return string.ch[i] - str.ch[i];
        }
    }
    return string.length - str.length;
}

字符串的截取

用 sub 返回串 string 的第 pos 个字符起长度为 len 的子串

bool subString(String &sub, String string, int pos, int len)
{
    if(pos+len > string.length)
    {
        return false;
    }
    for(int i=0; i<pos+len; ++i)
    {
        sub.ch[i] = string.ch[pos+i];
    }
    sub.length = len;
    return true;
}

字符串的连接

String & strConcat(String &sub, String string, string str)
{
    int i;
    for(i=0; i<string.length; i++)
    {
        sub.ch[i] = string.ch[i];
    }
    for(i=0; i<str.length; i++)
    {
        sub.ch[i+string.length] = str.ch[i];
    }
    sub.length = string.length + str.length;
    return sub;
}

字符串的定位

返回子串在主串中的位序

int strIndex(Sring string, String str)
{
    int i=0, n = string.length, m = str.length;
    String sub;
    while(i <=n-m)
    {
        subString(sub, string, i, m);
        if(strCompare(Sub, str)!=0)
        {
            i++;
        }else{
            return i;
        }
    }
    return 0;
}

字符串的清空

void strClear(String &string)
{
    for(int i=0; i<string.length; ++i)
    {
        string.ch[i] = '\0';
    }
    string.length = 0;
}

KMP 算法

这里视频讲的不清楚, 还是看博客吧

前缀是除了最后一个字符的所有子串, 后缀是除了第一个字符的所有子串

前后缀与公共前后缀

比如, abcabfabcab 的最长相等前后缀是 abcab

KMP 算法的思想

KMP 的目的是在主串中找到子串的位置, 也叫串的模式匹配. KMP 的主要思想是空间换时间. 朴素的模式匹配是一种时间复杂度为 $O(n\times m)$ , 空间复杂度为 $O(1)$ 的算法.

KMP 算法利用"匹配失败时, 失败之前的已知部分是匹配的"的信息, 保持主串的 i 指针不回溯, 通过修改模式串的 j 指针, 使目标串尽量地移动到有效的匹配位置, 算法时间复杂度是 $O(n+m)$

匹配失败时：失败位置之前的主串（i 前）和子串（j 前）部分一定都是匹配的。且对于子串来说，失败位置之前（j 前）的任一部分属于子串（模式串）的这段子串（子子串）的后缀
重新匹配时：我们重新匹配的开始一定是子串（模式串）的某部分前缀
要想移动子串（模式串）指针（i 下次匹配位置）到最大有效匹配位置，那么这个位置一定是这段前缀=后缀的部分

人话: 主串指针不回溯, 动子串的指针; 用子串匹配主串时, 求取该子串的公共最长前后缀 , 也即这个这个子串前缀和后缀相同的部分, 然后从将子串指针移动到后缀, 从后缀重新匹配

KMP的核心: 充分利用匹配模式串的最大相同前后缀信息（子串本身的重复性），即利用next数组实现模式串的移动与回溯，而主串不回溯, 从而减少无意义的匹配

next 数组概述

next 数组:在模式串中 (下标从 0 开始), next[i] 表示模式串中以下标 i 处字符结尾的子串的最大相同前后缀长度. 作用:

表示模式串中 1-i 位置子串中的最长相同前后缀长度
在该位置匹配失败时模式串回溯比较的下一个字符位置

如何求 next 数组

对模式串 S 来说, 初始化 next[0] = 0 (一个字符不存在相同前后缀, 故长度为 0), 假设 next[j] = k, 已知 next[j] 求取 next[j+1] 有以下两种情况:

S[j+1] == S[k]: next[j+1] = k+1. 表示该字符匹配, 继续向后搜索
S[j+1]!=S[k]: k = next[k-1], 重复步骤直至 next[k]==0 或匹配成功为止. 表示该字符不匹配, 模式串需要回溯

KMP 算法的代码实现

void getNext(char* s,int len){
    next[0] = 0;
    int k = 0; //k = next[0]
    int i = 1;
    while(i < len){
        if(s[i] == s[k]){
            next[i++] = ++k; //next[j+1] = k+1;
        }else{
            if(k > 0)k = next[k-1]; //k = next[k-1]
            else{
                next[i++] = k; //next[j+1] = 0 回溯到头了，找不到相同前缀，则最大相同前后缀长度=0
            }
        }
    }
}

void getNext(char* s,int len){
    next[0] = 0;
    int k = 0; //k = next[0]
    for(int i = 1;i < len;i++){
        while(k > 0 && s[i] != s[k])k = next[k-1]; //k = next[k-1]
        if(s[i] == s[k])k++; 
        next[i] = k; //next[j+1] = k+1 | next[j+1] = 0
    }
}

//返回模式串T中字串S第一次出现的位置下标，找不到则返回-1
int kmp(char *T, char* S){
    int len_T = strlen(T);
    int len_S = strlen(S);
    for(int i = 0,j = 0;i<len_T;i++){
        while(j > 0 && T[i] != S[j])j = next[j-1];
        if(T[i] == S[j])j++;
        if(j == len_S)return i-len_S+1;
    }
    return -1;
}
 
//返回模式串T中字串S出现的次数，找不到则返回0
int kmp(char *T, char* S){
    int sum = 0;
    int len_T = strlen(T);
    int len_S = strlen(S);
    for(int i = 0,j = 0;i<len_T;i++){
        while(j > 0 && T[i] != S[j])j = next[j-1];
        if(T[i] == S[j])j++;
        if(j == len_S){
            sum++;
            j = next[j-1];
        }
    }
    return sum;
}

举个栗子

串 ababaaababaa 的next数组为:

011234223456

人话: next[j] 怎么算? 默认前两个为 01,如果我想算 next[j], 需要找主串中 index 为 0~j-1 的字符, 找到这段字符的共享前后缀, 得到 next[j] = 共享前后缀的长度

note: next[5] 是 4 而不是 2, “ababa” 可以共享中间的 a

nextVal 不记了, 记不住

数组

一组连续的内存空间, 来存储一组具有相同类型的数据

定义

1	int[] a = new int[10]

二维数组的内存结构

行优先存储, M 行 N 列的 b[i] [j] 的存储地址为

\mathrm{LOC+(i*N+j)*sizepf(ElemType)}

列优先存储, M 行 N 列的 b[i] [j] 的存储地址为

\mathrm{基地址+(j*M+i)*sizeof(ElemType)}

广义表

列表, 现行存储结构, 可以存储不可再分的元素, 也可以存储可再分的元素

举例: $A=(), B=(e), C=(a, (b, c, d))$ 都是广义表的形式

广义表 $ LS=((a), (b), (©, (e)))$

表头: 第一个元素, (a)
表尾: 除第一个元素外的所有元素 (需要外加括号), ((b), (©, (e)))
长度: 元素的数量
深度: 最深的元素的层数, 3

树

树有 n 个节点, n=0 时称为空

度: 节点拥有的子树个数

树可以用顺序存储和链式存储

二叉树

二叉树: n 个结点的有限集合, 可以为空集, 不存在度大于 2 的结点

note: 二叉树包括空树, 只含根结点, 某个子树为空树的情况

二叉树和度为 2 的树的区别

度不同. 度为 2 的树要求每个结点最多有两棵子树, 且至少有一个结点有两颗子树. 二叉树要求度不超过 2
分支不同. 度为 2 的树有两个分支, 但没有左右之分; 二叉树的子树有左右之分
次序不同. 度为 2 的树的子树无序; 二叉树的子树有序

设 $n$ 为结点的度, 性质:

二叉树第 $i$ 层上最多有 $2^{i-1}$ 个节点
二叉树中如果深度为 $k$ , 最多有 $2^k-1$ 个节点
$n_0 = n_2 + n_1$ , 度为 0 的结点数等于度为 1 和度为 2 的结点数之和
完全二叉树中, 具有 n 个节点的完全二叉树的深度为 $\lfloor{\mathrm{log}}_2n\rfloor+1$
结点总数 = 总度数 + 1 = $0*n_0+1*n_1+2*n_2$ + 1
结点数 = $n_0 + n_1 + n_2$
二叉树中, $n_0 = n_2 + 1$

满二叉树

所有分支都有左右子树, 且所有叶子都在同一层上

性质:

叶子结点只出现在最下一层
非叶子节点的度一定为 2
同样深度的二叉树中, 满二叉树的结点个数最多, 叶子树最多

满二叉树

完全二叉树

叶子结点只出现在最下层和次下层, 且最下层的结点都集中在左边

完全二叉树

特点:

倒数第二层若存在叶子结点, 一定在右部连续位置
满二叉树一定是完全二叉树, 完全二叉树不一定是满二叉树
完全二叉树结点数 n 满足 $2^{k-1}-1<n\leq 2^k-1$
对有 $n$ $n$ 个结点的完全二叉树的结点按层序编号 ( $1\leq i\leq n$ $1 \leq i \leq n$ ), 对任一结点有
1. $i=1$ , 则结点 $i$ 是二叉树的根, 无双亲; 如果 $i>1$ , 双亲为 $\lfloor\frac{i}{2}\rfloor$ ;
2. 如果 $2*i>n$ , 则结点 $i$ 无左孩子; 如果 $2*i\leq n$ , 则左孩子是 $2*i$ ;
3. 如果 $2*i+1>n$ , 则结点 $i$ 无右孩子; 如果 $2*i+ 1\leq n$ , 则其右孩子是 $2*i+1$

二叉树的存储

以链式存储为例

typedef int BTDataType
struct BinaryTreeNode
{
    struct BinTreeNode* _pLeft;
    struct BinTreeNode* _pRight;
    BTDataType _data;
}

二叉树的遍历

以访问根结点的顺序, 分为先序遍历, 中序遍历, 后序遍历

二叉树的遍历

先序遍历: ABCDEFG (按顺序来)
中序遍历: CBEDAFG (落果果)
后序遍历: CEDBGFA (摘果果, 先把所有左子树摘掉)

先序遍历

先访问根结点
再访问左子树
后访问右子树

void PreOrderTraverse(BiTree T)
{
    if(T == NULL){
        return;
    }
    printf("%c", T->data);
    PreOrderTraverse(T->Lnode);
    PreOrderTraverse(T->Rnode);
}

中序遍历

先访问左子树
再访问根结点
后访问右子树

void InOrderTraverse(BiTree T)
{
    if(T == NULL){
        return;
    }
    PreOrderTraverse(T->Lnode);
    printf("%c", T->data);
    PreOrderTraverse(T->Rnode);
}

后序遍历

先访问左子树
再访问右子树
后访问根结点

void PostOrderTraverse(BiTree T)
{
    if(T == NULL){
        return;
    }
    PostOrderTraverse(T->Lnode);
    PostOrderTraverse(T->Rnode);
    printf("%c", T->data);
}

二叉树的代码

求二叉树所有结点个数

int size = 0;
void TreeSize(BTNode* root)
{
    if(root == NULL)
    {
    }else{
        size++;
    }
    TreeSize(root->left);
    TreeSize(root->right);
}

求叶子结点的个数

int TreeLeafSize(BTNode* root)
{
    if(root == NULL)
    {
        return 0;
    }
    if(root->left == NULL && root->right == NULL)
    {
        return 1;
    }
    return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

求二叉树的高度

int Height(Tree& t)
{
    if(t==NULL)
    {
        return 0;
    }
    if (Height(t->left) > Height(t->right))
    {
        return Height(t->left)+1;
    }else{
        return Height(t->right)+1;
    }
}

输出二叉树中的所有叶子结点

void PrintLeaves(BinTree BT)
{
    if(BT)
    {
        if(!BT->left && !BT->Right)
        {
            printf("%d", BT->Data);
        }
        PrintLeaves(BT->Left);
        PrintLeaves(BT->Right);
}

二叉树的变形

二叉排序树 BST

特点:

左子树上所有结点的值均小于或等于它根结点的值
右子树上所有结点的值均大于或等于它根结点的值
左右子树均为二叉排序树
中序遍历的序列是递增的序列

举个栗子: 将 (5, 2, 7, 3, 4, 1) 依次插入初始为空的二叉搜索树, 则该树的后序遍历结果是:

二叉排序树

查询成功平均 AVL:

AVL = \frac{每一层的结点数\times 层数和}{总结点数目}

上面这张图的 $AVL = \frac{1*1+2*2+3*3+1*4}{7}$

二叉排序树的插入

Status InsertBST(BiTree &T, ElemType e)
{
    if(SearchBST(T, e.key, p))
    {
        s = (BiTree)malloc(sizeof(BiTNode));
        s->data = e;
        s->lchild = s->rchild = NULL;
        if(!T)
        {
            T = s;
        }else if(e.key<p->data)
        {
            p->lchild=s;
        }else{
            p->rchild = s;
        }
        return true;
    }else{
        return false;
    }
}

二叉排序树的删除算法

删除叶子结点

只需要将双亲结点中指针域的值改为空
被删除结点只有左子树或右子树

双亲节点的指针域改为 “指向被删除结点的左子树或右子树”
被删除结点既有左子树, 又有右子树

以被删除结点的前驱代替被删除结点, 然后再删除该前驱结点 (这里的前驱和后继指的是中序遍历时的顺序)

二叉排序树的平衡 - 二叉平衡树 AVL 树

为什么 BST 需要平衡: 每个结点左右子树的高度差不超过1, 此时插入和删除的时间复杂度为 $O(\mathrm{log}n)$ ; 如果不平衡, 操作性能可能退化到 $O(n)$ , 退化成链表

note: 树的深度是根结点数到叶结点, 高度是从叶结点到它的根结点

常见的平衡 BST 包括

AVL 树
红黑树
伸展树
B 树和 B+ 树

如何构造二叉平衡树: 采用平衡旋转技术

二叉平衡树举例

左旋来源:

左旋示意图

右旋:

右旋示意图

平衡二叉树插入结点的四种情况:

新结点插入后, 可能导致树不平衡, 此时有"左左", “左右”, “右左”, "右右"等情况 (第一个左右代表位于根结点的左或者右, 第二个左右代表位于最接近插入节点的拥有两个子节点的父节点位置的左或右)

其中, 左左, 右右只需要一次旋转就能平衡; 左右, 右左需要两次才能平衡

举例

LL 型:
RR 型:
RL型:
LR 型

哈夫曼树及哈夫曼编码

哈夫曼树

树的带权路径长度最短的一类树为 “最优树”

具有 n 个叶子结点的哈夫曼树共有 2n-1 个结点

哈夫曼树中仅有度为 2 和度为 0 的结点

度为 m 的哈夫曼树中, 结点的度只有 0 或 m, 假设非叶节点个数为 a, 叶子结点个数为 n, 在该哈夫曼树中度为 m 的结点有 m 个分支, 度为 0 的结点有 0 个分支, 所以总结点数 = 总分支数 + 1, 所以 n+a = a*m+n*0+1, 化简后 a = (n-1)/(m-1)

哈夫曼树

举例: 已知权值 $W=\{5, 6, 2, 9, 7\}$

构造哈夫曼树

哈夫曼编码

堆

堆排序是树的应用, 堆适合使用顺序存储结构

堆是符合以下性质的数列 $\{r_1, r_2, \dots, r_n\}$ :

\begin{cases} r_i\leq r_{2i} \\ r_i\leq r_{2i+1} \end{cases}(小顶堆)\\ \begin{cases} r_i\geq r_{2i} \\ r_i\geq r_{2i+1} \end{cases}(大顶堆)\\

note: 倒置小顶堆不一定是大顶堆, 甚至不一定是堆

堆排序:

以初始关键字序列, 建立堆
输出堆顶最小元素
调整余下元素, 使其称为一个新堆
重复23, 直至有 n 个元素输出, 得到一个有序序列

举例, 反正考了也不会 (卒)

森林

森林的表示

note: 树没有中序遍历算法, 只有二叉树有中序遍历算法, 森林没有后序遍历算法

树转换成的二叉树, 其根结点的右子树一定为空

树转换为二叉树

图

有向图, 无向图, 路径, 连通图, 强连通图 (有向图)

生成树: 无向图 G 是含有 n 个顶点的连通图, 图 G 的生成树是含有 n 个顶点, 且只有 n-1 条边的连通子图

图的存储: 邻接矩阵, 邻接表

图的存储

放弃了

图的遍历

深度优先搜索 DFS, 广度优先搜索 BFS

深度优先搜索 DFS

用栈实现, 适合搜索全部的解

访问顶点 v
依次从 v 的未被访问的邻接点出发, 对图进行深度优先搜索, 如果到某一点的邻接点都被找到, 则回退; 直至图中和 v 有路径相通的顶点都被访问
若此时图中有顶点未被访问, 则从未被访问的顶点出发, 重新进行 DFS, 直至图中所有顶点均被访问

广度优先搜索 BFS

利用队列实现, 适合搜索最优解

广度优先搜索的解一定是路径最短解, 但是搜索效率较低

访问顶点 $v_i$
访问 $v_i$ 的所有未被访问的邻接点 $w_1, w_2, \dots, w_k$
依次从这些邻接点出发, 访问它们所有未被访问的邻接点

图的应用

最小生成树

对于具有 n 个顶点的无向连通图 G, 生成树不一定唯一. 最小生成树中的边权值和最小

参考算法导论–最小生成树（Kruskal和Prim算法）-CSDN博客

Kruskal 算法

加边法, 初始最小生成树边数为 0, 每迭代依次就选择一条满足条件的最小代价边, 加入到最小生成树的边集合里

Kruskal 算法

我的理解: 按权值从小到大选择边，并且保证选择的边不会形成环，直到生成树中包含所有节点. 对点到集合的路径进行排序

用二叉树实现

初始化空列表, 用于存储最小生成树的边
将所有边按权值从小到大排序
遍历排序后的边列表, 对于每条边, 检查两个端点是否形成环, 若未形成环, 则将边加入列表
重复步骤 3 直至最小生成树的边列表包含 $n-1$ 条边, $n$ 为结点数

Prim 算法

加点法, 每次迭代选择代价最小的边对应的点, 加入到最小生成树中

Prim 算法

我的理解: 每次选择与当前生成树连接的最小权重边，并且该边的另一端点不在生成树中 (不能形成环)，直到生成树包含所有节点. 对边排序

用列表实现:

初始化空列表, 用以存储最小生成树的边, 选择起始结点, 加入生成树集合, 再初始化
从队列中选择权重最小的边, 检查边的另一端点是否已经在生成树中, 若不是则没有环, 将该边加入最小生成树中
重复步骤 3, 直至生成树包含所有结点

拓扑排序 AOV 网

AOV 网, 表示流程图或程序框图, 用于判定工程的可行性和各项活动在工程中的先后顺序

拓扑排序算法

AOV网中, 选取一个没有前驱的顶点输出
删除该顶点和所有以它为弧尾的弧
重复以上两步, 直至 AOV 网中全部顶点都已输出, 或图中仅剩环

拓扑排序

关键路径 AOE 网

时间最长的路径为关键路径

关键路径

最短路径

包括广度优先搜索 (BFS) 算法, 迪杰斯特拉算法, 弗洛伊德算法. 其中 BFS 只能处理无权图, 迪杰斯特拉算法可以解决带权图问题, 弗洛伊德算法可以解决带负权边图问题. 三种算法都不能解决带负权回路图问题

广度优先搜索算法

通过队列实现

初始化队列, 将起始节点放到队列中
初始化访问集合, 创建一个集合记录被访问过的结点
遍历结点
1. 从队列中取出一个结点
2. 访问该结点并将该结点标记为已访问
3. 将结点的邻结点都加入队列中
4. 依次访问邻结点
重复步骤 3 直至队列为空

迪杰斯特拉算法

解决问题: 带权图的单源最短路径问题, 是贪心算法

核心思想: 将与起始结点直接相连的结点作为候选结点, 未直接相连的结点将距离标注为无穷; 选出候选结点中距离起始结点最短的结点作为下一次迭代的中间结点, 对与中间结点直接相连的结点的路径长度进行更新 (间接相连与直接相连取最小). 重复以上过程直至所有结点完成更新.

人话: 按路径长度递增的次序产生到各顶点的最短路径

时间复杂度: $O(n^2)$

通过邻接表来遍历:

初始化二维数组 dist[] (即邻接矩阵), 再初始化从起始结点出发的最短路径的结点集合 path[]
选择起始结点的邻结点, 将距离起始结点最短的邻结点加入 path (加入中间结点)
更新邻接矩阵 dist, 直接相连与间接相连取最小
重复步骤 2 和 3, 直至得到起始结点到所有结点的距离

弗洛伊德算法

解决问题: 带负权边图的最短路径问题, 运用动态规划思想

核心思想: 对图初始化, 遍历所有结点, 直接相连的边标注, 不直接相连的边权值标注为无穷; 再次遍历所有结点, 每次将遍历到的结点作为中间结点, 更新所有结点间的权值

时间复杂度: $O(n^3)$

用邻接表实现:

初始化二维数组 dist[] (即邻接矩阵), 再初始化
遍历所有结点, 以当前结点为中间结点, 更新所有结点间的距离, 直接相连与间接相连取最小
重复步骤 2 直至所有结点都被当作中心节点遍历过