数据结构与程序设计-绪论.pdf
教育部高等教育司推荐教育部高等教育司推荐国 外 优 秀 信 息 科 学 与 技 术 系 列 教 学 用 书国 外 优 秀 信 息 科 学 与 技 术 系 列 教 学 用 书数据结构与程序设计数据结构与程序设计C+语言描述语言描述（影印版）Data Structures and Program Design in C+Robert L.KurseAlexandeer J.Ryba主讲：主讲：中山大学计算机系高集荣E_mail:GPDF 文件使用 pdfFactory Pro 试用版本创建 数据结构与算法讲义22004年3月11日1 学习数据结构的意义和要求学习数据结构的意义和要求2 数据结构的兴起与发展数据结构的兴起与发展3 数据结构的研究对象数据结构的研究对象4 什么是数据结构什么是数据结构5 基本概念和术语基本概念和术语6 面向对象与数据结构面向对象与数据结构7 算法和算法分析算法和算法分析绪 论绪 论PDF 文件使用 pdfFactory Pro 试用版本创建 数据结构与算法讲义32004年3月11日1.学习数据结构的意义及要求学习数据结构的意义及要求一、意义一、意义1.算法和数据结构是算法和数据结构是计算机科学计算机科学的两大支柱的两大支柱n计算机科学早期定义为:研究算法算法的科学n近期定义为:研究数据数据的科学2.数据结构是程序设计的基础数据结构是程序设计的基础Program=Algorithms+Data Structure3.数据结构是计算机专业的一门综合性专业基础数据结构是计算机专业的一门综合性专业基础课课n是计算机专业本科生必修学位课程n是计算机研究生入学考试必考科目n是软件人员水平考试内容PDF 文件使用 pdfFactory Pro 试用版本创建 数据结构与算法讲义42004年3月11日二、要求二、要求1.掌握面向对象的程序设计方法学，强调数据抽象及抽象思维能力的训练；2.掌握如何在不同场合权衡算法的设计，学会讨论不同程度的抽象以及算法的时空性能，强调在理论、设计、抽象三方面的能力的培养；3.掌握基本的算法分析及设计方法，如迭代、递归、逐步求精、分治、动态规划、回溯与分枝定界等方法的基本思想及应用。三、培养目标三、培养目标1.提高阅读和编写算法的能力全面培养学生分析问题解决问题的综合能力2.结合实际应用问题的解决启发思维培养创新能力全面提高学生的综合专业素质PDF 文件使用 pdfFactory Pro 试用版本创建 数据结构与算法讲义52004年3月11日四、教科书及主要参考书四、教科书及主要参考书n数据结构与程序设计C+语言描述影印版高等教育出版社,2001年n数据结构算法与应用C+语言描述SartajSahni著，汪诗林等译，机械工业出版社，2000年n数据结构与算法，齐德昱，清华大学出版社，2003年n数据结构与算法，王若梅等著，中山大学出版社，2000年PDF 文件使用 pdfFactory Pro 试用版本创建 数据结构与算法讲义62004年3月11日五、关于五、关于英文版英文版教教材材教材在内容方面的特点n先给出实例及技术说明，再介绍基本概念，每个ADT都在章节的最后给出n算法复杂度分析的介绍推迟到第7章，树和图的概念推迟到排序搜索之后n注重软件工程的原理并结合C+介绍OOPn每章后面都有复习要点以及练习便于学生巩固所学内容PDF 文件使用 pdfFactory Pro 试用版本创建 数据结构与算法讲义72004年3月11日2.数据结构的兴起与发展数据结构的兴起与发展n数据结构问题起源于程序设计的发展。程序设计已经历了3个阶段：第一阶段是无结构阶段第一阶段是无结构阶段（20世纪40年代至60年代）第二阶段是结构化程序设计阶段第二阶段是结构化程序设计阶段（20世纪60年代末至80年代）第三阶段是面向对象技术阶段第三阶段是面向对象技术阶段（20世纪80年代初，但真正流行是在20世纪90年代。）PDF 文件使用 pdfFactory Pro 试用版本创建 数据结构与算法讲义82004年3月11日3.数据结构的研究对象数据结构的研究对象n计算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题：n信息的表示n信息的处理而信息的表示和组织又直接关系到处理信息的程序的效率。n数据结构研究的内容：数据结构研究的内容：为在计算机上解决具体问题，应如何对所需的数据/信息及其关系进行组织(组织起来的数据就具有了结构关系)，以及如何对它们进行基本操作。简言之，研究数据的组织方式(结构)及相应的抽象操作。PDF 文件使用 pdfFactory Pro 试用版本创建 n数据结构与数学、计算机硬件和软件有十分密切的关系。数据结构是介于数学、计算机硬件和计算机软件之间的一门计算机科学与技术专业的核心课程，是高级程序设计语言、编译原理、操作系统、数据库、人工智能等课程的基础。同时，数据结构技术也广泛应用于信息科学、系统工程、应用数学以及各种工程技术领域。n数据结构课程集中讨论软件开发过程中的设计阶段、同时设计编码和分析阶段的若干基本问题。此外，为了构造出好的数据结构及其实现，还需考虑数据结构及其实现的评价与选择。因此，数据结构的内容包括三三个层次个层次的五五个个要要素素，如下表所示。方面数据表示 数据处理层次抽抽象象逻辑逻辑结构基本结构基本运运算算实现实现存储存储结构算法结构算法评价评价不同不同数据结构的数据结构的比较比较及算法分析及算法分析PDF 文件使用 pdfFactory Pro 试用版本创建 数据结构与算法讲义102004年3月11日4.什么是数据结构什么是数据结构n众所周知，计算机的程序是对信息进行加工处理。在大多数情况下，这些信息并不是没有组织，信息（数据）之间往往具有重要的结构关系，这就是数据结构的内容。那么，什么是数据结构呢？先看以下几个例子。l 例1、电话号码查询系统设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按如下形式安排：(a1，b1)(a2，b2)(an，bn)其中ai，bi(i=1，2n)分别表示某人的名字和对应的电话号码。PDF 文件使用 pdfFactory Pro 试用版本创建 数据结构与算法讲义112004年3月11日要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的标志。n算法的设计，依赖于计算机如何存储人的名字和对应的电话号码，或者说依赖于名字和其电话号码的结构。n数据的结构，直接影响算法的选择和效率。n上述的问题是一种数据结构问题。可将名字和对应的电话号码设计成：二维数组、表结构、向量。n假定名字和其电话号码逻辑上已安排成N元向量的形式，它的每个元素是一个数对(ai，bi)，1in PDF 文件使用 pdfFactory Pro 试用版本创建 数据结构与算法讲义122004年3月11日n数据结构还要提供每种结构类型所定义的各种运算的算法。l例2、图书馆的书目检索系统自动化问题l例3、计算机和人对奕问题l例4、多叉路口交通灯的管理问题n通过以上几例可以直接地认为：数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。PDF 文件使用 pdfFactory Pro 试用版本创建 数据结构与算法讲义132004年3月11日5.基本概念和术语基本概念和术语n数据数据(Data):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。n数据数据类型类型(Data Type):一个值的集合和定义在这个值集上的一组操作的总称。数据类型主要表明数据的取值范围和操作特性，是具有相同取值范围和可实施同种操作的数据集合的总称。例如C语言中的无符号字符型代表闭区间0,255中的整数，对这种数可进行加、减、乘、除、取模等算术运算。如果在特定的环境下，某种数据类型不能由其他数据类型复合而成，则称这种数据类型为原子类型，否则，称为复合类型(或导出类型、结构类型)。PDF 文件使用 pdfFactory Pro 试用版本创建 数据结构与算法讲义142004年3月11日5.基本概念和术语基本概念和术语n数据数据元素元素(Data Element):能独立、完整地描述问题世界中的实体的最小数据单位称为数据数据元素元素(也称记录记录)。构成数据元素的不可分割的数据单位称为数据数据项项。例如，对于学生花名册，其中每个学生记录就是一个数据元素，而学生的姓名、年龄等项目为数据项。数据元素是讨论数据结构时涉及的最小数据单位，其中的数据项一般不予考虑。n数据对象数据对象(Data Object):是性质相同的数据元素的集合。例如，所有学生记录的集合，就是该问题世界的一个数据对象。n数据结构数据结构(Data Structure):是相互之间存在一种或多种特定关系的数据元素的集合。PDF 文件使用 pdfFactory Pro 试用版本创建 数据结构与算法讲义152004年3月11日n数据结构主要指逻辑结构和物理结构n数据之间的相互关系称为逻辑结构。通常分为四类基本结构：1.集集合合 结构中的数据元素除了同属于一种类型外，别无其它关系。2.线线性结构性结构 结构中的数据元素之间存在一对一的关系。3.树型树型结构结构 结构中的数据元素之间存在一对多的关系。4.图型图型结构结构或网状或网状结构结构 结构中的数据元素之间存在多对多的关系。PDF 文件使用 pdfFactory Pro 试用版本创建 数据结构与算法讲义162004年3月11日（a）集集合结构合结构（b）线线性结构性结构（c）树型树型结构结构（d）图形图形结构结构n 树形结构与图形结构均称为非线非线性结构性结构。PDF 文件使用 pdfFactory Pro 试用版本创建 数据结构的数据结构的表示方表示方法法示例示例教务处人事简表(表1-1）目录行包括六个数据项名，这些定义了表的结构。共有十条记录，一个记录就是一个数据元素。“职工号”的值能唯一地标识一个记录，该数据项叫做关键项（Key Item）。教学科教学科学籍科学籍科考务科考务科教学科教学科学籍科学籍科学籍科学籍科学籍科学籍科考务科考务科考务科考务科处长处长科长科长科长科长科长科长科员科员科员科员科员科员科员科员科员科员科员科员52.03.2058.06.1454.12.0762.08.0549.08.1565.04.0162.06.2857.03.1765.10.1266.07.05男男男男女女女女男男男男女女男男男男男男万明华万明华赵宁赵宁张利张利赵书芳赵书芳刘永年刘永年王明理王明理王敏王敏张才张才马立仁马立仁邢怀常邢怀常01020304050607080910部门部门职务职务出生日期出生日期性别性别姓名姓名职工号职工号PDF 文件使用 pdfFactory Pro 试用版本创建 数据结构与算法讲义182004年3月11日数据结构的数据结构的表示方表示方法法示例示例1、线性结构设表1-1中只考虑年龄大小的排列 图形表示图形表示 二二元组表示元组表示line(K，R)K01，02，03，04，05，06，07，08，09，10Rrr05,01,01,03,03,08,08,02,02,07,07,04,04,06,06,09,09,10结构特点：数据元素之间最多只有一个前驱，最多只有一个后继，元素之间是一对一联系，即11。05010308020704060910PDF 文件使用 pdfFactory Pro 试用版本创建 数据结构与算法讲义192004年3月11日数据结构的数据结构的表示方表示方法法示例示例2、树形结构设表1-1中只考虑领导和被领导关系 图形表示图形表示 二二元组表示元组表示tree(K，R)K01，02，03，04，05，06，07，08，09，10Rrr01,02,01,03,01,04,02,05,03,06,03,07,03,08,04,09,04,10 结构特点：每个元素最多有一个前驱，但可有多个后继，元素之间是一对多关系，即1N，有层次关系。05010308020704060910PDF 文件使用 pdfFactory Pro 试用版本创建 数据结构与算法讲义202004年3月11日数据结构的数据结构的表示方表示方法法示例示例3、图形结构设表1-1中只考虑个人之间的关系 图形表示图形表示0501030802070406091005010308020704060910简化PDF 文件使用 pdfFactory Pro 试用版本创建 数据结构与算法讲义212004年3月11日数据结构的数据结构的表示方表示方法法示例示例 二二元组表示元组表示graph(K，R)K 01，02，03，04，05，06，07，08，09，10Rrr(01,02)，(01,05)，(04,01)，(02,03)，(05,03)，(03,06)，(07,06)，(07,10)，(08,07)，(04,07)，(04,09)特点：每个元素可以有多个前驱和多个后继，即NM，包含回路，无层次关系。图有有向图和无向图之分。PDF 文件使用 pdfFactory Pro 试用版本创建 数据结构与算法讲义222004年3月11日n数据结构的形式定义为：数据结构是一个二元组：Data-Structure=(D，S)其中：D是数据元素的有限集，S是D上关系的有限集。n例 复数的数据结构定义如下：Complex=(C，R)其中：C是含两个实数的集合C1，C2，分别表示复数的实部和虚部。R=P，P是定义在集合上的一种关系C1，C2。PDF 文件使用 pdfFactory Pro 试用版本创建 数据结构与算法讲义232004年3月11日n数据结构在计算机中的表示称为数据的物物理理结构结构，又称为存储存储结构结构。n数据对象可以是有限的，也可以是无限的。n数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。PDF 文件使用 pdfFactory Pro 试用版本创建 数据结构与算法讲义242004年3月11日n数据结构在计算机中有两种不同的表示方法：顺序表示和非顺序表示由此得出两种不同的存储结构：顺顺序序存储存储结结构构和链式链式存储存储结构结构n顺顺序序存储存储结构结构:用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。n链式链式存储存储结构：结构：在每一个数据元素中增加一个存放地址的指针（），用此指针来表示数据元素之间的逻辑关系。PDF 文件使用 pdfFactory Pro 试用版本创建 数据结构与算法讲义252004年3月11日6.面向对象与数据结构面向对象与数据结构面向对象与数据结构的关系面向对象与数据结构的关系n数据结构起初是研究表、树、图等结构的，发展到现在，人们已将它的研究对象上升到了抽象的高度。数据结构主要强调两方面的内容：1.同类数据元素间的依赖关系；2.针对这些依赖关系的基本操作。这些操作是充分的，依赖它们可以实现对具有特定关系的元素的任意访问。n这两个方面实质上是对象的雏形，是面向对象思想的萌芽。PDF 文件使用 pdfFactory Pro 试用版本创建 数据结构与算法讲义262004年3月11日n在面向对象方法中，问题世界中相关实体被视为一个对象。用对象描述实体，对象由属性、方法、事件构成。属性用以描述实体的物质特征，是对实体状态的数字描述；方法是定义在属性上的操作，用以改变实体状态或访问实体；事件用于定义实体与其他实体间的通信关系，它说明了实体能感知什么样的外来信息。对象与数据结构具有下列对应关系：n对象数据结构n属性数据元素间的关系的描述n方法基本操作n事件无PDF 文件使用 pdfFactory Pro 试用版本创建 数据结构与算法讲义272004年3月11日n对象重点描述实体的状态与行为，而数据结构重点描述同类数据元素间的关系及其操作。数据结构中的元素间关系描述比起对象的属性，更为基本。属性的表达是基于数据结构中的元素间的关系描述的，数据元素及其相互关系构成了对实体的状态的描述，由此可见，一个数据结构就是一个独立的对象。n对象有更广泛的概念，它更注重不同对象间的关系，同时也更强调对实体的状态的改变，这些都是数据结构与抽象数据类型的概念中所不具有的。PDF 文件使用 pdfFactory Pro 试用版本创建 数据结构与算法讲义282004年3月11日6.面向对象与数据结构面向对象与数据结构面向对象数据结构面向对象数据结构n面向对象数据结构从下列几个方面改造传统的数据结构：n(1)将基本元素视为对象；n(2)将元素间的关系视为对象;n(3)将数据元素的集合视为对象；n(4)对“相似”数据结构应用继承；n(5)用继承机制扩展基本数据结构；n(6)用面向对象的形式描述数据结构。PDF 文件使用 pdfFactory Pro 试用版本创建 数据结构与算法讲义292004年3月11日6.面向对象与数据结构面向对象与数据结构数据结构的对象模型数据结构的对象模型n数据结构的对象模型，是指将逻辑数据结构及其成分看做一个带有属性、方法和事件的容器(container)，定义出它的属性、方法和事件。由于这里涉及的是基本数据结构，所以这里不考虑事件。n从实体角度看，数据结构包括元素、元素间的关系以及数据结构整体三个部分，所以对它的对象定义也分为这三个部分。PDF 文件使用 pdfFactory Pro 试用版本创建 数据结构与算法讲义302004年3月11日6.面向对象与数据结构面向对象与数据结构n1.元素对象模型元素对象模型将构成数据结构的数据元素看做单独的实体，定义它的属性和方法。元素的属性是对元素的数据的抽象，元素的方法是对元素数据的操作的代理，它的执行一般改变元素数据和属性。n2.关系对象模型关系对象模型关系也是一种实体，所以，对它的访问，抽象为对象模型有时会更方便。n3.数据结构对象模型数据结构对象模型数据结构对象表示的是数据结构的全局性的特性，它与多个数据元素及其关系相关。例如，查找操作，由于它涉及多个数据元素，所以属于全局操作。PDF 文件使用 pdfFactory Pro 试用版本创建 数据结构与算法讲义312004年3月11日7.1 算法算法n算法：算法：是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。算法具有以下五个特性：n（1）有穷有穷性性一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。n（2）确定确定性性 算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。n（3）可行可行性性 一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。n（4）输入输入 一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。n（5）输输出出 一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。7 算法和算法分析算法和算法分析PDF 文件使用 pdfFactory Pro 试用版本创建 数据结构与算法讲义322004年3月11日7.2 算法设计的要求算法设计的要求n评价一个好的算法有以下几个标准:(1)正确正确性性(Correctness)算法应满足具体问题的需求。(2)可读可读性性(Readability)算法应该好读。以有利于阅读者对程序的理解。(3)健健状状性性(Robustness)算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产年莫名其妙的输出结果。(4)效率效率与与存储存储量需量需求求效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有关。PDF 文件使用 pdfFactory Pro 试用版本创建 数据结构与算法讲义332004年3月11日7.3 算法的描述算法的描述n算法的描述方法可以归纳为以下几种：(1)自然语言自然语言，如中文、英文；(2)图形图形，如N-S图、流程图，图的描述与算法语言的描述对应；(3)算法语言算法语言，即计算机语言、程序设计语言、伪代码；(4)形式语言形式语言，用数学的方法，可以避免自然语言的二义性。n用各种算法描述方法所描述的同一算法，该算法的功用是一样的，允许在算法的描述和实现方法上有所不同。PDF 文件使用 pdfFactory Pro 试用版本创建 数据结构与算法讲义342004年3月11日算法描述示例，其函数如下，用流程图图形表示算法：1 (x0)f(x)=0 (xn goto ai=ai*10+aGoto stop PDF 文件使用 pdfFactory Pro 试用版本创建 数据结构与算法讲义362004年3月11日End of Chapter 0Thank you!PDF 文件使用 pdfFactory Pro 试用版本创建
