1968年美国人Donald E. Knuth开创了数据结构的最初体系，他所著的《计算机程序设计的艺术》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。\r\n1968年，数据结构作为一门独立的课程在国外开始出现。
数据结构历史沿革
8
数据结构的发展
从20世纪60年代末到70年代初，出现了大型程序，软件也相对独立，结构程序设计成为程序设计方法学的主要内容，人们越来越重视数据结构\r\n从70年代中期到80年代，各种版本的数据结构著作相继出现。目前，数据结构的发展并未终结，一方面，面向各专门领域中特殊问题的数据结构得到研究和发展，如多维图形数据结构等；另一方面，从抽象数据类型和面向对象的观点来讨论数据结构已成为一种新的趋势，越来越被人们所重视。
数据结构问题起源于程序设计
9
数据结构的发展并未终结
1. 无结构阶段\r\n2. 结构化阶段：数据结构＋算法＝程序\r\n3. 面向对象阶段： （数据结构＋算法）＝程序
数据结构的发展阶段
10
数据结构研究对象
计算机科学是对信息进行表示和处理的科学。\r\n计算机中表示和处理的信息以数据的形式体现。\r\n数据的表示和组织直接关系到计算机程序能否处理这些数据以及处理的效率。\r\n设计高效率、高可靠性的程序需要：\r\n (1)研究数据的特性、数据间的相互关系；\r\n (2)数据在计算机内部的存储表示。\r\n (3)利用这些特性和关系设计出相应的算法和程序
数值计算
非数值计算
11
结构静力分析计算
---- 线性代数方程组
---- 环流模式方程\r\n (球面坐标系)
全球天气预报
数值计算的程序设计问题
12
数据计算问题：百鸡问题
公元5世纪末，我国古代数据家张丘建在他所撰写的《算经》中，提出了这样一个问题：“鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡翁、母、雏各几何？即：\r\n公鸡每只5元、母鸡每只3元、小鸡3只1元，用100元钱买100只鸡，求公鸡、母鸡、小鸡的只数。
13
非数值计算问题：学籍管理问题
14
以上家庭成员关系之间构成了一个树状结构，结构中的数据元素之间存在一对多的关系。
构成家庭成员名的集合， 如{父亲，儿子，女儿，孙子，孙女}，这些数据有一个共同特征，即他们都是家庭的成员名。
非数值计算问题：家庭成员的关系
15
如何实现对弈?各格局之间是什么关系？
非数值计算问题：人机对弈问题
16
如何表示课程之间的先修关系？
非数值计算问题：教学计划编排问题
17
图 1-2 煤气管道的铺设示意图
以上煤气管道线之间构成了网状结构，结构中的数据元素之间存在多对多的关系。
非数值计算问题：煤气管道的铺设
如下图需为城市的各小区之间铺设煤气管道，对 n 个小区只需铺设 n-1 条管线，由于地理环境等不同因素使各条管线所需投资不同(如图上所标识)，如何使投资成本最低？
18
非数值计算问题： 多叉路口的交通灯设置
有连线的节点用不同的颜色标记, 表示不能同时通行\r\n要求使用的颜色数尽可能少, 以使减少等待时间\r\n这是图论中的四色问题
19
计算机处理问题的一般过程
20
数据结构研究范畴
(1) 建立数据模型
逻辑结构
(2) 计算机中的表示
物理/存储结构
(3) 操作在计算机中的实现
算法
21
表1-1
数据结构的核心技术是分解与抽象。通过分解可以划分出数据的三个层次；\r\n通过抽象，舍弃数据元素的具体内容，就得到逻辑结构。\r\n通过分解将处理要求划分成各种功能\r\n通过抽象舍弃实现细节，就得到运算的定义。
数据结构课程内容体系
数据结构的内容包括三个层次的五个“要素”，如表1-1所示。
22
数据结构地位
23
有关概念和术语
数据：所有能输入到计算机中并能被计算机程序识别和处理的符号集合。\r\n 数值数据：整数、实数等\r\n 非数值数据：图形、图象、声音、文字等 \r\n数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。\r\n数据项：构成数据元素的不可分割的最小单位。\r\n关键字：是指能识别一个或多个数据元素的数据项。若能起唯一识别的作用，则称之为 "主" 关键字，否则称之为 "次" 关键字。\r\n数据对象：具有相同性质的数据元素的集合。
24
数据、数据元素、数据项之间的关系
包含关系：数据是由数据元素组成，数据元素是由数据项组成。\r\n\r\n数据元素是讨论数据结构时涉及的最小数据单位，其中的数据项一般不予考虑。
25
数据结构：相互之间存在一定关系的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。\r\n逻辑结构：指数据元素之间逻辑关系的整体。
数据的逻辑结构是从具体问题抽象出来的数据模型
数据结构
存储结构：又称为物理结构，是数据及其逻辑结构在计算机中的表示。
实质上是内存分配，\r\n在具体实现时，依赖于计算机语言。
26
典型逻辑结构
2. 线性表：数据元素之间存在着一对一的线性关系；
3. 树：数据元素之间存在\r\n着一对多的层次关系
4. 图：数据元素之间存在\r\n 着多对多的任意关系。
1. 集合：数据元素之间就是 “属于同一个集合”
27
数据结构的形式定义
Data_Structure ＝（D，R） （1-1）\r\nD是数据元素的有限集，R是D上关系的有限集。
D={父亲，儿子，女儿，孙子，孙女}\r\nR={（父亲,儿子）,（父亲,女儿）,\r\n （儿子,孙子）， (儿子,孙女）}
例1.2中家庭成员数据结构可以表示成：\r\n F=(D, R)
28
数组的形式定义
例：一维数组，A[6]={a1, a2, a3, a4, a5, a6}
R= {
D= {a1, a2, a3, a4, a5, a6}
例：二维数组
D={a1, a2, a3, a4, a5, a6}
R={row,col}
row = {
col = {
29
存储结构
数据结构在计算机中的表示（又称映像）称为数据的物理结构，或称存储结构。它所研究的是数据结构在计算机中的实现方法，包括数据结构中元素的表示及元素间关系的表示。
1. 顺序存储
2. 链式存储
3. 散列存储
4. 索引存储
30
顺序存储方法
顺序存储方法：把逻辑上相邻的元素存储在物理位置相邻的存储单元中。顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。
31
链式存储方法
链式存储方法：对逻辑上相邻的元素不要求其物理位置相邻，元素间的逻辑关系通过附设的指针字段来表示。链式存储结构通常借助于程序设计语言中的指针类型来实现。
32
其它存储方法
根据关键字key?H(key)，来确定存储地址
散列存储
索引存储
33
逻辑结构和存储结构之间的关系
数据的逻辑结构属于用户视图，是面向问题的，反映了数据内部的构成方式；数据的存储结构属于具体实现的视图，是面向计算机的。\r\n\r\n 一种数据的逻辑结构可以用多种存储结构来存储，而采用不同的存储结构，其数据处理的效率往往是不同的。
34
1.2 数据类型
1. 数据类型
2. 抽象数据类型
35
数据类型
数据类型（Data Type）:是一个值的集合和定义在这个值集上的一组操作的总称。\r\n在高级程序设计语言中，数据类型可分为两类：原子类型和结构类型。\r\n原子类型 ：原子类型的值是不可分解的。如整型、字符型、浮点型、双精度型等\r\n结构类型：结构类型的值是可分解的，如数组 、指针、结构等。
36
整型 int
浮点型 float
字符型 char
逻辑型 bool
双精度型 double
实型
C 语言中提供的基本数据类型
37
typedef struct {\r\n int y; // 年号 Year \r\n int m; // 月号 Month\r\n int d; // 日号 Day\r\n} DateType; // 日期类型
定义“日期”为:
定义“学生”为:
typedef struct {\r\n char id[8]; // 学号 \r\n char name[16]; // 姓名\r\n char sex; // 性别‘M/F’:男/女\r\n DateType bdate; // 出生日期\r\n} Student; // 学生类型
结构类型
38
抽象数据类型
1. 数据类型（Data Type）：一组值的集合以及定义于这个值集上的一组操作的总称。\r\n 例如：C 中的整型变量 \r\n2. 抽象（Abstract）:抽出问题本质的特征而忽略非本质的细节。\r\n 例如： 地图、驾驶汽车\r\n3. 抽象数据类型（Abstract Data Type，ADT）:一个数据结构以及定义在该结构上的一组操作的总称。
39
ADT是对数据类型的进一步抽象
ADT的不同视图
抽象数据类型可用（D，S，P）三元组表示\r\n\r\n其中，D 是数据对象，\r\n S 是 D 上的关系集，\r\n P 是对 D 的基本操作集。
抽象数据类型的形式化描述
ADT描述
ADT 抽象数据类型名 {\r\n 数据对象：〈数据对象的定义\r\n 数据关系：〈数据关系的定义〉\r\n 基本操作：〈基本操作的定义〉\r\n} ADT 抽象数据类型名
基本操作的定义格式为：\r\n 基本操作名(参数表）\r\n 前置条件：执行此操作前数据所必须的状态 \r\n 输 入：执行此操作所需要的输入\r\n 功 能：该操作将完成的功能\r\n 输 出：执行该操作后产生的输出\r\n 后置条件：执行该操作后数据的状态