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

1、东南大学数据结构第东南大学数据结构第01讲绪论讲绪论1 东南大学 计算机科学与工程学院 数据结构 DATA STRUCTURE 东南大学数据结构第东南大学数据结构第01讲绪论讲绪论2 先修课程：离散数学、C+程序设计 参考教材：数据结构(用面向对象方法与C+描述) -清华大学出版社(殷仁昆) 数据结构(C+描述) -清华大学出版社(金远平) Fundamentals of Data Structures in C+ 东南大学数据结构第东南大学数据结构第01讲绪论讲绪论3 课程学习背景 u计算机是一门研究用计算机进行信息表示和处理的 科学。 u信息的表示和组织直接关系到信息处理程序的效率 。随着

2、计算机的普及，信息范围的拓宽，信息量的 增加，使许多系统程序和应用程序的规模和复杂性 增加。 u为编写出一个“好”的程序，必须分析待处理对象 的特征及各对象间存在的关系，这就是数据结构这 门课所要研究的问题。 东南大学数据结构第东南大学数据结构第01讲绪论讲绪论4 课程的地位 u数据结构是一门研究在非数值计算的程序设计问题 中计算机操作对象及其之间关系与操作的学科. u介于数学、计算机硬件和计算机软件三者之间，属 于计算机学科中的一门综合性专业基础课程。 u不仅是一般程序设计的基础，也是设计和实现编译 程序、操作系统、数据库系统及其他系统程序和大 型应用程序的重要基础。 u于1968年开始在国

3、外作为独立课程设立，由美国唐 欧克努特教授开创其最初体系。 东南大学数据结构第东南大学数据结构第01讲绪论讲绪论5 必修课程设置与DS的关系 程序设计与程序设计与 问题解决问题解决 数据结构基础数据结构基础 数学数学 1 数学数学 2 计算机科学基础计算机科学基础 计算机系统计算机系统 原理与汇编原理与汇编 算法与数算法与数 据结构据结构 程序设计语言基础程序设计语言基础 操作系统操作系统 有穷自动机有穷自动机 计算机组计算机组 织与结构织与结构 东南大学数据结构第东南大学数据结构第01讲绪论讲绪论6 选修课程设置与DS的关系 数据结构基础数据结构基础 计算机科学基础计算机科学基础 算法与数算

4、法与数 据结构据结构 文件处理文件处理 ( (数据库数据库) ) 算法设计与分析算法设计与分析 软件工程软件工程 图形学图形学 系统模拟系统模拟 东南大学数据结构第东南大学数据结构第01讲绪论讲绪论7 计算机解决具体问题时，经过下列几个步骤：首 先要从具体问题进行分析，从中抽象出一个数学模型， 然后设计算法，最后编出程序、进行测试、调整直至 得到最终解答。 问 题 分 析 数 学 模 型 抽 象 设 计 算 法 编 写 程 序 并 调 试 得 到 解 答 第1章 数据结构概论 东南大学数据结构第东南大学数据结构第01讲绪论讲绪论8 1.1 数据结构的概念 u计算机科学技术的应用已从传统的数值计

5、算领域发展 到各种非数值计算领域。 科学计算（数值运算）：解方程（组）、函数求值、概率 统计等； 非数值运算：字符、表格、图像、声音等； u数据处理的对象已从简单的数值发展到具有一定结构 的数据。 u面临的主要问题：针对应用领域的处理对象，如何选 择合适的数据表示，如何有效地组织计算机存贮、实 现对象之间的“运算”关系？ 东南大学数据结构第东南大学数据结构第01讲绪论讲绪论9 u数据结构就是研究和解决这些问题的重要基础理论。 u计算机程序是用于对信息进行加工处理的。一般而言 ，这些信息并不是没有组织的，信息之间往往具有重 要的结构关系，这就是数据结构需要研究的内容。 u计算机算法与数据的结构密

6、切相关，算法无不依附于 具体的数据结构，数据结构直接关系到算法的选择和 效率 Niklaus Wirth： Algorithm + Data Structures = Programs 东南大学数据结构第东南大学数据结构第01讲绪论讲绪论10 A data structure is a way to store and organize data in order to facilitate access and modifications. No single data structure works well for all purposes, and so it is important

7、 to know the strengths and limitations of several of them. 东南大学数据结构第东南大学数据结构第01讲绪论讲绪论11 例例1-1 电话号码查询问题电话号码查询问题 方法1：顺序存储，顺序查找 (a1,b1),(a2,b2),(a3,b3),(an,bn)） 姓名电话号码 a1b1 a2b2 anbn 问题：效率低 数据 关系 东南大学数据结构第东南大学数据结构第01讲绪论讲绪论12 方法2：有序顺序存储，二分查找 (（李1,a1),(李2,a2),(王1,ai),(王2,ai+1),) 姓名电话号码 李1a1 李2a2 王1ai 王2a

8、i+1 张1ak 张2ak+1 问题：修改不方便 数据 关系 东南大学数据结构第东南大学数据结构第01讲绪论讲绪论13 方法3：部分有序，建立索引表 李1a1 李2a2 姓地址 李 王 张 王1ai 王2ai+1 张1ak 张2ak+1 数据 关系 东南大学数据结构第东南大学数据结构第01讲绪论讲绪论14 例1-2 文件系统的组织（UNIX为例） 数据 关系 东南大学数据结构第东南大学数据结构第01讲绪论讲绪论15 例1-3 计算机和人对弈 数据 关系 东南大学数据结构第东南大学数据结构第01讲绪论讲绪论16 例例1-4交叉路口的交通灯管理问题交叉路口的交通灯管理问题 (1) 有连线的顶点用不

9、同的颜色标 记，表示不能同时通行； (2) 要求使用的颜色尽可能少，以 减少等待时间； (3) 图论中的着色问题。 数据 关系 东南大学数据结构第东南大学数据结构第01讲绪论讲绪论17 例例1-5田径赛的时间安排问题田径赛的时间安排问题 姓名项目1项目2项目3 丁1跳高跳远100M 马2标枪铅球 张3标枪100M200M 李4铅球200M跳高 王5跳远200M 跳高跳远 标枪 铅球 200M 100M (1) 任一选手所选中的项目之间应该两两有边相连； (2) 任一两个有边相连的顶点颜色（时间）不能相同。 数据 关系 东南大学数据结构第东南大学数据结构第01讲绪论讲绪论18 基本概念 u数据数

10、据：数据是信息的载体，是描述客观事物的数、 字符、以及所有能输入到计算机中、被计算机程序 识别和处理的符号集合。例如：数字、字母、汉字 、图形、图像、声音都称为数据。 数值性数据 非数值性数据 u数据元素数据元素：数据元素是组成数据的基本单位，在计 算机中作为一个整体进行考虑和处理。数据元素是 一个数据整体中相对独立的单位，但它还可以分割 成若干个具有不同属性的项（数据项或字段），故 不是组成数据的最小单位。 东南大学数据结构第东南大学数据结构第01讲绪论讲绪论19 数据项数据项：具有独立含义的最小标识单位，用于组成 数据元素。 姓姓 名名 学学 号号 性性 别别 班班 号号 出生出生 日期日

11、期 入学入学 成绩成绩 年年 月月 日日 关键字关键字：指的是能识别一个或多个数据元素的数 据项。若能起唯一识别作用，则称之为 主 关 键字，否则称之为 次 关键字。 东南大学数据结构第东南大学数据结构第01讲绪论讲绪论20 数据对象数据对象：具有相同性质的数据成员（数据元素） 的集合，是数据的子集。如：整数、实数等。整数 数据对象 N = 0, 1, 2, 学生数据对象:初等项（不可分割）、组合项（可再划分） 数据类型数据类型：具有相同性质的计算机数据集合（值的 集合）及在这个集合上的一组操作。例如，高级语 言中用到的整数数据类型，是指由32768到32767 中值构成的集合及一组操作（加、

12、减、乘、除、乘 方等）的总称。 结构结构：数据元素之间的关系。 东南大学数据结构第东南大学数据结构第01讲绪论讲绪论21 什么是数据结构 u定义定义: 由某一数据元素的集合以及该集合中所有数 据元素之间的关系组成。记为： Data_Structure = D, R 其中，D 是某一数据元素的集合，R 是该集合中所 有数据元素之间的关系的有限集合 例：例：N 个网点之间的不同关系个网点之间的不同关系 1 5 6 1 5 2 4 36 2 4 3 树形关系（代价最小）网状关系（连通） 东南大学数据结构第东南大学数据结构第01讲绪论讲绪论22 数据结构的内容 u数据元素间的逻辑关系，即数据的逻辑结构

13、； 从解决问题的需要出发，为实现必要的功能所建立的数 据结构，它属于用户的视图，是面向问题的。数据的逻 辑结构独立于计算机，是数据本身所固有的。 u数据元素及其关系在计算机存储内的表示，即数 据的存储表示（逻辑结构的实现） 存贮结构是逻辑结构在计算机存贮器中的映像，指数据 该如何在计算机中存放，是数据逻辑结构的物理存储方 式，是属于具体实现的视图，是面向计算机的。必须依 赖于计算机。 u数据的运算，即对数据元素施加的操作。 运算是指所施加的一组操作总称。运算的定义直接依赖 于逻辑结构，但运算的实现必依赖于存贮结构。 东南大学数据结构第东南大学数据结构第01讲绪论讲绪论23 数据的逻辑结构 u对

14、数据元素之间存在的逻辑关系的描述，它可以用 一个数据元素的集合和定义在此集合上的若干关系 表示。 u线性结构线性结构：元素之间为一对一的线性关系，第一个 元素无直接前驱，最后一个元素无直接后继，其余 元素都有一个直接前驱和直接后继。（表、串、栈 、队列） 东南大学数据结构第东南大学数据结构第01讲绪论讲绪论24 v非线性结构非线性结构 元素之间为一对多或多对多的非线性关系，每 个元素有多个直接前驱或多个直接后继。（树、图） 东南大学数据结构第东南大学数据结构第01讲绪论讲绪论25 数据的物理结构 逻辑结构在计算机存储器中的实现，故又称数据存 储结构。 (1) (1) 顺序（向量）顺序（向量）

15、所有元素存放在一片连续的存贮单元中，逻辑上相邻 的元素存放到计算机内存仍然相邻。 (2) (2) 链式链式 所有元素存放在可以不连续的存贮单元中，但元素之 间的关系可以通过地址确定，逻辑上相邻的元素存放 到计算机内存后不一定是相邻的。 东南大学数据结构第东南大学数据结构第01讲绪论讲绪论26 (3) (3) 索引索引 使用该方存放元素的同时，还建立附加的索引表， 索引表中的每一项称为索引项，索引项的一般形式 是：（关键字，地址），其中的关键字是能唯一标 识一个结点的那些数据项。 (4) (4) 散列散列 通过构造散列函数，用函数的值来确定元素存放的 地址。 东南大学数据结构第东南大学数据结构第

16、01讲绪论讲绪论27 数据结构的具体内容 u具体问题的逻辑数据结构是什么？ u适宜选用什么样的存储结构？ u采用什么样的操作实现算法？ 东南大学数据结构第东南大学数据结构第01讲绪论讲绪论28 1.2 抽象数据类型 u抽象数据类型(ADTs: Abstract Data Types)是由用户 定义，用以表示应用问题的数据模型。 u特点 数据抽象：强调实体的本质特征、其所能完成的功能以 及它和外部用户的接口； 数据封装：将实体的外部特性和其内部实现细节分离， 并且对外部用户隐藏其内部实现细节； u抽象数据类型可用（D, S, P）三元组表示，其中， D 是数据元素的集合（简称数据对象），S 是

17、D上 的关系集合，P 是对 D 的基本操作集合。 东南大学数据结构第东南大学数据结构第01讲绪论讲绪论29 抽象数据类型的格式定义： ADT Name Data 构造该抽象数据类型所必须的基本数据项 Operation 服务（或操作） End ADT Name 类的定义体现了抽象数据类型的思想，支持说明 与实现的分离，而C+对面向对象支持的核心就是 类的定义，故采用C+实现抽象数据类型的说明与 实现。 东南大学数据结构第东南大学数据结构第01讲绪论讲绪论30 1.4 算法定义 u算法算法：一个有穷的指令集，这些指令为解决某一特 定问题规定了一个运算序列。 u算法的特性： 输入输入：算法加工对象

18、的量值，常体现为算法的一组变量。 输出输出：一组与“输入”有确定关系的量值，算法进行信息 加工后得到的结果。 确定性确定性：对于每种情况下所应执行的操作，在算法中都有 确切的规定，使算法的执行者或阅读者都能明确其含义及 如何执行； 有穷性有穷性：对于任意一组合法的输入值，在执行有穷步骤之 后一定能结束；（与程序不同） 有效性有效性（可行性）：算法中的所有操作都必须足够基本， 都可以通过已经实现的基本操作运算有限次实现。 东南大学数据结构第东南大学数据结构第01讲绪论讲绪论31 算法的设计过程算法的设计过程 方法方法 自顶向下，逐步求精 过程过程 把一个具体问题的解决思路转变成一个算法 东南大学

19、数据结构第东南大学数据结构第01讲绪论讲绪论32 例例1-6 选择排序问题选择排序问题 49493838656597977676131327274949 13133838656597977676494927274949 13132727656597977676494938384949 13132727383897977676494965654949 13132727383849497676979765654949 13132727383849494949979765657676 13132727383849494949656597977676 1313272738384949494965657

20、6769797 东南大学数据结构第东南大学数据结构第01讲绪论讲绪论33 明确问题明确问题：非递减排序 解决方案解决方案：逐个选择最小数据 算法描述算法描述： for ( int i=0; in-1; i+ ) /n-1趟 从ai检查到an-1; 若最小的整数在ak, 交换ai与ak; 程序实现程序实现：程序 SelectSort 东南大学数据结构第东南大学数据结构第01讲绪论讲绪论34 void sort(int *a, const int n) /* sort the n integers a0 to an-1 into nondecreasing order*/ for(int i =

21、0; i n-1; i+) int j = i; /find smallest integer in ai to an-1 for (int k = i+1; k n; k+) if (ak aj) j = k; int temp = ai; ai = aj; aj = temp ; /interchange /Program Selection sort 东南大学数据结构第东南大学数据结构第01讲绪论讲绪论35 例例1-71-7二分查找二分查找 明确问题明确问题：假定有n1个不同的整数已经按从小到 大的顺序存放在数组元素a0, ,an-1中。我 们需要做的是判断整数x是否存放在某个数组元素中

22、 ，如果是，即x=aj，则返回j（被找到元素的下标 ）；否则返回1。 东南大学数据结构第东南大学数据结构第01讲绪论讲绪论36 确定搜索区间的左右边界left和right，不断缩小搜索的区 间。初始边界设定为left = 0 和right = n-1。令middle = (left + right)/2为搜索区间的中心位置元素。如果我们将 amiddle与x 比较，其结果有三种可能： 1. xamiddle。这种情况下，如果x存放在这个数组中， 则它的位置必然在middle+1和n-1之间。所以，我们将left设置 为middle+1，继续搜索。 算法有两个任务：1. 决定搜索区间；2. 将x

23、与中间元素 amiddle比较。 解决方案：解决方案： 东南大学数据结构第东南大学数据结构第01讲绪论讲绪论37 (1) 表现形式不同 (2) 是否具备有穷性。 实现数据结构操作的程序总是可结束的， 因此，后面将不再严格区分算法和程序这两个 术语。 东南大学数据结构第东南大学数据结构第01讲绪论讲绪论38 递归算法 对数据对象而言：若一个对象部分地包含它自己, 或用它自己给自己定义, 则称这个对象是递归的； 对算法而言：若一个算法直接地或间接地调用自己 , 则称这个算法是递归的算法。 一个递归的算法一般包含两个部分：一个基本部分 （不需要递归就可以解决问题）和一个一次或多次 递归调用自己的部分

24、。递归调用自己的部分解决与 原问题具有相同属性特征的问题，只是问题的规模 变小了。 递归算法的基本思想：“大事化小，小事化了” 东南大学数据结构第东南大学数据结构第01讲绪论讲绪论39 递归算法的特性：递归算法的特性： （1）必须有可最终达到的终止条件，否则程序将 陷入无穷递归； （2）子问题在规模上比原问题小，或更接近终止 条件； （3）子问题可通过再次递归调用求解或因满足终 止条件而直接求解； （4）子问题的解应能组合为整个问题的解。 东南大学数据结构第东南大学数据结构第01讲绪论讲绪论40 在解决以下三类问题时，常常需要用到递归算法。 （1）定义是递归的 例例1 18 8 求阶乘求阶乘

25、)!1( 1 ! nn n 1n 1n 当 当 long Factorial ( long n ) if ( n = = 1 ) return 1; / 终止条件 else return n*Factorial ( n-1); / 递归步骤 东南大学数据结构第东南大学数据结构第01讲绪论讲绪论41 用参数 n = 5 调用Fact的过程如下： Fact(5) = (5* Fact (4) = (5* (4* Fact (3) = (5* (4* (3* Fact (2) = (5* (4* (3* (2* Fact (1) = (5* (4* (3* (2* 1) = (5* (4* (3*

26、2) = (5* (4* 6) = (5* 24) = 120 东南大学数据结构第东南大学数据结构第01讲绪论讲绪论42 long Fib(long n) int s=1; for (int i=1; i=n; i+) s = s * i; return s; 采用递归的算法求解阶乘问题似乎并不能够充分说 明其必要性，因为用迭代的算法同样可以简单地解 决同一问题。 东南大学数据结构第东南大学数据结构第01讲绪论讲绪论43 例例1 19 9 求斐波那契数列求斐波那契数列 long Fib(long n) if (n 1 不过，下面的例子可以说明与迭代算法相比较，在解决某些 问题时，递归算法具有优

27、越性。 东南大学数据结构第东南大学数据结构第01讲绪论讲绪论44 f(4)f(4) f(3)f(3)f(2)f(2) f(2)f(2)f(1)f(1)f(1)f(1)f(0)f(0) f(1)f(1)f(0)f(0)1 10 0 0 01 11 11 1 1 12 2 3 3 用迭代的方式求解？ 东南大学数据结构第东南大学数据结构第01讲绪论讲绪论45 long Fib(long n) if (n=1) return n; else long twoback = 0, oneback = 1, Current; for (i=2; i=n; i+) Current = twoback + on

28、eback; twoback = oneback; oneback = Current; return Current; n=4 n=4 初始初始 2 3 4 2 3 4 Current 1 2 3Current 1 2 3 Twoback 0 1 1 2Twoback 0 1 1 2 Oneback 1 1 2 3Oneback 1 1 2 3 用迭代的方式求解用迭代的方式求解 东南大学数据结构第东南大学数据结构第01讲绪论讲绪论46 （2）数据结构是递归的（如树）数据结构是递归的（如树） （3）问题的解法是递归的）问题的解法是递归的 例1-10 求解汉诺塔（tower of hanoi)问

29、题 问题的提法是：“传说婆罗门庙有一个塔台，台上有3根标号为a,b c 的用钻石作成的柱子，a柱上放着64个金盘，每一个都比下面一个略 小一点。把a柱上的金盘全部移到c柱上的那一天就是世界末日。移动 的条件是：一次只能移动一个金盘，移动过程中大金盘不能放在小金 盘上面。庙里的僧人一直在移个不停。因为全部的移动是264-1次，如 果每钞移动一次的话，需用500亿年”；一位计算机科学家提出了一 种快速求解的递归解法。利用这个解法，将移动n个盘子的汉诺塔问 题归结为移动（n-1)个盘子的汉诺塔问题。与此类似，移动（n-1） 个盘子的汉诺塔问题又可归结为移动（n-2)个盘子的汉诺塔问题， ，最后总可以

30、归结到只移动一个盘子的汉诺塔，这样问题就解决 了。 东南大学数据结构第东南大学数据结构第01讲绪论讲绪论47 Example: the recursive Towers of Hanoi algorithm Void TOH(int n, Pole_start, Pole_goal, Pole_temp) if (n = 0 ) return; / base case TOH(n-1, start, temp, goal); / recursive call MOVE(start, goal); / move one disk TOH(n-1, temp, goal, start); / re

31、cursive call 许多数据结构是自然递归的（可以递归定义），这样，在这 类数据结构上的操作也常常表现为递归算法。此外，许多排 序和查找算法也是基于“分而治之”思想，即其解决方案是 将问题分解为更小（但与原问题是类似的）子问题，解决子 问题，然后将子问题的解决方案合并为原问题的解决方案。 东南大学数据结构第东南大学数据结构第01讲绪论讲绪论48 递归算法的特点： 易编程 可读性好 易检验 效率低 东南大学数据结构第东南大学数据结构第01讲绪论讲绪论49 给定n1个元素的集合，问题是输出这个集合中所有元素的 排列。例如：如果集合是a, b, c，那么,这个集合元素的 全排列为：(a,b,c), (a,c,b), (b,a,c), (b,c,a), (c,a,b), (c,b,a)。容易看出，如果给定的集合中有n个元 素，那么就有n!个不同的