数据结构第一章概论.ppt

1,数据结构,C语言版,2, 教材 数据结构 （ C语言版） 严蔚敏 吴伟民 清华大学出版社, 参考教材 1 数据结构 （ C语言版） 刘清 王琼 电子工业出版社 2 数据结构题集 （ C语言版） 严蔚敏 吴伟民 清华大学出版社,3,教学内容（总学时64, 其中有12学时实验） 第一章 绪论 （6学时） 第二章 线性表 （8学时） 第三章 栈和队列 （8学时） 第六章 树 （10学时） 第七章 图 （8学时） 第九章 查找 （4学时） 第十章 排序（6学时） 总复习 （2学时） 共计52学时,考核 平时成绩10%实验20%考试成绩70%,4,课程特点及教学方法,难度大 综合性强 必须要有C语言基础 关于教学的几个新观念 教学过程以学生为主体, 教师为主导 学生由知识技能的被动接受者向知识技能的主动探求者转变,。教学目标为使学生在知识、能力、素质方面协调发展 能力包括自学能力、知识运用能力、动手能力、创新能力、发现问题能力、分析问题和解决问题能力以及可持续发展能力,5,1.1 本课研究的问题 1.2 什么是数据结构 1.3 数据结构的基本概念和术语 1.4 数据结构的分类与表示 1.5 算法与算法分析,第一章 绪 论,6,计算机的发展 软件 硬件 应用领域,数据处理的种类和能力, 数据,数值数据,非数值数据,数 (整数,实数) 字符 字符串 文字 图形 图象 声音,数据：客观对象的符号表示 数学中的整数、实数， 课程名，地名、书名,1.1 本课程研究的问题,1.1 本课程研究的问题,7, 数值问题与非数值问题,1）数值问题 已知：游泳池的长len和宽wide，求面积area,设计 求解问题的方法 编程, 建模型： 问题涉及的对象：游泳池的长len 宽wide，面积area； 对象之间的关系：area=lenwide,1.1 本课程研究的问题,main ( ) int len, wide ,area ; scanf (“%d %d%n”, ,8,在这类文档管理的数学模型中, 计算机处理的对象之间通常存在着一种最简单的线性关系 , 这类数学模型称为线性模型,1.1 本课程研究的问题,9,1.1 本课程研究的问题,迷宫问题： 在迷宫中，每走到一处，接下来可走的通路有三条。计算机处理的这类对象之间通常不存在线性关系。若把从迷宫入口处到出口的过程中所有可能的通路都画出，则可得一棵“树”,10,数据结构的研究问题： 非数值数据之间的结构关系， 及如何表示，如何存储，如何处理。 本课程讨论的问题： 应用中常用的几种数据间的结构关系， 及如何表示,如何存储，如何处理。,1.1 本课程研究的问题,11,数据结构是一门研究数据组织、存储和运算的一般方法的学科。,1.2 什么是数据结构,1.2 什么是数据结构,整数(1,2)、实数(1.1,1.2) 字符串(Beijing)、 图形、声音。,计算机管理图书问题 在图书馆里有各种卡片：有按书名编排的、 有按作者编排的、有按分类编排 如何将查询图书的这些信息存入计算机中 既要考虑查询时间短，又要考虑节省空间,最简单的办法之一是建立一张表， 每一本书的信息在表中占一行，如,数据元素在 计算机中的表示,如何将0,1,2,3,4,5,6,7,8,9这10个数存放在 计算机中能最快地达到你所需要的目的？ 目的不同，最佳的存储方方法就不同。 从大到小排列：9,8,7,6,5,4,3,2,1,0 输出偶数：0,2,4,6,8,1,3,5,7,9,对数据结构中的节点进行 操作处理 (插入、删除、修改、查找、排序),程序算法数据结构,12,13 数据结构的有关概念,1.3 数据结构的有关概念,数据（data)所有能输入到计算机中去的描述客观事物的符号。例如：学号，姓名，班名都是数据。 数据元素（data element）数据的基本单位，也称节点（node）或记录（record） 。 数据项（data item）有独立含义的数据最小单位，也称域(field) 数据结构（data structure)数据元素和数据元素关系的集合。例如: 所有班名相同的记录集合,13,对每种数据结构，主要讨论如下两方面的问题： 1） 数据的逻辑结构，数据结构的基本操作； 2） 数据的存储结构，数据结构基本操作的实现；,数据的逻辑结构： 数据之间的结构关系，是具体关系的抽象。,数据结构的基本操作： 指对数据结构的加工处理,数据的存储结构 (物理结构)： 数据结构在计算机内存中的表示,数据结构基本操作的实现： 基本操作在计算机上的实现（方法),13 数据结构的有关概念,14,某班学生基本情况登记表，记录了每个学生的学号 姓名 专业 政治 面貌 ，表中的记录是按学生的学号顺序排列的。,学号 姓名 专业 政治面藐 001 王洪 计算机 党员 002 孙文 计算机 团员 003 谢军 计算机 团员 004 李辉 计算机 团员 005 沈祥福 计算机 党员 006 余斌 计算机 团员 007 巩力 计算机 团员 008 孔令辉 计算机 团员,学生基本情况登记表的图示,学生间学号顺序关系 是一种线性结构关系,一 常用的数据结构,1） 集合 2） 线性结构 3） 树结构 4） 图结构 5）其它复杂结构,例,1.4 数据结构的分类与表示,14 数据结构的分类与表示,15,家族的族谱 假设某家族有10个成员A， B， C， D， E， F， G， H，I， J，他们之间的血缘关系可以用如下图表示。,14 数据结构的分类与表示,例,16,多叉路口交通灯管理问题,例,14 数据结构的分类与表示,17,数据结构的表示,1、图示表示 图示表示是由顶点和边构成的图，其中顶点表示数据 ，边表示数据之间的结构关系；,学生基本情况表的图示表示,家族树的图示表示,14 数据结构的分类与表示,18,学生基本情况表的二元组表示（D，S）,2、二元组表示 二元组表示是用一个二元组（D，S）表示数据结构， 其中 D 是数据元素集合，S 是 D 上关系的集合。,D = 001，002，003，004，005，006，007，008 S = R R= , , ,家族树的二元组表示（D，S）,D = A，B，C，D，E，F，G，H，I，J S = R R = A,B, ,14 数据结构的分类与表示,19,1、数据的逻辑结构,2、数据的存储结构,3、数据的运算：检索、排序、插入、删除、修改等。,A线性结构,B非线性结构,A 顺序存储,B 链式存储,线性表,栈,队,树形结构,图形结构,数据结构的三个方面,数据结构可描述为 Group=（D，R）,(亦称物理结构),14 数据结构的分类与表示,20,数据的逻辑结构只抽象反映数据元素的逻辑关系 数据的存储（物理）结构数据的逻辑结构在计算机存储器中的实现,数据结构侧重于解决问题的策略和方法，即研究算法。 它不但要求给出问题的一种算法，还要求算法的时空效率高、算法结构和可读性好、容易验证等等。,14 数据结构的分类与表示,21,3、抽象数据结构描述：,有限个数据 元素的集合,是D上 关系的有限集,14 数据结构的分类与表示,有限个节点间 关系的集合,Group=（D , S , R）,ADT（Abstract Data Type），即抽象数据类型，是指一个数学模型及定义在该模型上的一组操作（运算）。ADT只考虑数据的逻辑结构,22,ADT的定义可以用一个三元组表示。其中D是数据对象，S是D上的关系集，R是对D的基本操作集。可以采用以下格式定义ADT： ADT 抽象数据类型名 数据对象： 数据关系： 基本操作： ADT 抽象数据类型名 其中，数据对象和数据关系的定义可以用形式化伪码描述，基本操作的定义格式为： 基本操作名（参数表） 初始条件： 操作结果：,23,ADT的定义与数据结构的定义有着明显的差别，它将基本操作与数据对象和数据关系在形式上封装在一起，并以此来建模。大多数的抽象数据类型是由用户自行设计和实现的。,例: 用ADT表示复数Complex。,ADT Complex 数据对象：D= ，R 数据关系： e1是实数，e是虚数 基本操作：主要加、减、乘、除等操作,24,GetReal(z) 初始条件：复数z已经存在。 操作结果：返回复数z的实部值。,GetImage (z) 初始条件：复数z已经存在。 操作结果：返回复数z的虚部值。,Add(z1, z2) 初始条件：z1,z2均为复数。 操作结果：返回复数z1和z2的和,Minus (z1, z2) 初始条件：z1,z2均为复数。 操作结果：返回复数z1减z2的差 。,Multiply (z1, z2) 初始条件：z1,z2均为复数。 操作结果：返回复数z1和z2的积,Multiply (z1, z2) 初始条件：z1,z2均为复数。 操作结果：返回复数z1除以z2的商,InitComplex(&z, v1,v2) 初始条件：无。 操作结果：构造复数z，其实部和虚部分别赋以参数v1和v2的值, ADT Complex,25,例： 采用前面定义的抽象数据类型Complex所提供的各种操作函数，编制一个算法（C语言），用以计算复数： z=（(8-6i)(4+3i)）/（2+6i）-(3+3i)的值。,分析：为简单起见，不妨假定ADT Complex中的所有操作函数已经实现，只要遵守ADT Complex中的约定即可。,26,算法： Complex z1, z2, z3, z4, z5;设置参数 InitComplex( ,抽象数据类型需要用具体的数据类型来实现。采用什么样的数据结构表示数学模型，要服从于方便有效地实现该抽象数据类型上定义的大多数操作。,27,1.5 算法与算法分析,一 、算法的概念 算法 ：是解决某一特定问题的具体步骤的描述，是指令的有限序列,算法的描述：采用C语言描述,15 算法与算法分析,算法的基本特征： 1）输入：0个或多个输入； 2）输出：1个或多个输出； 3）有穷性：算法必须在有限步内结束； 4）确定性：组成算法的操作必须清晰无二义性。 5）可行性：组成算法的操作必须能够在计算机上实现。,28,算法的评价衡量算法优劣的标准 正确性(correctness)：不含语法错误 可读性(readability)：便于维护 健壮性(robustness)：见错性好 效率与低存储量,算法效率用依据该算法编制的程序在计算机上执 行所消耗的时间来度量,29,例,试编写算法：输入一个正整数，并判断是否为素数,一般使用结构化程序设计方法解决问题。常用的是逐步求精和分而治之的设计方法，用来开发软件系统。一般情况下，采用分而治之将问题逐步化小，直到达到人们能够理解的程度，再用逐步求精找出算法，因而多把它们结合使用。,1、逐步求精方法把程序设计分为二步：第一步，只考虑“做什么”，即对问题进行分析，给出解决问题的思路；第二步，再考虑“如何去做”，给出具体代码。,30,2、分而治之的方法： 1)把问题分成两个或多个更小的问题； 2)分别解决每个小问题； 3)把各小问题的解答组合起来，即可得到原问题的解答。小问题通常与原问题相似，可以递归地使用分而治之策略来解决。,31,算法：int input(） /判断X是否为素数/ flog=1; i=2; while ( i= X-1 ) and ( flog=1 ) if ( X % i = =0) flog=0; i+; return ( flog ),本题用逐步求精方法完成： 1、第一步：分析所提出的问题，设计程序的结构 2、第二步：对 “素数”进一步求精，设置一个标志参数flog 3、第三步：对 “x 是一个素数”进一步求精，根据素数定义用i2,.,X，除以X，flog=0表示能除尽，为1则不能 4、第四步: 对“x不能被j整除”进一步求精，根据flog的值，判断X是否为素数,32,15 算法与算法分析,C语言程序： Main（） int x, flog, i; flog=1; scanf( “%d”, x ); for ( i =2, i=x-1, i+ ) if ( x % i = =0 ) flog=0 ,break if ( flog ) printf (“是一个素数”) else printf (“非素数”） ,33,例,试给你一个装有16个硬币的袋子。16个硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这个伪造的硬币。为了帮助你完成这一任务，提供一架天平用于找出伪币。,第一种方法：逐步求精方法；两个进行比较，找 出较轻者，最多需要8次比较。,第二种方法：分而治之方 ；把16硬币看成一个大 的问题。,34,16,8轻,4轻,2轻,35,15 算法与算法分析,二、算法时间复杂度T（n） 本课程采用以求解问题的基本操作（原操作）的执行次数作为算法时间的度量。,算法的时间复杂度 一般来说，设算法中基本操作的执行次数是问题规模n的某个函数f(n)，算法的时间复杂度记作： T(n) = O(f(n) 语句重复执行的次数称为语句的频度,36,一个算法的时间复杂度（Time Complexity，简称为时间复杂性）T(n)是该算法的时间耗费，是该算法所求解问题规模n的函数。当问题的规模n趋向无穷大时，时间复杂度T(n)的数量级(阶)称为算法的渐进时间复杂度。,例,求两个 n 阶矩阵的乘法CAB的算法，写出算法中带标号语句的频度，并求该算法的时间复杂度,37,15 算法与算法分析,For ( i = 1; i=n; i+ ) (1) For (j = 1; j=n; j+ ) (2) x=0; (3) For (k = 1; k= n; k+ ) (4) c i j += a i k * b k j ; (5) c i j = x; (6) ,该算法主体是一个三重循环，先以标号（2）的语句说明其频度：对于固定的i、j从1变到n,指令j+需执行n+1步，而相对于外循环(1),i从1变到超过n，内循环重复n次，故(2)的执行频度为n(n+1),(1) n+1,(2) n(n+1),(3) n2,(4) n2(n+1),(5) n3,(6) n2,标号语句的频度分别为：,算法时间复杂度为所有语句的频度之和： T(n) = n+1+n(n+1)+n2+n2(n+1)+n3+n2 =2 n3 +4 n2 +2n+1 O(n3),38,15 算法与算法分析,有些算法，基本操作执行次数与问题的输入数据有关，这时可考虑 （1） 算法平均时间复杂度 （2） 算法在最坏情况下的时间复杂度,例,指出下列算法的时间复杂度： Void prume(int n) int i=2; While( ( x % i) ,39,算法:是一个有穷规则的集合，其中之规则确定了一个解决某一特定类型问题的运算序列。 算法具有五个特点：有穷性、确定性、输入、输出和能行性。 算法的正确性判定是:一个比较复杂的问题，对于简单的算法，可以采用穷举法或程序正确性证明等方法来确定算法的正确性；而对于复杂的算法，人们不可能采用穷举法或程序正确性证明来验证算法的正确性，只能说明算法在给定的测试下没有错误发生，而不能说明算法是正确的。,40,算法分析: 评价一个算法的好坏主要是从算法的时间复杂度和算法的空间复杂度两个方面来考察。 算法的时间复杂度和空间复杂度是两个相互矛盾的性能指标，一个算法要么其所占存储空间较小，要么其运行时间较短，两者性能均好的算法往往难以找到。,41,本章节的重点 1数据结构及其表示。数据结构包括数据的逻辑结构和物理结构，数据呈现给用户是其逻辑结构，其物理存储对用户是透明的。为了有效地处理数据，数据结构必须给出数据集上操作的统一接口，而不管其存储结构。 2ADT是一种描述数据结构的常用工具，它能很好地描述数据的逻辑结构和其上的操作。在用ADT描述数据结构时，可以不考虑其存储结构。,42,3结构化程序设计方法是一种典型的程序设计方 法。由于结构化程序设计方法将问题划分成一个个的相互独立又相互联系的子问题，解决子问题相对容易，而且子问题的正确性也易于保证，因此结构化程序设计方法是数据结构中采用的一种典型设计方法。 4算法。算法是实现结构化程序设计方法的基础，一个子问题可以用一个算法来实现，将各个子问题的算法有机地结合起来就构成了整个问题的实现算法。,43,例,设有数据逻辑结构为： D（K R） K（K1，K2，K3，K9） RK1，K3， K1，K8， K2，K3， K2，K4， K2，K5， K3，K9 ，K5，K6 K8，K9 ，K9，K7 ，K4，K7 ，K4，K6 画出这个逻辑结构的图示，并确定相对于关系R，哪些结点是开始结点，哪些结点是终端结点？,开始结点：是指无前趋的结点，,终端结点：是指无后续的结点，,只有K1和K2。,只有K6和K7。,14 数据结构的分类与表示,44,已知m，n均为正整数，试用ADT描述求m和n的最小公倍数的算法。,例,算法的步骤如下： （1）计算r(m*n)； （2）若m等于n，则输出最小公倍数r/m，算法结束； （3）若m大于n，计算m(m-n；否则计算n(n-m； （4）转（2）。,分析：题设虽只要描述其求两个正整数的最小公倍数，为了ADT描述的方便，我们可以针对整个正整数集来讨论。 ADT是一种描述数据结构的常用工具，针对具体问题，只要按照ADT的描述规范实现就可以了。,45,下面是其ADT描述： ADT Positive_Int 数据对象：Dx | x是正整数 基本操作： LCM(x1, x2) 初始条件：要求x1和x2都是正整数。 操作结果：返回x1和x2的最小公倍数。 ADT Positive_Int;,46,基本操作LCM的C语言形式的具体实现为： int LCM( int x1, int x2 ) /* 求正整数x1和x2的最小公倍数 */ int r = x1 * x2; /* 存放x1和x2的积 */ if( x1 x2 ) x1 = x1 x2; else x2 = x2 x1; return r / x1; /* 返回正整数x1和x2的最小公倍数 */ ,47,作 业 1、写出下题算法，并求出其时间复杂度。(C语言） 100元买100支笔, 其中钢笔 3元/支, 圆珠笔 2元/支, 铅笔 0.5元/支，用C语言编程输出可能的各种组合方案。 2、有一个老板有一袋金块。每个月将有两名雇员会因其优异的表现分别被奖励一个金块。按规矩，排名第一的雇员将得到袋中最重的金块，排名第二的雇员将得到袋中最轻的金块。根据这种方式，除非有新的金块加入袋中，否则第一名雇员所得到的金块总是比第二名雇员所得到的金块重。如果有新的金块周期性的加入袋中，则每个月都必须找出最轻和最重的金块。假设有一架天平，请你设计一个算法用最少的比较次数找出最轻和最重的金块。,48,算法的时间复杂度为O (N3),49,# define N 100 Void scheme( ) int i, j; for (i=0; i=N/3; i+) for (j=0; j=(N-3*i)/2; j+) if (3*i+2*j+0.5*(N-i-j)= =N) printf(“%d, %d, %dn%”, i, j, N-i-j); 时间复杂度为O(N2 ),解法2,50,线性结构,A , B , C , ，X ,Y , Z,学 生 成 绩 表,线性表结点间是以线性关系联结,A1， A2 Ai-1， Ai， Ai+1， An,A