第1章 数据结构与算法

整理文档很辛苦,赏杯茶钱您下走!

免费阅读已结束,点击下载阅读编辑剩下 ...

阅读已结束,您可以下载文档离线阅读编辑

资源描述

第2页2020年1月21日数据结构是计算机及相关专业中一门重要的专业基础课程。当用计算机来解决实际问题时,就要涉及到数据的表示及数据的处理,而数据表示及数据处理正是数据结构课程的主要研究对象,通过这两方面内容的学习,为后续课程,特别是软件方面的课程打下厚实的知识基础,同时也提供了必要的技能训练。因此,数据结构课程在计算机应用专业中具有举足轻重的作用。第3页2020年1月21日课程任务在基础方面,要求学生掌握常用数据结构的基本概念及其不同的实现方法;在技能方面,通过系统学习能够在不同存储结构上实现不同的运算,并对算法设计的方式和技巧有所体会。学业基础本课程的先修课程为离散数学和高级语言程序设计。学习本课程必须具备高级语言程序设计(C语言)的基础知识与基本技能。它的后续课程有操作系统和数据库原理等。第4页2020年1月21日⒈教学内容:(1)数据结构的概念;(2)抽象数据类型;(3)算法和算法分析。⒉教学目的:(1)领会数据、数据元素和数据项的概念及其相互间的关系;(2)清楚数据结构的逻辑结构、存储结构的联系与区别;(3)理解抽象数据类型的概念;(4)掌握进行简单算法分析的方法。第1章数据结构与算法第5页2020年1月21日⒊教学重点:⑴数据、数据项、数据元素、数据结构的概念;⑵逻辑结构和数据结构在概念上的联系与区别;⑶抽象数据类型和数据抽象;⑷评价算法优劣的标准及方法。⒋教学难点:⑴区别算法与程序;⑵逻辑结构、存储结构的联系与区别;⑶抽象数据类型与数据抽象;⑷算法的时间复杂度分析。第6页2020年1月21日1.1.1为什么要学习数据结构在计算机发展的初期,人们使用计算机的目的主要是处理数值计算问题。由于当时所涉及的运算对象是简单的整型、实型或布尔类型数据,所以程序设计者的主要精力是集中于程序设计的技巧上,而无须重视数据结构。随着计算机应用领域的扩大和软、硬件的发展,非数值计算问题越来越显得重要。这类问题涉及到的数据结构更为复杂,数据元素之间的相互关系一般无法用数学方程式加以描述。解决这类问题的关键是要设计出合适的数据结构,才能有效地解决问题。1.1引言第7页2020年1月21日【例1-1】成绩检索系统。要求成绩检索系统提供自动查询的功能,如查找某个学生的单科成绩或平均成绩,查询某门课程的最高分等等。学号姓名考试成绩平均成绩高等数学C语言英语20071801吴承志9095859020071802李淑芳8876918520071803刘丽9278828420071804张会友8178727720071805石宝国7682797920071806何文颖8690918920071807赵胜利7678807820071808崔文靖8293868720071809刘丽80858182………………图1-1学生成绩表第8页【例1-2】棋盘布局问题。要求将4个棋子布在4行4列的棋盘上,使得任两个棋子既不在同一行或同一列,也不在同一对角线上。第9页2020年1月21日【例1-3】教学计划编排问题一个教学计划包含许多课程,在教学计划包含的许多课程之间,有些必须按规定的先后次序进行,有些则没有次序要求。即有些课程之间有先修和后续的关系,有些课程可以任意安排次序。这种各个课程之间的次序关系可用一个称作图的数据结构来表示,如图所示。有向图中的每个顶点表示一门课程,如果从顶点vi到vj之间存在有向边vi,vj,则表示课程i必须先于课程j进行。第10页2020年1月21日由以上三个例子可见,描述这类非数值计算问题的数学模型不再是数学方程,而是诸如表、树、图之类的数据结构。因此,可以说数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。第11页2020年1月21日1、数据结构课程的发展数据结构作为一门独立的课程在国外是从1968年才开始的,但在此之前其有关内容已散见于编译原理及操作系统之中。从20世纪60年代末到70年代初,出现了大型程序,软件也相对独立,结构程序设计成为程序设计方法学的主要内容,人们越来越重视数据结构。从70年代中期到80年代,各版本的数据结构著作相继出现。1.1.2数据结构课程的内容第12页2020年1月21日数据结构课程集中讨论软件开发过程中的设计阶段、同时涉及编码和分析阶段的若干基本问题。此外,为了构造出好的数据结构及其实现,还需考虑数据结构及其实现的评价与选择。因此,数据结构的内容包括三个层次的五个“要素”。2、数据结构课程的内容第13页2020年1月21日1.2.1有关概念和术语1、数据数据是信息的载体,是所有能够被计算机识别、存储和加工处理的符号的总称。2、数据项数据项(DataItem)是具有独立含义的标识单位,是数据不可分割的最小单位。3、数据元素数据元素(DataElement)是数据的基本单位。4、数据对象数据对象(DataObject)或数据元素类(DataElementClass)是具有相同性质的数据元素的集合。1.2数据结构的概念第14页2020年1月21日4、数据结构数据结构(DataStructure)是指互相之间存在着一种或多种关系的数据元素的集合。在任何问题中,数据元素之间都不会是孤立的,在它们之间都存在着这样或那样的关系,这种数据元素之间的关系称为结构。根据数据元素间关系的不同特性,通常有下列四类基本的结构:⑴集合结构。⑵线性结构。⑶树结构。⑷图结构。第15页2020年1月21日(a)集合结构(b)线性结构(c)树结构(d)图结构四类基本结构的示意图下图为表示上述四类基本结构的示意图。第16页2020年1月21日(1)逻辑层次的数据结构有两个要素。一个是数据元素的集合,另一个是关系的集合。形式上,数据结构可以采用一个二元组来表示:Data_Structure=(D,R)其中,D是数据元素的有限集,R是D上关系的有限集。(2)应用层次的数据结构包括数据的逻辑结构和数据的物理结构。数据的逻辑结构可以看作是从具体问题抽象出来的数学模型,它与数据的存储无关。数据结构在计算机中的标识称为数据的物理结构,或称存储结构。第17页2020年1月21日1.2.2抽象数据类型1、数据类型数据类型是一个值的集合和定义在这个值集上的一组操作的总称。2、抽象数据类型抽象数据类型(AbstructDataType,简称ADT)是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义取决于它的一组逻辑特性,而与其在计算机内部如何表示和实现无关。即不论其内部结构如何变化,只要它的数学特性不变,都不影响其外部的使用。第18页2020年1月21日1.3.1数据结构的C语言描述根据数据结构的概念,在计算机中表示用户自定义的数据结构,实现数据结构上的操作及应用,需要描述三方面的内容:数据对象的类型、数据对象的关系和对数据对象的操作。C语言不是面向对象的程序设计语言,因此不具有将数据结构三方面的内容封装的功能,必须分别描述。1.3数据结构的描述方法第19页2020年1月21日数据对象的联系数据对象的关系体现了数据的逻辑结构,可以采用顺序存储表示,也可以采用链式存储表示。一般顺序存储采用数组类型表示,链式存储采用指针类型表示。数据对象的操作数据对象的操作在C语言中被描述为独立的函数。第20页2020年1月21日1.3.2数据结构的C++描述C++是对C语言的改进和扩充,以C为基础,包含了整个C,具备C的全部特性、属性和优点,同时添加了对面向对象编程的完全支持。因此采用C++描述数据结构,可以仍采用和C描述一样的方式,也可以采用面向对象的方式描述。数据对象的联系对数据对象的关系和数据对象的操作的描述也是通过定义类的形式,将对数据对象关系的存储与对数据对象操作的定义封装到一个类中,数据对象的关系通过类的私有数据描述体现。数据对象的操作被描述成类的成员函数,较好地保证了数据结构的抽象和独立第21页2020年1月21日1.3.3数据结构的Java描述Java语言的数据类型分为两大类:基本数据类型和引用数据类型。其中,基本数据类型有八种,即四种整型类型、两种浮点类型、一种字符类型和一种布尔类型。没有前面在C语言、C++中描述数据结构时用到的结构体类型和指针类型。在Java语言中类似C++,仍然采用类定义数据对象,并将对数据对象的关系的存储描述与数据对象的操作封装到类的定义中,主要不同的是使用引用类型代替指针类型。不用指针类型描述数据结构,使得数据结构的描述中没有了与地址相关的运算*和&,更易于对数据结构的理解。第22页2020年1月21日数据对象的类型classDataType{public:[数据成员列表]}数据对象的联系,数据对象的关系体现了数据的逻辑结构,可以采用顺序存储表示,也可以采用链式存储表示。一般顺序存储采用数组类型表示,链式存储采用指针类型表示。例如,顺序存放a1,a2,…,an的存储定义为:classSeqList{privateDataType[]data;privateintlast;[成员函数]}第23页2020年1月21日1.4.1算法及其特性算法(Algorithm)是对特定问题求解步骤的一种描述,是指令的有限序列。其中每一条指令表示一个或多个操作。一个算法应该具有下列特性:⑴有穷性。⑵确定性。⑶可行性。⑷输入。⑸输出。1.4算法第24页2020年1月21日算法与数据结构是相辅相承的。解决某一特定类型问题的算法可以选定不同的数据结构,而且选择恰当与否直接影响算法的效率。反之,一种数据结构的优劣由各种算法的执行来体现。要设计一个好的算法通常要考虑以下的要求。⑴正确。⑵可读。⑶健壮。⑷高效。第25页2020年1月21日1.4.2算法描述算法可以使用各种不同的方法来描述。自然语言:程序流程图、N-S图等算法描述工具:直接使用某种程序设计语言:用伪码语言的描述方法:第26页2020年1月21日1.4.3算法的性能分析时间复杂度、空间复杂度:也成为时间性能和空间性能,是对某个算法的时间效率和空间效率的度量。时间复杂度将一个算法转换成程序并在计算机上执行时,其运行所需要的时间取决于下列因素:⑴硬件的速度。⑵书写程序的语言。⑶编译程序所生成目标代码的质量。⑷问题的规模。第27页2020年1月21日时间复杂度:一个算法的时间复杂度(TimeComplexity)就是指算法的时间耗费,这里用T(n)表示。一个算法执行所耗费的时间,是算法中所有语句执行时间之和,而每条语句的执行时间是该语句执行一次所用时间与该语句重复执行次数的乘积。一个语句重复执行的次数称为语句的频度(FrequencyCount)。算法的时间复杂度T(n)表示为:其中ti表示语句i执行一次的时间,ci表示语句i的频度。假设每条语句执行一次的时间均为一个单位时间,那么算法的时间耗费可简单表示为各语句的频度之和:ii()tciTn语句()i()ciTn语句第28页2020年1月21日【例1-5】下面的程序段用来求两个n阶方阵A和B的乘积C。for(i=0;in;i++)/*n+1*/for(j=0;jn;j++)/*n(n+1)*/{C[i][j]=0;/*n2*/for(k=0;kn;k++)/*n2(n+1)*/C[i][j]+=A[i][k]*B[k][j];/*n3*/}右边列出了各语句的频度,因而算法的时间复杂度T(n)为:T(n)=(n+1)+n(n+1)+n2+n2(n+1)+n3=2n3+3n2+2n+1可见,T(n)是矩阵阶数n的函数。第29页2020年1月21日【例1-6】冒泡排序。voidBublleSort(inta[],intn){for(i=0;in-1&&swap;i++){swap=0;for(j=0;jn-i;j++)if(a[j]a[j+1]){a[j]a[j+1];swap=1;}}}选择交换相邻的两个元素“a[j]a[j+1];”作为基本操作。而n个元素组成的输入集可能有n!中排列情况,若各种情况等概率,则冒泡排序的平均时间复杂

1 / 31
下载文档,编辑使用

©2015-2020 m.777doc.com 三七文档.

备案号:鲁ICP备2024069028号-1 客服联系 QQ:2149211541

×
保存成功