《数据结构(第1章)讲义.ppt》由会员分享，可在线阅读，更多相关《数据结构(第1章)讲义.ppt（40页珍藏版）》请在三一办公上搜索。
1、授课教师：张小莉 联系电话：5079389办公室：主楼1208Email:,数 据 结 构,2,数据是计算机可以直接处理的基本和最重要的对象。计算机科学是一门研究数据表示和数据处理的科学。计算机进行科学计算、过程控制、对文件的存储和检索及数据库技术等计算机应用，都是对数据进行加工处理的过程。-这个过程是按照程序进行的。要设计出一个结构好而且效率高的程序，必须研究数据的特性、数据间的相互关系及其对应的存储表示方法，并利用这些特性和关系设计出相应的算法和程序。,数据结构课程就是围绕这些问题带你走进数据表示和数据处理的大门。-研究数据表示和数据处理,3,数据结构作为一门独立的课程在国外是从1968年
2、才开始的，但在此之前其有关内容已散见于编译原理及操作系统之中。从20世纪60年代末到70年代初，出现了大型程序，软件也相对独立，结构程序设计成为程序设计方法学的主要内容，人们越来越重视数据结构。从70年代中期到80年代，各种版本的数据结构著作相继出现。目前，数据结构的发展并未终结，一方面，面向各专门领域中特殊问题的数据结构得到研究和发展，如多维图形数据结构等；另一方面，从抽象数据类型和面向对象的观点来讨论数据结构已成为一种新的趋势，越来越被人们所重视。,4,本课程的任务是：在基础方面，要求学生掌握常用数据结构的基本概念及其不同的实现方法；在技能方面，通过系统学习能够在不同存储结构上实现不同的运
3、算，并对算法设计的方式和技巧有所体会。,学业基础：本课程的先修课程为高级语言程序设计。学习本课程必须具备高级语言程序设计(如C 或C+，等等)的基础知识与基本技能。它的后续课程有操作系统和数据库原理、算法分析与设计等。学时安排：总学时100。其中课堂讲授68学时,实验教学32学时。,5,6,理论学习（4学分）：平时成绩（30%）：出勤、课上提问、课后作业、小测、论坛参与等等；考试成绩（70%）：期末考试卷面分数。实验（1学分）：实验课：每个实验按照要求进行，并提交实验报告。,7,教学内容：1.1 数据结构的概念；1.2 抽象数据类型；1.3 算法和算法分析。教学目的：领会数据、数据元素和数据项
4、的概念及其相互间的关系；清楚数据结构的逻辑结构、存储结构的联系与区别；理解抽象数据类型的概念；掌握进行简单算法分析的方法。,第1章 绪论,8,教学重点：数据、数据项、数据元素、数据结构的概念；逻辑结构和数据结构在概念上的联系与区别；抽象数据类型和数据抽象；评价算法优劣的标准及方法。教学难点：区别算法与程序；逻辑结构、存储结构的联系与区别；抽象数据类型与数据抽象；算法的时间复杂度分析。学时安排：2学时,9,1.1 数据结构的概念,为什么要学习数据结构有关概念和术语数据结构课程的内容,10,1.1.1 为什么要学习数据结构,现实中有计算机处理的两大类问题：数值问题和非数值问题 计算机使用初期：主要
5、是处理数值计算问题（归结为解方程、求值）。涉及的运算对象是简单，不重视数据结构。发展之后：非数值计算问题越来越显得重要。据统计，当今处理非数值计算性问题占用了90%以上的机器时间。数据结构更为复杂；数据元素之间的相互关系无法用数学方程式加以描述；要分析所处理的数据必要分析数据间的关系。,11,例1 学生信息检索系统,该系统的主要操作之一便是按照某个特定要求（如给定姓名）对学生信息文件进行查询。当我们需要查找某个学生或查询某个专业或年级的学生的有关情况的时候，只要我们建立了相关的数据库，按照某种算法编写了相关程序，就可以实现计算机自动检索。根据需求分析，可以建立以下四张表：,12,13,例1 学
6、生信息检索系统,学号顺序排列的学生信息表 姓名顺序排列的索引表专业顺序排列的索引表年级顺序排列的索引表,学生信息检索系统 的数学模型,相对每一张表，表中的每一行的信息，我们可以成为一个数据元素，每张表中的数据元素之间是一个序列的关系，我们称之为线性关系。,14,例2 八皇后问题,该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。,为了描述方便，将八皇后问题简化为四皇后问题:,15,在八皇后问题中，处理过程不是根据某种确定的计算法则，而是利用试探和回溯的探索技术求解。为了求得合
7、理布局，在计算机中要存储布局的当前状态。从最初的布局状态开始，一步步地进行试探，每试探一步形成一个新的状态，整个试探过程形成了一棵隐含的状态树。每一个状态，也是一个数据，而所有的数据之间是一种树型关系。,16,例3 教学计划编排问题,一个教学计划包含许多课程。课程之间，有些必须按规定的先后次序进行，有些则没有次序要求。即课程之间有先修和后修的关系，有些课程可以任意安排次序。某个专业的教学计划的各个课程之间的次序关系可用一个称作图的数据结构来表示。,17,18,由以上三个例子可见，描述这类非数值计算问题的数学模型不再是数学方程，而是根据数据元素之间构成的线性关系、树型关系、网状关系等，抽象出来的
8、描述各自问题的表、树、图。,数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。,19,学习数据结构的目的是为了了解计算机处理对象的特性，将实际问题中所涉及的处理对象在计算机中如何表示出来并对它们进行处理。与此同时，通过算法训练来提高学生的思维能力，通过程序设计的技能训练来促进学生的综合应用能力和专业素质的提高。,20,1.1.2 有关概念和术语,数据 数据元素 数据项 数据对象或数据元素类,21,数据结构（Data Structure）是指互相之间存在着一种或多种关系的数据元素的集合。在任何问题中，数据元素之间都不会是孤立的，在它们之间都存在
9、着这样或那样的关系，这种数据元素之间的关系称为结构。,根据数据元素间关系的不同特性，通常有下列四类基本的结构:(1)线性结构。(2)树型结构。(3)图型结构。(4)集合结构。,22,可以从两个层面上研究数据结构。抽象层面：数据结构有两个要素。一个是数据元素的集合，另一个是关系的集合。形式上，数据结构可以采用一个二元组来表示：,23,应用层次(具体的)：数据结构包括数据的逻辑结构和数据的物理结构。(1)逻辑结构:数据的逻辑结构可以看作是从具体问题抽象出来的数学模型，它与数据的存储无关。(2)物理结构：如何在计算机中表示一个数据结构。数据结构在计算机中的表示（又称映像）称为数据的物理结构，或称存储
10、结构。它所研究的是数据结构在计算机中的实现方法，包括数据结构中元素的表示及元素间关系的表示。,24,1.1.3 数据结构课程的内容,数据结构课程集中讨论软件开发过程中的数据分析及表示阶段、编码分析和实现阶段，同时，为了构造出好的数据结构及其实现，还需考虑数据结构及其实现的评价与选择。因此，数据结构的内容包括三个层次的五个“要素”。,25,1.2 抽象数据类型,数据类型抽象数据类型,26,1.2.1 数据类型,数据类型是和数据结构密切相关的一个概念。它最早出现在高级程序设计语言中，用以刻划程序中操作对象的特性。在用高级语言编写的程序中，每个变量、常量或表达式都有一个它所属的确定的数据类型。类型显
11、式的或隐含的规定了在程序执行期间变量或表达式所有可能的取值范围，以及在这些值上允许进行的操作。因此，数据类型（Data Type）是一个值的集合和定义在这个值集上的一组操作的总称。,27,抽象数据类型（Abstruct Data Type，简称ADT）是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。抽象数据类型和数据类型实质上是一个概念。有如下几个特点：,1.2.2 抽象数据类型,28,抽象数据类型的范畴更广，它不再局限于前述各处理器中已定义并实现
12、的数据类型，还包括用户在设计软件系统时自己定义的数据类型。为了提高软件的重用性，在近代程序设计方法学中，要求在构成软件系统的每个相对独立的模块上，定义一组数据和施于这些数据上的一组操作，并在模块的内部给出这些数据的表示及其操作的细节，而在模块的外部使用的只是抽象的数据及抽象的操作。这也就是面向对象的程序设计方法。抽象数据类型的定义可以由一种数据结构和定义在其上的一组操作组成，而数据结构又包括数据元素及元素间的关系，因此抽象数据类型一般可以由元素、关系及操作三种要素来定义。抽象数据类型的特征是使用与实现相分离，实行封装和信息隐蔽。就是说，在抽象数据类型设计时，把类型的定义与其实现分离开来。,29
13、,1.3 算法和算法分析,算法特性 算法描述 算法性能分析与度量,30,1.3.1 算法特性,算法（Algorithm）是对特定问题求解步骤的一种描述，是指令的有限序列。其中每一条指令表示一个或多个操作。一个算法应该具有下列特性：有穷性。一个算法必须在有穷步之后结束，即必须在有限时间内完成。确定性。算法的每一步必须有确切的定义，无二义性。算法的执行对应着的相同的输入仅有唯一的一条路经。可行性。算法中的每一步都可以通过已经实现的基本运算的有限次执行得以实现。输入。一个算法具有零个或多个输入，这些输入取自特定的数据对象集合。输出。一个算法具有一个或多个输出，这些输出同输入之间存在某种特定的关系。,
14、31,算法与数据结构是相辅相承的。解决某一特定类型问题的算法可以选定不同的数据结构，而且选择恰当与否直接影响算法的效率。反之，一种数据结构的优劣由各种算法的执行来体现。要设计一个好的算法通常要考虑以下的要求。正确。算法的执行结果应当满足预先规定的功能和性能要求。可读。一个算法应当思路清晰、层次分明、简单明了、易读易懂。健壮。当输入不合法数据时，应能作适当处理，不至引起严重后果。高效。有效使用存储空间和有较高的时间效率。,32,1.3.2 算法描述,算法可以使用各种不同的方法来描述。自然语言:程序流程图、N-S图等算法描述工具：直接使用某种程序设计语言：用伪码语言的描述方法：伪码语言介于高级程序
15、设计语言和自然语言之间，它忽略高级程序设计语言中一些严格的语法规则与描述细节，因此它比程序设计语言更容易描述和被人理解，而比自然语言更接近程序设计语言。它虽然不能直接执行但很容易被转换成高级语言。,33,1.3.3 算法性能分析与度量,怎样衡量一个算法：时间复杂度和空间复杂度 算法的好坏主要取决于算法在执行的过程中所占用的空间和耗费的时间，称之为算法的时间复杂度和空间复杂度。用时间复杂度和空间复杂度来评价算法的优劣。,34,问题：在各种因素都不能确定的情况下，很难比较出算法的执行时间。因此，使用算法执行的绝对时间来衡量算法的效率是不合适的。将一个算法转换成程序并在计算机上执行时，其运行所需要的
16、时间取决于下列因素：硬件的速度。书写程序的语言。编译程序所生成目标代码的质量。问题的规模。,35,例：float sum(float a,int n)float s;int i;s=0.0;for(i=0;in;i+)s+=ai;return s;,问题规模 n：一般情况下，一段程序执行操作的次数是问题规模 n 的某个函数：T(n)=f(n),1、时间复杂度,36,大“”表示法 与 算法的渐进时间复杂度。许多时候要精确地计算T(n)是困难的，我们引入渐进时间复杂度在数量上估计一个算法的执行时间，也能够达到分析算法的目的。如果存在两个正常数c和n0，使得对所有的n（nn0），有：f(n)cg(n
17、)，则记为：f(n)O(g(n)例：一个程序的实际执行时间为：T(n)2.7n3+3.8n2+5.3 当n-：（2.7n3+3.8n2+5.3)/n3=C 则记为：T(n)O(n3)前面例子：T(n)=2n+3 则：T(n)O(n)使用大记号表示算法的时间复杂度，称为算法的渐进时间复杂度。,37,通常用(1)表示常数阶时间复杂度。常见的渐进时间复杂度有：O(1)O(log2n)O(n)O(nlog2n)O(n2)O(n3)O(2n),2、空间复杂度：一般来讲，一个算法的空间复杂度主要考虑除数据结构本身之外因为该算法的设计所需求的额外的空间开销。通常也是问题规模n的函数，也用空间渐进复杂度表示。
18、,38,数据结构是计算机及相关专业中的一门重要的专业基础课程，具有举足轻重的作用。当用计算机来解决实际问题时，就要涉及到数据的表示和数据的处理，而数据表示及数据处理正是数据结构课程的主要研究对象，通过这两方面内容的学习，为后续课程，特别是软件方面的课程打下厚实的知识基础，同时也提供了必要的技能训练。,39,40,对于DonaldE.Knuth本人，一生中获得的奖项和荣誉不计其数，包括图灵奖、美国国家科学金奖、美国数学学会斯蒂尔奖（AMSSteelPrize），以及发明先进技术荣获的极受尊重的京都奖（KyotoPrize）等等，写过19部书和160余篇论文，每一篇著作都能用影响深远来形容。Don
19、aldE.Knuth也被公认是美国最聪明的人之一。当年他上大学的时候，常写些各种各样的编译器来挣外快，只要是他参加的编程比赛，总是第一名，同时也是世上少有的编程达到40年以上的程序员之一。他除了是技术与科学上的泰斗外，更是无可非议的写作高手，技术文章堪称一绝，文风细腻，讲解透彻，思路清晰而且没有学究气，估计这也是计算机程序设计艺术被称为圣经的原因之一。其个人主页：http:/www-cs-faculty.stanford.edu/knuth/,DonaldE.Knuth，中文名：高德纳(1938-)算法和程序设计技术的先驱者。Oh,God!一些国外网站这样评价他。一般说来，不知道此人的程序员是不可原谅的。其经典著作 计算机程序设计艺术更是被誉为算法中“真正”的圣经，像KMP和LR(K)这样令人不可思议的算法，在此书里比比皆是。难怪连BillGates都说：“如果能做对书里所有的习题，就直接来微软上班吧！”,
