数据结构和算法

本视频源于B站小甲鱼的数据结构和算法视频。点我直达

本文档只了解数据结构和算法的基本介绍，所有的代码实现见本系列下篇文章。

数据结构

    数据分为逻辑结构和物理结构
  1. 逻辑结构
    2. 数据对象中数据元素之间的相互关系
  2. 物理结构
    3. 数据的逻辑结构在计算机中的存储形式

四种逻辑结构

  1. 集合结构
    2. 数据元素除了同属于一个集合外，他们之间没有其他关系
  2. 线性结构
    3. 数据元素之间是一对一的关系
  3. 树形结构
    4. 数据元素之间存在一种一对多的层次关系
  4. 图形结构
    5. 数据元素多对多的关系

两种物理结构

  1. 顺序存储
    2. 数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的
  2. 链式存储
    3. 数据结构存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的

算法

算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。

特性

  1. 输入
  2. 输出
  3. 有穷性
  4. 确定性
  5. 可行性

算法效率的度量方法

时间复杂度

定义：在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，记作T(n)=O(f(n))。他表示随问题规模n的增大，算法的执行时间和增长率和f(n)的增长率相同，称作算法的渐进时间复杂度。简称时间复杂度。

???,概念就是个鬼

常用的时间复杂度所消耗的时间从小到大依次是

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

空间复杂度

通过空间复杂度通过计算算法所需的存储空间实现，算法的空间复杂度的计算公式记作：S(n)=O(f(n))，其中n为问题的规模，f(n)为语句关于n所占存储空间的函数。

???,重复：概念就是个鬼

直接求复杂度时，通常指的是时间复杂度。

线性表

由零个或多个数据元素组成的有限序列。

    note:
  1. 线性表是一个序列，元素之间有先后顺序。
  2. 若元素存在多个，则第一个元素无前驱，最后一个元素无后继。其他都只有一个前驱和后继
  3. 线性表是有限的

数据类型

数据类型：一组性质相同的值的集合及定义在此集合上的一些操作的总称。

  1. 原子类型
    2. 不可以再分解的基本类型。
  2. 结构类型
    3. 由多种类型组合而成，可以再进行分解。

常见操作

初始化，求长，获取元素，获取元素位置，插入元素，删除元素，清空元素，查询是否为空

顺序存储结构

数组

对数组进行封装：

#define MAXSIZE 20
typedef int ElemType;
typedef struct{
    ElemType data[MAXSIZE];
    int length;//线性表当前长度
}Sqlist;
    封装需要三个属性：
  1. 起始位置
  2. 最大存储容量
  3. 当前长度

线性表的顺序存储结构，再存、读取数据时，时间复杂度都为O(1)。而在插入或者删除时，时间复杂度都是O(n)。比较适合元素个数比较稳定，不经常插入和删除元素，而更多的而操作时存取数据的应用。

优点：无需为表中元素之间的逻辑关系而增加额外的存储 空间。可以快速的存取表中任意位置的元素。

缺点：插入和删除操作需要移动大量元素。当线性表长度变化比较大时，难以确定存储空间的容量。容易造成存储空间的碎片。

链式存储结构

链表

链表的第一个节点的存储位置叫做头指针，最后一个节点指针为空（NULL）

头指针和头节点的异同：

头指针：

​ 头指针是指向第一个节点的指针若链表有头节点，则是指向头节点的指针。

​ 头指针具有标识作用，所以常用头指针冠以链表的名字（指针变量的名字）。

​ 无论链表为空，头指针均不为空。

​ 头指针是链表的必要元素。

头节点：

​ 头节点是为了操作的统一和方便而设立的。放在第一个元素的节点之前，其数据域一般无意义或者存放链表的长度。

​ 有了头节点，对再第一元素节点前插入节点和删除第一节点起操作与其他节点的操作就统一了

​ 头节点不一定是链表的必须要素。

对链表进行封装：

typedef struct Node{
    ElemType data;//数据域
    struct Node*Next;//指针域
}Node;
typedef struct Node* LinkList;

对于插入和删除操作：顺序存储结构和链式存储结构时间复杂度为O(n)，但是由于顺序存储结构但每次插入都要移动n-i个位置，所以每次都是O(n)，而单链表找到第i个位置的指针的时候，只是简单的移动指针，时间复杂度都是O(1)。因此对于插入和删除数据越频繁的操作，单链表的效率优势就越明显。

单链表

头插法：从一个空表开始，生成新节点，读取数据放到新节点的数据域中，然后将新节点插入到当前链表的表头上，直到 结束。

尾插法：头插法算法简单，生成链表中节点的次序和输入的顺序相反。把新节点都插入到最后称为尾插法。

整表删除：不使用链表时，需要再内存中进行释放，留出空间。

单链表结构与顺序存储结构优缺点：

存储分配方式

顺序存储结构用一段连续的存储单元依次存储线性表的数据元素。

单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素。

时间性能

查找：

​ 顺序存储结构O(1)

​ 单链表O(n)

插入和删除

​ 顺序存储结构需要平均移动表长一半的元素，时间为O(n)。

​ 单链表再计算出某位置的指针后，插入和删除时间仅为O(1)。

空间性能

顺序存储结构需要预分配存储空间，分大造成空间浪费，分小容易溢出。

单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制。

结论

若线性表需要频繁进行查找，很少进行插入和删除操作时，宜采用顺序存储结构

若需要频繁插入和删除时，宜采用单链表结构。

静态链表

1、数组的第一个元素和最后一个元素不存放数据

2、未使用的数组元素称为备用链表

3、数组的第一个元素即下表为0的那个元素的cur就存放备用链表的第一个节点的下标。

4、数组的最后一个元素，即下标为MAXSIZE-1的cur则存放第一个有数值的元素的下标，相当于单链表中头节点的作用。

为了辨明数组中哪些分量未被使用，解决的方法是将所有未被使用过的以及已被删除的分量用游标链成一个备用的链表。

静态链表的插入

静态链表的插入

静态链表插入2，图中有点错误：数据为E的游标应该为0.静态链表的最后一个元素需要指向下标0

//获取第一个空闲分量的下标
int malloc_sll(staticLinkList space){
    int i = space[0].cur;//备用链表的第一个节点
    if(space[0].cur){
        space[0].cur = space[i].cur;//并将第一个元素指向下一个备用节点
    }
    return i;
}
//在链表第i个位置插入
bool listInsert(staticLinkList L,int i,ElemType e){
    int j,k,l;
    k = MAX_SIZE-1;//第一个节点的数据游标
    //合法输入性判断
    if(i < 1 || i > ListLength(L) + 1){
        return false;
    }
    j=malloc_sll(L);//获取下标
    if(j){
        //数据赋值
        L[j].data = e;  
        //修改游标
        for(l = 1;l<= i-1;l++){
            k = L[k].cur;//遍历链表，找出第i个数据的游标。
        }
        L[j].cur = L[k].zhixiangcur;//链表游标赋值
        L[k].cur = j;
        
        return true;
    }
    return false;
}

每当进行插入时，便可以从备用链表上取得第一个节点作为待插入的新节点。

静态链表的删除

删除链表中的第i个元素

//下标为k的链表回收到备用链表
void Free_sll(staticLinkList space,int L){
    space[k].cur = sapce[0].cur;//将空闲节点的下个游标放到k处。
    space[0].cur = k;//k节点变为空，且当为第一个空闲节点
}

bool listDelete(staticLinkList L,int i){
    int j,k;
    if(i<1 || i>listLength(L)){
        return false;
    }
    
    k = MAX_SIZE - 1;
    
    for(j = 1;j <= i - 1;j++){
        k = L[k].cur;//遍历链表，找到指向该节点的游标
    }
    
    j = L[k].cur;//链表游标指向变化
    L[k].cur = L[j].cur;
    
    Free_sll(L,j);
    return true;
}

静态链表的长度

int listLength(staticLinkList L){
    int j=0;
    int i=L[MAX_SIZE - 1].cur;
    
    while(i){//链表遍历，找到最后一个有数据的元素，此元素游标为0
        i = L[j].cur;
        j++;
    }
    return j;
}

总结

优点：

​ 在插入和删除操作时，只需要修改游标，不需要移动元素，从而改进了在顺序存储结构中的插入和删除操作需要移动大量元素的缺点。

缺点：

​ 没有解决连续存储分配（数组）带来的表长难以确定的问题。

​ 失去了顺序存储结构随机存取的特性。

总的来说，静态链表其实时为了实现给没有指针的编程语言设计的一种实现单链表功能的方法。

腾讯面试题

快速找到长度单链表的中间节点。

1、遍历确定长度，再次循环到中间节点。

2、快慢指针，快指针是慢指针移动速度的两倍。

循环链表

对于单链表，由于每个节点只存储了向后的指针，到了尾部标识就停止了向后链的操作，也就是说，按照这样的方式，只能索引后继节点不能索引前驱节点。

将单链表中的最后一个节点的指针端由空指针改为指向头节点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表。

循环链表和单链表的主要差异就在于循环的判断空链表的条件上，原来判断head->next是否为null，现在判断head->next是否等于head。

有环链表：

​ 链表的为节点指向了链表中的某个节点。

双向链表

typedef struct DualNode{
    ElemType data;
    struct DualNode * prior;
    struct DualNode * next;
}DualNode, * DulinkList;

双向链表对于单链表来说，每个节点多了一个prior指针，对于插入和删除操作需要格外小心。不过，双向链表可以有效提高算法的时间性能，使用空间来换取时间。

栈和队列

栈

栈使一种重要的线性结构，使线性表的一种具体表现形式。

栈(stack)是一个后进先出(LIFO)的线性表，要求只在表尾进行删除和插入操作。

特点：

​ 栈的元素必须后进先出

​ 栈的操作智能在线性表的表尾进行

注：对于栈来说，表尾称为栈的栈顶(top)，相应的表头称为栈底(bottom)。

栈的插入操作(push)，叫做进栈，也成为压栈，入栈。

栈的删除操作(pop),叫做出栈，也成为弹栈。

栈的顺序存储结构

栈的本质是一个线性表，线性表有两种存储形式，栈也有顺序存储结构和链式存储结构。
最开始的栈中不含有任何数据，叫做空栈，此时栈顶就是栈底。数据从栈顶进入，栈顶栈底份力，整个栈的当前容量变大。数据出战时从栈底弹出，栈顶下移，整个栈的当前容量变小。

栈的顺序存储结构

typedef struct
{
    ElemType *base;//指向栈底的指针变量
    ElemType *top;//指向栈顶的指针变量
    int stackSize;//当前可用的最大容量
}sqStack;

栈在初始化的时候已经先确定好了空间大小，使用malloc开辟，因此地址连续。所以top++的结果就是入栈，top–就是出栈。当空间不足时，使用realloc重新开辟一定量的空间。

栈的链式存储结构

栈因为只是栈顶做插入和删除操作，所以比较好的方法就是将栈顶放在单链表的头部，栈顶指针和单链表的头指针合二为一。

栈的链式存储结构

队列

只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

队列是一种先进先出的线性表。

队列既可以使用链表实现，也可以使用顺序表实现。

队列结构体

与栈相反的是，栈一般使用顺序表实现，而队列一般用链表进行实现。如下图

在顺序存储结构中，插入队列的时间复杂度为O(1)，但是删除队列的时间复杂度需要所有元素前移为O(n)，

队列的存储结构

因此一个解决方法是，头指针不断向后偏移，但是会造成假溢出.

因此，需要使用循环队列解决该问题。解决假溢出的办法就是如果后面满了，就再从头开始，也就是头尾相接的循环。

循环队列的逻辑

循环链表的容量是固定的，而且队头和队尾指针都可以随着元素入出队列而发生改变，这样循环队列逻辑上好像是一个环形存储空间。但是要注意的是，在实际的内存当中，不可能真的环形存储区，只是使用顺序表模拟出来的逻辑上的循环。

递归和分治

递归

在高级语言中，函数调用自己和调用其他函数并没有本质的不同，我们把一个直接调用自己或通过一系列的调用语句间接的调用自己的函数，称作递归函数。

每个递归定义必须至少有一个条件，满足该条件时，递归不再进行。

使用递归能使程序的结构更清晰、更简洁、更容易让人理解，从而减少读懂代码的时间。

但大量的递归调用会建立函数的副本，会消耗大量的时间和内存，而迭代则不需要此种付出。

递归函数分为调用和回退阶段，递归的回退顺序是它调用顺序的逆序。

分治

当一个问题规模比较大且不容易求解的时候，就可以考虑将问题分成几个小的模块，逐一解决。

汉诺塔

代码略

八皇后

代码略

字符串

串是由零个或多个字符组成的有限序列，又名叫字符串。

串可以为空串，即没有字符。

子串和主串

子串完全包含于主串，且不可被打乱。

字符串的比较

字符串的比较是比较首字母的ASCII码大小，一般比较大小太多意义，更着重于字符串是否相等。

字符串的存储结构

字符串的存储结构和线性表相等，也分顺序存储结构和链式存储结构。

字符串的顺序存储结构是用一组地址连续的存储单元来存储串中的字符序列的。

按照预定义的大小，为每个定义的字符串变量分配一个固定长度的存储区，一般用定长数组定义。

BF算法

Brute Force

BF算法属于朴素的模式匹配算法。该算法最坏情况下要进行M(N-M+1)次比较，时间复杂度为O(M*N)。

KMP算法

算法思路

该算法大大的避免重复遍历的情况。

BF算法：

使用回溯，当遇到不同时，重新回到最开始进行比较，效率较低。

KMP算法的核心就是避免不必要的回溯。

KMP基本思想：

舍弃掉BF算法中当匹配到不重复的时候，重新进行匹配的方式，而是通过一个方式来实现只是回溯到不重复的位置 。

例：abcdabcdfghj为S串

​ abcdg为T串

BF算法实现为：T[0]与S[0]相等，匹配到T[4]与S[4]不相等时，重新进行回溯，将T[0]再与S[1]的进行依次比较。

KMP的算法实现为：匹配到T[4]与S[4]不相等时，直接跳过S[0]-S[3]，而直接使用S[4]与T[0]进行比较，减少回溯，优化时间

KMP基本了解：

将子串命名为T串，也是模式匹配字符串。将父串命名为S串，

T串，S串的第0个元素均用来存储字符串的长度。

给模式匹配串添加一个k数组（就是KMP算法中的next数组）。该数组指导这模式匹配字符串下一步该用第几号元素进行匹配。k的值即为T串的第k个元素进行匹配。该数组只与模式匹配字符串有关。

kmp算法

相关名词与图中k值分析：

前缀：从T串的第一个元素开始计算

后缀：从T[n]的前面的元素与前缀相等的最大部分。需要为正序相等。我最开始理解成了逆序相等就觉得很不对劲。

k值为后缀长度加1。

上例分析：

​ T[0] = length = 9

​ T[1]的固定k值为0

​ T[2]的k值为1，因为与T[0]不同。

​ T[3]的k值为1，因为前缀为a，后缀为b。

​ T[4]的k值为2，因为前缀为a(T[0])，后缀为a(T[3])。

​ T[5]的k值为3，因为前缀为ab（T[0]，T[1]），后缀最大匹配为ab（T[3]，T[4]）。

​ T[6]的k值为4，因为前缀为aba（T[0]，T[1]，T[2]），后缀最大匹配为aba（T[3]，T[4]，T[5]）。

​ T[7]的k值为2，因为前缀为a(T[0])，后缀最大匹配为a(T[6])。

​ T[8]的k值为2，因为前缀为ab(T[0]，T[1])，后缀最大匹配为ab(T[6]，T[7])。

​ T[9]的k值为3，因为前缀为ab（T[0]，T[1]），后缀最大匹配为ab（T[7]，T[8]）。

NEXT数组代码原理

NEXT数组：当模式匹配串T失配的时候，NEXT数组对应的元素指导应该用T串的哪个元素进行下一轮的匹配。

图示：

NEXT数组图示

代码如下，突然懵逼，很精髓。优化代码是优化部分新增。详见下一小节的优化

void get_next(String T,int *next){
    //j是前缀，i是后缀
    j = 0;
    i = 1;
    next[1] = 0;
    while(i < T[0]){
        if(j == 0 || T[i] == T[j]){
            i++;
            j++;
            next[i] = j;
            /*下面为优化代码*/
            if(T[i] != T[j]){
                next[i] = j;
            }
            else{
                next[i] = next[j];
            }
            /*优化代码结束*/
        }
        else{
            //j回溯
            j=next[j];
        }
    }
    //前缀是固定的，后缀是相对的
}
//懵逼树上懵逼果，懵逼树下只有我

最终实现

搞定NEXT数组，KMP就容易多了。（搞定可真不容易，我现在还没搞定）

实现

//返回子串T在主串S第pos个字符之后的位置，不存在则返回0
int index_kmp(String S,String T,int pos){
    int i = pos;
    int j = 1;
    int next[255];
    
    get_next(T,next);
    
    while(i < S[0] && j <= T[0]){
        if(0 == j || S[i] == T[j]){
            i ++;
            j ++;
        }
        else{
            j = next[j];
        }
    }
    
    if(j > T[0]){
        return i - T[0];
    }
    else{
        return 0;
    }
    
}

改进

其实吧，第一遍我不太明白，在第二遍手动撸代码的时候，在代码注释中详解。

KMP算法改进

树

之间讨论的都是一对一的线性结构，无论是线性表还是栈和队列，都是一对一的数据结构。

一对多的数据结构，称为树。

树

相关定义

树的定义：

树（Tree）是n（n>0）个节点的有限集。当n=0时称为空树。在任意一棵非空树中：

- 有且仅有一个特定的称为根（Root）节点；
- 当n>1时，其余节点可分为m（m>0）个互不相交的有限集T1，T2，。。。Tm，其中每一个集合本身又是一棵树，并且称为根的子树（Subtree）

节点分类：

刚刚的图片中，每一个圈圈称为树的一个节点。节点拥有的子树数称为节点的度（Degree），树的度取树内各节点的度的最大值。

  • 度为0的节点称为叶节点或终端节点
  • 度不为0的节点称为分支节点或非终端节点。除根节点外，分支节点也成为内部节点。

节点分类

节点的关系

节点的子树的根称为节点的孩子（child），相应的，该节点称为孩子的双亲（Parent），同一双亲的孩子之间互称为兄弟（SiBling）

节点的祖先时从根到该节点所经分支上的所有节点。

节点的层次

节点的层次（Level）是从根开始定义起，根为第一层，根的孩子为第二层。

其双亲在同一层的节点互为堂兄弟。

树中节点的最大层次称为树的深度（Depth）或高度。

其他概念

如果将树中节点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。

森林（Forest）是m（m>=0）棵互不相交的树的集合。对树中每个节点而言，其子树的集合即为森林。

树的存储结构

三种不同的表示法：双亲表示法，孩子表示法，孩子兄弟表示法。

双亲表示法

以双亲作为做因的关键词的一种存储方式。

假设以一组连续空间存储树的节点，同时在每个节点中，附设一个指示其双亲节点在数组中位置的元素。每个节点除了知道自己是谁之外，还需要知道双亲在哪里。

这样的存储结构，可以根据某节点的parent指针找到双亲节点。所用的时间复杂度是O(1)，索引到parent的值为-1时，表示找到了根节点。如果找到某个节点的孩子，则需要遍历整个树结构。

双亲表示法

孩子表示法

孩子表示法

由于树中每个节点可能有多个子树，无法确保只有一个子树。

孩子兄弟表示法

孩子兄弟表示法

二叉树

二叉的基本知识

二叉树是n个节点的有限集合，该集合或者为空集，或者由一个根节点和两颗互不相交的、分别称为根节点的左子树和右子树的二叉树组成。

每个节点最多有两个子树，所以二叉树中不存在度大于2的节点。

左子树和右子树是有顺序的，次序不能颠倒。

即使树中某节点只有一颗子树，也要区分他是左子树和右子树。

特殊二叉树

斜树 ：斜树需要所有的节点都是属于左节点或者都属于右节点。

满二叉树：二叉树中，如果所有的分支节点都存在左子树和右子树。并且所有叶子都在痛一层上，这样的二叉树称为满二叉树。

特点：

​ 叶子只在最后一层。

​ 非叶子节点的度一定是2。

​ 在同样深度的二叉树中，满二叉树的节点个数一定最多，同时叶子也是最多。

完全二叉树：对一颗具有n个节点的二叉树按层序编号，如果编号为i的节点与同样深度的满二叉树中编号为i的节点位置完全相同。则称之为完全二叉树。

特点：

​ 叶子节点只能出现在最下两层。

​ 最下层的叶子一定集中在左部连续位置。

​ 倒数第二层，若有叶子节点，一定在右部连续位置。

​ 如果节点度为1，则该节点只有左子树。

​ 同样节点数目的二叉树，完全二叉树的深度最小。

二叉树的遍历

从根节点触发，按照某种次序依次访问二叉树中所有节点，使得每个节点被访问且仅被访问一次。

前序遍历、中序遍历、后序遍历、层序遍历。

线索二叉树

将二叉树进行扩容，加入ltag和rtag。

当ltag为0时指向左节点，为1时指向该节点的前驱。

当rtag为0时指向右节点，为1时指向该节点的后继。

该方式通过中序遍历，可以通过牺牲一部分空间来换取时间。

二叉排序树

    或者是一个空树，或者具有下列性质
  • 左子树不为空，则左子树上左右节点的值均小于它的根结构的值
  • 右子树不为空，则右子树上所有节点的值均大于它的根结构的值
  • 他的左右子树也分别为二叉排序树

查找算法

静态查找

数据集合稳定、不需要添加，删除元素的查找操作。

使用线性表结构组织数据，可以使用顺序查找算法。如果对关键字进行排序何以使用折半查找算法或斐波那契算法等来提高查找的效率

顺序查找

略

插值查找（按比例查找）

与折半查找的时间复杂度均为O(log2n)，但是在数值分布较为均匀时，使用按比例查找速度会快很多，当数值分布不均匀时，按比例查找会相对于折半查找速度会慢很多。

斐波那契查找（黄金分割法查找）

与折半查找类似

线性索引查找

稠密索引、分块索引、倒排索引

动态查找

数据集合在查找的过程中需要同时添加和删除元素的查找操作。

可以考虑使用二叉排序树的查找技术，另外我们还可以使用散列表结构来解决一些查找问题。

散列表查找

该方式通过一定的计算方式，将数据存到指定位置的数组。当出现冲突时，也需要一些解决方案。但是总体来说，对于大量的数据，该方法有着无与伦比的优势。

排序

冒泡排序

依次比较并排序

选择排序

先取出最小的，放在前面，后面同理。

直接插入排序

从头遍历，顺序相同则遍历下一元素，否则插入到前面的对应顺序的位置。

希尔排序

从直接插入排序改进而来，第一次将数据分成两段，然后依次比较转换位置进行排序，再次将数据分为四段，再三个数据对比排序，直到缩小跨度到两个为最后一次。

堆排序

选择排序改进而来。使用完全二叉树。

将待排序的序列构造成一个大顶堆。

此时，整个序列的最大值就是堆顶的根节点。将它移走（将其与堆数组的末尾元素交换，此时末尾元素就是最大值）

然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素的最大值。

归并排序

假设初始序列有n个记录，则可以看成时n个有序的子序列，每个子序列的长度为1，然后两两归并，重复进行直到结束。

快速排序

略

总结

排序算法总结

排序算法的总结

排序算法比较

排序算法比较

algorithm skill
c

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！