数据结构(C语言版) Data Structure

Presentation on theme: "数据结构(C语言版) Data Structure"— Presentation transcript:

1 数据结构(C语言版) Data Structure
主讲教师 王晓刚

2 课程安排 -----清华大学出版社 总学时：64 讲课学时：54（上课27次） 实验学时：10（上机5次）
教材： 《数据结构》（ C语言版）严蔚敏、吴伟民 -----清华大学出版社 《数据结构题集》 （ C语言版）严蔚敏、吴伟民

3 课程重要性 编程基础 考研课程 计算机等级考试课程 程序员考试课程

4 参考书目 计算机及软件技术丛书—— 现代计算机常用数据结构和算法  潘金贵 编著 南京大学出版社 数据结构习题解析

5 本课程的体系结构 介绍数据、数据结构和抽象数据类型的概念。 从抽象数据类型的角度， 介绍操作系统和编译程序中涉及的 第一章 绪论
第一章 绪论 介绍数据、数据结构和抽象数据类型的概念。 第二章 ~ 第七章 基本数据结构 从抽象数据类型的角度， 分别讨论线性表、栈和队列、串、数组和广义表、 树、图等基本数据结构及其应用。 第八章 动态存储管理 介绍操作系统和编译程序中涉及的 动态存储管理的基本技术。

6 介绍了各种实现方法， 介绍数据库系统中组织文件的常用方法。 第九章 ~第十一章 查找和排序 第十二章 文件结构
第九章 ~第十一章 查找和排序 介绍了各种实现方法， 并着重从时间上进行定性或定量的分析和比较。 第十二章 文件结构 介绍数据库系统中组织文件的常用方法。

7 数据结构的概念 算法的概念和描述 算法的简单分析
第一章 绪论 数据结构的概念 算法的概念和描述 算法的简单分析

8 第一章 绪论 为什么要学习数据结构？ 什么是程序、软件？ -----数据结构的概念 N.沃思（Niklaus Wirth)教授提出：
第一章 绪论 为什么要学习数据结构？ 什么是程序、软件？ N.沃思（Niklaus Wirth)教授提出： 程序=算法+数据结构 以上公式说明了如下两个问题： （1）数据上的算法决定如何构造和组织数据（算法→数据结构）。 （2）算法的选择依赖于作为基础的数据结构（数据结构→算法）。 软件=程序+文档（软件工程的观点）

9 第一章 绪论 电子计算机的主要用途： 处理逐渐扩大到非数值计算领域（能处理多种复杂的具有一定结构关系的数据）。 -----数据结构的概念
第一章 绪论 电子计算机的主要用途： 早期： 主要用于数值计算。 后来： 处理逐渐扩大到非数值计算领域（能处理多种复杂的具有一定结构关系的数据）。

10 第一章 绪论 数值计算解决问题的一般步骤： 非数值计算问题： -----数据结构的概念 数学模型→选择计算机语言→编出程序→测试→最终解答。
第一章 绪论 数值计算解决问题的一般步骤： 数学模型→选择计算机语言→编出程序→测试→最终解答。 数值计算的关键是：如何得出数学模型（方程）？ 程序设计人员比较关注程序设计的技巧。 非数值计算问题： 数据元素之间的相互关系一般无法用数学方程加以描述

11 第一章 绪论 非数值计算问题： 例1.1 电话号码查询问题： -----数据结构的概念 （1）按顺序存储方式：须遍历表
第一章 绪论 非数值计算问题： 例1.1 电话号码查询问题： （1）按顺序存储方式：须遍历表 （2）按姓氏索引方式：索引 要写出好的查找算法，取决于这张表的结构及存储方式。 电话号码表的结构和存储方式决定了查找（算法）的效率。

12 第一章 绪论 非数值计算问题： 例1.2 田径赛的时间安排问题（无向图的着色问题） ： -----数据结构的概念
第一章 绪论 非数值计算问题： 例1.2 田径赛的时间安排问题（无向图的着色问题） ： 设有六个比赛项目，规定每个选手至多可参加三个项目，有五人报名参加比赛（如下表所示）设计比赛日程表，使得在尽可能短的时间内完成比赛。

13 第一章 绪论 非数值计算问题 ----田径赛的时间安排问题解法 （1）设用如下六个不同的代号代表不同的项目： （2）用顶点代表比赛项目
-----数据结构的概念 第一章 绪论 非数值计算问题 ----田径赛的时间安排问题解法 （1）设用如下六个不同的代号代表不同的项目： 跳高 跳远 标枪 铅球 米 200米 A B C D E F （2）用顶点代表比赛项目 不能同时进行比赛的项目之间连上一条边。 （3）某选手比赛的项目必定有边相连（不能同时比赛）。

14 第一章 绪论 -----数据结构的概念 只需安排四个单位时间进行比赛 1 A，C 2 B，D 3 E 4 F 比赛时间 比赛项目 姓名
第一章 绪论 姓名 项目1 项目2 项目3 丁一 A B E 马二 C D 张三 F 李四 王五 只需安排四个单位时间进行比赛 比赛时间 比赛项目 1 A，C 2 B，D 3 E 4 F A B F E C D

15 第一章 绪论 求解非数值计算的问题： 主要考虑的是设计出合适的数据结构及相应的算法。 即：首先要考虑对相关的各种信息如何表示、组织和存储？
-----数据结构的概念 第一章 绪论 求解非数值计算的问题： 主要考虑的是设计出合适的数据结构及相应的算法。 即：首先要考虑对相关的各种信息如何表示、组织和存储？ 因此，可以认为：数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。

16 第一章 绪论 数据结构课程的形成和发展： -----数据结构的概念 形成阶段：
第一章 绪论 数据结构课程的形成和发展： 形成阶段： 60年代初期，“数据结构”有关的内容散见于操作系统、编译原理和表处理语言等课程。1968年，“数据结构”被列入美国一些大学计算机科学系的教学计划。 发展阶段： 数据结构的概念不断扩充，包括了网络、集合代数论、关系等“离散数学结构”的内容。 70年代后期，我国高校陆续开设该课程。

17 -----数据结构的概念 第一章 绪论 《数据结构课程》所处的地位：

18 第一章 绪论 什么是数据结构？ 几个概念： -----数据结构的概念
第一章 绪论 什么是数据结构？ 几个概念： 数据(Data):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素(Data Element):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。 数据对象(Data Object)：是性质相同的数据元素的集合。是数据的一个子集。

19 第一章 绪论 什么是数据结构？ -----数据结构的概念 几个概念：
第一章 绪论 什么是数据结构？ 几个概念： 数据类型（Data Type)：在一种程序设计语言中，变量所具有的数据种类。 例1、 在FORTRAN语言中，变量的数据类型有整型、实型、和复数型 例2、在C语言中 数据类型：基本类型和构造类型 基本类型：整型、浮点型、字符型 构造类型：数组、结构、联合、指针、枚举型、自定义

20 第一章 绪论 什么是数据结构？ -----数据结构的概念 几个概念： 抽象数据类型(Abstract Data Type简称ADT）
抽象数据类型是用户在数据类型基础上 新定义的数据类型 抽象数据类型定义包括数据组成 和对数据的处理操作 抽象数据类型是数据和数据的使用者的一个接口 抽象数据类型的三元组表示 （D，S，P） D：数据对象 S：D上的关系集 P：对D的基本操作 -----数据结构的概念 第一章 绪论

21 第一章 绪论 什么是数据结构？ -----数据结构的概念 几个概念：
抽象数据类型的定义：包括数据对象定义、数据关系定义和基本操作定义，书写格式为： ADT：抽象数据类型名{ 数据对象：数据对象的定义 数据关系：数据逻辑关系的定义 基本操作：基本操作的定义 } ADT 抽象数据类型名 （P9 例 1-6） -----数据结构的概念 第一章 绪论

22 第一章 绪论 什么是数据结构？ 定义1---- 定义2---- -----数据结构的概念
是相互之间存在一种或多种特定关系的数据元素的集合。 Data_Structure = (D,S) D：数据对象 ，S：D上的关系集。 定义2---- 按某种逻辑关系组织起来的一批数据（或称带结构的数据元素的集合）应用计算机语言并按一定的存储表示 方式把它们存储在计算机的存储器中，并在其上定义了一个运算的集合。 -----数据结构的概念 第一章 绪论

23 第一章 绪论 数据结构的三个方面的含义： 逻辑结构--- 存储结构（物理结构）---- 运算（算法） -----数据结构的概念
数据元素间抽象化的相互关系（简称为数据结构）。 与数据的存储无关，独立于计算机，它是从具体问题抽象出来的数学模型。 存储结构（物理结构）---- 数据元素及其关系在计算机存储器中的存储方式。 是逻辑结构用计算机语言的实现，它依赖于计算机语言。 运算（算法） -----数据结构的概念 第一章 绪论

24 第一章 绪论 数据结构的三个方面的含义之： 逻辑结构---划分方法一 -----数据结构的概念 （1）线性结构----
有且仅有一个开始和一个终端结点，并且所有结点都最多只有一个直接前趋和一个后继。 例如：线性表、栈、队列、串 （2）非线性结构---- 一个结点可能有多个直接前趋和直接后继。 例如：树、图、多维数组、广义表等。 -----数据结构的概念 第一章 绪论

25 第一章 绪论 数据结构的三个方面的含义之： 逻辑结构---划分方法二 -----数据结构的概念
一、集合 结构中的数据元素除了同属于一种类型外，别无其它关系。 二、线性结构 结构中的数据元素之间存在一对一的关系。 三、树型结构 结构中的数据元素之间存在一对多的关系。 四、图状结构或网状结构 结构中的数据元素之间存在多对多的关系。 -----数据结构的概念 第一章 绪论

26 第一章 绪论 数据结构的三个方面的含义之： 存储结构 -----数据结构的概念 存储结构两方面的内容： 四种基本的存储方法：
（1）数据元素自身值的表示（数据域） （2）该结点与其它结点关系的域（链域） 四种基本的存储方法： （1）顺序存储方法（结构） （2）链接存储方法（链式存储结构） （3）索引存储方法 （4）散列存储方法 同一种逻辑结构可采用不同的存储方法（以上四种之一或组合），这主要考虑的是运算方便及算法的时空要求。 -----数据结构的概念 第一章 绪论

27 第一章 绪论 数据结构的三个方面的含义之： 逻辑结构存储结构小结： -----数据结构的概念
（1）数据的逻辑结构、存储结构和数据的运算（算法）构成了数据结构三个方面的含义。 （2）程序设计的实质是对实际问题选择一个好的数据结构，加之设计一个好的算法。而好的算法在很大程度上取决于描述实际问题的数据结构。 -----数据结构的概念 第一章 绪论

28 第一章 绪论 数据结构的三个方面的含义之： 算法的概念和描述： 什么是算法？
所谓算法（Algorithm)是描述计算机解决给定问题的操作过程（解题方法），即为解决某一特定问题而由若干条指令组成的有穷序列。 -----数据结构的概念 第一章 绪论

29 第一章 绪论 数据结构的三个方面的含义之： 算法的概念和描述： 一个算法必须满足以下五个准则：
（1）有穷性---执行了有限条指令后一定要终止。 例1.3、例1.4 （2）确定性（无二义）--- 算法的每一步操作都必须有确切定义，不得有任何歧义性。 -----数据结构的概念 第一章 绪论

30 例1.3 一个不是算法的例子 (1)begin (2)n=0 (3)n=n+1 (4)repeat (3) (5)end
例1.3 一个不是算法的例子 (1)begin (2)n=0 (3)n=n+1 (4)repeat (3) (5)end 例1.4 一个不超过100次计数的算法 (1)begin (2)n=0 (3)n=n+1 (4)if n>=100 do (5) else repeat(3) (5)output n (6)end 返回

31 第一章 绪论 数据结构的三个方面的含义之： -----数据结构的概念 一个算法必须满足以下五个准则： （3）可（能）行性---
算法的每一步操作都必须是可行的，即每步操作均能在有限时间内完成。 （4）输入数据--- 一个算法有n（n>=0)个初始数据的输入。 （5）输出数据--- 一个算法有一个或多个的有效信息的输出。 思考：算法与程序有何区别？ -----数据结构的概念 第一章 绪论

32 第一章 绪论 数据结构的三个方面的含义之： 算法的描述和实现 描述---可采用自然语言、数学语言或约定的符号语言。
实现---必须借助程序设计语言提供的数据类型及其运算。 本课的描述---采用类C语言 （P9-13 §1.3）。 -----数据结构的概念 第一章 绪论

33 第一章 绪论 算法的简单分析： 算法设计的要求：正确性、可读性、健壮性、高效率、低存储量需求 -----数据结构的概念
第一章 绪论 算法的简单分析： 算法设计的要求：正确性、可读性、健壮性、高效率、低存储量需求 算法的效率指算法的执行时间，也称作算法的时间复杂度 算法的存储量需求指算法执行过程中所需的最大存储空间，也称作算法的空间复杂度

34 第一章 绪论 算法的简单分析： -----数据结构的概念 程序正确性的四个层面： （1）不含语法错误
（2）程序对于n组输入数据能够得出满足规格说明要求的结果。 （3）程序对于精心选择的典型、边界性的n组输入数据能得出满足规格说明要求的结果。 （4）程序对于一切合适的输入数据都能得出满足规格说明要求的结果（穷举）。 -----数据结构的概念 第一章 绪论 返回

35 第一章 绪论 -----数据结构的概念 算法的简单分析之： --------算法效率的度量 1.程序运行所耗费的时间(由下列因素决定)：
算法所选用的策略 问题的规模 书写程序所采用的语言 编译程序所产生的机器代码的质量 机器执行指令的速度 一个算法耗费的时间=算法中每条语句的执行时间之和。 若不考虑机器硬、软件因素，可以认为算法“运行工作量”的大小是问题规模的函数。 -----数据结构的概念 第一章 绪论

36 第一章 绪论 -----数据结构的概念 算法的简单分析之： --------算法效率的度量 2.问题的规模（size)---
算法求解问题的输入量（或初始数据量）。 3.不考虑机器软硬件环境时算法的时间耗费： 设：执行每条语句所需时间为单位时间，则： 一个算法耗费的时间=所有语句的频度之和。 时间复杂度T(n)--- 即：时间耗费，它是算法求解问题n的函数。 渐近时间复杂度(Asymptotic Time Complexity)--- 即当问题的规模n→∞时的时间复杂度T(n)的数量级（阶），记作：T(n)=O(f(n)) 评价一个算法的时间性能，主要标准是算法的渐近时间复杂度 -----数据结构的概念 第一章 绪论

37 算法效率的度量：采用时间复杂度 例1.5 分析以下程序段的时间复杂度 for (i=1;i<n;i++) { y=y+1;
例1.5 分析以下程序段的时间复杂度 for (i=1;i<n;i++) { y=y+1; for (j=0; j<=(2*n); j++) x++; } /* * / /* * /

38 分析：语句的频度指的是该语句重复执行的次数。一个算法中所有语句的频度之和构成了该算法的运行时间。
语句1的频度是：n-1 语句2的频度是： 则该程序段的时间复杂度： T(n)=

39 例1.6 分析以下程序段的时间复杂度 i=1; while (i<=n) /* 1 * / 语句1的频度是：1
例1.6 分析以下程序段的时间复杂度 i=1; while (i<=n) i=i*2 语句1的频度是：1 设语句2的频度是f(n)，则有： 即 ，取最大值 则该程序段的时间复杂度为： /* * / /* * /

40 由于内循环的执行次数虽与规模n无直接关系，但与外循环的变量取值有关。因此从内层向外层循环分析执行次数。
例1.7 x=1; for (i=1;i<=n;i++) for (j=1;j<=i;j++) for (k=1;k<=j;k++) x++; 由于内循环的执行次数虽与规模n无直接关系，但与外循环的变量取值有关。因此从内层向外层循环分析执行次数。

41

42

43

44 即: T(n)=[n(n+1)(2n+1)/6+n(n+1)/2]/2 所以： T(n)=O(n3/6+低次项) 取T(n)的数量级阶，得最后结果为： T(n)=O(n3) 当n→∞时，即n足够大时

45  常见函数的时间复杂度按数量递增排列及增长率。 常数阶O(1) 对数阶O(log2n) 线性阶O(n) 线性对数阶O(nlog2n)
 常见函数的时间复杂度按数量递增排列及增长率。 常数阶O(1) 对数阶O(log2n) 线性阶O(n) 线性对数阶O(nlog2n) 平方阶O(n2) 立方阶O(n3) …… k次方阶O(nk) 指数阶O(2n) 问题规模n 渐进时间复杂度O(n)

46  本章小结 数据、数据结构、ADT等基本概念 数据结构的三个方面的内容 线性和非线性结构的逻辑特征 数据存储的四种基本方法 算法、算法的时间复杂度及其分析的简易方法

47 课外学习 看书 P1——P17 题集 P P P