什么是数据结构

一、数据结构的起源

1968年，美国高德纳教授，《计算机程序设计艺术》第一卷《基本算法》提出，开创了数据结构与算法的先河

数据结构是一门研究数据之间关系、操作的学科，而非计算数据方法

数据结构 + 算法 = 程序 揭露了程序的本质，沃思凭借这个观点获得了图灵奖

二、数据结构中的基本概念

数据：任何能够输入到计算机中，能被程序处理的描述客观事物的符号

数据项：有独立含义的最小单位，也叫做 数据域、域

数据元素：组成数据的、有一定意义的基本单位，也叫做节点、结点、顶点； 一个数据元素是由若干项数据项组成

数据结构：相互之间存在一种或多种特定关系的数据元素的结合

算法：数据结构中所具备的功能，能够解决某种问题的方法

三、研究数据结构的三个方面

数据的逻辑结构：一对一 一对多 多对多

数据的存储结构(物理结构)：顺序存储、链式存储

数据结构的运算

四、数据的逻辑结构

集合：数据元素同处于同一个集合中，但是元素之间没有任何关系

线型结构(表)：数据元素之间存在一对一的关系

树型结构(树): 数据元素之间存在一对多的关系

图型结构(图): 数据元素之间存在多对多的关系

五、数据的存储结构\物理结构

顺序结构：

数据元素是存储在连续的内存中，用数据元素的相对位置来表示数据元素之间的关系，内存空间是连续的，并且数据元素之间也要确保连续

优点：支持随机访问，访问效率极高，适合查找数据，不容易产生内存碎片

缺点：对数据元素的插入、删除操作效率低、实现不方便，对内存的要求较高

链式结构：

数据元素存储在彼此独立的内存空间中，每个独立的元素称为节点，每个节点中额外增加一块指针域，通过该指针可以指向下一个与该节点有关系的节点，以此来表示数据节点之间的关系

优点：对节点的删除、插入操作效率高，实现简单，适合增删数据操作，对内存空间的要求较低

缺点：不支持随机访问，只能从前往后逐一访问，不适合频繁地查找数据、容易产生内存碎片

六、逻辑结构与存储结构的对应关系

表：   顺序(数组) 、 链式(链表)

树：   链式（优先）  、 顺序

图：   顺序+链式

每种逻辑结构采用哪种存储结构没有明确规定，通常根据实现的难度、空间的要求、时间的要求综合选择最合适的存储结构

七、数据结构的运算

1、建立数据结构     create\creat

2、销毁数据结构     destroy

3、清空数据结构     clear

4、插入元素         insert\add

5、删除元素         delete

6、修改元素         modify

7、访问元素         access

8、查询元素         query

9、遍历数据结构     show\list\ergodic

10、排序数据结构    sort