数据结构与算法

2021-11-05 17:06:48   76  举报





AI智能生成

数据结构与算法是计算机科学的两个核心领域，它们共同构成了解决实际问题的基础。数据结构是一种组织和存储数据的方式，使得我们可以高效地访问、修改和删除数据。常见的数据结构有数组、链表、栈、队列、哈希表、树、图等。而算法则是一系列解决问题的步骤和规则，它决定了如何操作数据结构以实现特定的功能。常见的算法有排序、查找、递归、动态规划、贪心算法等。通过学习和掌握数据结构和算法，我们可以更好地理解计算机科学的本质，提高编程能力，为解决实际问题提供有力支持。

算法和数据结构

算法与数据结构

java

数据结构与算法

算法思想

作者其他创作

大纲/内容

数据结构与算法基本概述

什么是数据结构？

数据结构是一门研究非数值计算的程序设计问题中计算
机的操作对象及其关系的学科。

包括：逻辑结构，存储结构，运算结构

数据结构（存储结构）

什么是存储结构？

存储结构是逻辑结构在计算机中的实际表现，称为物理结构。
它包括数据元素的表示和关系的表示。

包括：顺序存储 ,链式存储

顺序结构

将内容放在连续的容器中，依照他们之间的相对位置来存储。
（里面的数据是不具备关系的）

链式结构

利用数据元素之间引用或者指针来建立关系
（里面的数据随机分配）

图示

数据结构（运算结构即算法）

什么是算法？

算法是对特定问题求解步骤的一种描述，是指令的有限序列，
其中每一条指令表示一个或多个操作。

什么是数据？

数据是客观现实在计算机中的符号表现，一切可以运用计算并可以被计算机识别的符号就被称为数据。

什么是数据元素？

数据元素是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理，也被称为记录。

什么是数据项？

数据元素中的一项被称为数据项，若干个数据项组成了数据元素。

程序

什么是程序？

程序=数据结构+算法

衡量程序优劣

时间复杂度

什么时程序复杂度？

时间复杂度是指程序执行的时间粒子的个数

标准写法

常数阶O(1) （没有循环一句话只跑一次）

对数阶O(logN) （循环为对应的while循环里面的数值越来越靠近终止条件）

线性阶O(n) （for循环）

线性对数阶O(nlogN) （for循环+while循环）

平方阶O(n²) （俩个for循环）

立方阶O(n³) （三个for循环）

K次方阶O(n^k) （k次循环）

指数阶(2^n) （越来越多）

空间复杂度

什么是空间复杂度？

空间复杂度是指开辟的内容空间个数

线性表

什么是线性表？

线性表是最基本、最简单、也是最常用的一种数据结构。线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。

线性表的特点

有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2

有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋a n-1。

除第一个节点外，线性表中的其它结点ai(2≤i≤n)都有且仅有一个直接前趋ai-1。

除最后一个节点外，线性中的其它节点ai(1≤i≤n-1) 都有且仅有一个直接后继a i+1

线性表的操作（接口）

数组

特点

有序下标长度不可变存储同一类型数据

数组操作

链表（依照元素的关系来建立联系

单向链表

单向链表的设计（增删改）

双向链表

单向链表的设计（增删改）

栈

概述

栈是一个特殊的线性表，他的特点为先进后出，后进先出。添加操作称为入栈，删除操作出栈。操作的
位置永远是栈顶。栈底是第一次进入元素。当栈中没有元素称为空栈。

实现栈

栈的接口

使用数组来实现栈

使用链表实现栈

解决迷宫寻路问题

队列

概述

队列属于特殊的线性表，他主要特点是只允许在一端做插入（入队）另一端做删除（出队）。他是一个
先进先出（FIFO）的容器。

队列接口

顺序队列

数组实现

链式队列

链表实现

串

字符串概述

串就是字符串是由一个个的字符组成的有限序列。（char数组作为底层实现）

串接口

实现类

String类型里面的char数组的长度由你的值来绝对
StringBuffer 线程安全长度可变值的长度+16 （缓冲区）
StringBuilder 线程不安全长度可变值的长度+16

树

概述

树又被称为二叉树，由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组
成的一个树状结构。

术语

节点度子节点的个数
树的度二叉树最大的度
层数从根节点（层为1）数起逐层递增其余结点的层数等于它的双亲结点的层数加1。
深度最大的层数被称为深度
叶节点没有子节点的节点（度为0的结点）被称为叶节点
分支节点度不为0的节点被称为分支节点
左孩子左边的子节点右孩子右边的子节点双亲父节点兄弟节点拥有同一双亲的子节点
路径 n1,n2,…,nk称为一条由n1至nk的路径（nk是nk+1的子节点）这条路径的长度是k-1
子孙和祖先子节点的节点被称为子孙节点父节点的父节点被称为祖先节点
满二叉树在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层
上，这样的一棵二叉树称作满二叉树。
完全二叉树基于满二叉树，叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部

性质

一棵非空二叉树的第i层上最多有2 i-1 个结点（i≥1）(每层节点数)

一棵深度为k的二叉树中，最多具有2 k -1个结点（总的节点数量）

对于一棵非空的二叉树，如果叶子结点数为n0，度数为2的结点数为n2，则有: n0＝n2＋1(叶子
节点数)

具有n个结点的完全二叉树的深度k为[log 2 n]+1 （深度）

对于具有n个结点的完全二叉树，如果按照从上至下和从左到右的顺序对二叉树中的所有结点从1
开始顺序编号，则对于任意的序号为i的结点，有：
（1）如果i>1，则序号为i的结点的双亲结点的序号为i/2(“/”表示整除)；如果i＝1，则序号为i的结
点是根结点，无双亲结点。
（2）如果2i≤n，则序号为i的结点的左孩子结点的序号为2i；如果2i>n，则序号为i的结点无左孩
子。
（3）如果2i＋1≤n，则序号为i的结点的右孩子结点的序号为2i＋1；如果2i＋1>n，则序号为i的
结点无右孩子。

此外，若对二叉树的根结点从0开始编号，则相应的i号结点的双亲结点的编号为（i－1）/2，左
孩子的编号为2i＋1，右孩子的编号为2i＋2。

顺序二叉树

底层使用数组来实现

链式二叉树

使用链表来实现二叉树（俩个单向链表）

红黑树

左边只能放比自己小的右只能放比自己大的

翻转二叉树

哈夫曼树

概述

哈夫曼树（haffman）他又被称为最优二叉树（寻宝）。根据权值判断。
对于多个叶节点，且带有权值。进行计算得出带权路径最小的为最优二叉树

带权路径

各个(叶节点的权值*叶节点的路径长度)的总和=带权路径

特点

哈夫曼树权值越大的叶节点离根节点越近，权值越小离根远

构建过程

由给定的n个权值{W1，W2，…，Wn}构造n棵只有一个叶结点的二叉树，从而得到一个二叉树的集合F＝
{T1，T2，…，Tn}；

在F中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树，这棵新的二叉树
根结点的权值为其左、右子树根结点权值之和；

在集合F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合F中；

重复步骤（2）（3）两步，当F中只剩下一棵二叉树时，这棵二叉树便是所要建立的哈夫曼树

图

概述

图是一系列顶点（结点）和描述顶点之间的关系边（弧）组成 G =(V,E) V是顶点的集合 E是边的集
合

专业术语

无向图: 俩个顶点之间没有指向的图叫做无向图。
有向图：俩个顶点之间有指向的图叫做有向图.
加权图：对应的边存在权值叫做加权图。
顶点集：图中具有相同特性的数据元素的集合称为顶点集
边（弧）：边是一对顶点间的路径，通常带箭头的边称为弧
弧头：每条箭头线的头顶点表示构成弧的有序对中的后一个顶点，称为弧头或终点
弧尾：每条箭头线的尾顶点表示构成弧的有序对中的前一个顶点，称为弧尾或始点。
度：在无向图中的顶点的度是指连那个顶点的边的数量。在有向图中，每个顶点有两种类的的度：出度
和入度。
出度：我指向别人的边的个数
入度：箭头指向我边的个数
权：有些图的边（或弧）附带有一些数据信息，这些数据信息称为边（或弧）的权（weigh）.
完全图：所有的顶点的度都一样，且如果有向那么对应的出度和入度也一致
有很少条边或弧的图称为稀疏图，反之称为稠密图。

使用邻接矩阵（array）实现

dfs深度优先搜索算法（先一条走到底直到走不通了回溯标识是否已经走过）

bfs广度优先搜索算法（层级遍历一层一层的往下走）

使用链表实现（顶点使用数组顶点包含边边链表）

狄克斯特拉算法（最短路径）

概述

他是用来解决有向图的最短赋权路径，或者是无向图的单源赋权最短路径。

排序算法

冒泡排序(逐层往上冒每次交换位置)

选择排序（选一个值跟其他的所有比较）

插入排序(后面跟前面的比)

快速排序（冒泡排序的升级）