数据结构课件第一章.ppt

1、1数据结构数据结构(C语言版语言版) Data Structure主讲教师主讲教师 秦俊平秦俊平 2 数据结构的概念数据结构的概念 算法的概念和描述算法的概念和描述 算法的简单分析算法的简单分析3&电子计算机的主要用途：电子计算机的主要用途： 早期：早期： 主要用于数值计算。 后来：后来： 处理逐渐扩大到非数值计算领域（能处理多种复杂的具有一定结构关系的数据）。4& 数值计算解决问题的一般步骤：数值计算解决问题的一般步骤： 数学模型选择计算机语言编出程序测试最终解答。 数值计算的关键是：数值计算的关键是： 如何得出数学模型（方程） 程序设计人员比较关注程序设计的技巧。& 非数值计算问题：非数值

2、计算问题： 数据元素之间的相互关系一般无法用数学方程加以描述5 例例1.1 电话号码查询问题：电话号码查询问题： （1）按顺序存储方式：须遍历表 （2）按姓氏索引方式：索引 （3）按号码 要写出好的查找算法，取决于这张表的结构及存储方式。 电话号码表的结构和存储方式决定了查找（算法）的效率。 非数值计算问题：非数值计算问题：6 例1.2 磁盘目录的描述7 例例1.3 田径赛的时间安排问题（无向图的着色田径赛的时间安排问题（无向图的着色问题）问题） ： 设有六个比赛项目，规定每个选手至多可参加三个设有六个比赛项目，规定每个选手至多可参加三个项目，有五人报名参加比赛（如下表所示）设计比赛项目，有五

3、人报名参加比赛（如下表所示）设计比赛日程表，使得在尽可能短的时间内完成比赛。日程表，使得在尽可能短的时间内完成比赛。8 解法：解法： （1）设用如下六个不同的代号代表不同的项目：）设用如下六个不同的代号代表不同的项目： 跳高 跳远 标枪 铅球 100米 200米 A B C D E F （2）用顶点代表比赛项目用顶点代表比赛项目 不能同时进行比赛的项目之间连上一条边。 （3）某选手比赛的项目必定有边相连（不能同时比赛）某选手比赛的项目必定有边相连（不能同时比赛）姓名项目1项目2项目3丁一 A B E马二 C D 张三 C E F李四 D F A王五 B F9丁一马二张三李四王五100M200M

4、标枪铅球跳高跳远10姓名项目1项目2项目3丁一 A B E马二 C D 张三 C E F李四 D F A王五 B F比赛时间比赛项目1A，C2B，D3E4FBAEFDC 只需安排四个单位时间进行比赛11&求解非数值计算的问题：求解非数值计算的问题： 主要考虑的是设计出合适的数据结构及相应的算法。 即：首先要考虑对相关的各种信息如何表示、对相关的各种信息如何表示、组织和存储组织和存储 因此，可以认为：数据结构是一门研究非数值数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。它们之间的关系和操作的学科。12&数据结构

5、课程的形成和发展：数据结构课程的形成和发展： 形成阶段：形成阶段： 60年代初期，“数据结构”有关的内容散见于操作系统、编译原理和表处理语言等课程。1968年，“数据结构”被列入美国一些大学计算机科学系的教学计划。 发展阶段：发展阶段： 数据结构的概念不断扩充，包括了网络、集合代数论、关系等“离散数学结构”的内容。1370年代后期，我国高校陆续开设该课程。 数据结构课程数据结构课程所处的地位：所处的地位：14&数据结构的几个相关概念：数据结构的几个相关概念：数据(Data):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素(Data Ele

6、ment):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。数据对象(Data Object)：是性质相同的数据元素的集合。是数据的一个子集。15数据类型：在一种程序设计语言中，变量所具有的数据种类。例1、 在FORTRAN语言中，变量的数据类型有整型、实型、和复数型 例2、在C语言中数据类型：基本类型和构造类型基本类型：整型、浮点型、字符型构造类型：数组、结构、联合、指针、枚举型、自定义16&什么是数据结构？什么是数据结构？&定义定义1-是相互之间存在一种或多种特定关系的数据元素的集合。&定义定义2- 按某种

7、按某种逻辑逻辑关系关系组织起来的一批数据（或称带结构的数据元素的集合）应用计算机语言并按一定的按一定的存储存储表示方式表示方式把它们存储在计算机的存储器中，并在其上定义了一个在其上定义了一个运算运算的的集合。集合。17&数据结构的三个方面的含义：数据结构的三个方面的含义：&逻辑结构逻辑结构- 数据元素间抽象化的相互关系（简称为数据结构）。 与数据的存储无关，独立于计算机，它是从具体问题抽象出来的数学模型。&存储结构（物理结构）存储结构（物理结构）- 数据元素及其关系在计算机存储器中的存储方式。 是逻辑结构用计算机语言的实现，它依赖于计算机语言。&运算（算法）运算（算法）18&数据结构的三个方面

8、的含义之：数据结构的三个方面的含义之：&逻辑结构逻辑结构-划分方法一划分方法一 （1）线性结构线性结构- 有且仅有一个开始和一个终端结点，并且所有结点都最多只有一个直接前趋和一个后继。 例如：线性表、栈、队列、串 （2）非线性结构非线性结构- 一个结点可能有多个直接前趋和直接后继。 例如：树、图、多维数组、广义表等。19&逻辑结构逻辑结构-划分方法二划分方法二一、集合 结构中的数据元素除了同属于一种类型外，别无其它关系。二、线性结构 结构中的数据元素之间存在一对一的关系。数据之间存在前后顺序关系(每一个元素都有唯一的前驱和后继，第一个元素可以没有前驱,最后一个可以没有后继)三、树型结构 结构中

9、的数据元素之间存在一对多的关系。除一个特殊元素没有前驱外,其他每个元素都有惟一的前驱，其中无前驱的元素称为树根四、图状结构或网状结构 结构中的数据元素之间存在多对多的关系。任一数据元素均可有多个前驱和后继。20&数据结构的三个方面的含义之：数据结构的三个方面的含义之：&存储结构存储结构 存储结构两方面的内容：存储结构两方面的内容： （1）数据元素自身值的表示（数据域） （2）该结点与其它结点关系的域（链域） 四种基本的存储方法：四种基本的存储方法： （1）顺序存储方法顺序存储方法（结构） （2）链接存储方法链接存储方法（链式存储结构） （3）索引存储方法索引存储方法 （4）散列存储方法散列存储

10、方法 同一种逻辑结构可采用不同的存储方法（以上四种之一或组合），这主要考虑的是运算方便及算法的时空要求。21&逻辑结构、存储结构小结：逻辑结构、存储结构小结：（1）数据的逻辑结构、存储结构和数据的运算（算法）构成了数据结构三个方面的含义。（2）程序设计的实质是对实际问题选择一个好的数据结构，加之设计一个好的算法。而好的算法在很大程度上取决于描述实际问题的数据结构。22&数据结构的三个方面的含义之：数据结构的三个方面的含义之：& 算法算法 所谓算法（所谓算法（Algorithm) 是描述计算机解决给定问题的操作过程（解题方法），即为解决某一特定问题而由若干条指令组成的有穷有穷序列序列。23&算法

11、的概念和描述：算法的概念和描述： 一个算法必须满足以下五个准则：一个算法必须满足以下五个准则： （1）有穷性）有穷性-执行了有限条指令后一定要终止。 例1.3、例1.4 （2）确定性）确定性（无二义）- 算法的每一步操作都必须有确切定义，不得有任何歧义性。24 例1.3 一个不是算法 的例子 (1)begin (2)n=0 (3)n=n+1 (4)repeat (3) (5)end 例1.4 一个不超过100次计数的算法 (1)begin (2)n=0 (3)n=n+1 (4)if n=100 do (5),else repeat(3) (5)output n (6)end25 （3）可（能）

12、行性）可（能）行性- 算法的每一步操作都必须是可行的，即每步操作均能在有限时间内完成。 （4）输入数据）输入数据- 一个算法有n（n=0)个初始数据的输入。 （5）输出数据）输出数据- 一个算法有一个或多个与输入有某种关系的有效信息的输出。 思考：算法与程序有何区别？26 N.沃思（Niklaus Wirth)教授提出： 程序程序=算法算法+数据结构数据结构 以上公式说明了如下两个问题： （1）数据上的算法决定如何构造和组织数据（算法数据结构）。 （2）算法的选择依赖于作为基础的数据结构（数据结构算法）。 软件软件=程序程序+文档（软件工程的观点）文档（软件工程的观点）27算法与程序的区别 程

13、序中的指令必须是机器可执行的，而算法中的指令则无此限制 算法代表了对问题的求解过程，而程序则是算法在计算机上的实现。算法用特定的程序设计语言来描述，就成了程序 算法与数据结构是相辅相成的。28&算法的描述和实现算法的描述和实现 描述描述-可采用自然语言、数学语言或约定的符号语言。 实现实现-必须借助程序设计语言提供的数据类型及其运算。 本课的描述本课的描述-采用类C语言。29例：例： 假设8枚金币中有一枚是伪造的，真假金币的区别仅仅是重量不同，现只有一个没有砝码的天平做工具，则至少用3次比较即可找出这枚伪造的金币。要求用文字写出这三此比较的算法。 (提示：参考折半查找法即二分法) 【解答：】先

14、任选4枚金币，每边各2枚置于天平上，若天平平衡，则说明伪造的金币在另外4枚中，若不平衡，则说明伪造的金币在选择的4枚中，于是1次比较可以确定伪造的金币在哪4枚中；然后在含伪造的金币的4枚中，任选2枚金币，每边各1枚置于天平上，若天平平衡，则说明伪造的金币在另外2枚中，若不平衡，则说明伪造的金币在选择的2枚中，于是2次比较可以确定伪造的金币在哪2枚中；最后在含伪造的金币的2枚中，任选1枚金币与其他1枚真币置于天平上，若不平衡，则选择的这枚是伪造的，否则余下的1枚是伪造的。因此3次比较即可找出伪造的金币。30&算法的简单分析：算法的简单分析：&算法的评价准则算法的评价准则 （1）正确性 （2）可读

15、性）可读性 （3）键壮性）键壮性(鲁棒性鲁棒性) （4）执行算法所耗费的存储空间（主要考虑辅存空间；低存储低存储要求）。执行算法所耗费的时间（效率要高效率要高）。31附：附：程序正确性的四个层面：程序正确性的四个层面： （1）不含语法错误 （2）程序对于n组输入数据能够得出满足规格 说明要求的结果。 （3）程序对于精心选择的典型、边界性的n组输入数据能得出满足规格说明要求的结果。 （4）程序对于一切合适的输入数据都能得出满足规格说明要求的结果（穷举）。32&算法的简单分析之：算法的简单分析之： （1）算法效率的度量）算法效率的度量& 1. 程序运行所耗费的时间程序运行所耗费的时间(由下列因素决

16、定由下列因素决定)： 算法所选用的策略 问题的规模 :算法求解问题n的输入量（或初始数据量） 书写程序所采用的语言 编译程序所产生的机器代码的质量 机器执行指令的速度 一个算法耗费的时间一个算法耗费的时间=算法中每条语句的执行时间之和。算法中每条语句的执行时间之和。 若不考虑机器硬、软件因素，可以认为算法若不考虑机器硬、软件因素，可以认为算法“运行工作量运行工作量”的大小是问题规模的大小是问题规模n的函数的函数。 33& 2. 不考虑机器软硬件环境时算法的时间耗费：不考虑机器软硬件环境时算法的时间耗费： 设：执行每条语句所需时间为单位时间，则： 一个算法耗费的时间=所有语句的频度之和。 频度频

17、度-是指基本操作语句重复执行的次数。一个算法中所有语句的频度之和构成了该算法的运行时间 渐近时间复杂度（简称时间复杂度渐近时间复杂度（简称时间复杂度T(n)-） 即：时间耗费，它是算法求解问题n的函数。 记作：T(n)=O(f(n) 即当问题的规模n时的时间复杂度T(n)的数量级(阶) *评价一个算法的时间性能，主要标准是算法的渐近时评价一个算法的时间性能，主要标准是算法的渐近时间复杂度间复杂度34算法效率的度量：采用算法效率的度量：采用时间复杂度时间复杂度 例1.5 分析以下程序段的时间复杂度for (i=1;in;i+) y=y+1; for (j=0; j=(2*n); j+)x+; /

18、* 1 * /* 2 * /35分析：语句的频度指的是该语句重复执行的次数。一个算法中所有语句的频度之和构成了该算法的运行时间。语句1的频度是：n-1语句2的频度是：12) 12)(1(2nnnn则该程序段的时间复杂度：T(n)=)(2222nOn36例1.6 分析以下程序段的时间复杂度i=1;while (i=n) i=i*2语句1的频度是：1 设语句2的频度是f(n)，则有： 即 取最大值 则该程序段的时间复杂度为：/* 1 * /* 2 * /nnf)(2nnf2log)(nnf2log)()(loglog1)(1)(22nOnnfnT37 例1.7 x=1; for (i=1;i=n;

19、i+) for (j=1;j=i;j+) for (k=1;k=j;k+) x+; 由于内循环的执行次数虽与规模n无直接关系，但与外循环的变量取值有关。因此从内层向外层循环分析执行次数。38 niijniijjkjkniijjkjnTjjnT1111111111)()1(1 . 1111)(故相加个注共因为39niniijniijjkiij1111112/ ) 1(1所以niniijiij1112/)1(又因为402/ 2/ ) 1(6/ ) 12)(1()(2/12/ ) 1(:1121nnnnniiiininini又因为41 即: T(n)=n(n+1)(2n+1)/6+n(n+1)/2/

20、2 所以： T(n)=O(n3/6+低次项) 取T(n)的数量级阶，得则该程序段的时间复杂度为： T(n)=O(n3)42 & 常见函数的时间常见函数的时间复杂度按数量递增排复杂度按数量递增排列及增长率。列及增长率。 常数阶O(1) 对数阶O(log2n) 线性阶O(n) 线性对数阶O(nlog2n) 平方阶O(n2) 立方阶O(n3) k次方阶O(nk) 指数阶O(2n)43&算法的简单分析之：算法的简单分析之： （2）算法的存储空间）算法的存储空间 一个程序的空间复杂度是指程序运行从开一个程序的空间复杂度是指程序运行从开始到结束所需要的存储空间。类似于算法始到结束所需要的存储空间。类似于算

21、法的时间复杂度，记作：的时间复杂度，记作： S(n)=O(f(n)44 & 本章小结本章小结 数据、数据结构等基本概念数据、数据结构等基本概念 数据结构的三个方面的内容数据结构的三个方面的内容 线性和非线性结构的逻辑特征线性和非线性结构的逻辑特征 数据存储的四种基本方法数据存储的四种基本方法 算法、算法的时间复杂度及其分析的简算法、算法的时间复杂度及其分析的简易方法易方法45 顺序存储结构顺序存储结构：面向线性关系的存储方法，对于线性数据结构，可将其数据元素按相应的线性关系的前后次序，存放在物理存储器中，使得数据元素在此线性关系下的逻辑顺序与它们在存储器中的存放次序一致。 链式存储结构：链式存储结构：每个元素的存储区分为两部分：第一部分为数据区，存储元素的内容；第二部分为指针区，存放存放该元素与其他元素之间的关系信息，这种关系信息一般为地址。数据元素的存储区之间可以是连续的，也可以是不连续的。 索引存储结构：索引存储结构：主要针对集合和线性表，面向检索操作。主要是在数据结构的存储区（称数据区）外，增加一个或若干个索引区，索引区中的每个元素用于记录数据区中的一个或一组元素的存储位置。 散列存储结构：散列存储结构：是一种按元素内容存储元素的方法。主要是设置散列函数，规定元素内容到存储地址的映射，并通过散列函数进行存储和读取。