第4章计算机专业基础知识(7数据结构)祥解.ppt

数据结构 数据结构 1 数据结构概述 数据结构的定义 数据（Data）:是信息的载体。它能够被计算机识别、存储和加工处理，是计算机程序加工的“原料”。数据的范畴包括整数、实数、字符串、图像和声音等。 数据元素（Data Element）:是数据的基本单位。在不同的条件下，数据元素又可称为元素、结点、顶点和记录等。一个数据元素可由若干个数据项（Data Item）组成. 如：学籍管理系统中学生信息表的每一个数据元素就是一个学生记录。它包括学生的学号、姓名、性别、籍贯、出生年月和成绩等数据项。 1 数据结构概述 数据结构的定义 数据对象（Data Object）:是具有相同性质的数据元素的集合。 数据结构（Data Structure）:是指数据之间的相互关系。涉及数据之间的逻辑关系、数据在计算机中的存储方式和在这种结构上的一组操作（运算）。 （1）数据的逻辑结构（Logical Structure）:即数据元素之间的逻辑关系，是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。 1 数据结构概述 数据结构的定义 （2）数据的存储结构（Storage Structure）：即数据元素及其关系在计算机存储器内的表示，是逻辑结构在计算机中的表示（亦称为映像），它包括数据元素的表示和关系的表示。 （3）数据的运算，即对数据施加的操作，操作的种类是没有限制的，可以根据需要而定义。基本的操作主要有检索、插入、删除、更新和排序。 《数据结构》研究的对象 (1) 对所加工的对象进行逻辑组织 (2) 如何把加工对象存储到计算机中去 (3) 数据运算 1 数据结构概述 数据结构与算法的关系: 计算机科学家沃斯（N.Wirth）提出的: “算法+数据结构=程序” 揭示了程序设计的本质：对实际问题选择一种好的数据结构，加上设计一个好的算法，而好的算法很大程度上取决于描述实际问题的数据结构。算法与数据结构是互相依赖、互相联系的。 一个算法总是建立在一定数据结构上的；反之，算法不确定，就无法决定如何构造数据。 1 数据结构概述 数据的逻辑结构 数据的逻辑结构由某一数据对象及该对象中所有数据成员之间的关系组成。 常见的逻辑关系有： 线性结构 树形结构 图结构 1 数据结构概述 数据的逻辑结构 (1)线性结构 所有的数据元素按某种次序排列在一个序列中。对线性结构中的每一个数据元素，除第一个元素外，其他每个元素有且仅有一个直接前驱，第一个数据元素无直接前驱。除最后一个元素外，其他每一个元素有且仅有一个直接后继，最后一个数据元素无直接后继。 该结构的数据元素之间存在着一对一的关系。 [例1] 线性数据结构=(D,S) D={1,2,3,4,5,6,7,8,9,10} S={1,2,2,3,3,4,4,5,5,6,6,7,7,8, 8,9,9,10} 1 数据结构概述 数据的逻辑结构 (2)树形结构 所有的数据元素之间呈现出层次结构，每个数据元素可以有多于一个的“直接下级”，但它只能有唯一的“直接上级”。树形结构中有且仅有一个根结点，该结点没有父结点。树形结构可以类比为家族的家谱层次结构。 该结构的数据元素之间存在着一对多的关系。 [例3] 树形结构 =（D,R） D={a, b, c, d, e, f, g, h, i, j, k, l} R={a,b,a,c,a,d,b,e,b,f,b,g,c,h,c,i,c,j, d,k,d,l} 1 数据结构概述 数据的逻辑结构 (3)图结构 可称为网络结构。对于图结构中的所有数据元素之间的关系没有任何约束。可以将图结构看作层次结构的一种扩展且允许数据元素之间具有多个“直接上级”。因特网的网页链接关系就是一个非常复杂的图结构。 该结构的数据元素之间存在着多对多的关系。 1 数据结构概述 [例2] 图形数据结构=(D,R) D={1, 2, 3, 4, 5, 6, 7, 8, 9} R={1,2,1,3,2,4,2,5,2,6,2,8,3,2,3,4,4,5,5,7,6,7,6,9,7,9,8,9} 1 数据结构概述 数据的存储结构 数据的存储结构是指在计算机中的存储器内如何表示数据元素及数据元素之间的关系。 两种最基本的存储方法。 1.顺序方法 2.链接方法 1 数据结构概述 数据的存储结构 1.顺序方法 顺序方法是借助元素在存储器中的相对位置来表示数据元素间的逻辑关系。 该方法把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。 1 数据结构概述