数据结构与算法——基础知识

数据结构概述

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。

定义

数据结构(data structure)是带有结构特性的数据元素的集合，它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系，并对这种结构定义相适应的运算，设计出相应的算法，并确保经过这些运算以后所得到的新结构仍保持原来的结构类型。简而言之，数据结构是相互之间存在一种或多种特定关系的数据元素的集合，即带“结构”的数据元素的集合。“结构”就是指数据元素之间存在的关系，分为逻辑结构和存储结构（也称为物理结构）。

数据的逻辑结构和存储结构是数据结构的两个密切相关的方面，同一逻辑结构可以对应不同的存储结构。算法的设计取决于数据的逻辑结构，而算法的实现依赖于指定的存储结构。

数据结构的研究内容是构造复杂软件系统的基础，它的核心技术是分解与抽象。通过分解可以划分出数据的3个层次；再通过抽象，舍弃数据元素的具体内容，就得到逻辑结构。类似地，通过分解将处理要求划分成各种功能，再通过抽象舍弃实现细节，就得到运算的定义。上述两个方面的结合可以将问题变换为数据结构。这是一个从具体（即具体问题）到抽象（即数据结构）的过程。然后，通过增加对实现细节的考虑进一步得到存储结构和实现运算，从而完成设计任务。这是一个从抽象（即数据结构）到具体（即具体实现）的过程。

按逻辑结构的分类

数据结构有很多种，一般来说，按照数据的逻辑结构对其进行简单的分类，包括线性结构和非线性结构两类；

线性结构

简单地说，线性结构就是表中各个结点具有线性关系。如果从数据结构的语言来描述，线性结构应该包括如下几点：

• 线性结构是非空集。
• 线性结构有且仅有一个开始结点和一个终端结点。
• 线性结构所有结点都最多只有一个直接前趋结点和一个直接后继结点。
• 现行结构有两种不同的存储结构：顺序存储结构（数组）和链式存储结构（链表）
• 线性结构主要包含：数组、队列、链表和栈

非线性结构

简单地说，非线性结构就是表中各个结点之间具有多个对应关系。如果从数据结构的语言来描述，非线性结构应该包括如下几点：

• 非线性结构是非空集。
• 非线性结构的一个结点可能有多个直接前趋结点和多个直接后继结点
• 非线性结构主要包含：二维数组、多维数组、广义表、树结构、图结构
• 在实际应用中，数组、广义表、树结构和图结构等数据结构都属于非线性结构

按存储结构的分类

按照数据的存储结构对其分类，包括链式存储结构和顺序存储结构两类。

顺序存储结构

逻辑上相邻的结点存储在物理位置上相邻的存储单元中，结点之间的逻辑关系由存储单元的邻接关系来体现。主要优缺点如下：

• 节省存储空间：因为分配给数据的存储单元都会用来存储数据，节点的逻辑关系不会占用额外的存储空间。
• 随机存储更方便：通过对应的序号就能快速的取出所需要的数据。
• 对结点的插入、删除运算时，由于需要移动其他结点，可能存在性能问题。
• 在JAVA/C/C++等语言中的数组就是典型的顺序存储结构。

链式存储结构

它不要求逻辑上相邻的元素在物理位置上也相邻，因此它没有顺序存储结构所具有的弱点，但也同时失去了顺序表可随机存取的优点。其特点主要表现在：

• 比顺序存储结构的存储密度小(链式存储结构中每个结点都由数据域与指针域两部分组成，相比顺序存储结构增加了存储空间)。
• 逻辑上相邻的节点物理上不必相邻。
• 插入、删除灵活 (不必移动节点，只要改变节点中的指针)。
• 查找节点时链式存储要比顺序存储慢。
• 每个节点是由数据域和指针域组成。