数据结构的基本介绍

数据结构就是数据的组织形式，用一种提前设计好的框架去存取数据，以便更方便，高效的对数据进行增删查改。正确选择合适的数据结构，对软件程序的高效执行的影响作用不亚于算法的设计。此外，在计算机系统中数据结构的作用也是非同小可。例如常常在编程语言中听到的栈，堆等，就是经典的数据结构。

 

经典的数据结构大致如下：

 

一：线性数据结构

(1)：列表

a：有序列表

其项保持排序次序。

b：无序列表

其项不按任何特殊顺序排列。

(2)：队列

先进先出(FIFO)，通常没有在队列中搜索项的操作。

(3)：栈

后进先出(LIFO)，通常没有在栈中搜索项的操作。

 

二：树

(1)：二叉树

其项对整棵树的贡献依赖于它们在树中的位置。

(2)：普通树

二叉树结构的一般化。

(3)：二叉查找树

每一项都是自足的，整棵树的意义与项的相对排列无关。它是有序列表的树模拟。可以随意添加，删除或搜索项。

(4)：AVL树

特殊的高度平衡的二叉查找树。在搜索项的机制方面，其搜索速度得到极大的提高。

(5)：作为优先队列的堆

优先队列，其中的项有指定的优先度。在优先队列的所有项中，有最高优先度的项最先离开。根据概念结构，它是作为堆实现的，而堆是特殊的二叉树结构。

(6)：可更新堆

可更新优先度的堆。

 

三：散列表

存储以高效搜索为唯一目的的项。与二叉查找树不同，散列表不以有效的顺序排列项，也没有树结构。其实现需要关于树的数学性质的丰富知识，以及关于操作数的所谓的散列函数的丰富知识。

 

四：图

普通树是图的特殊形式，因为层次是项间关系的特殊系统。用图来模拟如万维网(网页与网页间的链接)，计算机网络和航线等结构系统，使用一个或多个标准图算法来解决问题。

 

在选择正确的数据结构时，一般从支持的操作的接口，效率，占据空间的大小，接口中的操作的运行时间等几个方面进行考虑。通常时间和空间是可以相互转换的。在构建不断复杂化的程序时，必须十分注意在最少量的结构和弹性结构之间做出选择，同时要尝试寻找更合适的中间结构。对于每一种数据结构，给出其接口中的每一个操作的运行时间。这是实现的价格标签，也是更一般的效率成本的定量衡量。