数据结构(第1讲)

数据结构教案第1讲【主要讲授内容】1.1.1数据结构示例1.1.2基本概念和术语1.1.3数据结构(DataStructure)【重点与难点】1.重点a.熟悉数据结构常用术语b.掌握基本概念c.数据结构的逻辑结构d.数据结构的物理结构2．难点数据元素间的4种结构关系【教学要求】1．通过本次课程的学习使同学们对数据结构能有一个初步的认识。2．了解数据结构的教学方法和学习方法。【实施方法】课堂讲授，采用案例式教学激发学生对数据结构课程的兴趣。【学时安排】2学时数据结构教案2讲授内容1.1什么是数据结构计算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题：（1）信息的表示；（2）信息的处理而信息的表示和组织又直接关系到处理信息的程序的效率。现在许多系统程序和应用程序的规模越来越大，结构变得十分复杂。为了编写出一个“好”的程序，必须分析待处理对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。【定义】数据结构：研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。1.1.1数据结构示例【例1-1】图书目录表【例1-2】磁盘目录结构和文件管理系统【例1-3】逻辑磁盘上的目录结构和文件管理系统【例1-4】教学计划编排问题1.1.2基本概念和术语数据(Data)对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素(DataElement):数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据对象(DataObject)是性质相同的数据元素的集合。是数据的一个子集。如：整数的数据对象是{…-3，-2，-1，0，1，2，3，…}英文字符类型的数据对象是{A，B，C，D，E，F，…}数据类型(DataType)是一组性质相同的值的集合以及定义在这个值集合上的一组操作的总称。例如:整型，字符型、浮点型、双精度抽象数据类型(AbstructDataType,简称ADT)ADT是指一个数学模型以及定义在该模型上的一组操作，可看作是数据的逻辑结构及其在逻辑结构上定义的操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。1.1.3数据结构(DataStructure)数据结构是研究数据元素（DataElement）之间抽象化的相互关系（逻辑结构）和这种关系在计算机中的存储表示（物理结构），并对这种结构定义相适应的运算，设计出相应的算法。数据结构主要指逻辑结构和物理结构。1.逻辑结构：数据结构教案3数据之间的相互关系称为逻辑结构。通常分为4类基本结构：集合结构中的数据元素除了同属于一种类型外，别无其它关系。线性结构结构中的数据元素之间存在一对一的关系。树型结构结构中的数据元素之间存在一对多的关系。图状结构或网状结构结构中的数据元素之间存在多对多的关系。数据结构的形式定义为：数据结构是一个二元组：Data-Structure=(D，S)其中：D是数据元素的有限集，S是D上关系的有限集。例复数的数据结构定义如下：Complex=(C，R)其中：C是含两个实数的集合﹛C1，C2﹜，分别表示复数的实部和虚部。R={P}，P是定义在集合C上的一种关系{〈C1，C2〉}。【例1-5】设一个数据结构的描述如下：D=(K，R)K={1，2，3，4，5，6，7，8，9}R={1,2,1,3,3,4,3,5,4,6,4,7,5,8,7,9}试画出对应的逻辑结构图，并给出哪些是开始结点，哪些是终端结点，说明是何种数据结构。【解】【例1-6】设一个数据结构的描述如下：D=(K，R)K={1，2，3，4}R={1,2,1,3,1,4,2,3,2,4,3,4}试画出对应的逻辑结构图，说明是何种数据结构。【解】123458769开始结点：1中间结点：3，4，5，7终端结点：2，6，8，9树型结构数据结构教案4（图状结构）2.存储结构（物理结构）：数据结构在计算机中的表示称为数据的物理结构，又称为存储结构。数据既可以存放在一块连续的内存单元中，通过元素在存储器中的位置来表示它们之间的逻辑关系（顺序）；也可以随机分布在内存中的不同位置，通过指针元素表示数据元素之间的逻辑关系（链式）。这两种不同的表示方法对应有四种不同的存储结构（亦称方式）：顺序存储结构、链式存储结构、索引存储结构和散列存储结构。顺序存储结构是把逻辑上相邻的结点存储在物理上相邻的存储单元里，结点之间的逻辑关系由存储单元位置的邻接关系来体现。优点：占用较少的存储空间；缺点：由于只能使用相邻的一整块存储单元，因此可能产生较多的碎片现象。顺序存储结构通常借助程序语言中的数组来描述。顺序存储结构主要应用于线性的数据结构。链式存储结构将结点所占的存储单元分为两部分，一部分存放结点本身的信息，另一部分存放结点的后继结点地址，结点间的逻辑关系由附加的指针字段表示。链式存储结构常借助于程序语言的指针类型描述。优点：不会出现碎片现象，充分利用所有的存储单元；缺点：每个结点占用较多的存储空间。索引存储方式是用结点的索引号来确定结点的存储地址。在储存结点信息的同时，要建立附加的索引表。优点：检索速度快。缺点：增加了附加的索引表，占用较多的存储空间；在增加和删除数据时需要修改索引表而花费较多时间。散列存储方式是根据结点的关键字值直接计算出该结点的存储地址。通过散列函数把结点间的逻辑关系对应到不同的物理空间。优点：检索、增加和删除结点的操作都很快；缺点：当采用不好的散列函数时可能出现结点存储单元的冲突，为解决冲突需要附加时间和空间的开销。3．数据的运算数据运算定义在数据的逻辑结构上，即施加于数据的操作。例如：对一张表的记录进行查找、增加、删除、修改，这就是对数据的运算。4．数据结构三方面的关系数据的逻辑结构、数据的存储结构及数据的运算三方面构成一个数据结构的整体。存储结构是对数据项的存储。同一逻辑结构可用不同存储结构就对应不同的存储1234数据结构教案5标识。例如：线性表若采用顺序存储方式，称为顺序表；若采用链式存储方式，称为链表；若采用散列存储方式，可称为散列表。【小结】本次课介绍了数据结构的定义，从逻辑上讲，数据有集合、线性、树和图四种结构。从存储结构上讲，数据有顺序结构、链接结构、索引结构和散列结构四种。理论上，任一种数据逻辑结构都可以用任一种存储结构来实现。【问题与思考】1．数据类型和抽象数据类型是如何定义的。二者有何相同和不同之处？2．抽象数据类型的主要特点是什么？3．使用抽象数据类型的主要好处是什么？【课后作业】1.数据结构是一门研究什么内容的学科？2.数据元素之间的关系在计算机中有几种表示方法？各有什么特点？