数据结构.第1章绪论--2010

课程编号：08T1031010英文译名：DATASTRUCTUREandALGORITHMS总学时：40/8授课对象：计算机科学与技术本科生先修课程：高等数学、集合与图论、C程序设计课程要求：必修课课程分类：技术基础授课教师：张岩/李秀坤答疑地点：综合楼403/格物楼203办公电话：86413213/86403146E-mail：[e-mail]@hit.edu.cn数据结构与算法数据结构与算法教学目的:(1)学会分析和研究计算机处理的数据对象的特性,掌握常用数据结构内在的逻辑关系、在机内的存储表示,掌握常用数据结构上的运算操作的动态性质和执行算法.(2)能够为实际应用选择适当的数据结构、存储结构和相应算法；(3)初步掌握算法性能的分析方法。参考书目1.[美]SartajSahni著，汪诗林孙晓东等译：《数据结构、算法与应用》C++语言描述，机械工业出版社，2000年1月2.高质量C++/C编程指南计算机系列课程之间的联系计算机概论与上机操作（对21世纪公民要求）程序设计与算法语言（BASIC、FORTRAN、PASCAL、C语言等）计算机组成原理（介绍计算机的共性）微机原理及应用（特定机型介绍，如PC机或单片机）工业控制之路数据处理之路汇编语言程序设计数据结构单片机技术/微机接口操作系统软件技术基础数据库理论计算机网络软件工程计算机网络数据结构涵盖的内容例如：在城市交通运输中，从A点到B点有很多条道路，每条道路的长度不同，拥挤程度不同，要选择一条最快的线路到达目的地，该如何选择？再比如：图书馆有成千上万的图书资料，该如何进行管理才能使我们可以快速查找到需要的资料。数据结构与算法数值处理科学计算一、数据结构是怎样产生的？早期非数值计算控制管理及数据处理城市人口问题，怎样保存这些人口的资料信息，才能使快速查找到所需要查找的人。以上都是典型的非数值问题。思考：1.如何在计算机内部描述这些非数值问题？2.采用什么样的算法可以快速、有效地完成问题的求解？对于不同的处理对象，要想设计出高质量的程序，就必须研究如何组织数据和处理数据，根据问题的要求及数据元素之间的特性，确定相应的存储结构和算法，这些都是数据结构研究的内容。数据结构就是研究这类非数值处理的程序设计问题。数据结构与算法二、选择合适数据结构解决应用问题1．计算机处理问题的分类（1）数值计算问题在计算机发展初期，人们使用计算机主要是处理数值计算问题。【例】线性方程的求解该类问题涉及的运算对象是简单的整型、实型或布尔型数据。程序设计者的主要精力集中于程序设计的技巧，无须重视数据结构。（2）非数值性问题据统计，当今处理非数值性问题占用了90%以上的机器时间，这类问题涉及到的数据结构更为复杂，数据元素之间的相互关系一般无法用数学方程式加以描述。数据结构与算法2．非数值问题求解著名的瑞士计算机科学家沃思（N.Wirth）教授曾提出：算法+数据结构=程序数据结构：是指数据的逻辑结构和存储结构算法：是对数据运算的描述程序设计的实质是对实际问题选择一种好的数据结构，加之设计一个好的算法，而好的算法在很大程度上取决于描述实际问题的数据结构。因此，解决此类问题的关键已不再是分析数学和计算方法，而是要设计出合适的数据结构，才能有效地解决问题。数据结构与算法要解此问题首先构造一张电话号码登记表。表中每个结点存放两个数据项：姓名和电话号码。快的查找算法，取决于这张表的结构及存储方式。最简单的方式是将表中结点顺序地存储在计算机中。查找时从头开始依次查对姓名，直到找出正确的姓名或是找遍整个表均没有找到为止。若这张表是按姓氏排列的，则可另造一张姓氏索引表，采用如下图所示的存储结构。因此，在这种新的结构上产生的查找算法就更为有效。【例】电话号码查询问题。编一个查询某个城市或单位的私人电话号码的程序。要求对任意给出的一个姓名，若该人有电话号码，则迅速找到其电话号码；否则指出该人没有电话号码。数据结构与算法数据结构与算法【例】田径赛的时间安排问题。假设某校的田径选拔赛共设六个项目的比赛，即跳高、跳远、标枪、铅球、100米和200米短跑，规定每个选手至多参加三个项目的比赛。现有五名选手报名比赛，选手所选择的项目如参赛选手比赛项目表所示。现在要求设计一个竞赛日程安排表，使得在尽可以短的时间内安排完比赛。（1）为了能较好地解决这个问题，首先应该选择一个合适的数据结构来表示它。表示该问题的数据结构模型图如下图。数据结构与算法显然同一个选手选择的几个项目是不能在同一时间内比赛的，因此该选手选择的项目中应该两两有边相连。（2）竞赛项目的时间安排问题可以抽象为对无向图进行“着色”操作：即用尽可能少的颜色去给图中每个顶点着色，使得任意两个有边连接的相邻顶点着上不同的颜色。每一种颜色表示一个比赛时间，着上同一种颜色的顶点是可以安排在同一时间内竞赛的项目。由此可得：只要安排4个不同的时间竞赛即可。数据结构与算法时间1内可以比赛跳高（A）和标枪（C），时间2内可以比赛跳远（B）和铅球（D），时间3和时间4内分别比赛100米（E）和200米（F）。解决问题的一个关键步骤是，选取合适的数据结构表示该问题，然后才能写出有效的算法.数据结构与算法绪论1.1数据结构的研究对象1.2数据结构的发展概况1.3抽象数据型(ADT)1.4算法及其复杂性1.5逐步求精的程序设计方法1.1数据结构的研究对象1.1.1基本概念和术语1.1.2四种基本的数据结构1.1.3数据结构的研究对象返回1.1.1基本概念和术语一.客观世界与计算机世界的关系客观世界概念世界机器世界映象抽象映象实现(逻辑模型)映象模拟客观世界与计算机的关系计算机科学是研究信息表示和信息处理的科学。信息在计算机内是用数据表示的。用计算机解决实际问题的实质可以用下图表示：1.1.1基本概念和术语二.基本概念和术语1.数据数据是用于描述客观事物的数值、字符，以及一切可以输入到计算机中的并由计算机程序加以处理的符号的集合。其范围随着计算机技术的发展而不断发展。2.数据元素数据的基本单位是数据元素，在计算机程序中通常作为一个整体进行考虑和处理。3.数据项是数据的不可分割的最小单位，一个数据元素可由若干个数据项组成。4.数据对象性质相同的元素的集合叫做数据对象。5.结点数据元素在机内的位串表示，即数据元素在计算机内的映象。6.域/字段当数据元素由若干个数据项组成时，位串中对应于各个数据项的子串称为域/字段，是数据元素中数据项在计算机中的映象。7.信息表计算机程序所作用的一组数据通常称为信息表，是数据对象在计算机中的映象。1.1.1基本概念和术语8.数据结构数据结构指的是数据元素之间的相互关系，这种关系是抽象的，即并不涉及数据元素的具体内容。是数据元素及其相互间的关系的数学描述。9.逻辑结构和存储结构(1)逻辑结构数据结构中描述的是数据元素之间的抽象关系(逻辑关系)，称为逻辑结构。(2)存储结构/物理结构数据结构在计算机中的表示（映象）称为存储结构/物理结构。1.1.1基本概念和术语(3)数据元素之间的关系（逻辑结构）在计算机中有两种表示方法：顺序映象(表示)和非顺序映象(表示)，从而导致两种不同的存储结构：顺序结构和链式结构。顺序映象（表示）的特点是借助数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。非顺序映象（表示）的特点是借助指示数据元素存储地址的指针来表示数据元素之间的逻辑关系。1.1.1基本概念和术语二.基本概念和术语返回结构化程序设计结构化程序设计：自顶向下、逐步求精；其程序结构是按功能划分为若干个基本模块，这些模块形成一个树状结构；各模块之间的关系尽可能简单，在功能上相对独立；每一模块内部均是由顺序、选择和循环三种基本结构组成；其模块化实现的具体方法是子程序。面向对象程序设计面向对象程序设计：是将数据及对数据的操作方法组合在一起，作为一个相互依存、不可分离的整体——对象；对同类型对象抽象出共性，形成类；类中的大多数数据，只能用本类的方法进行处理；类通过一个简单的外部接口与外界发生关系，对象与对象之间通过消息进行通信。对象、类、封装、继承和多态是面向对象程序设计的重要概念。1.1.2四种基本的数据结构1.集合结构结构中的数据元素之间除了“属于同一个集合”的关系之外，别无其他关系。关系比较松散，可用其他结构来表示。结构中的数据元素之间存在一个对一个的关系，即线性关系，每个元素至多有一个直接前导和后继。2.线性结构e.g.set=(K,R)K={01,02,03,04,05,06,07,08,09,10}R={}特点：元素按任一序列排列e.g.linearity=(K,R)K={1,2,3,4,5,6,7,8,9,10}R={5,1,1,3,3,8,8,2,2,7,7,4,4,6,6,9,9,10}对应的图形：⑤→①→③→⑧→②→⑦→④→⑥→⑨→⑩特点：数据元素之间是1对1（1：1）联系。1.1.2四种基本的数据结构3.树型结构结构中的数据元素之间存在一个对多个的关系，即层次关系，即每一层上的元素可能与下层的多个元素相关，而至多与上层的一个元素相关。结构中的数据元素之间存在多个对多个的关系，即任意关系，任何元素之间都可能有关系。4.网状/图型结构e.g.tree=(K,R)K={1,2,3,4,5,6,7,8,9,10}R={1,2,1,3,1,4,2,5,2,6,3,7,3,8,3,9,4,10}对应的图形:e.g.graph=(K,R)K={1,2,3,4,5,6,7}R={r}R={1,2,2,1,1,4,4,1,2,3,3,2,2,6,6,2,2,7,7,2,3,7,7,3,4,6,6,4,5,7,7,5}对应的图形:特点：数据元素之间是M对N（M:N）(M≥0,N≥0)图结构和网状结构统称为非线性结构。1.1.3数据结构的研究对象数据结构的研究对象(研究内容)1.数据对象的结构形式,各种数据结构的性质(逻辑结构);2.数据对象和”关系”在计算机中的表示(物理结构/存储结构);3.数据结构上定义的基本操作(算法);4.算法的效率;5.数据结构的应用,如数据分类,检索.返回数据结构的作用图数据结构数据关系数据表示数据类型数学离散数学应用数学硬件存储设备总体结构软件系统软件应用软件算法设计数据运算编码理论数据组合系统设计数据存取正所谓道可道，非常道。编程之道就如武学之道，VB，VC，dephi等开发工具的技巧好比各门各派的武功招数，算法和数据结构好比内功心法和武学原理。内力深厚，任何招数到了用上都能够化腐朽为神奇；掌握了武学原理，更能做到无招胜有招。1.2数据结构的发展概况1.程序设计方法学的发展极大地促进了数据结构的发展(1)计算机科学及其应用的发展时数据结构成为独立学科.(2)以数据为中心的程序设计方法推动了数据结构的发展.面向过程的程序设计的特点是以程序为中心，侧重于建立程序，程序在简单的数据结构上进行复杂的运算，软件设计的主要工作就是设计求解问题的过程。注重于程序设计技巧，适合于数值计算。返回2.数据结构在计算机科学中的地位(1)是计算机科学的一门专业基础和核心课程。(2)是学习、设计和实现操作系统、编译系统、数据库系统和其它应用系统的重要基础。结构化特别是面向对象的程序设计以数据(结构)为中心，系统采用复杂的数据结构来描述系统状态，程序围绕数据结构进行加工。这种编程语言更适合于非数值计算。1.3抽象数据型(ADT)1.3.1抽象数据型的定义1.3.2数据类型,数据结构和ADT返回1.3.4抽象数据型的优点1.3.3多层次抽象技术1.3.1抽象数据型的定义一.抽象数据型的定义1.定义:是一个数学模型和在该模型上定义的操作集合