软件复习指导-第2章基本数据结构

2第二章

基本数据结构及其运算2.1数据结构的基本概念结构2.2线性表及其顺序2.3线性链表及其运算2.4树与二叉树本次课主要内容数据结构学习数据结构的意义数据结构主要涵盖内容——基本概念和术语——数据的逻辑结构——数据的物理结构——数据的运算计算机解题的基本方法是：分析问题，确定数据模型；设计相应的算法；编写程序；反复调试程序直至得到正确的结果。有些问题的数据模型可以用具体代数方程、矩阵等表示。然而，的实际问题是无法用数学方程表示的。下面给出三个简单的例子加以说明。举例1表2-1是一个学生基本情况表。表中有30个记录，按学号顺序排列，它们之间存在一对一的关系，这是一种线性结构，主要操作有查找、修改、或删除等。2.1.1

数据结构学

号姓

名性

别班级......1200302001男电气（1）......1200302002男电气（1）.......1200302003男电气（1）......…………......1200302030巨园园女电气（1）......表2-12.1.1数据结构作是遍历、查找、

或删除等。2.1.1举例2图2-1表示的是我院的专业设置情况。在图2-1中可以把一所学院名称看成树根，把下设的若干个教育类别名看成它的树枝中间结点，把每个教育类别的若干个专业方向看成树叶，这就形成一个树形结构。树形结构通常用表示结点的分层组织，结点之间是一对多的关系。对于树形结构的主要操数据结构水利水电学院水利水电工程教育本科教育电气工程及其自动化水利工程水文学与水资源图2-12.1.1数据结构2.1.1

数据结构举例3图2-2是一个描述若干个城镇之间的公路网。图中每个顶点代表一个城镇，边表示城镇之间的道路。显然在图2-2中各个顶点之间的关系更加复杂，它们是一种多对多的关系。具有这种关系的结构称之为图形结构。在实际应用中，假设从某个原料产地把原料运往各加工地，需要制定一个方案使得费用最省。DCABE图3-50302.1.1数据结构2.1.1数据结构是相互之间存在一种或多种特定关系的数据元素的集合，表示为：（数值或非数值）Data_Structure=（D,

R）——是指同一种数据元素类型中各元

间存在的关系。——针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作。元素有限集关系有限集2.1.2

学习数据结构的意义计算机内的数值运算依靠方程式，而非数值运算（如表、树、图等）则要依靠数据结构。数据结构是，针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作等的一门学科。程序设计＝好算法＋好结构同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。2.1.3

数据结构主要涵盖内容基本概念和术语数据(data)——所有能被计算机识别、和处理的符号的集合（包括数字、字符、声音、图像等信息）。数据元素(data element)——是数据的基本单位，具有完整确定的实际意义(又称元素、结点，顶点、记录等）。数据对象(dataobject)——由性质相同(类型相同)的数据元素组成的集合。数据对象是数据的一个子集。2.1.3

数据结构主要涵盖内容2.1.3

数据结构主要涵盖内容基本概念和术语例1由4个整数组成的数据对象D1={20,-30,88,45}例2由正整数组成的数据对象D2={1,2,3,...}例3由26个字母组成的数据对象D3={A,B,C,...,Z}其中：D1，D3是有穷集，D2是无穷集。集合线性结构树形结构图状结构基本概念和术语4.数据结构(data

structure)——相互之间存在一种或多种特定关系的数据元素的集合。数据元

间的关系称为结构。四类基本结构：2.1.3

数据结构主要涵盖内容集合结构：仅同属一个集合线性结构:

一对一（1:1)树

结构:

一对多（1:n)图

结

构:

多对多

(m:n)非线性线性逻辑结构可细分为4类：指数据元据，它与数据的间的逻辑关系。即从逻辑关系上描述数无关，是独立于计算机的。数据的逻辑结构2.1.3

数据结构主要涵盖内容线性表栈队列,双队列数组字符串线性结构逻辑结构非

线

性结

构树,二叉树图数据的逻辑结构分类2.1.3

数据结构主要涵盖内容数据的逻辑结构——线性结构（1）

S=(D,

R)D={

a,

b,

c,

d,

e,

f

}R={(a,e),(b,c),

(c,a),

(e,f),

(f,d)}f解：上述表达式可用图形表示为：b

c

a

e此结构为线性的。d例：用图形表示下列数据结构，并性结构还是非线性结构。它们是属于线2.1.3

数据结构主要涵盖内容2.1.3

数据结构主要涵盖内容数据的逻辑结构——线性结构不是线性结构的数据结构特例

如果一个数据结构不是线性结构，则称之为非线性结构该结构是非线性的。数据的逻辑结构——非线性结构（2）

S=(D,

R)D={di

|1≤i≤5}R={(di

,

dj

),

i<j}解：上述表达式可用图形表示为：d1d2d3d4d52.1.3

数据结构主要涵盖内容前后件关系是数据元

间的一个基本关系，但前后件关系所表示的实际意义是随具体对象的不同而不同。为了反映数据对象D中各数据元

间的前后件关系，一般用二元组来表示。设a与b是D中的两个数据，则二元组（a，b）表示a是b的前件（前驱），b是a的后件（后继）。间的关系描述2.1.3

数据结构主要涵盖内容数据的逻辑结构——数据元例如

四季的数据结构B＝（D，R）D＝{春，夏，秋，冬}R＝{(春，夏)，(夏，秋)，(秋，冬)}“夏”是“秋”的前件；“秋”是“夏”的后件。家庭成员数据结构B＝（D，R）D＝{父亲，儿儿}R＝{(父亲，儿子），(父亲，女儿）}“父亲”是“儿子”、“女儿”的前件；“儿子”、“女儿”是“父亲”的后件。2.1.3

数据结构主要涵盖内容数据的逻辑结构——数据元

间的关系描述在数据结构中，没有前件的结点称为根结点；没有后件的结点成为终端结点（也称为叶子结点）；除了根结点与终端结点外的其他结点一般称为结点。根结点叶子结点结点终端结点2.1.3

数据结构主要涵盖内容数据的逻辑结构——数据元

间的关系描述结构可分为4大类：物理结构亦称

结构，是数据的逻辑结构在计算机

器内的表示（或映像）。它依赖于计算机。顺序、链式、索引、散列例：表2-1（学生信息表）的两种

方式：记录2方式1：地址03000301记录10415记录10415记录2方式2：地址03000301内容内容数据的物理结构2.1.3

数据结构主要涵盖内容在数据的逻辑结构上定义的操作算法。它在数据的

结构上实现。最常用的数据运算有5

种：、删除、修改