算法--基本数据结构总结

约定不等于承诺〃 2022-08-07 06:40 169阅读 0赞

其实数据结构和算法真的很重要，以前一直不怎么在意，所以每次笔试面试都被鄙视。“编程就是算法和数据结构，算法和数据结构是编程的灵魂”，现在感觉这句话还是有点道理的。今天翻了翻一些基本的数据结构，记了一些基本的性质，进行总结，后面还会继续总结一些常见的查找和排序算法。

### 一、线性结构 ###

顺序存储线性表：将元素依次存储在地址连续的存储单元中，**物理上相邻**；

链式存储线性表：将元素按照逻辑顺序链接在依次，**不要求地址连续**；

栈:仅在表的一端进行插入、删除操作的线性表，**“后进先出”**；

队列:仅在表的一端进行插入，另一端进行删除的线性表，**“先进先出”**

栈和队列有时候笔试会针对”FIFO“这些特性出问题，不过一般理解了，就比较简单。

### 二、树    ###

#### 2.1概念    ####

二叉树是每个节点最多有两个子树（“左子树”和“右子树”）的树结构。

满二叉树：二叉树的每一层节点个数都达到最大（即深度为k，且有2^k-1个节点）；

完全二叉树：只有最下面两层节点的度数可以小于2，并且最下一层的节点都集中在左边（深度为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中，序号为1至n的节点对应）。

满二叉树是完全二叉树的特例，如下图：

![Center][]

平衡二叉树：又被称为AVL树，它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树（完全二叉树是平衡二叉树），如下图

![Center 1][]

#### 2.2二叉树性质：    ####

*  a.二叉树的第i层至多有2^\{i-1\}个结点；

*  b.深度为k的二叉树至多有2^k-1个结点;

*  c.具有n个节点的完全二叉树的深度k=log2n+1；

*  d.对任何一棵二叉树T，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1。

#### 2.3二叉树遍历    ####

二叉树遍历记住一点就行了，即遍历的顺序都是针对根节点而言的。例如先序即先访问根节点，再遍历左子树，最后遍历右子树。结合实例来讲，如下图：

![Center 2][]

先序遍历结果：abdgcefh

中序遍历结果：dgbaechf

后序遍历结果：gdbehfca

### 三、图    ###

无向完全图：任意两个顶点都有一条直接边相连接；在含有n个顶点的无向完全图中，有n(n-1)/2条边；

有向完全图：任意两个顶点都有方向互为相反的两条弧相连接；在含有n个顶点的有向完全图中，有n(n-1)条边。

图的深度优先遍历：类似于树的先序遍历，下图显示了深度优先搜索顶点被访问的顺序：

![Center 3][]

图的广度优先遍历：类似于树的按层次遍历，下图显示了广度优先搜索顶点被访问的顺序：

![Center 4][]

ps.上面两张图片来源 http://blog.csdn.net/andyelvis/article/details/1728378。 由于CSDN加了水印，有些模糊，看不清楚的话可以去图片原址去看。

[Center]: /images/20220805/44af6ea1e93e4673b86b63c8d5e7f08a.png
[Center 1]: /images/20220805/e7b8563ea3834f4c8d6a82eab771f3d2.png
[Center 2]: /images/20220805/2519e9e4e9c0447a83fd30305538d994.png
[Center 3]: /images/20220805/6f7cb3ab72be4f8fb6d06fa7c7126b26.png
[Center 4]: /images/20220805/fdb5678f060b4379bc57e7197f4a6c9d.png

发表评论取消回复

表情：

评论列表（有 0 条评论，169人围观）

还没有评论，来说两句吧...

相关阅读

相关【数据结构】排序算法总结

1. 归并排序2. 排序算法复杂度及稳定性分析在总结之前我们先介绍一下归并排序！

不念不忘少年蓝@/ 2024年04月23日 20:31/ 0 赞/ 91 阅读

相关 Python3 基本数据结构总结

简介 Python3基本数据结构有列表（list），元组（tuple），字典（dictionary）和集合（set）四种，结构如下： list = ['Goog

你的名字/ 2023年10月11日 10:13/ 0 赞/ 29 阅读

相关【数据结构与算法】【算法思想】【算法总结】索引结构

> “基础不是100分考60分，而是建摩天大楼的地基。” 为什么需要索引？（1）在实际的软件开发工作的本质都可以抽象为“对数据的存储和计算”。对应到数据结构和算法中，

深碍√TFBOYSˉ_/ 2022年12月10日 03:40/ 0 赞/ 258 阅读

相关数据结构——排序算法总结

排序（Sorting）就是将一组对象按照规定的次序重新排列的过程，排序往往是为检索而服务的，它是数据处理中一种很重要也很常用的运算。例如我们日常学习中的查字典或者书籍的目录

淡淡的烟草味﹌/ 2022年08月10日 12:57/ 0 赞/ 208 阅读

相关算法--基本数据结构总结

其实数据结构和算法真的很重要，以前一直不怎么在意，所以每次笔试面试都被鄙视。“编程就是算法和数据结构，算法和数据结构是编程的灵魂”，现在感觉这句话还是有点道理的。今天翻了翻一些

约定不等于承诺〃/ 2022年08月07日 06:40/ 0 赞/ 170 阅读

相关数据结构---排序算法总结

一、插入排序 1、直接插入排序 2、折半插入排序 3、希尔排序 -------------------- 1.1直接插入排序是最简单直接的排序

比眉伴天荒/ 2022年07月15日 10:22/ 0 赞/ 224 阅读

相关数据结构与算法基本概念

数据 > 数据（Data）是能够被计算机程序识别、存储、加工和处理的描述客观事物的数字等符号集合的总称。数据项 > 数据项（Data Item）是具有独立含义的

r囧r小猫/ 2022年05月28日 07:39/ 0 赞/ 253 阅读

相关数据结构与算法总结

数据结构与算法总结 https://blog.csdn.net/u010273362/article/details/77920891 标签： [数据

布满荆棘的人生/ 2022年05月28日 00:42/ 1 赞/ 541 阅读

相关数据结构和算法总结

一、二叉查找树也称有序二叉树，它是指一棵空树，或者满足以下性质的树：若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若任意节点的右

向右看齐/ 2022年05月19日 07:27/ 0 赞/ 249 阅读

相关数据结构与算法-基本概念

概要数据结构基本概念逻辑结构与物理结构抽象数据类型

迈不过友情╰/ 2022年03月25日 14:30/ 0 赞/ 325 阅读