资源描述
第一章绪论,1946年第一台计算机ENIAC问世。,计算机的应用:,数值计算；,用于控制、管理及数据处理等非数值计算的处理工作；,数值问题:,数学模型:c2=a2+b2,c=5,解决数值计算问题的核心:,建立适当的数学模型,期末考试成绩,非数值问题:,表,例2，对奕问题,计算机可以根据当前棋盘格局，来判断棋局发展的趋势。,对弈树,派生格局,例3，地图的着色问题,对地图上的每个区域涂一种颜色，要求用最少的颜色涂写地图且相邻的两个区域不能具有相同颜色。,图,按红、绿、蓝、黑的顺序，用最少的颜色染色,解决非数值计算问题的核心:,寻找适当的数据结构,数据结构最早出现在由美国计算机协会制定的教程68。(ACMscurriculum68),1.1数据结构的发展史,开始时，侧重介绍一些具有表格处理功能的系统；,稍后，加入图论问题（树、图）；,随后，被扩充到包括代数集合论、关系等方面；,随着数据量的不断增大，在数据结构理论中又增加了文件管理，特别是大型文件组织等内容，以及数据库系统管理。,数据结构的新发展,专业领域中特殊问题:多维图形结构,抽象数据类型思想:面向对象思想,数据结构,学习什么？,掌握什么？,领悟什么？,1.2基本概念和术语,数据:是对客观事物的符号表示，是所有能输入到计算机中并被计算机程序处理的符号的总称。,数据元素:数据的基本单位。,例，整数、书目中的记录、“对弈树”中的格局,例，一个整数、书目中的一条记录、“对弈树”中的一个格局,数据项:一个数据元素可由若干个数据项组成。,例，一条书目记录是由序号、书名、作者、分类等数据项组成,数据项是数据的不可分割的最小单位。,数据对象:是性质相同的数据元素的集合，是数据的子集。,例，整数对象、书目对象,数据结构:数据元素之间存在一种或多种关系的数据对象。,通常，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为结构。,集合:数据元素之间无关系,线性结构:数据元素之间一对一,树形结构:数据元素之间一对多,图状结构:数据元素之间多对多,例，线性结构中的前驱后继关系、树结构中的父子关系。,例，数据如何在计算机中存储，如何分配内存空间。,数据结构包含逻辑结构和存储结构,一个逻辑结构可能存在多个存储结构。,包括数据元素的表示和数据元素之间关系的表示,存储结构,数据元素的表示:通常用位串表示一个数据元素,例，用八位表示一个字符、三十二位表示一个整数,若数据元素由若干数据项组成，则用表示各个数据项的子位串连接而成的位串来表示。,问:在C语言中表示一个学生的基本信息(学号(60人)、性别(男女)、年龄(31岁)，用什么样的数据表示占用空间最少？,Structstudentunsignednum:6unsignedsex:1unsignedage:5,数据元素之间关系的计算机表示:,顺序存储结构:借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。,链式存储结构:借助指示元素存贮地址的指针表示数据元素之间的逻辑关系。,例，线性数据为3，5，7,数据类型=数据结构+操作,例，整型:整数的集合，定义在其上的操作包括(加、减、乘、除),按值的不同性质，数据类型可以分为两类,原子类型:值是不可分解的、非结构的。,例，基本语言类型(整型、实型、字符型),结构类型:值是由若干成分按某种结构组成的、可分解的。,例，数组、结构体、文件,例，线性表:记录的集合，定义在其上的操作包括(插入、删除),抽象数据类型,即数据类型，只是将数据结构(数据对象、数据关系)和对数据元素的操作封装在一起，构成一个抽象体。,其实例化为一个对象。,抽象数据类型人,数据元素:,大脑、嘴、耳朵、脖子、胳膊、手,数据关系:,有机体,数据操作:,组装(大脑、嘴)思考(大脑)交谈(嘴)听音乐(耳朵),一个抽象数据类型的模块通常应包含定义、表示和实现三部分。,数据对象的定义,数据关系的定义,基本操作的定义,例，抽象数据类型三元素组的定义,数据对象:D=e1,e2,e3|e1,e2,e3ElemSet,数据关系:R1=,基本操作:,抽象数据类型的表示与实现,表示:是指在计算机中的存储方式(顺序存储、链式存储)。,实现:是指各操作的执行过程(算法)。,实现依赖于表示。,例，抽象数据类型三元素组的表示和实现,typedefInt*Triplet；,T=(Int*)malloc(3*sizeof(Int)；,if(!T)exit(OVERFLOW)；,T0=v1；T1=v2；T2=v3；,returnOK；,引用型参数传递,1.4算法和算法分析,算法:是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。,一个算法通常具有五个重要特性:,有穷性有穷步结束,确定性唯一执行路径,可行性可以通过基本运算实现,输入零个或多个输入,输出一个或多个输出,if(x=5)y=1;elsey=2;,算法和数据结构是两个不可分割的统一体,程序=数据结构+算法,数据结构通过算法实现操作,算法依赖数据结构设计程序,算法设计的要求:,正确性能够正确反映需求(通过测试),可读性有助于理解、调试和维护,健壮性完备的异常和出错处理,高效性时间、空间的要求,算法效率的度量,事后的统计:通过计算机内部的计时功能。,缺点:,2.依赖于计算机软硬件环境。,事前的估计:,事后的统计、事前的估计,1.必须运行算法。,通常，从算法中选取一种对于研究的问题来说是基本操作的原操作，以该基本操作重复执行的次数作为算法执行的时间度量。,基本操作重复执行的次数分别为1，n，n2,频度:语句重复执行的次数称为该语句的频度，记f(n)。,设算法的问题规模为n；,时间复杂度:记T(n)=O(maxlevel(f(n)。,对算法各基本操作的频度求和，便可得算法的时间复杂度。,但实际中我们通常是以算法各基本操作的最大频度数量级表示算法的时间复杂度。,f(n)=1+2n+4n2+7n3,T(n)=O(n3),算法执行总的时间花费为1+n+2n2,算法的时间复杂度为T(n)=O(n2),常见函数增长率,O(1)，O(logn)，O(nk)，O(2n),有时，算法中基本操作重复执行的次数随问题的输入不同而不同，通常分析最好、最坏、平均情况下的时间复杂度。,例，顺序查找算法,最好1次比较，最坏n次比较，平均(n+1)/2次比较。,了解数据结构学科的发展,掌握相关基本概念,数据结构(逻辑结构、存储结构),数据类型、抽象数据类型,理解算法的重要特性及算法设计的要求,掌握算法时间复杂度的计算,学习要点,作业,1.描述一个抽象数据类型的定义。,2.计算算法时间复杂度。,for(i=1；i=n；i+)for(j=1；j=i2；j+)X=X+1；,
展开阅读全文