什么是数据结构

数据结构是计算机存储、组织数据的方式（指能够被计算机识别、存储和加工处理的信息的载体），是指相互之间存在一种或多种特定关系的数据元素的集合

将数据合理的组织起来，就可以称做一种数据结构。

数据结构的几个基本概念和术语

1.数据

是指能直接输入计算机中，被计算机处理的符号和被计算机操作的对象。总的来说，数据就是计算机处理的符号。

数据有两个必备条件：能直接输入计算机，能被计算机直接处理。

2.数据元素

是数据结构中基本的独立单位，也被叫做元素、结点、记录等。

数据元素往往是由若干个数据项组成，数据项是具有独立含义的最小标识单位。

3.数据对象

是性质相同的数据元素的集合。（所谓性质相同就是指数据元素具有相同数量和相同类型的数据项）

数据结构以某种内在联系将由数据项组成的数据元素组织成为一个数据对象。

数据结构的分类

之前知道了数据结构是相互之间的存在一种或多种关系的数据元素的集合。

这种关系可以分为两个反面：逻辑关旭和存储方式。

1.逻辑结构分类：

1.1集合

在集合中，数据元素都属于这个集合，但数据元素之间并没有什么关系。

1.2线性结构

线性结构中的元素具有一对一的关系，通过前一个结点可以找到后一个结点。（单向链表、双向链表）

线性结构分为顺序存储和链式存储：

• 顺序存储是由一段地址连续的空间来存储元素。
• 链式存储是由分散的单元空间来存储元素，存储单元由指针相连接。

在线性结构中，除了头尾结点外，可以通过前一个结点来寻找后一个结点，也可以通过后一个结点来寻找前一个结点。

1.3树形结构

树形结构中数据元素之间存在一对多的层次关系。

除了根结点外，每一个结点都必须有一个且只有一个前驱结点，但可以有任意个后继结点。这些数据元素有自顶向下的层次的关系。

1.4图形结构

图形元素中的数据元素存在多对多的关系，每个结点的前驱和后继结点都可以是任意个。

2.存储结构：

存储结构反映的是数据元素在计算机中的存储形式。

常见的存储结构有：顺序存储结构、链式存储结构、索引存储结构、散列表。

2.1顺序存储结构

顺序存储结构是把逻辑上相邻的结点存储在地址连续的存储单元里。

通常同编程里的数组来描述，数据的逻辑关系与物理关系是一致的。

例如：int a[5] = {100,200,30,40,5};

其中的元素a[0]~a[4]在逻辑上是连续的，在存储器物理地址也是连续的。

顺序存储结构的优缺点：

• 优点：可以提高空间利用率，对于随机访问元素，效率非常高（按元素序号来快速查找到元素）
• 缺点：实现元素的插入和删除效率非常低，因为插入时要将部分元素全部往后移动一个位置，删除一个元素时将部分元素全部向前移动一个位置。

在使用时顺序存储结构还有空间限制：

• 当需要存储的元素的个数多于预先分配的空间时，会出现溢出问题。
• 当元素个数少于预先分配的空间时，又会造成空间浪费。（一般来说浪费比溢出好，溢出会出现很多问题）

2.2链式存储结构

链式存储结构在空间上是一些不连续的存储单元，这些存储单元的逻辑关系通过附加的指针字段来表示。

链式存储结构中，有指向前驱元素的指针字段，有指向后继元素的指针字段。

• 单向链式：通过前面的元素找到后面的元素。（前找后）
• 双向链式：通过前面的元素找到后面的元素，也可以通过后面的元素找到前面的元素。（前找后、后找前）

链式存储在内存中分配的单元是不连续的，需要用指针将它们串起来。链式存储结构更利于元素的插入与删除。

• 在两个元素之间插入一个元素时，