《数据结构的基本概念》由会员分享,可在线阅读,更多相关《数据结构的基本概念(52页珍藏版)》请在金锄头文库上搜索。
1、前言数据结构是计算机系的专业基础课,它不但是 计算机学科的理论基础之一,也是软件开发的 必备基础。因此,无论是从事计算机行业,还 是希望在计算机方面继续深造,都应该学好这 门课程。1第1章 数据结构的基本概念抽象数据类型和算法描述n抽象和实现n术语和概念n抽象数据类型n算法与伪码n程序结构化与设计风格n程序分析的方法n时间复杂性分析n渐进式表示法n递归式的复杂性计算21.1 抽象和实现n什么是抽象和实现? 抽象是信息隐蔽的方法,用这种方法将数据表 示或处理过程中的细节对不需要(或不想)了 解的人隐藏起来。 实现是已屏蔽掉的繁琐的细节。31.1.1数和变量n平时使用的数据类型中哪些是抽象出来的?
2、 整型、实型、字符型、枚举型等。n抽象出来的数据类型是怎样实现处理过程的? 各种计算机语言的编译程序有它们各自所抽象出来的数 据类型与计算机自身的数值进制有相应的转换规则,也 能够对其进行存储和计算。n变量是抽象的吗?其作用是什么? 变量是一种抽象。它的作用是减少程序设计人员对内存 细节的考虑,而将主要精力用于程序算法的编写。41.1.2两维数组n计算机存储是按一维方式还是二维方式? 计算机存储区是按字节或字的一维或线性序列 方式进行编址。n计算机是如何解释带有二维数组的语句的? 通过编译程序。n二维数组的应用 矩阵51.1.3过程和抽象n过程是什么? 过程是程序设计的基本工具和方法,它将操作
3、符 和操作对象的概念一般化,使程序员不受程序设 计语言提供的基本数据类型和操作符的约束,可 以利用过程自由地定义操作数和操作方法。n过程的优点 利用过程的优点在于信息的隐蔽和模块化,它实 现了对算法的若干部分的封装。n抽象都是程序设计语言提供的吗?n过程是一种抽象吗? 61.2 术语和概念 1.2.1数据、数据元素和数据对象n数据就是指所有能被输入到计算机中,且被计算机处理的符号 的集合,它也是计算机操作的对象的总称。是计算机处理的信 息的某种特定的符号表示形式。 注意:数据的范围是随着计算机的发展而不断扩大的。n数据元素是数据中的一个个体,是数据结构中讨论的基本单位 。一个数据元素还可以由若
4、干个数据项组成。数据项是具有独 立含义的最小标识单位。如整数这个集合中,10这个数就可称 是一个数据元素.又比如在一个数据库表(关系式数据库)中,一 个记录可称为一条数据,每一个字段可称为一个数据元素,而 每个字段的组成部分可称为一个数据项(例如出生日期中的年、 月、日)。n数据对象是性质相同的数据元素的集合,是数据的一个子集。71.2.2 数据类型n在用高级语言编写的程序中,必须对程序中出 现的每个变量、常量和表达式,明确说明它们 所属的数据类型。n数据类型是程序设计语言中对于给定变量的所 有可能取值的集合。n数据类型是一个值的集合和定义在此集合上的 一组操作的总称。n每一个对象仅由单值构成
5、的类型称为标量类型 或原子类型。每一个对象可由一组值构成的类 型称为组合类型或结构类型(有时也称为数据 结构)81.2.3 抽象数据类型n抽象数据类型(abstract data type简称ADT)是 一种数据类型及在这个类型上定义的一组合法 的操作。n程序设计语言提供的ADT定义工具 Ada提供包、c+提供类n使用ADT的作用 减少程序的复杂性91.2.4 数据结构 (带结构的数据元素的集合)n定义: 数据结构是以某种方式联系在一起的数据元素的集合。n数据结构研究的内容 数据结构研究的是数据元素之间抽象化的相互关系及这 种关系在计算机中的存储表示,对每种结构定义各自的 运算,设计出相应的算
6、法,并用某种语言实现该算法。n数据结构包含的内容: 逻辑结构和物理结构,甚至包括对数据的操作。 数据的逻辑结构是指各数据元素之间的逻辑关系,是用 户按使用需要建立起来的,呈现在用户面前的结构形式 。数据的物理结构又称为数据的存储结构,是指数据在 计算机内的表示方法,即存储形式。10比如一个表(数据库),我们就称它为一个数据结构, 它由很多记录(数据元素)组成,每个元素又包括很多 字段(数据项)组成。那么这张表的逻辑结构是怎么样 的呢? 对于这个表中的任一个记录(结点),它只有一 个直接前趋,只有一个直接后继(前趋后继就是前相邻 后相邻的意思),整个表只有一个开始结点和一个终端 结点,那我们知道
7、了这些关系就能明白这个表的逻辑 结构了。 常见的逻辑结构有:线性结构、树形结构、图状结构 和集合结构。11n存储结构是逻辑结构在存储器中的映像。 数据元素的映像方法: 用二进制位(bit)的位串表示数据元素。 (320)10=(501)8=(101000001)2 (A)=(101)8=(001000001)2n关系的映像方法(表示的方法) 顺序映像:以存储位置的相邻表示后继关系。 Y的存储位置和X的存储位置之间相差一个常量C,而C是一 个隐含值(与数据在内存中占据的宽度有关),整个存储 结构中只含数据元素本身的信息。12链式映像:以附加信息(指针)表示后继关系 需要一个和X在一起的附加信息指
8、示Y的存储位置。 在不同的存储环境中,存储结构可有不同的描述方 法。 当用高级程序设计语言进行编程时,通常可用高级 编程语言提供的数据类型描述之。13例如:以三个带有次序关系的整数表示一个长 整数时,可利用C语言中提供的整数数组类型 ,定义长整数为: typedef int Long_int314n对数据的运算:比如一张表格,我们需要进行 查找,增加,修改,删除记录等工作,而怎么 样才能进行这样的操作呢? 这也就是数据的运 算,它不仅仅是加减乘除这些算术运算了,在 数据结构中,这些运算常常涉及算法问题。151.3 抽象数据类型1.3.1抽象数据类型的描述n研究抽象数据类型的原因? 人们认识到在
9、问题的描述和程序的实现之间存 在着一个可适当定义的中间领域,这个中间领 域比问题的描述具体些,但比最终的程序抽象 些。n数据结构的类型:线性、层次、网状n抽象数据类型的组成部分:元素(Elements)、 结构(Structure)和操作(Operation)161.3.2抽象数据类型的说明n元素n结构n操作 ADT的说明基本上是功能性的说明,对具体的 实现并不作过多的约束。在具体现实时,完成 任务的算法、数据类型、数据结构、程序的逻 辑组织甚至采用哪种程序设计语言都是可自由 选择的。17nADT的主要目的:对用户隐蔽所有的表示方法 、算法的详细细节、实现操作的具体代码及其 他所有不必要的细节
10、,这些细节被局限于具体 实现的模块内部,从而实现了信息的隐蔽。nADT的重要优点:简单性。n抽象的目的:将数据的本质特征、它们的结构 及操作同它们的非本质的具体表示及实现细节 区别开来,从而得到了简化。181.3.3抽象数据类型的表示为扑克牌设计抽象数据类型,你会怎样设计?n使用枚举类型n使用整数型n使用位向量表示法 程序设计的主要目标是产生一个正确的程序, 并能尽量避免错误的输入对程序的结果造成不 良的影响,但是还有其他第二位重要的目标。 好的程序不仅要运行正确,而且要具有通用性 、模块化和信息隐蔽性。191.3.4实现的独立性由于在ADT的说明中,只指明了其功能而未指 明要采用的何种方法,
11、因此实现的独立性是显 而易见的。 具体的实现只要根据ADT的数据类型及说明的 各个抽象操作和ADT的表示,用某种程序设计 语言写出一个个独立的过程和函数的具体语句 来即可。201.3.5一个复数抽象数据类型n元素介绍 复数的实部(rpart)和虚部(ipart)n结构说明 复数的元素之间不存在任何结构n操作部分 复数的生成(Create),两个复数的加(Add)、减 (Sub)、乘法(Product)运算21编程练习:试分别用结构和类两种方式实现复数抽象数据 类型的定义。 设两个复数c1=x1+iy1, c2=x2+iy2 和 sum=(x1+y1)+i(y1+y2) 差 difference
12、=(x1-x2)+i(y1-y2) 积 product=(x1*x2-y1*y2)+i(x1*y2+x2*y1)221.4算法分析算法+数据结构=程序(N.沃恩)这个公式的含义是什 么? 1.4.1算法的概念n算法是能在计算机上经过有限的时间内完成,毫不 含糊的有限的指令序列。n程序设计:为计算机处理问题编制的一组指令集。 计算机对某类问题进行某种处理,包含了两方面的 问题:一个是怎样进行处理;另一个是对处理的信 息怎样表示。n算法:处理问题的策略(怎样处理问题)n数据结构:问题的数学模型(处理的问题怎样表示 )23例如:数值计算的程序问题n结构静力分析计算 数据模型:线性代数方程组n全球天气
13、预报 数据模型:环流模型方程24非数值计算的程序设计问题n例一:求一组(n个)整数中的最大值。n算法:基本操作是比较两个数的大小n模型:存储这组整数所需的数据类型。25例二:计算机对弈n算法:对弈的规则和策略n模型:棋盘、棋子的表示26例三:医院的数据库管理n算法:需要管理的项目?如何管理?界面?n模型:各种表格和数据库27n综合各种程序设计问题,抽去它具体的物理含 义,就可以得到几类基本的数学模型,比如和 数值计算相关的数学模型就有线性代数方程、 非线性代数方程、微分方程等。它们的数值解 问题,也就是计算求解的问题,就是计算数学 要解决的问题。而类似的非数值计算问题,它 的数学模型的表示和求
14、解的方法就是数据结构 研究的内容。n概括的说: 数据结构描述现实世界实体的数学模型(非数 值计算)及其上的操作在计算机中的表示和实 现。28算法与代码算法是为了解决某类问题而规定的一个有限长 的操作序列。 简单的说,算法是对求解某一问题的描述。算法都必须满足下列几个条件: 有穷性:对于任意一组合法输入值,在执行有穷 步骤之后一定能结束,即:算法中的每个步骤 都能在有限时间内完成。29确定性:对于每种情况下所应执行的操作,在 算法中都有确切的规定,使算法的执行者或阅 读者都能明确其含义及如何执行。并且在任何 条件下,算法都只有一条执行路径(对同样的输 入值,不管在什么条件下,重复执行多遍,都 能
15、够得到相同的结果)。 可行性:算法中的所有操作都必须足够基本,都可 以通过已经实现的基本操作运算有限次实现之。 例如:将x和y两个正整数的最大公因子赋值给z, 由于求最大公因子本身就是一个算法,因此这个 操作不是基本操作。 例如:将变量x的值增加,看似简单,但到底给x 增加多少却并不明确,因此它也不是基本操作。30有输入:作为算法加工对象的量值,通常体现为算 法中的一组变量。有些输入量需要在算法执行过 程中输入,而有的算法表面上可以没有输入,实 际已被嵌入算法之中。 例如求100以内的素数。数据的范围是从1到100 ,此时的数据就没有从键盘输入而是嵌入到了算 法之中。 有输出:它是一组与输入有
16、确定关系的量值,是算 法进行信息加工后得到的结果,这种确定关系即 为算法的功能。31算法设计的原则1.正确性n程序中不含语法错误n程序对于几组输入数据能够得出满足要求的结 果n程序对于精心选择的、典型、苛刻且带有刁难 性的几组输入数据能够得出满足要求的结果n程序对一切合法的输入数据都能得出满足要求 的结果322.可读性 算法主要是为了人的阅读与交流,其次才是为 计算机执行。因此算法易于人的理解,另一方 面,晦涩难读的程序易于隐藏较多错误而难以 调试。 3.健壮性 当输入的数据合法时,算法应当恰当地作出反 应或进行相应的处理,而不是莫名其妙地输出 结果。并且处理出错的方法不应时中断程序的 执行,而应是返回一个表示错误或错误性质的 值,以便在更高的抽象层次上进行处理。334.高效率与低存储量需求n通常,效率指的是算法执行的时间;存储量指 的是算法执行过程中所需的最大存储空间。两 者都与问题的规模有关。34用来写算法的方式有好几种,一般而言,我们可以 分为下列4种方式: 条列式的步骤: 以条列式的步骤来描述解决问题的方法。 流程图: 以图形符号来描述解决问题的方法。