数据结构与算法——知识点总结_数据结构与算法知识点总结-程序员宅基地

技术标签: 算法  数据结构与算法  数据结构  

本文包含数据结构与算法主要的基本知识点,便于知识的梳理与回顾。

部分知识点的详细介绍请在专栏内查阅。

目录

一、概述

二、线性表

三、栈

四、队列

五、串

六、多维数组和广义表

七、树和二叉树

八、图

九、查找

十、排序


一、概述

数据结构(逻辑结构、存储结构、算法)
数据项 ∈ 数据元素(记录) ∈ 数据。

数据元素(结点):数据的基本单位。
数据项:不可分割,最小数据单位。
数据对象 :性质相同的数据元素的集合, 数据的子集。
1、逻辑结构(线性和非线性)
数据结构(相互之间存在一种或多种特定关系的数据元素的集合)

  1. 集合:同属于一个集合是数据元素之间的唯一关系。
  2. 线性结构:“一对一”关系,仅有一个直接前驱和一个直接后继。
  3. 树形结构:”一对多”关系,除根节点外仅有唯一直接前驱,所有结点都可以有0到多个直接后继。
  4. 图形结构:”多对多”关系,多个直接前驱和多个直接后继。

2、存储结构

  1. 顺序存储(一维数组)
  2. 链式存储(链表)
  3. 索引存储(索引表)
  4. 散列(hash)存储(构造散列函数)

3、算法和效率

  • 算法:有穷性、确定性、可行性、输入、输出。
  • 目标:正确性、可读性、健壮性、高效性、低存储量。
  • 效率:事先估算法和事后统计法。
  • 评价(数量级):时间复杂度和空间复杂度。

二、线性表

1、线性表
基本操作:创建、求长度、查找(按值)、插入、删除、显示。
2、顺序存储
顺序表
        元素的物理顺序和逻辑顺序一致。
·特点:按数据元素的序号随机存取。
·优点:节约存储空间。
·缺点
        插入和删除操作耗时。
        预先分配最大空间,存储空间浪费。
        表的容量难以扩充。
3、链式存储
线性链表

  1. 单向链表:一个数据域和一个指针域
  2. 循环链表:最后一个结点的指针指向头结点
  3. 双向链表:一个数据域和两个指针域

三、栈

后进先出。
运算:进栈、出栈、判栈空、判栈满、读栈顶元素、显示栈元素。

  1. 顺序栈(顺序存储)
  2. 链栈(链式存储)

应用:
        ·数制转换
                十进制N转k进制,循环(执行N=N/k操作,余数入栈),直到余数为0,出栈即结果。
        ·表达式求值
                1. 中缀表达式(Infix Notation)
                        运算符放在两个操作数之间。(存在优先级问题,处理速度慢)
                2. 前缀表达式(Prefix Notation)
                        运算符放在两个操作数之前。(不存在优先级问题,自右向左扫描)
                3. 后缀表达式(Postfix Notation)
                        运算符放在两个操作数之后。(不存在优先级问题,自左向右扫描)
        ·中缀表达式转后缀表达式

        (1)读人操作数,直接输出到后缀表达式。
        (2)读入运算符。压入运算符号栈。
            ①若后进的运算符优先级高于先进的,则继续进栈。
            ②若后进的运算符优先级不高于先进的,则将运算符号栈内高于或等于后进运算符级别的运算符依次弹出并输出到后缀表达式。
        (3)括号处理。
            ①遇到开括号“(”,进运算符号栈。
            ②遇到闭括号“)”,则把最靠近的开括号“(”以及其后进栈的运算符依次弹出并输出到后缀表达式(开括号和闭括号均不输出)。
        (4)遇到结束符“#”,则把运算符号栈内的所有运算符号依次弹出,开输出到后缀表达式。
        (5)若输入为+、-单目运算符,改为0和运算对象在前,运算符在后。

        ·后缀表达式求值
        ·中断处理和现场保护

四、队列

先进先出。
运算:入队、出队、读队头、显示队列元素、判队空、判队满、求队长。
1、顺序队列
        1. 顺序队列
                “假溢出”现象。
        2. 循环队列
                解决“假溢出”。
2、链队列
应用:
        ·输入输出管理
        ·对CPU的分配管理
        ·优先队列(priority queue)
                权值优先。
        ·双(双端)队列(double-ends queue)
                操作系统的调度工作则是采用双端队列。

五、串

术语:长度、空串、空格串、串相等、字串、主串、模式匹配(主串:目标串,子串:模式)。
运算:求串长、串连接、求子串、串比较、插入子串、删除子串、模式匹配。

  1. 顺序存储(类似线性表)
  2. 链接存储
  3. 堆分配存储(开辟一块地址连续的存储空间)

六、多维数组和广义表

1、多维数组
        数组是一个有固定格式和数量的有序集合,每个数据元素由唯一的一组下标来标识。多维数组为非线性结构,n维数组最多有n个直接前驱和n个直接后继。
        ·以行为主(按行优先顺序)
        ·以列为主序(按列优先顺序)
2、特殊矩阵的压缩存储
对称矩阵:n(N+1)/2
三角矩阵:n(n+1)/2+1
        ·上三角矩阵
        ·下三角矩阵
3、稀疏矩阵
1)存储
        ·三元组表
                行列值(i,j,v)。
        ·带行指针的链表
                根据行指针将同一行的值(三元组形式)用链表连接起来。
        ·十字链表
                解决三元组存储稀疏矩阵的缺点:在进行运算(如加、减)时非零元素的位置和个数会发生变化。
思想:
        把非零元素作为一个结点(i,j,v,down,right,三元组+列指针域+行指针域)存储。
列指针域:指向本列中下一个非零元素。
行指针域:指向本行中下一个非零元素。
行头结点只使用right指针域。
列头结点只使用down指针域。
总头结点存储原矩阵的行数和列数。
2)算法
创建

加法

4、广义表
线性表的推广,广义表通常用小括号括起来并用逗号隔开表中元素。
        长度:第一层所包含的元素(原子、子表)个数。
        深度:展开后所包含括号的层数(嵌套数)。
首尾存储法

  • 表结点:标志域、表头指针域、表尾指针域。
  • 原子结点:标志域、值域。

特点:采用链式存储(广义表的数据元素可以具有不同的结构)

七、树和二叉树

1、树
术语

结点(包含数据和分支)、结点的度(结点的子树数)、树的度(树中各结点度的最大值)、叶子(度为零)、分支结点(度不为零)、兄弟结点、层数、树的深度(高度)、森林(零或者有限棵互不相交的树的集合)、有序树(结点的子树从左到右有序)和无序树。
树根(根节点),有且仅有一个,无前驱结点。
表示法

  • 嵌套集合法(文氏图法)
  • 圆括号表示法
  • 凹入法

2、二叉树
特殊的有序树。
性质1:一颗非空二叉树的第i层上最多有2^(i-1)个结点(i>=1)。
性质2:深度为h的二叉树中,最多具有2^h-1个结点(h>=1)。

性质3:对于一颗有n个结点的完全二叉树,若按满二叉树的同样方法对结点进行编号,则对于任意序号为i的结点,有:

  1. (父结点):若i=1,则序号为i的结点是根结点。若i>1,则序号为i的结点的父结点的序号为(向下取整i/2)。
  2. (左孩子):若2i<=n,则序号为i的结点的左孩子结点的序号为2i。若2i>n,则序号为i的结点无左孩子。
  3. (右孩子):若2i+1<=n,则序号为i的结点的右孩子结点的序号为2i+1。若2i+1>n,则序号为i的结点无右孩子。

性质4:具有n(n>0)个结点的完全二叉树(包括满二叉树)的深度(h)为(向下取整log2^n)+1。

性质5:对于一颗非空的二叉树,设n0, n1, n2分别为表示度为0、1、2的结点个数,则有n0=n2+1。
满二叉树
        深度为h,且有2^h-1个结点的二叉树。
完全二叉树
        深度为h,有n个结点的二叉树。当且仅当每一个结点都与深度为h的满二叉树中编号从1至n的结点一一对应时,缺失部分一定是右边的。
存储
        一般二叉树:

                链式存储(二叉链表,左数右、三叉链表,左数右父)
        完全二叉树或满二叉树:

                顺序存储(既能节省空间,又能利用下标确定结点在二叉树中的位置)
3、遍历二叉树和线索二叉树
1. 遍历二叉树

  1. 先序遍历(DLR,根左右)
  2. 中序遍历(LDR,左根右)
  3. 后序遍历(LRD,左右根)
  4. 层次遍历(逐层访问,自上而下,从左到右)

2. 恢复二叉树
前序+中序(前序确定根节点,中序确定左子树和右子树)

  1. 根据前序序列确定根节点,根据中序序列确定左子树和右子树。
  2. 分别找出左子树和右子树的根节点,并把左、右子树的根节点连到父节点上。
  3. 对左子树和右子树重复以上两步,直到子树只剩下1个结点或2个结点或空为止。

中序+后序(后序确定根节点,中序确定左子树和右子树)

        同上
3. 线索二叉树
        带有线索(指向直接前驱结点或指向直接后继结点的指针)的二叉树。
优点:
        ·进行中序遍历时不必采用堆栈处理,遍历速度快,节约存储空间。
        ·任意一个结点能直接找到它相应遍历顺序的直接前驱和直接后继结点。
缺点:
        ·节点的插入和删除麻烦且速度慢。
        ·线索树不能共用。
线索化:对二叉树以某种次序遍历使其变为线索二叉树的过程。
先序线索二叉树、中序线索二叉树(中序线索化使用最多)、后序线索二叉树。
4、二叉树的转换
一般树转换为二叉树
        把一般树的长子作为其父结点的左子树,次弟作为其兄结点的右子树。

方法:

  1. 连线:链接树中所有相邻的亲兄弟之间连线。
  2. 删线:保留父结点与长子的连线,打断父结点与非长子之间的连线。
  3. 旋转:以根节点为轴心,将整棵树顺时针旋转一定的角度,使之层次分明。

森林转换为二叉树

        森林是若干棵树的集合。只要将森林中的每一棵树的根视为兄弟,而每一棵树又可以用二叉树表示,这样,森林也就可以用二叉树来表示了。
方法:
(1)将森林中的每一棵树转换成相应的二叉树。
(2)第一棵二叉树保持不动,从第二棵二叉树开始,依次把后一棵二叉树的根结
点作为前一棵二叉树根结点的右子树,直到把最后一棵二叉树的根结点作为其前一棵二叉树的右子树为止。

二叉树转换为树和森林

        树转换为二叉树以后,其根结点必定无右子树;而森林转换为二叉树以后,其根结点有右分支。显然这一转换过程是可逆的,即可以依据二叉树的根结点有无右子树,将一棵二叉树还原为树或森林。
方法:
(1)若某结点是其父结点的左孩子,则把该结点的右孩子、右孩子的右孩子,直到最后一个石核于都与该结点的父结点连起来。
(2)删除原二叉树中所有的父结点与右孩子结点的连线。
(3)整理(1)、(2)的结果,使之层次分明。

5、哈夫曼树
术语

路径长度(结点间)、树的路径长度(根结点到每个结点的路径长度之和)、结点的带权路径长度(结点到根结点之间路径长度与该结点上的权的乘积)、树的带权路径长度(树中所有叶子结点的带权路径长度之和)。
注:决策判定问题中,哈夫曼树可以获得最佳的决策算法。
基本思想

(1)由给定的n个权值{W1,W2,…,Wn}构造n棵只有一个叶结点的二叉树,从而得到一个二叉树的集合F={T1,T2,…, Tn}。
(2)在F中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树,这棵新的二叉树根结点的权值为其左、右子树根结点权值之和。
(3)在集合F中删除作为左、右子树的两棵二叉树,并将新建立的二叉树加入到集合F中。

(4)重复(2)、(3)两步,直到F中只剩下一棵二叉树时,这棵二叉树便是所要建立的哈夫曼树。

哈夫曼编码

        在数据通信中,经常需要将传送的文字转换成由二进制字符0和1组成的二进制代码,称之为编码。如果在编码时考虑字符出现的频率,让出现频率高的字符采用尽可能短的编码,出现频率低的字符采用稍长的编码,构造一种不等长编码,则电文的代码就可能更短。
        哈夫曼编码是一种用于构造使电文的编码总长最短的编码方案。

八、图

边:无向直接连线(边)
弧:有向直接连线(弧:弧头、弧尾)
术语

无向图、有向图、无向完全图(任意两顶点有一条边相连,n(n-1)/2条边)、有向完全图(任意两顶点有方向相反的两条弧相连,n(n-1)条弧)、稠密图、稀疏图、顶点的度(拥有的边数,度、入度、出度)、权、网(带权图,无向网、有向网)、路径、路径长度(路径上边的数目)、回路、简单路径、简单回路、子图、连通图(任意两顶点都相连通)、连通分量(极大连通子图)、强连通图(有向图中)、强连通分量(有向图中)、弱连通图(有向图中,考虑方向不连通,不考虑方向则连通)、生成树(连通图的一个子图,该子图是一个包含连通图所有顶点的树)。
1、存储
邻接矩阵
表示顶点之间相邻关系的矩阵。
邻接表
图的一种顺序存储与链式存储结合的存储方法。

  • 顶点结点结构:顶点标志域、指针域(指向第一条邻接边)
  • 边结点结构:下标域(邻接顶点的)、指针域(指向第一条邻接边)

优点:通过某顶点查找以该顶点为弧尾的弧结点很方便。
缺点:通过该顶点查找以其为弧头的弧结点需要遍历整张邻接表。
注:逆邻接矩阵的优缺点和邻接矩阵相反。
十字链表

优点:方便通过某顶点能够同时查找以该顶点为弧尾和弧头的弧结点。
2、遍历

  • 广度优先搜索(BFS,类似树的层次遍历)
  • 深度优先搜索(DFS,类似树的先序遍历)

3、连通性
最小生成树
        构造算法:Prim算法、Kruskal算法
4、最短路径
算法:迪杰斯特拉(Dijkastra)、
5、有向无环图
有向无环图(不存在环的有向图)
应用:
        ·拓扑排序

        ·关键路径

九、查找

1、静态查找表
顺序查找

基本思想:

        从表的一端开始扫描线性表,依次按给定值与关键字进行比较,若相等,则查找成功,并给出数据元素在表中的位置;若整个表查找完毕,仍未找到与给定值相等的关键字,则查找失败,给出失败信息。
时间复杂度:查找长度的量级(O(n))
优点:对表中数据元素的存储没有要求。
缺点:当n很大时,平均查找长度较大,效率低。只能进行顺序查找(线性链表)

二分查找

基本思想:

        在有序表中,取中间元素作为比较对象,若给定值与中间元素的关键字相等,则查找成功;若给定值小于中间元素的关键字,则在中间元素的左半区继续查找;若给定值大于中间元素的关键字,则在中间元素的右半区继续查找。不断重复上述查找过程,直到查找成功,或所查找的区域无数据元素,查找失败。
时间复杂度:O(log2^n)
优点:效率高
缺点:
    ·必须按关键字排序,有时排序也很费时。
    ·只适用顺序存储结构,进行插入、删除操作必须移动大量的结点。

分块查找

基本思想:

        将具有n个元素的主表分成m个块(又称子表),每块内的元素可以无序,但要求块与块之间必须有序,并建立索引表。索引表包括两个字段:关键字字段(存放对应块中的最大关键字值)和指针字段(存放指向对应块的首地址)。查找方法如下:
        (1)在索引表中检测关键字字段,以确定待找值kx所处的分块(可用二分查找)位置。
        (2)根据索引表指示的首地址,在该块内进行顺序查找。

2、动态查找表

二叉排序树
        二叉排序树是空树或者具有以下性质的二叉树:
        (1)若左子树不空,则左子树上所有结点的值均小于根结点的值。
        (2)若右子树不空,则右子树上所有结点的值均大于根结点的值。
        (3) 左、右子树也都是二叉排序树。
基本思想:

  1. 若查找树为空,查找失败。
  2. 查找树非空,将给定值与杳找树的根结点关键字比较。
  3. 若相等,查找成功,结束查找过程,否则:

        ·当给定值小于根结点关键字时,查找将在左子树上继续进行,转到①。
        ·当给定值大于根结点关键字时,查找将在右子树上继续进行,转到①。
时间复杂度:(n+1)/2(最差)
平衡二叉树
        平衡二叉树是指树中任一结点的左、右子树高度大致相等的二叉树。平衡二叉树有很多种,最著名的是AVL树。平衡二叉树是一棵空树或者是具有以下性质的二叉排序树:
        (1)它的左子树和右子树的高度之差(称为平衡因子)的绝对值不超过1。
        (2)它的左子树和右子树又都是平衡二叉树。
解决插入结点后失去平衡:

  1. 不平衡子树形态为LL型。
  2. 不平衡子树形态为LR型。
  3. 不平衡子树形态为RR型。
  4. 不平衡子树形态为RL型。

3、哈希表

        哈希查找也称为散列查找,它既是一种查找方法,又是一种存储方法(散列存储)。散列存储的内存存放形式称为散列表(哈希表)。
        散列查找与前述的方法不同,数据元素的存储位置与关键字之间不存在确定的关系,也不需要进行一系列的关键字查找比较。它是依据关键字直接得到其对应的数据元素位置,即要求关键字与数据元素间存在一一对应的关系。通过这个关系,很快地由关键字得到对应的数据元素位置。
哈希函数的构造方法

1)直接定址法

2)除留余数法

处理冲突的方法
1)开放定址法

  • 线性探测法
  • 二次探测法(平方探测法)

2)拉链法(链地址法)

十、排序

十大常用排序算法比较
排序算法 平均时间复杂度 最好情况 最坏情况 空间复杂度 排序方式 稳定性
冒泡 O(n^{2}) O(n) O(n^{2}) O(1) in-place 稳定
选择 O(n^{2}) O(n^{2}) O(n^{2}) O(1) in-place 不稳定
插入 O(n^{2}) O(n) O(n^{2}) O(1) in-place 稳定
希尔 O(nlogn) O(nlog^{2}n) O(nlog^{2}n) O(1) in-place 不稳定
归并 O(nlogn) O(nlogn) O(nlogn) O(n) out-place 稳定
快速 O(nlogn) O(nlogn) O(n^{2}) O(nlogn) in-place 不稳定
O(nlogn) O(nlogn) O(nlogn) O(1) in-place 不稳定
计数 O(n+k) O(n+k) O(n+k) O(k) out-place 稳定
O(n+k) O(n+k) O(n^{2}) O(n+k) out-place 稳定
基数 O(n\times k) O(n\times k) O(n\times k) O(n+k) out-place 稳定
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_41750911/article/details/125041841

智能推荐

C语言实现 产生可能的集合_c语言集合-程序员宅基地

文章浏览阅读1.8k次,点赞2次,收藏7次。C语言实现 产生可能的集合。给定一组数字或符号,输出产生的所有可能的集合(包括空集合)。 _c语言集合

sqli-labs Less-25、25a(sqli-labs闯关指南 25、25a)_saqi-labs第25关报错注入-程序员宅基地

文章浏览阅读867次。sqli-labs Less-25、25a(sqli-labs闯关指南 25、25a)_saqi-labs第25关报错注入

pygame连续移动图片,并且背景颜色改变_pygame明明已经实现了持续移动-程序员宅基地

文章浏览阅读1.1k次。import sys, pygame,randompygame.init()size = width, height = 1920, 1800black =[(250,235,215),(0, 0, 0),(0,238,238)]screen = pygame.display.set_mode(size)ball = pygame.image.load("11.jpg")ballrect = ball.get_rect()pygame.key.set_repeat(pygame.KEY_pygame明明已经实现了持续移动

H5嵌入原生开发小结----兼容安卓与ios的填坑之路-程序员宅基地

文章浏览阅读251次。一开始听说开发H5,以为就是做适配现代浏览器的移动网页,心想不用管IE了,欧也。到今天,发现当初too young too simple,兼容IE和兼容安卓与IOS,后者让你更抓狂。接下来数一下踩过的坑。主要分UI展示,键盘,输入框等等。解决bug最苦恼的问题不是没有解决方案,而是你没有找到真正的原因。再就是现象难以重现,每次都要发布代码,然后到手机app中去测试,模拟。这些地方会耗费大量的精力。..._ios输入框被键盘挡住的解决办法

一个实习生java面试过程班,秋招,实习,面试,offer之路_java实习生面试流程-程序员宅基地

文章浏览阅读931次。不知不觉已经工作一年多的,我是2019年7月毕业的,但是如果算上实习就工作差不多两年了的吧。最近不是刚刚过了圣诞节吗?然后又准备到元旦了,迎来2021年!在微信公众号上看到小部分公众号在总结2020年了。所以就勾起自己从毕业到现在的回忆,顺便总结一下,自己如何从准备秋招到拿到offer的,算作记录一下自己的另一个阶段。犹记得,当初高考结束的时候后,自己填报的志愿大部分都是计算机相关的,因为从高中开始,就一直对于电脑方面比较感兴趣,可能跟自己小时候喜欢看科幻片有关吧????(一个科幻迷)。小时候,就觉得以_java实习生面试流程

vue项目启动报错 Error: spawn cmd ENOENT_note that the development build is not optimized. -程序员宅基地

文章浏览阅读5.9k次,点赞5次,收藏8次。【代码】vue项目启动报错 Error: spawn cmd ENOENT_note that the development build is not optimized. to create a production bui

随便推点

成功解决for循环语句中,后几次循环输出数据一直全部为空_taro小程序 定时器循环方法里面数据赋值一直为空-程序员宅基地

文章浏览阅读5.5k次,点赞6次,收藏12次。成功解决for循环语句中,后几次循环输出数据一直全部为空目录解决问题解决思路解决方法解决问题for循环语句中,后几次循环输出数据一直全部为空解决思路 数据为空,如果不是数据本身的问题,那么,很有可能是在for循环中,定义变量被覆盖,下次循环中,该变量内的数据已被重新定义,再次循环时该变量已经被改变!解决方法for循环的定义中,切记,变量不要覆盖!..._taro小程序 定时器循环方法里面数据赋值一直为空

Linux>>CentOS 7镜像下载及安装_centos7 2009j最小化版下载-程序员宅基地

文章浏览阅读1.3k次。Linux>>CentOS 7镜像下载下载映像文件,地址https://www.centos.org/download/1.虚拟机配置好后,安装等待就好了…2.出现如下界面选择简体中文,继续…3.进入如下页面,选择分区:添加新的挂载点–>4.选择软件选择,进入如下界面5.选择网络和主机名,开启,然后开始安装…6.设置root密码,密码最好复杂点…7.创建用户,8.完成安装,重启…9.重启后点击许可协议,接受即可,完成配置…10.完成安装_centos7 2009j最小化版下载

java中的数据类型概述_请对java的数据类型所包含的内容进行表述。-程序员宅基地

文章浏览阅读109次。数据类型的作用:数据类型用来声明变量,程序在运行过程中根据不同的数据类型分配不同大小的空间.数据类型在java语言中包括两种:第一种:基本数据类型基本数据类型又可以分为四大类八小种第一类:整数型(byte,short,long,int)第二类:浮点型(float,double)第三类:布尔型(boolean)boolean只有两个值true和false,true表示真,false表示假.第四类:字符型(char)java中规定字符型字面量必须使用单引号括起来.第二种:_请对java的数据类型所包含的内容进行表述。

第三章_简述core dom与html dom访问和修改节点属性值的方法-程序员宅基地

文章浏览阅读591次。第三章 JavaScript操作DOM对象3.1 DOM操作DOM是Document Object Model的缩写,即文档对象模型。3.1.1 DOM操作分类操作DOM是通常分为三类:DOM Core(核心)、HTML-DOM和CSS-DOM。1.DOM CoreDOM Core不是JavaScript的专属品,它的用途不仅限于处理一种使用标记语言编写出来的文档。2.HTML-DOM它提供了一些更简单的标记来描述各种HTML元素的属性。3.CSS-DOMCSS-DOM技术的主要作用是_简述core dom与html dom访问和修改节点属性值的方法

pyecharts 入门之词云图(六)_pyecharts制作词云图-程序员宅基地

文章浏览阅读382次。pyecharts 关于词云图的绘制_pyecharts制作词云图

【Spring Boot 4(1),2021年春招Java面试题-程序员宅基地

文章浏览阅读43次。<artifactId>mybatis-spring-boot-starter</artifactId> <version>2.1.1</version> <groupId>com.oracle.ojdbc</groupId> <artifactId>ojdbc8</artifactId> <scope>runtime</scope> ..

推荐文章

热门文章

相关标签