东南大学数据结构课件第01讲绪论

void sort(int *a, const int n) /* sort the n integers a[0] to a[n-1] into nondecreasing order*/ { for(int i = 0; i < n-1; i++) { int j = i; //find smallest integer in a[i] to a[n-1] for (int k = i+1; k < n; k++) if (a[k] < a[j]) j = k; int temp = a[i]; a[i] = a[j]; a[j] = temp ; //interchange } } //Program Selection sort
方法3：部分有序，建立索引表
李1 a1
数据
李2
……
a2
…… 张1 ak
姓
李 …… 王 张
地址
……
张2
…… 王1 王2
ak+1
…… ai ai+1 ……
关系
……
[例1-2] 文件系统的组织（UNIX为例）
关系 数据
[例1-3] 计算机和人对弈
数据
⊙ × ×⊙
关系
⊙
×
⊙
×× ×⊙
× ×⊙
× ⊙ × ×⊙
well for all purposes, and so it is important to know the strengths and limitations of several of them.
[例1-1] 电话号码查询问题 方法1：顺序存储，顺序查找
数据
关系
((a1,b1),(a2,b2),(a3,b3),…,(an,bn)）
跳高
姓名 丁1 马2 张3 项目1 跳高 标枪 标枪 项目2 跳远 铅球 100M 200M 项目3 100M
数据
跳远
100M 200M
李4
王5
铅球
跳远
200M
200M
跳高
铅球
标枪
关系
(1) 任一选手所选中的项目之间应该两两有边相连；
(2) 任一两个有边相连的顶点颜色（时间）不能相同。
基本概念
数据：数据是信息的载体，是描述客观事物的数、
字符、以及所有能输入到计算机中、被计算机程序 识别和处理的符号集合。例如：数字、字母、汉字 、图形、图像、声音都称为数据。


数值性数据 非数值性数据
数据元素：数据元素是组成数据的基本单位，在计
算机中作为一个整体进行考虑和处理。数据元素是 一个数据整体中相对独立的单位，但它还可以分割 成若干个具有不同属性的项（数据项或字段），故 不是组成数据的最小单位。
⊙ × × ×⊙
⊙
× ×⊙ ×
[例1-4]交叉路口的交通灯管理问题
(1) 有连线的顶点用不同的颜色标 记，表示不能同时通行；
(2) 要求使用的颜色尽可能少，以 减少等待时间； (3) 图论中的着色问题。 数据 C B C
C D
D
A D B A
[例1-5]田径赛的时间安排问题
非线性结构
元素之间为一对多或多对多的非线性关系，每 个元素有多个直接前驱或多个直接后继。（树、图）
数据的物理结构
逻辑结构在计算机存储器中的实现，故又称数据 "存 储结构"。 (1) 顺序（向量） 所有元素存放在一片连续的存贮单元中，逻辑上相邻 的元素存放到计算机内存仍然相邻。 (2) 链式
所有元素存放在可以不连续的存贮单元中，但元素之 间的关系可以通过地址确定，逻辑上相邻的元素存放 到计算机内存后不一定是相邻的。
计算机科学技术的应用已从传统的数值计算领域发展
到各种非数值计算领域。

科学计算（数值运算）：解方程（组）、函数求值、概率 统计等； 非数值运算：字符、表格、图像、声音等；
数据处理的对象已从简单的数值发展到具有一定结构
的数据。 面临的主要问题：针对应用领域的处理对象，如何选 择合适的数据表示，如何有效地组织计算机存贮、实 现对象之间的“运算”关系？
Scanning direction
13
13
27
27
38
38
49
49
49’
49’
97
65
65
97
76
76
13
27
38
49
49’
65
76
97




明确问题：非递减排序 解决方案：逐个选择最小数据 算法描述： for ( int i=0; i<n-1; i++ ) { //n-1趟 从a[i]检查到a[n-1]; 若最小的整数在a[k], 交换a[i]与a[k]; } 程序实现：程序 SelectSort
课程学习背景
计算机是一门研究用计算机进行信息表示和处理的
科学。 信息的表示和组织直接关系到信息处理程序的效率 。随着计算机的普及，信息范围的拓宽，信息量的 增加，使许多系统程序和应用程序的规模和复杂性 增加。 为编写出一个“好”的程序，必须分析待处理对象 的特征及各对象间存在的关系，这就是数据结构这 门课所要研究的问题。

1.4 算法定义
算法：一个有穷的指令集，这些指令为解决某一特 定问题规定了一个运算序列。 算法的特性：




输入：算法加工对象的量值，常体现为算法的一组变量。 输出：一组与“输入”有确定关系的量值，算法进行信息 加工后得到的结果。 确定性：对于每种情况下所应执行的操作，在算法中都有 确切的规定，使算法的执行者或阅读者都能明确其含义及 如何执行； 有穷性：对于任意一组合法的输入值，在执行有穷步骤之 后一定能结束；（与程序不同） 有效性（可行性）：算法中的所有操作都必须足够基本， 都可以通过已经实现的基本操作运算有限次实现。

数据项：具有独立含义的最小标识单位，用于组成 数据元素。
姓 名 学 号 性 别 班 号 出生 日期
年 月 日
入学 成绩

关键字：指的是能识别一个或多个数据元素的数 据项。若能起唯一识别作用，则称之为 "主" 关 键字，否则称之为 "次" 关键字。

数据对象：具有相同性质的数据成员（数据元素） 的集合，是数据的子集。如：整数、实数等。整数 数据对象 N = { 0, 1, 2, … }
数据结构就是研究和解决这些问题的重要基础理论。 计算机程序是用于对信息进行加工处理的。一般而言 ，这些信息并不是没有组织的，信息之间往往具有重 要的结构关系，这就是数据结构需要研究的内容。 计算机算法与数据的结构密切相关，算法无不依附于 具体的数据结构，数据结构直接关系到算法的选择和 效率
抽象数据类型可用（D,
S, P）三元组表示，其中， D 是数据元素的集合（简称数据对象），S 是 D上 的关系集合，P 是对 D 的基本操作集合。

抽象数据类型的格式定义： ADT Name Data 构造该抽象数据类型所必须的基本数据项 Operation 服务（或操作） …… End ADT Name 类的定义体现了抽象数据类型的思想，支持说明 与实现的分离，而C++对面向对象支持的核心就是 类的定义，故采用C++实现抽象数据类型的说明与 实现。
课程的地位
数据结构是一门研究在非数值计算的程序设计问题
中计算机操作对象及其之间关系与操作的学科. 介于数学、计算机硬件和计算机软件三者之间，属 于计算机学科中的一门综合性专业基础课程。 不仅是一般程序设计的基础，也是设计和实现编译 程序、操作系统、数据库系统及其他系统程序和大 型应用程序的重要基础。 于1968年开始在国外作为独立课程设立，由美国唐· 欧· 克努特教授开创其最初体系。
数据结构的内容
数据元素间的逻辑关系，即数据的逻辑结构；

从解决问题的需要出发，为实现必要的功能所建立的数 据结构，它属于用户的视图，是面向问题的。数据的逻 辑结构独立于计算机，是数据本身所固有的。
数据元素及其关系在计算机存储内的表示，即数据
的存储表示（逻辑结构的实现）

存贮结构是逻辑结构在计算机存贮器中的映像，指数据 该如何在计算机中存放，是数据逻辑结构的物理存储方 式，是属于具体实现的视图，是面向计算机的。必须依 赖于计算机。 运算是指所施加的一组操作总称。运算的定义直接依赖 于逻辑结构，但运算的实现必依赖于存贮结构。
采用什么样的操作实现算法？
1.2 抽象数据类型
抽象数据类型(ADTs:
Abstract Data Types)是由用户 定义，用以表示应用问题的数据模型。 特点


数据抽象：强调实体的本质特征、其所能完成的功能以 及它和外部用户的接口； 数据封装：将实体的外部特性和其内部实现细节分离， 并且对外部用户隐藏其内部实现细节；

学生数据对象:初等项（不可分割）、组合项（可再划分）


数据类型：具有相同性质的计算机数据集合（值的 集合）及在这个集合上的一组操作。例如，高级语 言中用到的整数数据类型，是指由－32768到32767 中值构成的集合及一组操作（加、减、乘、除、乘 方等）的总称。 结构：数据元素之间的关系。
什么是数据结构
定义:
由某一数据元素的集合以及该集合中所有数 据元素之间的关系组成。记为： Data_Structure = {D, R} 其中，D 是某一数据元素的集合，R 是该集合中所 有数据元素之间的关系的有限集合。
例：N 个网点之间的不同关系 1 6
5 4 2
1 3
5 6
2
3