软件设计师-数据结构

数据结构基本概念

首先了解三个概念

数据：所有能输入到计算机中并能够被计算机程序处理的符 的总称.它是计算机程序加工的原料

数据元素：数据的基本单位,在计算机程序中通常作为一个整体来进行考虑和处理.如数组中一个存储单元里面的数或者链表中一个结点

数据结构：是数据元素相互之间存在的一种或多种特定关系的集合.主要研究数据逻辑结构和存储结构及其运算的实现

数据的逻辑结构：结构定义中的“关系” 描述的是数据元素之间的逻辑关系，又称为逻辑结构，比如平常教学中所画的内存图，数组等为数据的逻辑结构.

数据的物理结构：数据结构在计算机中的实际表示形式称为数据的物理结构,又称为物理存储。

线性结构：结构中的数据元素之间存在一个对一个的关系 

图：状结构或 状结构  结构中的数据元素之间存在多对多的关系

线性表

按物理存储结构划分

线性结构中又分为顺序表和链表（按物理存储结构划分），顺序表按顺序存储结构，链表按链式存储结构。

链表的分类

单链表

双向链表

栈

先进后出原则

广义表

广义表(Lists，又称列表)是一种非线性的数据结构，是线性表的一种推广。即广义表中放松对表元素的原子限制，容许它们具有其自身结构。

树的遍历

前序遍历：根在前面，然后子结点从左到右排序

中序遍历：根结点在中间

后序遍历：根在后面，然后子结点从左到右排序

层次遍历：从上到下（根结点开始），每层从左到右开始遍历

二叉树（重要）

满二叉树：除了叶子结点，每个结点都有两个子结点

完全二叉树：只能缺叶子结点的右结点（从上到下从左到右的序 不能断）

如果完全二叉树根结点下标为0(例如用数组存储完全二叉树)，对于任意结点i，左子结点为2*i+1（前提2*i+1<数组.len），右子结点为2*i+2（前提2*i+2<数组.len）。

树转二叉树

最优二叉树（哈夫曼树）

用于哈夫曼编码，节省存储空间和传输带宽，是无损压缩的方式。

平衡二叉树

一棵平衡二叉树越平衡，查找效率越高。

定义

图的存储

邻接矩阵

图的遍历

广度优先遍历(BFS)

英文全称broadFirstSearch

V0 – V4 – V3 – V1 -》（V4链表，V1-V0已经访问过不再访问）V6-》（V3链表，V6-V0都已经访问过）-》(V1链表，V4-V0都已经访问) V2 

图的最小生成树

最小生成树，留下图中权值比较小的边。

普利姆算法

起点的所有边 – 》取最短的那条边连起来 -》两个点的所有边中最短边 -》连起来

克鲁斯卡尔算法

直接找最短的边然后连起来。（边数 <= 结点数 – 1）

树和图的区别

树是没有环路的（没有封闭区域）

树的结点为n，则边的最大值为n-1（即树：边数<=节点数-1）

稀疏矩阵

二维数组的的变种稀疏矩阵，为了节省空间提出的概念，有上三角下三角之分。（邻接矩阵可以用这种方式存储）

文章知识点与官方知识档案匹配，可进一步学习相关知识算法技能树首页概览33820 人正在系统学习中 相关资源：【内存遍历工具】Cheat.Engine.V5.4.简体中文版-专业指导文档类…