第一章数据结构概述.ppt

《第一章数据结构概述.ppt》由会员分享，可在线阅读，更多相关《第一章数据结构概述.ppt（37页珍藏版）》请在三一文库上搜索。

1、数据结构,谢陆宁 67703850,成绩如何评定？,平时成绩：40% 考勤：10% 作业：30% 期末考试：60%,教材和参考书,黄国瑜，数据结构（C语言版），清华大学出版社 严蔚敏，数据结构，清华大学出版社 张瑞军，数据结构（C语言描述），清华大学出版社 数据结构基础（C语言版)，美 Ellis Horowitz，清华大学出版社,第一章 数据结构的基本概念,1.1 何谓数据结构 1.2 算法 1.3 程序结构化设计风格 1.4 程序分析的方法 1.5 时间复杂度分析 1.6 渐进式表示法,1.1 数据结构,计算机解决问题的步骤： 分析问题，建立数学模型：界定问题的输入输出边界，抽取问题的实

2、质，对问题进行抽象，形成相应的数学模型。 确定数据结构：设计合适的数据结构对解决问题所需的数据及数据之间的关系进行存储，描述出其相应的逻辑结构及存储结构。 算法设计：根据问题要求和数据结构的特点来选择和设计算法，同时要考虑算法的效率和占用内存空间。 编程实现,1.1 数据结构,例子：新生入学注册 学号的编码规则。采用入学年份+学院编号+专业编号+流水号的编码方式,1.1 数据结构,确定数据结构。设计适当的数据格式来存储和表达这些信息 算法设计。主要涉及学生信息的增加、删除、修改、查询等操作 程序设计,1.1 数据结构,数据结构这门学科主要完成以下工作： 数据集合中个数据元素之间的逻辑关系，即数

3、据的逻辑结构 在对数据集合进行访问和处理时，个数据元素在计算机物理介质中的实际存储，即数据的物理结构 对数据集合中个数据元素的各种运算,1.1 数据结构,数据：对客观事物的符号表示，它描述客观事物的数值、字符等所有输入到计算机中并能被计算机所接受和处理的符号的集合 数据类型：程序语言中变量所能表示并存储的数据种类 在C语言中 数据类型：基本类型和构造类型 基本类型：整型、浮点型、字符型 构造类型：数组、结构、联合、指针、枚举型、自定义,1.1 数据结构,数据对象（数据实体）：是性质相同的数据元素的集合。是数据的一个子集。 整数的数据对象是-3，-2，-1，0，1，2，3， 英文字符类型的数据对

4、象是A，B，C，D，E，F， 数据结构：数据实体中元素之间的关系，包括数据的表示法（逻辑结构和存储结构）和运算 数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。,1.1 数据结构,数据的逻辑结构和物理结构 数据之间的相互关系称为逻辑结构。通常分为四类基本结构： 一、集合：结构中的数据元素除了同属于一种类型外，别无其它关系。 二、线性结构：结构中的数据元素之间存在一对一的关系。 三、树状结构：结构中的数据元素之间存在一对多的关系。 四、图状结构或网状结构：结构中的数据元素之间存在多对多的关系。 数据结构在计算机中的表示称为数据的物

5、理结构，又称为存储结构。,1.2 算法,数据结构与算法是有紧密联系的。对于某一问题，如果使用计算机求解，其本质上是对某一种或几种数据结构施加一些运算。 程序=数据结构+算法 算法是对特定问题求解步骤的一种描述，算法是指令的有限序列，其中每一条指令表示一个或多个操作。,1.2 算法,算法是指为了完成某项特定工作所设计出的一连串用来说明工作是如何被完成的步骤。 算法必须满足下列几个条件： 输入：有零个或多个输入数据 输出：具有一个以上的结果输出 定义明确：每一个步骤的语句必须很明确，不允许有二义性 有限性：对所有情形都能在执行有限步之后结束 有效性：每一个步骤必须是基本的、可执行的（feasibl

6、e）指令（即使是用纸和笔也可以完成计算）,1.2 算法,用来写算法的方式： 条列式的步骤 流程图：以图形符号来描述解决问题的方法。 伪码：以夹杂程序语法和自然语言的形式来描述解决问题的方法。 程序语句,1.2 算法,算法设计的要求 正确性：算法应满足具体问题的需求，对任何合法的输入，算法都能给出正确的输出。 可读性：算法应该好读。以有利于阅读者对程序的理解。 健状性：算法应具有容错处理。当输入非法数据时，算法能适当的作出反应，并做相应的异常处理，而不是产生莫名其妙的输出结果。 效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有

7、关。,1.3 程序结构化与设计风格,程序设计是设计和编制程序的全过程。程序，设计发展的历史,可以分为三个不同的时期： 20世纪50年代，程序都是用指令代码或汇编语言来编写的。评论程序好坏的标准是能否做到指令条数少，存储单元省，执行速度快。 20世纪60年代，高级语言蓬勃发展，出现了一系列不同风格、为不同对象服务的程序设计语言。但程序设计方法并无实质性进展。 20世纪70年代，程序设计观念发生重大改变。这一时期，出现了大型软件系统，如操作系统、数据库系统等，带来了“软件危机”。传统的程序设计观念只注重效率，忽略了程序结构和清晰度，软件的可靠性、可读性、可维护性都相当差。,1.3 程序结构化与设计

8、风格,程序结构化：结构化程序设计由迪克斯特拉(E.W.dijkstra)在1969年提出，是以模块化设计为中心，将待开发的软件系统划分为若干个相互独立的模块，这样使完成每一个模块的工作变单纯而明确，为设计一些较大的软件打下了良好的基础。 模块化：将原来的大问题区分成几个小问题，再从解决小问题的过程中，组合成大问题的解法。 由于模块相互独立，因此在设计其中一个模块时，不会受到其它模块的牵连，因而可将原来较为复杂的问题化简为一系列简单模块的设计。模块的独立性还为扩充已有的系统、建立新系统带来了不少的方便，因为我们可以充分利用现有的模块作积木式的扩展。,1.3 程序结构化与设计风格,结构化程序设计主

9、要包括两个方面： 在程序设计过程中，提倡采用自顶向下，逐步求精的模块化程序设计原则。 在程序设计过程中，强调采用单入口单出口的三种基本控制结构（顺序结构、选择结构和循环结构），避免使用GOTO语句。 用结构程序设计方法编出的程序不仅结构良好、易读易写，而且易于证明其正确性。结构程序设计方法的推行，其意义远不止它的实用价值，而在于它向人们揭示了研究程序设计方法的必要性。,1.3 程序结构化与设计风格,自顶向下设计(逐步分解方法 )：将大模块分成更小的模块，解决小模块以组合出大模块的解法。一种逐步求精的设计程序的过程和方法。对要完成的任务进行分解，先对最高层次中的问题进行定义、设计、编程和测试。这

10、样逐层、逐个地进行定义、设计、编程和测试，直到所有层次上的问题均由实用程序来解决，就能设计出具有层次结构的程序。 按自顶向下的方法设计时,设计师首先对所设计的系统要有一个全面的理解.然后从顶层开始,连续地逐层向下分解,起到系统的所有模块都小到便于掌握为止,1.3 程序结构化与设计风格,结构化程序设计方法存在的问题： 结构化程序设计主要是面向过程的。“面向过程”是一种以事件为中心的编程思想。就是分析出解决问题所需要的步骤，然后用函数把这些步骤一步一步实现，使用的时候一个一个依次调用就可以了。 程序可重用性差 结构化程序设计方法不具备建立“软件部件”的工具，即使是面对老问题，数据类型的变化或处理方

11、法的改变都必将导致重新设计。这种额外开销与可重用性相左，称为“重复投入”。 程序模块和数据结构是松散的耦合在一起的。在大型多文件软件系统中，随着数据量的增大，由于数据与数据处理相对独立，程序变得越来越难以理解，文件之间的数据沟通也变得困难。,1.3 程序结构化与设计风格,20世纪80年代提出了面向对象的程序设计方法。该方法不是将问题分解为过程，而是分解为对象。对象是现实世界中可以独立存在、可以区分的实体，也可以是一些概念上的试题，现实世界是由众多对象组成。对象有自己的数据（属性）和作用于数据的操作（方法），将属性与方法封装成一个整体，供程序设计者使用。对象之间的相互作用通过消息传递来实现。,1

12、.3 程序结构化与设计风格,自底向上设计(逐步归纳法 )：一种设计程序的过程和方法。在设计具有层次结构的大型程序时，先设计一些较下层的程序，即去解决问题的各个不同的小部分，然后把这些部分组合成为完整的程序。,1.3 程序结构化与设计风格,编写风格 注释 变量命名 程序缩排 段落,1.4 程序分析的方法,程序运行效率：时间、空间 程序效率分析：事前预测、事后测试 事前预测：程序未运行前，依程序可能使用的空间与时间来评价其效率 事后测试：收集此算法的执行时间和实际占用空间的统计资料。 衡量一个指令执行的时间t取决于以下几个方面： 机器的速度 指令集 指令周期：指令集中每一个指令所需要的运行时间 编

13、译器：不同的编译器所编译出的机器语言不相同,1.4 程序分析的方法,为了能以相同的标准来进行程序效率的分析，我们常常以执行次数（Frequency counter, 语句频度）来作为程序效率分析的方式。 执行次数（语句频度）：指某一语句在算法中重复执行的次数。,1.4 程序分析的方法,执行次数实例： 例1： x=x+1; 例2： for (i=0; in; i+) x=x+1; 例3： for (i=0; in; i+) for (j=0; jn; j+) x=x+1;,1.5 时间复杂度分析,算法运行所需要的时间资源的量是时间复杂度（也称为算法的效率）。影响算法运行时间的因素很多，主要有：计

14、算机系统的性能、问题规模、输入数据、算法本身等。显然，对于同一个算法，用不同的语言实现，或用不同的编译程序编译，或在不同的计算机上运行，算法的效率都是不同的。这表明用绝对时间单位的概念来衡量算法的效率是不合适的。 时间复杂度：基本操作重复执行的次数,1.5 时间复杂度分析,时间复杂度依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数f(n)。 从算法中选取一种所研究的问题的基本操作，以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则。这个基本操作多数情况下是最深层次循环内的语句中的基本操作。,程序实例：设计一个顺序查找的程序 int seq_search(int ke

15、y) int i; for(i=0;i20;i+) printf(“%d“,datai); if(key=datai) return 1; counter+; return 0; ,1.6 渐进式表示法,算出语句执行次数的精确值是非常困难的。由于执行次数概念本身的不精确性，花费大量精力计算其精确值，实际上并无可取之处。由于执行次数意义的不精确，即使使用其精确值作比较，结论也不准确，因此没有多大用处。只有在执行次数相差很大时，相比才有意义。,O( )表示法,定义： 对f(n)和g(n)，存在正常量c和 ， 使当 时，满足 则称： f(n)=O(g(n)。也就是g(n)是f(n)复杂度的渐进紧密上

16、限。 称g(n)是算法的渐进时间复杂度，简称为时间复杂度。 例1：3n+2=O(n) 对所有的n=2，有3n+2=5，有10n2+4n+2 =11n2,例3：2n+n2=O(2n) 当n=4时，n2 =2n 2n+n2 =2*2n 定理：如果f(n)=amnm+a1n+ a0 那么f(n)=O(nm),O(1)：常数阶 O(n)：线性阶 O(n2)：平方阶 O(n3)：立方阶 O(logn)：对数阶 O(2n)：指数阶 O(logn) O(n) O(n2) O(n3) O(2n),分析以下程序段的时间复杂度： 例1： for(i=1;im;i+) a=a+1; for(j=1;j3*m;j+)

17、 b=b*2; ,例2： i=1; while(i=n) i=i*3;,平均时间复杂度,算法的时间复杂度除了与问题规模n有关外，有时还因特定的输入数据集不同而不同。例如，在一个长度为n的一维数组中按顺序查找某个数x。如果第一个数正好是该数x，则只需查找一次，其时间复杂度为O(1)，把这种情况下的时间复杂度称为最优时间复杂度B(n)；如果最后一个是数x或不存在该数，则需查找n次，其时间复杂度为O(n)，把这种情况下的时间复杂度称为最坏时间复杂度W(n)。多数情况下则考虑所有可能输入数据集的期望值，由此得到的时间复杂度成为平均时间复杂度A(n)。,作 业,一、复习（是非、选择） 1，2，3，4，5，6，7，8，10 二、应用 1，2，5,