搜索
2014-2-20数据结构2014-2-20第一章绪论学习目的：掌握数据结构的基本概念和术语。重点难点：数据结构的基本概念。2014-2-201.1什么是数据结构1.2基本概念和术语教学内容2014-2-20•IT计算机科学家pascal语言的创始人NiklausWirth（尼古拉斯·沃斯）教授在1976年出版了一本书：“Algorithms+DataStructures=Programs”说明了算法和数据结构是进行程序设计的两大要素。1.1什么是数据结构2014-2-201.计算机是怎么解决问题的？很多数值计算问题的数学模型通常可用一组线性或非线性的代数方程组或微分方程组来描述：如：结构静力分析计算---线性代数方程组，全球天气预报---环流模式方程抽象模型设计算法调试测试编码得出结果2014-2-20如今计算机所处理的是大量的非数值计算的程序设计问题：例1**数据库管理系统例2计算机对弈：数学模型：表格和数据库数学模型：树形结构2014-2-20例3交叉路口的红绿灯管理。如今十字路口横竖两个方向都有三个红绿灯，分别控制左拐、直行和右拐，那么如何控制这些红绿灯既使交通不堵塞，又使流量最大呢？数学模型：图状结构2014-2-20例4煤气管道的铺设问题。如下图：需为城市的各小区之间铺设煤气管道，对n个小区只需铺设n-1条管线，由于地理环境不同等因素使各条管线所需投资不同(如图上所标识)，如何使投资成本最低？2014-2-20•综合各种程序设计问题，抽取它具体的物理含义，就可以得到两类数学模型：–和数值计算相关的数学模型：（非）线性代数方程，常微分方程--计算数学–非数值计算问题的数学模型：数学模型的表示和求解方法--数据结构•由以上几个例子可见，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树、图之类的数据结构。2014-2-202.什么是数据结构?•数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。•要使计算机能够更有效地进行这些非数值性处理，就必须弄清楚这些操作对象的特点，在计算机中的表示方式以及各个操作的具体实现手段。这些就是《数据结构》这门课程研究的主要内容。2014-2-20是所有能被输入到计算机中，且能被计算机处理的所有符号(数字、字符等)的集合，它是计算机操作对象的总称，是计算机处理的信息的载体，是信息的某种特定的符号表示形式。数据是个集合，如果用集合的表示方法来写的话，就是：数据={x|x是计算机操作的对象}是数据(集合)中的一个“个体”，在计算机中通常作为一个整体进行考虑和处理，是数据结构中讨论的“基本单位”，但不是“最小单位”。1、数据2、数据元素1.2基本概念和术语2014-2-20数据元素分类•一类是不可分割的“原子”型数据元素，如：整数“5”，字符“N”等•另一类是由多个款项构成的数据元素，其中每个款项被称为一个“数据项”。例如描述一个学生的信息的数据元素可由下列6个数据项组成。•数据项是数据结构中讨论的“最小单位”。•数据元素是数据项的集合。称之为组合项2014-2-20•是性质相同的数据元素的集合，它是数据的一个子集。如：–整数数据对象N={0,1,2,…}–字母字符数据对象C={‘A’,’B’,……‘Z’}•在同一个数学模型中的数据元素必然具有相同特性。3、数据对象4、数据结构1）概念：是相互之间存在一种或多种特定关系的数据元素的集合，即带“结构”的数据元素的集合。“结构”即指数据元素之间存在的约束关系。数据结构是一堆数据元素和这些数据元素之间的关系的总和。2014-2-20例5一个12位数的十进制数可以用3个4位的十进制数表示：3214，6587，9345--a1(3214),a2(6587),a3(9345)a1,a2,a3之间存在“次序”关系a1,a2,a2,a3，x,y意为x和y之间存在“x领先于y”的次序关系。a1a2a3≠a2a1a32014-2-20例6可以用下述数据结构来描述2行3列的矩阵：它是一个含6个数据元素{a1,a2,a3,a4,a5,a6}的集合，且集合上存在“行关系”和“列关系”两个次序关系，其中：–行row={a1,a2，a2,a3，a4,a5，a5,a6}–列col={a1,a4，a2,a5，a3,a6}654321aaaaaaa1a3a5a2a4a6a1a2a3a4a5a6同样的这6个数据元素组成的一维数组{a1,a2,a3,a4,a5,a6}的数据元素之间存在如下的次序关系:{ai,ai+1|i=1,2,…5}同样的数据元素，不同的关系构成了不同的结构，因此数据结构是带结构的数据元素的集合。或者说，数据结构是相互之间存在着某种逻辑关系的数据元素的集合。2014-2-202）数据结构的形式定义•数据结构是一个二元组Data_Structures=(D,S)•其中：D是数据元素的有限集，S是D上关系的有限集。例7复数的二元组定义复数由实部和虚部构成（构成元素），两者之间存在着一种次序关系（逻辑关系）。可以表示为：Complex=(C,R)其中,C={c1,c2}R={c1,c2}说明:表示有序数对,用图示法表示时画箭头()表示无序数对,用图示法表示时画线段2014-2-20数据的逻辑结构：描述数据元素之间的逻辑关系，不依赖于具体表示，是抽象的。可归结为以下四类:线性结构树形结构图/网状结构集合结构3）数据的“逻辑结构”一对一一对多多对多2014-2-204）数据的存储结构——逻辑结构在存储器中的具体实现表示(映象)。故又称数据存储结构。它包括数据元素的表示和关系的表示。“数据元素”的映象？“关系”的映象？2014-2-20①数据元素的映象方法：用二进制位(bit)的位串表示数据元素(321)10=(501)8=(101000001)2A=(101)8=(001000001)22014-2-20②关系的映象方法：•顺序映象借助元素在存储器中相对的位置来表示数据元素之间的关系。地址是连续的。如数组。例8存储复数z=3.0-2.3i用顺序结构，内存存储情况为:20012004200520083.0-2.3顺序存储结构2014-2-20•链式映象借助元素存储地址的指针来表示数据元素之间的关系。地址可以是离散的。如上复数的存储20012004200520063.0203620362039-2.3链式存储结构2014-2-20当用高级程序设计语言进行编程时，通常可用高级编程语言中提供的数据类型来描述存储结构。两种存储的比较：顺序结构:占用最少的存储空间，产生较多碎片。非顺序：不会出现碎片，每个结点占用较多空间。2014-2-205、数据类型•数据类型是一个“值”的集合和定义在此集合上的“一组操作”的总称。•在用高级程序语言编写的程序中，必须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。程序中对变量或常量说明其所属类型的作用是，对它们加上两个约束条件：一是可取值的范围，二是可进行的操作。•不同类型的变量，其所能取的值的范围不同，所能进行的操作不同。2014-2-20例如，C语言中提供的基本数据类型有:整型int浮点型float字符型char空类型void双精度型double实型（C++语言）2014-2-206、抽象数据类型(AbstractDataType简称ADT)–指一个数学模型以及定义在该模型上的一组操作。–由用户定义，用以表示应用问题的数据模型–由基本的数据类型组成,并包括一组相关的服务（或称操作）2014-2-20抽象数据类型的描述方法(P8)抽象数据类型可用（D，S，P）三元组表示。其中：D是数据对象；S是D上的关系集；P是对D的基本操作集。格式：ADT抽象数据类型名{数据对象：〈数据对象的定义〉数据关系：〈数据关系的定义〉基本操作：〈基本操作的定义〉}ADT抽象数据类型名2014-2-20其中基本操作的定义格式为:基本操作名（参数表）初始条件：〈初始条件描述〉操作结果：〈操作结果描述〉赋值参数只为操作提供输入值。引用参数以&打头，除可提供输入值外，还将返回操作结果。初始条件描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。操作结果说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，则省略之。2014-2-20例9、抽象数据类型复数的定义•ADTComplex{数据对象：D={e1,e2|e1,e2RealSet}数据关系：R1={e1,e2|e1是复数的实部，e2是复数的虚部}基本操作：InitComplex(&Z,v1,v2)操作结果：构造复数Z，其实部和虚部分别被赋以参数v1和v2的值。DestroyComplex(&Z)初始条件：复数已存在。操作结果：复数Z被销毁。GetReal(Z,&realPart)初始条件：复数已存在。操作结果：用realPart返回复数Z的实部值。GetImag(Z,&ImagPart)初始条件：复数已存在。操作结果：用ImagPart返回复数Z的虚部值。Add(z1,z2,&sum)初始条件：z1，z2是复数。操作结果：用sum返回两个复数z1，z2的和值。}ADTComplex假设:z1和z2是上述定义的复数则Add(z1,z2,z3)操作的结果即为用户要求的结果z3=z1+z22014-2-20课堂总结主要内容：什么是数据结构、数据结构的基本概念。重点难点：数据结构的基本概念。2014-2-20作业•复习，理解相关概念•预习，算法及其分析