数据结构与算法（概述）：数据结构概述

数据：全部能被输入到计算机中，且能被计算机处理的符号的集合。是计算机操做的对象的总称。
数据元素：数据（集合）中的一个“个体”，数据及结构中讨论的基本单位
数据项：数据的不可分割的最小单位。一个数据元素可由若干个数据项组成。
数据类型：在一种程序设计语言中，变量所具备的数据种类。整型、浮点型、字符型等等
逻辑结构：数据之间的相互关系。
集合：结构中的数据元素除了同属于一种类型外，别无其它关系。
线性结构：数据元素之间一对一的关系
树形结构：数据元素之间一对多的关系
图状结构或网状结构：结构中的数据元素之间存在多对多的关系
物理结构/存储结构：数据在计算机中的表示。物理结构是描述数据具体在内存中的存储（如：顺序结构、链式结构、索引结构、哈希结构）等
在数据结构中,从逻辑上能够将其分为线性结构和非线性结构
数据结构的基本操做的设置的最重要的准则是,实现应用程序与存储结构的独立。实现应用程序是“逻辑结构”，存储的是“物理结构”。逻辑结构主要是对该结构操做的设定，物理结构是描述数据具体在内存中的存储（如：顺序结构、链式结构、索引结构、希哈结构）等。
顺序存储结构中，线性表的逻辑顺序和物理顺序老是一致的。但在链式存储结构中，线性表的逻辑顺序和物理顺序通常是不一样的。

什么是数据结构

简单地说，数据结构是以某种特定的布局方式存储数据的容器。这种“布局方式”决定了数据结构对于某些操做是高效的，而对于其余操做则是低效的。首先咱们须要理解各类数据结构，才能在处理实际问题时选取最合适的数据结构。

数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。

为何咱们须要数据结构

数据是计算机科学当中最关键的实体，而数据结构则能够将数据以某种组织形式存储，所以，数据结构的价值不言而喻。不管你以何种方式解决何种问题，你都须要处理数据——不管是涉及员工薪水、股票价格、购物清单，仍是只是简单的电话簿问题。数据须要根据不一样的场景，按照特定的格式进行存储。有不少数据结构可以知足以不一样格式存储数据的需求。

常见的数据结构

首先列出一些最多见的数据结构，之后的文章会将逐一说明：

数组
栈
队列
链表
树
图
字典树（这是一种高效的树形结构，但值得单独说明）
散列表（哈希表）

数据结构分类

数据存储结构

简单理解为在计算机中如何存储，主要分为两种，一种为顺序存储结构，一种为链式存储结构；

顺序存储结构

在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素,称做线性表的顺序存储结构。

把数据元素存放在地址连续的存储单元里，其数据间逻辑关系和物理关系是一致的；数组就是典型的顺序存储结构。

特色：

一、随机存取表中元素。

二、插入和删除操做须要移动元素。

链式存储结构

在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元能够是连续的,也能够是不连续的)。它不要求逻辑上相邻的元素在物理位置上也相邻.所以它没有顺序存储结构所具备的弱点,但也同时失去了顺序表可随机存取的优势。

特色：

一、比顺序存储结构的存储密度小 (每一个节点都由数据域和指针域组成，因此相同空间内假设全存满的话顺序比链式存储更多)。
二、逻辑上相邻的节点物理上没必要相邻。
三、插入、删除灵活 (没必要移动节点，只要改变节点中的指针)。
四、查找结点时链式存储要比顺序存储慢。
五、每一个结点是由数据域和指针域组成。

顺序存储结构和链式存储结构的区别

链表存储结构的内存地址不必定是连续的，但顺序存储结构的内存地址必定是连续的；
链式存储适用于在较频繁地插入、删除、更新元素时，而顺序存储结构适用于频繁查询时使用。

顺序存储结构和链式存储结构的优缺点

空间上
顺序比链式节约空间。是由于链式结构每个节点都有一个指针存储域。
存储操做上：
顺序支持随机存取，方便操做
插入和删除上：
链式的要比顺序的方便（由于插入的话顺序表也很方便，问题是顺序表的插入要执行更大的空间复杂度，包括一个从表头索引以及索引后的元素后移，而链表是索引后，插入就完成了）

数据逻辑结构

数据逻辑结构就是数据与数据以前有什么关系；

集合结构

集合结构中的数据元素同属于一个集合，他们之间是并列关系，没有其余关系。

线性结构

开始节点和终端节点都是惟一的，咱们能够把第一个节点认为是开始节点，第四个节点认为是终端节点。除了开始节点和终端节点之外，其他节点都有且仅有一个前驱节点，有且仅有一个后继节点。对于第二个节点来讲，它的前驱节点就是第一个节点，它的后继节点是第三个节点。

概念

线性结构做为最经常使用的数据结构，其特色是数据元素之间存在一对一的线性关系。
线性结构拥有两种不一样的存储结构，即顺序存储结构和链式存储结构。顺序存储的线性表称为顺序表，顺序表中的存储元素是连续的，链式存储的线性表称为链表，链表中的存储元素不必定是连续的，元素节点中存放数据元素以及相邻元素的地址信息。
线性结构中存在两种操做受限的使用场景，即队列和栈。栈的操做只能在线性表的一端进行，就是咱们常说的先进后出（FILO），队列的插入操做在线性表的一端进行而其余操做在线性表的另外一端进行，先进先出（FIFO），因为线性结构存在两种存储结构，因此队列和栈各存在两个实现方式。

树形结构

开始节点惟一，终端节点不惟一，开始节点就是指的根节点，终端节点就是指的最下面的节点。除终端节点之外，每一个节点有一个或多个后继节点，在根节点的左节点中有三个后继节点，右节点有两个后继节点，除开始节点外（根节点没有前驱节点），每一个节点有且仅有一个前驱节点。

树做为一种应用普遍的一对多非线性数据结构，不只有数据间的指向关系，还有层级关系，示例见图一。因树的结构比较复杂，为了简化操做及存储，咱们通常将树转换为二叉树处理，所以本文主要讨论二叉树。

二叉树
　　二叉树是每一个节点最多拥有两个子节点的树结构，若移除根节点则其他节点会被分红两个互不相交的子树，分别称为左子树和右子树。二叉树是有序树，左右子树有严格的次序，若颠倒则成为一棵不同的二叉树。
满二叉树
　　满二叉树，顾名思义除叶子节点外全部节点都拥有两个孩子，且叶子节点在同一层的二叉树，示例见图二。
彻底二叉树
　　彻底二叉树，移除最后一层节点后是满二叉树，且最后一层的节点都连续集中在最左面，示例见图三。

图形结构

没有开始节点和终端节点，全部节点均可能有多个前驱节点和多个后继节点，也就是说造成了一个多对多的图形结构，咱们在图形结构中也看到了，节点之间是相互链接的。

总结

对于集合结构集合中的元素是并列的；线性结构来讲，节点之间的关系是一对一的；树形结构的节点是一对多；图形结构的节点是多对多的关系。