《第一章数据结构概述》由会员分享，可在线阅读，更多相关《第一章数据结构概述（37页珍藏版）》请在金锄头文库上搜索。
1、数据结构谢陆宁67703850成绩如何评定？n平时成绩：40%n考勤：10%n作业：30%n期末考试：60%教材和参考书教材和参考书n黄国瑜，数据结构（C语言版），清华大学出版社n严蔚敏，数据结构，清华大学出版社n张瑞军，数据结构（C语言描述），清华大学出版社n数据结构基础（C语言版)，美EllisHorowitz，清华大学出版社第一章第一章 数据结构的基本概念数据结构的基本概念n1.1何谓数据结构n1.2算法n1.3程序结构化设计风格n1.4程序分析的方法n1.5时间复杂度分析n1.6渐进式表示法1.1数据结构n计算机解决问题的步骤：n分析问题，建立数学模型：界定问题的输入输出边界，抽取问题
2、的实质，对问题进行抽象，形成相应的数学模型。n确定数据结构：设计合适的数据结构对解决问题所需的数据及数据之间的关系进行存储，描述出其相应的逻辑结构及存储结构。n算法设计：根据问题要求和数据结构的特点来选择和设计算法，同时要考虑算法的效率和占用内存空间。n编程实现1.1数据结构n例子：新生入学注册n学号的编码规则。采用入学年份+学院编号+专业编号+流水号的编码方式学号学号姓名姓名学院编号学院编号专业编号专业编号性别性别出生年月出生年月200805165001200805165001赵飞霞赵飞霞5 5165165女女1988.51988.5学院编号学院编号学院名称学院名称5 5管理学院管理学院专业
3、编号专业编号专业名称专业名称165165财务管理财务管理1.1数据结构n确定数据结构。设计适当的数据格式来存储和表达这些信息n算法设计。主要涉及学生信息的增加、删除、修改、查询等操作n程序设计1.1数据结构n数据结构这门学科主要完成以下工作：n数据集合中个数据元素之间的逻辑关系，即数据的逻辑结构n在对数据集合进行访问和处理时，个数据元素在计算机物理介质中的实际存储，即数据的物理结构n对数据集合中个数据元素的各种运算1.1数据结构数据结构n数据：对客观事物的符号表示，它描述客观事物的数值、字符等所有输入到计算机中并能被计算机所接受和处理的符号的集合n数据类型：程序语言中变量所能表示并存储的数据种
4、类在C语言中数据类型：基本类型和构造类型基本类型：整型、浮点型、字符型构造类型：数组、结构、联合、指针、枚举型、自定义1.1数据结构数据结构n数据对象（数据实体）：是性质相同的数据元素的集合。是数据的一个子集。整数的数据对象是-3，-2，-1，0，1，2，3，英文字符类型的数据对象是A，B，C，D，E，F，n数据结构：数据实体中元素之间的关系，包括数据的表示法（逻辑结构和存储结构）和运算n数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。1.1数据结构数据结构n数据的逻辑结构和物理结构n数据之间的相互关系称为逻辑结构。通常分为四类
5、基本结构：n一、集合：结构中的数据元素除了同属于一种类型外，别无其它关系。n二、线性结构：结构中的数据元素之间存在一对一的关系。n三、树状结构：结构中的数据元素之间存在一对多的关系。n四、图状结构或网状结构：结构中的数据元素之间存在多对多的关系。n数据结构在计算机中的表示称为数据的物理结构，又称为存储结构。1.2算法n数据结构与算法是有紧密联系的。对于某一问题，如果使用计算机求解，其本质上是对某一种或几种数据结构施加一些运算。n程序=数据结构+算法n算法是对特定问题求解步骤的一种描述，算法是指令的有限序列，其中每一条指令表示一个或多个操作。1.2算法n算法是指为了完成某项特定工作所设计出的一连
6、串用来说明工作是如何被完成的步骤。n算法必须满足下列几个条件：n输入：有零个或多个输入数据n输出：具有一个以上的结果输出n定义明确：每一个步骤的语句必须很明确，不允许有二义性n有限性：对所有情形都能在执行有限步之后结束n有效性：每一个步骤必须是基本的、可执行的（feasible）指令（即使是用纸和笔也可以完成计算）1.2算法n用来写算法的方式：n条列式的步骤n流程图：以图形符号来描述解决问题的方法。n伪码：以夹杂程序语法和自然语言的形式来描述解决问题的方法。n程序语句1.2算法n算法设计的要求n正确性：算法应满足具体问题的需求，对任何合法的输入，算法都能给出正确的输出。n可读性：算法应该好读。
7、以有利于阅读者对程序的理解。n健状性：算法应具有容错处理。当输入非法数据时，算法能适当的作出反应，并做相应的异常处理，而不是产生莫名其妙的输出结果。n效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有关。1.3程序结构化与设计风格n程序设计是设计和编制程序的全过程。程序，设计发展的历史,可以分为三个不同的时期：n20世纪50年代，程序都是用指令代码或汇编语言来编写的。评论程序好坏的标准是能否做到指令条数少，存储单元省，执行速度快。n20世纪60年代，高级语言蓬勃发展，出现了一系列不同风格、为不同对象服务的程序设计语言。但程序设
8、计方法并无实质性进展。n20世纪70年代，程序设计观念发生重大改变。这一时期，出现了大型软件系统，如操作系统、数据库系统等，带来了“软件危机”。传统的程序设计观念只注重效率，忽略了程序结构和清晰度，软件的可靠性、可读性、可维护性都相当差。1.3程序结构化与设计风格n程序结构化：结构化程序设计由迪克斯特拉结构化程序设计由迪克斯特拉(E.W.dijkstra)在在1969年提出，是以模块化设计为中年提出，是以模块化设计为中心，将待开发的软件系统划分为若干个相互独立的模心，将待开发的软件系统划分为若干个相互独立的模块，这样使完成每一个模块的工作变单纯而明确，为块，这样使完成每一个模块的工作变单纯而明
9、确，为设计一些较大的软件打下了良好的基础。设计一些较大的软件打下了良好的基础。n模块化：将原来的大问题区分成几个小问题，再从解决小问题的过程中，组合成大问题的解法。n由于模块相互独立，因此在设计其中一个模块时，不由于模块相互独立，因此在设计其中一个模块时，不会受到其它模块的牵连，因而可将原来较为复杂的问会受到其它模块的牵连，因而可将原来较为复杂的问题化简为一系列简单模块的设计。模块的独立性还为题化简为一系列简单模块的设计。模块的独立性还为扩充已有的系统、建立新系统带来了不少的方便，因扩充已有的系统、建立新系统带来了不少的方便，因为我们可以充分利用现有的模块作积木式的扩展。为我们可以充分利用现有
10、的模块作积木式的扩展。1.3程序结构化与设计风格n结构化程序设计主要包括两个方面：n在程序设计过程中，提倡采用自顶向下，逐步求精的模块化程序设计原则。n在程序设计过程中，强调采用单入口单出口的三种基本控制结构（顺序结构、选择结构和循环结构），避免使用GOTO语句。n用结构程序设计方法编出的程序不仅结构良好、易读易写，而且易于证明其正确性。结构程序设计方法的推行，其意义远不止它的实用价值，而在于它向人们揭示了研究程序设计方法的必要性。1.3程序结构化与设计风格n自顶向下设计(逐步分解方法)：将大模块分成更小的模块，解决小模块以组合出大模块的解法。一种逐步求精的设计程序的过程和方法。对要完成的任务
11、进行分解，先对最高层次中的问题进行定义、设计、编程和测试。这样逐层、逐个地进行定义、设计、编程和测试，直到所有层次上的问题均由实用程序来解决，就能设计出具有层次结构的程序。n按自顶向下的方法设计时,设计师首先对所设计的系统要有一个全面的理解.然后从顶层开始,连续地逐层向下分解,起到系统的所有模块都小到便于掌握为止1.3程序结构化与设计风格n结构化程序设计方法存在的问题：n结构化程序设计主要是面向过程的。“面向过程”是一种以事件为中心的编程思想。就是分析出解决问题所需要的步骤，然后用函数把这些步骤一步一步实现，使用的时候一个一个依次调用就可以了。n程序可重用性差程序可重用性差结构化程序设计方法不
12、具备建立“软件部件”的工具，即使是面对老问题，数据类型的变化或处理方法的改变都必将导致重新设计。这种额外开销与可重用性相左，称为“重复投入”。n程序模块和数据结构是松散的耦合在一起的。在大型多文件软件系统中，随着数据量的增大，由于数据与数据处理相对独立，程序变得越来越难以理解，文件之间的数据沟通也变得困难。1.3程序结构化与设计风格n20世纪80年代提出了面向对象的程序设计方法。该方法不是将问题分解为过程，而是分解为对象。对象是现实世界中可以独立存在、可以区分的实体，也可以是一些概念上的试题，现实世界是由众多对象组成。对象有自己的数据（属性）和作用于数据的操作（方法），将属性与方法封装成一个整
13、体，供程序设计者使用。对象之间的相互作用通过消息传递来实现。1.3程序结构化与设计风格n自底向上设计(逐步归纳法)：一种设计程序的过程和方法。在设计具有层次结构的大型程序时，先设计一些较下层的程序，即去解决问题的各个不同的小部分，然后把这些部分组合成为完整的程序。1.3程序结构化与设计风格n编写风格n注释n变量命名n程序缩排n段落1.4程序分析的方法n程序运行效率：时间、空间n程序效率分析：事前预测、事后测试n事前预测：程序未运行前，依程序可能使用的空间与时间来评价其效率n事后测试：收集此算法的执行时间和实际占用空间的统计资料。n衡量一个指令执行的时间t取决于以下几个方面：n机器的速度n指令集
14、n指令周期：指令集中每一个指令所需要的运行时间n编译器：不同的编译器所编译出的机器语言不相同1.4程序分析的方法n为了能以相同的标准来进行程序效率的分析，我们常常以执行次数（Frequencycounter,语句频度）来作为程序效率分析的方式。n执行次数（语句频度）：指某一语句在算法中重复执行的次数。1.4程序分析的方法n执行次数实例：n例1：x=x+1;n例2：for(i=0;in;i+)x=x+1;n例3：for(i=0;in;i+)for(j=0;jn;j+)x=x+1;1.5时间复杂度分析n算法运行所需要的时间资源的量是时间复杂度（也称为算法的效率）。影响算法运行时间的因素很多，主要有
15、：计算机系统的性能、问题规模、输入数据、算法本身等。显然，对于同一个算法，用不同的语言实现，或用不同的编译程序编译，或在不同的计算机上运行，算法的效率都是不同的。这表明用绝对时间单位的概念来衡量算法的效率是不合适的。n时间复杂度：基本操作重复执行的次数1.5时间复杂度分析n时间复杂度依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数f(n)。n从算法中选取一种所研究的问题的基本操作，以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则。这个基本操作多数情况下是最深层次循环内的语句中的基本操作最深层次循环内的语句中的基本操作。n程序实例：设计一个顺序查找的程序nintse
16、q_search(intkey)nninti;nfor(i=0;i=2，有3n+2=5，有10n2+4n+2=4时，n2=2n2n+n2=2*2n定理：如果f(n)=amnm+a1n+a0那么f(n)=O(nm)nO(1)：常数阶nO(n)：线性阶nO(n2)：平方阶nO(n3)：立方阶nO(logn)：对数阶nO(2n)：指数阶O(logn)O(n)O(n2)O(n3)O(2n)n分析以下程序段的时间复杂度：n例1：for(i=1;im;i+)a=a+1;for(j=1;j3*m;j+)b=b*2;n例2：i=1;while(i=n)i=i*3;平均时间复杂度n算法的时间复杂度除了与问题规模n有关外，有时还因特定的输入数据集不同而不同。例如，在一个长度为n的一维数组中按顺序查找某个数x。如果第一个数正好是该数x，则只需查找一次，其时间复杂度为O(1)，把这种情况下的时间复杂度称为最优时间复杂度最优时间复杂度B(n)；如果最后一个是数x或不存在该数，则需查找n次，其时间复杂度为O(n)，把这种情况下的时间复杂度称为最坏时间复杂度最坏时间复杂度W(n)。多数情况下则考虑所有可能输入数据集的期望值，由此得到的时间复杂度成为平均平均时间复杂度时间复杂度A(n)。作业n一、复习（是非、选择）1，2，3，4，5，6，7，8，10n二、应用1，2，5
