1.1968年,美国的Donald Ervin Knuth教授开设了一门基本算法的课程,开设了数据结构的先河.
数据结构:研究数据与数据之间的关系,而非计算方法.
程序 = 数据结构 + 算法 -> 沃思,获得图灵奖
2.数据结构的基本概念
数据: 所有能够输入到计算机中去描述事物的符号
数据元素: 数据的基本单位又叫节点,结点,顶点,记录
数据项: 有独立含义的数据最小单位,也叫域.
数据结构: 数据元素和数据关系的集合
算法:数据结构所具备的功能,解决特定问题的方法
二.逻辑结构 和 存储(物理)结构
逻辑结构:
集合: 数据元素同属于一个集体,但是元素之间没有任何关系
线性结构: 数据元素之间存在一对一的关系(表)
树型结构: 数据元素之间存在一对多的关系(倒悬树)
图型结构: 数据元素之间存在多对多的关系(地图)
物理(内存)结构:
顺序结构(数组)
数组存储在连续的内存空间中,用数据元素的相对位置来表示关系.
链式结构(链表)
数据元素存储在彼此独立的内存空间中,每个独立的元素也叫做节点,每个数据元素中增加一个数据项用来存储其他元素的地址,用来表示元素之间的关系.
逻辑结构和物理结构之间的关系:
表 -> 顺序 链式
树 -> 顺序 链式
图 -> 顺序 + 链式
三.数据结构的运算
创建
增
删
改
查
插入
遍历
排序
顺序结构:
