第一章数据结构

1、数据结构数据结构Data Structures Data Structures 讲课学时：讲课学时：3636上机学时：上机学时：3636课程设计：课程设计：2 2周周教学安排教学安排参考书目参考书目算法与数据结构（算法与数据结构（C语言版）语言版）， 范策，周世平，胡哓范策，周世平，胡哓琨琨 等编著，机械工业出版社，等编著，机械工业出版社， 2004数据结构与算法数据结构与算法，许卓群，杨冬青，唐世渭，张铭，许卓群，杨冬青，唐世渭，张铭，高等教育出版社，高等教育出版社，2004数据结构实用教程（第二版）数据结构实用教程（第二版），徐孝凯编著，清华大，徐孝凯编著，清华大学出版社学出版社 2006

2、数据结构辅导与提高实用教程（第二版）数据结构辅导与提高实用教程（第二版），徐孝凯，徐孝凯，清华大学出版社清华大学出版社 2003算法与数据结构算法与数据结构C语言描述语言描述，张乃孝等，高等教育出版，张乃孝等，高等教育出版社，社，2002The Art of Computer Programing.，D.E.Knuth, Volume 1/Fundamentals. Volume 3/Sorting and Searching. MA: Aderson-WesleyFundamentals of Data Structures, Algorithms and Performance, D.Wo

3、rd. MA: Addison-WesleyFundamentals of Data Structures,Horowitz, E. and Sahn, S., Computer Science Press, Inc.参考书目参考书目 第第1章章 绪论绪论 第第2章章 线性表线性表 第第3章章 栈和队列栈和队列 第第4章章 串串 第第5章章 数组和广义表数组和广义表 第第6章章 树和二叉树树和二叉树 第第7章章 图图 第第8章章 查找查找 第第9章章 排序排序本课程的教学内容本课程的教学内容1.1 数据结构及其讨论范畴数据结构及其讨论范畴1.2 基本概念和术语基本概念和术语1.3 抽象数据类型

4、的表示与实现抽象数据类型的表示与实现1.4 算法和算法分析算法和算法分析本章重点难点 重点重点: 数据结构的逻辑结构、存储结构数据结构的逻辑结构、存储结构以及基本操作的概念及相互关系；抽象数据类以及基本操作的概念及相互关系；抽象数据类型型(ATD)的概念和实现方法，算法的时间复杂性的概念和实现方法，算法的时间复杂性和空间复杂性分析。和空间复杂性分析。 难点难点: 抽象数据类型抽象数据类型(ATD)的概念和实现的概念和实现方法；算法的时间复杂性和空间复杂性分析。方法；算法的时间复杂性和空间复杂性分析。1.1 数据结构及其讨论范畴数据结构及其讨论范畴1.2 基本概念和术语基本概念和术语1.3 抽象

5、数据类型的表示与实现抽象数据类型的表示与实现1.4 算法和算法分析算法和算法分析第第1章章 绪论绪论1.1 数据结构及其讨论范畴数据结构及其讨论范畴算法算法+ +数据结构数据结构 = = 程序设计程序设计 处理问题的策略处理问题的策略给出问题的数学模型给出问题的数学模型编制出用计算机编制出用计算机处理问题的指令处理问题的指令问题问题构建数学模型构建数学模型算法实现算法实现 在解决问题时可能遇到的典型的逻辑结构在解决问题时可能遇到的典型的逻辑结构（数据结构）（数据结构） 逻辑结构的存储映象（存储实现）逻辑结构的存储映象（存储实现） 数据结构的相关操作及其实现。数据结构的相关操作及其实现。 数据结

6、构是一门讨论数据结构是一门讨论描述现实世界实体的数描述现实世界实体的数学模型学模型(非数值计算非数值计算)及其上的操作在计算机中如何及其上的操作在计算机中如何表示和实现表示和实现的学科。的学科。 第第1章章 绪论绪论1.1 数据结构及其讨论范畴数据结构及其讨论范畴例例1 求求 n 个整数中的最大值。个整数中的最大值。例例2 交叉路口的红绿灯管理。交叉路口的红绿灯管理。例例3 煤气管道的铺设问题。煤气管道的铺设问题。 说明：说明： 例子中的例子中的数学模型数学模型正是数据结构要讨论的问题。正是数据结构要讨论的问题。第第1章章 绪论绪论1.1 数据结构及其讨论范畴数据结构及其讨论范畴例例p计算机的

7、发展计算机的发展p数据处理的种类数据处理的种类p数据数据数值数据数值数据非数值数据非数值数据数数 (整数整数,实数实数) 字符字符 字符串字符串 文字文字 图形图形 图象图象 声音声音对客观对象的符号表示对客观对象的符号表示程序程序原始数据原始数据结果数据结果数据第第1章章 绪论绪论1.1 数据结构及其讨论范畴数据结构及其讨论范畴软件软件 硬件硬件 应用领域应用领域p 数值问题与非数值问题数值问题与非数值问题 数值问题数值问题 例例1 已知：游泳池的长已知：游泳池的长len和宽和宽wide，求面积，求面积area 设计设计 求解问题的方法求解问题的方法 编程编程 建模型：建模型： 问题涉及的对

8、象：游泳池的长问题涉及的对象：游泳池的长len 宽宽wide，面积，面积area； 对象之间的关系：对象之间的关系：area=len wide第第1章章 绪论绪论1.1 数据结构及其讨论范畴数据结构及其讨论范畴学号学号 姓名姓名 性别性别 出生日期出生日期 籍贯籍贯 入学成绩入学成绩 所在班级所在班级 00201 杨润生杨润生 男男 82/06/01 广州广州 561 00计算机计算机200102 石磊石磊 男男 83/12/21 汕头汕头 512 00计算机计算机100202 李梅李梅 女女 83/02/23 阳江阳江 532 00计算机计算机200301 马耀先马耀先 男男 82/07/1

9、2 广州广州 509 00计算机计算机3非数值问题非数值问题 已知某级学生情况已知某级学生情况 , 要求分班按入学成绩排列顺序。要求分班按入学成绩排列顺序。说明：说明： 在此类文档管理的数学模型中在此类文档管理的数学模型中, 计算机处理的对象之间通常计算机处理的对象之间通常存在着一种最简单的线性关系存在着一种最简单的线性关系 , 该数学模型称为该数学模型称为线性模型线性模型。第第1章章 绪论绪论1.1 数据结构及其讨论范畴数据结构及其讨论范畴例例非数值问题非数值问题第第1章章 绪论绪论1.1 数据结构及其讨论范畴数据结构及其讨论范畴 下棋程序下棋程序-国际象棋：国际象棋： 每次需要考虑的合乎规

10、则的着法平均只有每次需要考虑的合乎规则的着法平均只有3535步回合，计步回合，计算机预先分析算机预先分析7 7至至8 8个回合的着法。若设为个回合的着法。若设为7 7个回合，则有超过个回合，则有超过1 1亿亿亿个不同的变化，经简化后，仍有亿亿亿个不同的变化，经简化后，仍有500500亿至亿至600600亿个变化。亿个变化。多分析一步，增加多分析一步，增加1818亿个变化。亿个变化。根据计算机根据计算机“深蓝深蓝”的速度，的速度，平均平均5 5分钟走一步。分钟走一步。算法算法：对弈的规则和策略对弈的规则和策略棋盘及棋盘的格局棋盘及棋盘的格局模型模型：根据计算机：根据计算机“深蓝深蓝”的速度的速度

11、例例 迷宫问题：迷宫问题：在迷宫中，每走到一处，接下来可走的通路在迷宫中，每走到一处，接下来可走的通路有三条。计算机处理的这类对象之间通常不存在线性关有三条。计算机处理的这类对象之间通常不存在线性关系。若把从迷宫入口处到出口的过程中所有可能的通路系。若把从迷宫入口处到出口的过程中所有可能的通路都画出，则可得一棵都画出，则可得一棵“树树”。 入口入口 出口出口第第1章章 绪论绪论1.1 数据结构及其讨论范畴数据结构及其讨论范畴例例第第1章章 绪论绪论1.1 数据结构及其讨论范畴数据结构及其讨论范畴对每种数据结构，主要讨论如下三方面的问题：对每种数据结构，主要讨论如下三方面的问题：数据的逻辑结构数

12、据的逻辑结构 数据元素之间的逻辑关系，是具体关系的抽象。数据元素之间的逻辑关系，是具体关系的抽象。数据的存储结构数据的存储结构( (物理结构物理结构) )： 数据元素及其关系在计算机内存中的表示；数据元素及其关系在计算机内存中的表示；数据的运算数据的运算 即对数据施加的操作。定义在数据的逻辑结构上的即对数据施加的操作。定义在数据的逻辑结构上的抽象的操作。抽象的操作。1.1 数据结构及其讨论范畴数据结构及其讨论范畴1.2 基本概念和术语基本概念和术语1.3 数据结构的分类及表示数据结构的分类及表示1.4 抽象数据类型的表示与实现抽象数据类型的表示与实现1.5 算法和算法分析算法和算法分析 数据数

13、据：是信息的载体，能够被计算机识别、存储和加工处：是信息的载体，能够被计算机识别、存储和加工处理。如整数，实数，字符串、图象、声音等都是数据。理。如整数，实数，字符串、图象、声音等都是数据。数据元素数据元素：数据的基本单位。相当于：数据的基本单位。相当于“记录记录”, ,在计算机程在计算机程序中通常作为一个整体考虑和处理。序中通常作为一个整体考虑和处理。数据项数据项: : 相当于记录的相当于记录的“域域”或字段或字段, , 是数据不可分割的最是数据不可分割的最小单位。如学号。小单位。如学号。数据对象数据对象：性质相同的数据元素的集合。如所有班名相同的：性质相同的数据元素的集合。如所有班名相同的

14、记录集合。记录集合。第第1章章 绪论绪论1.2 基本概念和术语基本概念和术语数据结构类型数据结构类型树树图图第第1章章 绪论绪论1.2 基本概念和术语基本概念和术语数据结构数据结构是数据之间的相互关系，是数据之间的相互关系，即数据的组织形式。即数据的组织形式。 线性表线性表栈栈队列队列串串数组数组广义表广义表数据结构数据结构线性结构线性结构非线性结构非线性结构线性结构线性结构：除第一个元素和最后一个元素之外，其他元素：除第一个元素和最后一个元素之外，其他元素都都有且仅有一个有且仅有一个直接前驱，直接前驱，有且仅有一个有且仅有一个直接后继；直接后继；非线性结构非线性结构：其逻辑特征是一个结点可能

15、有：其逻辑特征是一个结点可能有多个多个直接前驱直接前驱和直接后继；和直接后继；第第1章章 绪论绪论1.2 基本概念和术语基本概念和术语p数据的逻辑结构数据的逻辑结构 学号学号 姓名姓名 专业专业 政治面藐政治面藐 001 王洪王洪 计算机计算机 党员党员 002 孙文孙文 计算机计算机 团员团员 003 谢军谢军 计算机计算机 团员团员 004 李辉李辉 计算机计算机 团员团员 005 沈祥福沈祥福 计算机计算机 党员党员 006 余斌余斌计算机计算机 团员团员 007 巩力巩力计算机计算机 团员团员 008 孔令辉孔令辉 计算机计算机 团员团员 00100300200400600500800

16、7学生间学号顺序关系学生间学号顺序关系是一种线性结构关系是一种线性结构关系第第1章章 绪论绪论学生基本情况登记表，记录了每个学生的学号、姓名、专业、学生基本情况登记表，记录了每个学生的学号、姓名、专业、政治、面貌，表中的记录是按学生的学号顺序排列的。政治、面貌，表中的记录是按学生的学号顺序排列的。 1.2 基本概念和术语基本概念和术语例例家族的族谱家族的族谱:假设某家族有假设某家族有10个成员个成员A， B， C， D， E， F， G， H，I， J，他们之间的血缘关系可以用如下图表示。，他们之间的血缘关系可以用如下图表示。JIACBDHGFE第第1章章 绪论绪论1.2 基本概念和术语基本概

17、念和术语例例顺序存储方法：数组顺序存储方法：数组链接存储方法：指针链接存储方法：指针索引存储方法索引存储方法散列存储方法散列存储方法说明：说明： 同一逻辑结构的不同存储结构，冠以不同的数据结构名同一逻辑结构的不同存储结构，冠以不同的数据结构名称。如顺序表、链表、散列表。称。如顺序表、链表、散列表。 运算不同，数据结构也不同。如栈和队列。更进一步，运算不同，数据结构也不同。如栈和队列。更进一步，顺顺 序栈、链栈、顺序队列、链队列。序栈、链栈、顺序队列、链队列。第第1章章 绪论绪论1.2 基本概念和术语基本概念和术语p数据的存储结构数据的存储结构算法：数据运算的描述算法：数据运算的描述数据结构：数

18、据的逻辑结构和存储结构数据结构：数据的逻辑结构和存储结构算法算法+数据结构数据结构=程序程序第第1章章 绪论绪论1.2 基本概念和术语基本概念和术语1.1 数据结构及其讨论范畴数据结构及其讨论范畴1.2 基本概念和术语基本概念和术语1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现1.4 算法和算法分析算法和算法分析p抽象数据型抽象数据型Abstract Data Types（ADT）定义定义：抽象数据型是一个数学模型和在该模型抽象数据型是一个数学模型和在该模型 上定义的操作的集合上定义的操作的集合ADT特点：特点：降低了软件设计的复杂性；降低了软件设计的复杂性；提高了程序的可读性和可维

19、护性；提高了程序的可读性和可维护性；程序的正确性容易保证程序的正确性容易保证第第1章章 绪论绪论1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现在软件设计中，可以对哪在软件设计中，可以对哪三种不同的对象进行抽象？三种不同的对象进行抽象？第第1章章 绪论绪论1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现第第1章章 绪论绪论1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现软件系统软件系统数据结构数据结构控制机能控制机能操作过程操作过程软件设计软件设计抽象抽象软件设计是对软件设计是对数据抽象、过程抽象和控制抽象。数据抽象、过程抽象和控制抽象。p抽象数据型的规格描述抽象数据型

20、的规格描述完整性：反映所定义的抽象数据型的全部完整性：反映所定义的抽象数据型的全部 特征；特征；统一性：前后协调，不自相矛盾；统一性：前后协调，不自相矛盾；通用性：适用于尽量广泛的对象；通用性：适用于尽量广泛的对象；不依赖性：不依赖于程序设计语言。不依赖性：不依赖于程序设计语言。语法：给出操作的名称、语法：给出操作的名称、I/OI/O参数的数目和类型；参数的数目和类型；语义：由一组等式组成，定义各种操作的功能及相互之间的语义：由一组等式组成，定义各种操作的功能及相互之间的关系；关系；p规格描述的两个方面规格描述的两个方面: 语法和语义语法和语义第第1章章 绪论绪论1.3 抽象数据类型的表示与实

21、现抽象数据类型的表示与实现抽象描述抽象描述 （高级语言）编写的程序（高级语言）编写的程序三条原则：三条原则：符合规格描述的定义；符合规格描述的定义；有尽可能好的通用性；有尽可能好的通用性；尽可能独立于程序的其它部分尽可能独立于程序的其它部分自底向上与自顶向下相结合、由简单到复杂自底向上与自顶向下相结合、由简单到复杂第第1章章 绪论绪论1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现p抽象数据型的实现抽象数据型的实现多层次抽象技术多层次抽象技术抽象数据类型的形式描述抽象数据类型的形式描述 DT = ( D，S，P ),其中：其中：D 是数据对象是数据对象; 是是 D 上的关系集上的关系集

22、;是是 D 的基本操作集。的基本操作集。第第1章章 绪论绪论1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现数据类型和抽象数据类型数据类型和抽象数据类型抽象数据类型需要通过高级编程语言中已经实现的数抽象数据类型需要通过高级编程语言中已经实现的数据类型（通常称之谓固有数据类型）来实现；据类型（通常称之谓固有数据类型）来实现；抽象数据类型的实现包括数据结构的实现和操作的实抽象数据类型的实现包括数据结构的实现和操作的实现。现。第第1章章 绪论绪论1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现抽象数据类型抽象数据类型“复数复数”的定义为：的定义为：ADT Complex 数据对象：数

23、据对象：D = e1,e2 | e1,e2 RealSet 数据关系：数据关系：R1 = | e1是复数的实部，是复数的实部， e2是复数的虚部是复数的虚部 其中用两个实数来表示复数，将复数定义为两个实数的其中用两个实数来表示复数，将复数定义为两个实数的有序对，并约定实部是前驱，虚部是后继。有序对，并约定实部是前驱，虚部是后继。 例例 设计函数设计函数 DELEVAL（LIST &L, elementtype d) ，其功能，其功能 为删除为删除 L 中所有值为中所有值为 d 的元素。的元素。 Void DELEVAL( LIST &L, elementtype d ) pos

24、ition p ; p = FIRST( L ) ; while ( P != END( L ) ) if ( same( RETRIEVE( p, L ), d ) ) DELETE(p, L ) ; else p = NEXT(p, L ) ; 第第1章章 绪论绪论1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现例例1.1 数据结构及其讨论范畴数据结构及其讨论范畴1.2 基本概念和术语基本概念和术语1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现1.4 算法和算法分析算法和算法分析第第1章章 绪论绪论1.4 算法与算法分析算法与算法分析p算法（算法（algorithm）的概

25、念）的概念算法是对问题求解过程的一种描述，是为解决一个或算法是对问题求解过程的一种描述，是为解决一个或一类问题给出的一个确定的、有限长的操作序列。严一类问题给出的一个确定的、有限长的操作序列。严格说来，一个算法必须满足以下五个重要特性格说来，一个算法必须满足以下五个重要特性关于本书采用的类语言描述：关于本书采用的类语言描述：C 或或 C+自然语言；自然语言；程序设计语言；程序设计语言；类语言类语言 ；p算法描述算法描述第第1章章 绪论绪论1.4 算法与算法分析算法与算法分析p 算法的基本特征算法的基本特征有穷性：有穷性：算法中的操作步骤为有限个，且每个步骤都能在有限算法中的操作步骤为有限个，且

26、每个步骤都能在有限时间内完成。时间内完成。确定性：确定性：组成算法的操作必须清晰无二义性。组成算法的操作必须清晰无二义性。可行性：可行性：算法中的所有操作都必须足够基本，都可以通过已经算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。实现的基本操作运算有限次实现之。输入：输入：作为算法加工对象的量值，通常体现为算法中的一组变作为算法加工对象的量值，通常体现为算法中的一组变量。些算法的字面上可以没有输入，实际上已被嵌入算法之中。量。些算法的字面上可以没有输入，实际上已被嵌入算法之中。输出：输出：它是一组与输入有确定关系的量值，是算法进行信息加它是一组与输入有确定关系的

27、量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。工后得到的结果，这种确定关系即为算法的功能。p在设计算法时通常应考虑以下原则在设计算法时通常应考虑以下原则算法必须是算法必须是“正确的正确的”l所谓算法是正确的，除了应该满足算法说明中写明的所谓算法是正确的，除了应该满足算法说明中写明的“功能功能”之外，应对各组典型的带有苛刻条件的输入数据得出正确的结之外，应对各组典型的带有苛刻条件的输入数据得出正确的结果。果。l在算法是正确的前提下，算法的可读性是摆在第一位的，这在在算法是正确的前提下，算法的可读性是摆在第一位的，这在当今大型软件需要多人合作完成的环境下是换重要的，另一方当今大

28、型软件需要多人合作完成的环境下是换重要的，另一方面，晦涩难读的程序易于隐藏错误而难以调试。面，晦涩难读的程序易于隐藏错误而难以调试。应有很好的应有很好的“可读性可读性”第第1章章 绪论绪论1.4 算法与算法分析算法与算法分析p在设计算法时通常应考虑以下原则在设计算法时通常应考虑以下原则必须具有必须具有“健壮性健壮性”l算法的健壮性指的是，算法应对非法输入的数据作出恰当算法的健壮性指的是，算法应对非法输入的数据作出恰当反映或进行相应处理，一般情况下，应向调用它的函数返反映或进行相应处理，一般情况下，应向调用它的函数返回一个表示错误或错误性质的值。回一个表示错误或错误性质的值。算法的效率算法的效率

29、l应考虑所设计的算法具有应考虑所设计的算法具有“高效率与低存储量高效率与低存储量”。高效率。高效率与低存储量是矛盾的，要视具体问题而定。与低存储量是矛盾的，要视具体问题而定。第第1章章 绪论绪论1.4 算法与算法分析算法与算法分析p影响时间特性的四个因素影响时间特性的四个因素 定义定义 语句频度语句频度：语句重复执行的次数：语句重复执行的次数第第1章章 绪论绪论1.4 算法与算法分析算法与算法分析 程序运行时输入数据的总量程序运行时输入数据的总量; 对源程序编译所需的时间对源程序编译所需的时间; 计算机执行每条指令所需的时间计算机执行每条指令所需的时间; 程序中指令重复执行的次数。程序中指令重

30、复执行的次数。所有算法均以函数形式给出所有算法均以函数形式给出, , 算法的输入数据来自参数表；算法的输入数据来自参数表；参数表的参数在算法之前均进行类型说明；参数表的参数在算法之前均进行类型说明；有关结点结构的类型定义有关结点结构的类型定义, ,以及全局变量的说明等均在算法以及全局变量的说明等均在算法之前进行说明之前进行说明p描述算法的书写规则描述算法的书写规则第第1章章 绪论绪论1.4 算法与算法分析算法与算法分析p 评价算法标准评价算法标准本课程采用以求解问题的基本操作（原操作）的执行次数本课程采用以求解问题的基本操作（原操作）的执行次数作为算法时间的度量。作为算法时间的度量。 O(n3) 称为矩阵相乘算法时间复杂度；称为矩阵相乘算法时间复杂度； O(n3)表示矩阵相乘算法执行时间与表示矩阵相乘算法执行时间与n3成正比成正比, 即即O（n3）与）与n3 同一数量级；同一数量级； n 阶矩阵相乘的算法阶矩阵相乘的算法For ( i = 1; i=n; i+ ) For (j = 1; j=n; j+ ) c i j = 0 ; For (k = 1;