第1章数据结构概论.

1数据结构DataStructure答疑方式：扬帆楼405室周二中午联系方式：[e-mail]84724497(O)22•学时数：46（32讲课+12上机+2考试）•学分：2.5•教材：《数据结构（C语言版）》严蔚敏吴伟民编著清华大学出版社•参考书：《数据结构题集(C语言版)》严蔚敏、吴伟民著《数据结构课程设计》苏仕华等编著机械工业出版社《数据结构题集(C语言篇)——习题与解析（修订版）》李春葆编著清华大学出版社•上机：第10-15周，星期四，1-2节，扬帆楼105室33内容安排章内容学时章内容学时1绪论27图42线性表88动态存储管理略3栈和队列69查找44串略10内部排序45数组和广义表略11外部排序略6树和二叉树412文件略44第1章序论1.1数据结构基本概念1.2算法效率的度量本章小结作业551.1数据结构基本概念Q1什么是数据结构？Q2学习数据结构有什么用？Q3数据结构涵盖的主要内容？讨论：返回章66Q1：什么是数据结构？•计算机的应用范畴•问题求解的过程•基本概念与术语返回节77计算机的应用范畴1）数值计算2）非数值计算（1958年起）图书信息管理、博弈、交通控制、语音处理等。这些问题的求解，需要借助“数据结构”。数据结构着重研究非数值计算领域的问题求解。方程组求解，微分方程求解、数理方程求解等。这些问题的求解方法在“数值计算”课程中已解决。返回主题88抽象出数学模型问题描述设计算法程序实现调试运行结果输出数据结构所解决的问题是数学模型的描述问题。主要工作是分析所要解决的问题，从中找出操作对象以及这些对象之间蕴涵的逻辑关系，并定义基于这些关系的操作，然后用计算机语言加以描述。概要设计事实上，这类问题也可以用数学方法描述为：f(X)=Y上图中黑色框部分，就可以看成是函数f，问题是这里的“函数”可能是相当复杂的。问题求解的过程编码(写程序)详细设计99NiklausWirth：Algorithm+DataStructures=Programs描述待求解问题的数学模型。数据结构程序算法学术界没有给出精确定义，只能给出对它的一种描述。如：算法是解决问题的一种策略（方法或过程）。算法就是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算。近年来有人从状态变换的角度给出了一种定义。在并行计算中，还有关于并行算法的概念。为计算机处理问题所编制的指令序列或指令集。几个相关的术语数学模型的几个例子1010例1求解梁架结构中应力问题的数学模型是：线性代数方程组环流模式方程(球面坐标系)例2求解全球天气预报问题的数学模型是：更多问题的数学模型是无法用方程或方程组加以描述的。微分方程例3预报人口增长情况的数学模型是：数学模型的几个例子（续）1111例4:图书书目检索系统自动化问题。为了实现图书书目检索系统的自动化，需要具有如上形式的信息集，习惯上，我们称这样的信息集为“表”或“线性表”。登录号书名分类号作者名出版社出版时间架位…XXXXXXXXXXXXXXXXXXXXX…XXXXXXXXXXXXXXXXXXXXX…………诸如此类的问题还很多。比如，电话号码查询系统、人事信息系统、产品库存管理系统、原材料系统、财务系统等。描述这类问题的数学模型通常是数据表。通常所说的管理信息系统(MIS)中，大量地涉及到这种数学模型。这种数学模型的特点是：有大量的数据存在，但这些数据间满足线性关系。习惯上，将上述表中的一行信息称为“记录”，将这些记录的集合称为“文件”。数学模型的几个例子（续）1212例5:计算机博弈问题（对弈或下棋）计算机如何能够与人对弈？解决这个问题的思路是(见右图)算法：对弈的规则模型：棋盘格局，树状结构这类问题的关键是控制从棋盘的一种格局向另一种格局过度。由于从一种状态变化到另一种状态可以多种选择，所以，这类问题的特点是：一个格局可能对应多个格局。习惯上，我们称这种类型的数学模型为一棵“树”。初始状态状态1…状态n状态2状态21状态2i……最终状态数学模型的几个例子（续）1313例6:交通灯控制问题在多叉路口如何设计交通灯？或者说，在如图所示的多叉路口应该选用几种颜色的信号灯，才能保证不撞车？解决这个问题的思路是：将所有可能的通路用“点”表示，而不能同时开放的两个通路之间增加一条连线。这样，只要我们给用连线连接的点涂成不同的颜色，那么，该控制问题就圆满解决了。BADCE五叉路口的交通管理示意图见书第3页这类问题的特点是任意两个点之间都有可能有连线。习惯上，我们称这种类型的数学模型为一个“图”。算法：实际问题的约束规则模型：点与点间的关系描述，图形结构数学模型的几个例子（续）返回主题1414基本概念和术语1）数据(data)所有能被计算机识别、存储和处理的符号的总称。数据的概念是广义的，图像、声音、温度等都是数据。数据是计算机处理的信息的某种特定的符号表示形式。对于线性表，数据元素就是指记录，对于树，则是树中结点。2）数据元素(dataelement)是组成数据的基本单位，在计算机程序中通常作为一个整体被处理。(又称元素、结点，顶点、记录等）。3）数据项(Dataitem)构成数据元素的不可分割的最小单位。是数据集合中可以命名的、具有独立含义的最小标识单位，又称字段、域、属性等。1515例如：描述一个运动员的数据元素可以是如下格式：称之为组合项姓名俱乐部名称出生日期参加日期职务业绩年月日上述“姓名”，“俱乐部名称”，“出生日期”，“参加日期”，“职务”，“业绩”6个数据项构成了一个数据元素，也叫做“记录”。如果系统处理需要用到“年”或“月”或“日”这样的数据项，那么就有必要再进一步细分。基本概念和术语（续）在实际问题处理过程中，如果只关心某运动员的出生日期1616例如：整数的数据对象是集合N={0，1，-1，2，-2…}海大人事信息的数据对象是集合{海大职工的个人自然信息}4）数据对象性质相同的数据元素的集合，它是数据的子集。是描述问题空间的数据元素的集合。数据项数据项数据项数据项数据元素数据项数据项数据项数据元素数据对象数据项数据项数据项数据元素数据项数据项数据项数据项数据元素数据对象数据基本概念和术语（续）1717基本概念和术语（续）5）数据结构是相互之间存在一种或多种特定关系的数据元素的集合。或：是指同一数据元素类中各元素之间存在的关系。在任何实际问题中，数据元素之间都不是孤立存在的，一定存在着某种关系。这种数据元素相互之间的关系称为“结构”。根据数据元素间关系的不同特性，通常可以有如下几种数据结构的形态：•集合关系：数据元素同属于该集合。•线性关系：线性关系。•树型关系：用分支关系定义的层次关系。•图型关系：任意两个数据元素间都有可能存在关系。1818基本概念和术语——数据结构（续）例1：带结构的数据元素的集合假设用三个4位的十进制数表示一个含12位数的十进制数。3214,6587,9345─a1(3214),a2(6587),a3(9345)则在a1、a2和a3之间存在着“次序”关系a1,a2、a2,a3。3214，6587，9345a1a2a36587，3214，9345a2a1a3≠例如:在2行3列的二维数组中六个元素之间存在两个关系:行的次序关系:列的次序关系:row={a1,a2,a2,a3,a4,a5,a5,a6}col={a1,a4,a2,a5,a3,a6}例2：带结构的数据元素的集合≠a1a3a5a2a4a6a1a2a3a4a5a6a1a2a3a4a5a61919基本概念和术语——数据结构（续）数据结构的形式定义：（数值或非数值）Data_Structure=（D,S）亦可表示为：S＝（D,R）或B=（K,R）元素有限集关系有限集线性结构树形结构图状结构集合结构一对一的关系一对多的关系多对多的关系同属于同一个集合从逻辑上讲，数据结构可归结为以下四类:返回主题2020Q2：学习数据结构有什么用？答：计算机内的数值运算依靠方程式，而非数值运算（如表、树、图等）则要依靠数据结构。这是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。程序设计实质＝好算法＋好结构同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。返回节2121逻辑结构数据结构物理（存储）结构数据运算Q3：数据结构涵盖的内容？2222解释1：什么叫数据的逻辑结构？答：数据元素间内在的关系是逻辑关系，也称逻辑结构。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。逻辑关系取决于问题空间的问题描述。例如：图书问题中书与书之间的关系可以由登录号来确定为线性关系（结构）；博弈问题中的状态关系是树型关系（结构）等。这些关系都是由问题本身所描述的。2323例：用图形表示下列数据结构，并指出它们是属于线性结构还是非线性结构。（1）S=(D,R)D={a,b,c,d,e,f}R={(a,e),(b,c),(c,a),(e,f),(f,d)}解：上述表达式可用图形表示为：bcaefd此结构为线性的。2424（2）S=(D,R)D={di|1≤i≤5}R={(di,dj),ij}d1d5d2d4d3该结构是非线性的。解：上述表达式可用图形表示为：2525解释2：什么叫数据的物理结构？答：物理结构亦称存储结构或存储映象，是数据结构在计算机存储器内的表示（或映像）。它依赖于计算机。存储（映像）什么？A.数据元素必须加以存储；B.数据元素间的逻辑关系在存储结构中必须得到反映。2626数据元素的映象方法用二进制位(bit)的位串表示数据元素。(321)10=(501)8=(101000001)2A=(101)8=(001000001)2计算机的存储装置是一维的连续空间，那么如何存储数据元素之间的关系(关系未必是1:1的)呢？常见的存储方式有两种：顺序存储结构：用一组连续的存储空间存储数据元素，并用数据元素的物理位置来反映数据元素间的逻辑关系。链式存储结构：用一组并不连续的存储空间存储数据元素，并用指针来反映数据元素间的逻辑关系。所有的数据（汉字，语音等）都表示成二进制形式加以存储。关系的映象方法数据的物理结构（续1）2727数据的物理结构（续2）存储结构可分为4大类：例：复数3.0－2.3i的两种存储方式：顺序、链式、索引、散列－2.303023.00300041503023.003000415－2.3顺序映像：地址内容链式映像：地址内容2字节借助元素在存储器中的相对位置来表示元素之间的逻辑关系借助指针来表示元素之间的逻辑关系2828如何描述存储结构？•用高级语言提供的数据类型来描述如：用一维数组来描述顺序存储结构用指针来描述链式存储结构•数据类型明显或隐含地规定了在程序执行期间变量或表达式所有可能取值的范围，以及在这些值上允许进行的操作。2929解释3：什么是数据的运算？答：在数据的逻辑结构上定义的操作算法。它在数据的存储结构上实现。最常用的数据运算有5种：插入、删除、修改、查找、排序返回节30301.3抽象数据类型概念Q1数据类型与抽象数据类型的区别？Q2抽象数据类型如何定义？Q3抽象数据类型如何表示和实现？讨论：提示：教材中例1-6和例1-7分别给出了抽象数据类型“三元组”的定义、表示和实现，请试阅读。返回章3131抽象数据类型的定义仅仅取决于它的一组逻辑特性，而与其在计算机内部的表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不会影响其外部的使用。抽象数据类型与数据类型实质上是同一个概念，所不同的是，它未必是一个实际类型，而是用户自己定义的数据类型。Q1数据类型与抽象数据类型的区别？数据类型：是一个值的集合和定义在该值上的一组操作的总称。抽象数据类型：是指一个数学模型以及定义在此数学模型上的一组操作。返回节3333Q2抽象数据类型如何定义？抽象数据类型可以用以下的三元组来表示：ADT=（D，S，P）数据对象D上的关系集D上的操作集ADT抽象数据类型名{数据对象：数据对象的定义数据关系：数据关系