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

数据结构1 概 述

2线 性 表

3 堆 栈

4 队 列

5 树

6 图

数据结构

1 概 述

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 数据结构概述[例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)树形结构所有的数据元素之间呈现出层次结构，每个数据元素可以 有多于一个的“直接下级”,但它只能有唯一的“直接上 级”。树形结构中有且仅有一个根结点，该结点没有父结 点。树形结构可以类比为家族的家谱层次结构。 该结构的数据元素之间存在着一对多的关系。

1 数据结构概述[例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 数据结构概述 数据的存储结构 2.链接方法 链接方法是借助指示元素存储地址的指针表示数据元 素间的逻辑关系。