第2章 基本数据结构2.1(new)

软件技术基础软件基础学习交流QQ群：3380756622第二章基本数据结构及其运算2.1数据结构的基本概念2.2线性表及其顺序存储结构2.3线性链表及其运算2.4树与二叉树数据库应用基础本次课主要内容2.1.1什么是数据结构2.1.2学习数据结构的意义2.1.3数据结构主要涵盖内容 ——基本概念和术语 ——数据的逻辑结构 ——数据的物理结构 ——数据的运算

计算机解题的基本方法是：分析问题，确定数据模型；设计相应的算法；编写程序；反复调试程序直至得到正确的结果。有些问题的数据模型可以用具体代数方程、矩阵等表示。然而，更多的实际问题是无法用数学方程表示的。下面给出三个简单的例子加以说明。

举例1

表2-1是一个学生基本情况表。表中有30个记录，按学号顺序排列，它们之间存在一对一的关系，这是一种线性结构，主要操作有查找、修改、插入或删除等。2.1.1什么是数据结构表2-12.1.1什么是数据结构举例2

图2-1表示的是我院的专业设置情况。在图2-1中可以把一所学院名称看成树根，把下设的若干个教育类别名看成它的树枝中间结点，把每个教育类别的若干个专业方向看成树叶，这就形成一个树形结构。

树形结构通常用表示结点的分层组织，结点之间是一对多的关系。对于树形结构的主要操作是遍历、查找、插入或删除等。2.1.1什么是数据结构水利水电学院水利水电工程研究生教育本科教育电气工程及其自动化水利工程水文学与水资源图2-12.1.1什么是数据结构举例3

图2-2是一个描述若干个城镇之间的公路网。图中每个顶点代表一个城镇，边表示城镇之间的道路。

显然在图2-2中各个顶点之间的关系更加复杂，它们是一种多对多的关系。具有这种关系的结构称之为图形结构。在实际应用中，假设从某个原料产地把原料运往各加工地，需要制定一个运输方案使得运输费用最省。2.1.1什么是数据结构DCEAB图3-1402035305550302.1.1什么是数据结构2.1.1什么是数据结构是相互之间存在一种或多种特定关系的数据元素的集合，表示为：

（数值或非数值）

Data_Structure=（D,

R）——是指同一种数据元素类型中各元素之间存在的关系。——针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作。元素有限集关系有限集2.1.2学习数据结构的意义计算机内的数值运算依靠方程式，而非数值运算（如表、树、图等）则要依靠数据结构。

数据结构是，针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作等的一门学科。程序设计＝好算法＋好结构同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。

2.1.3数据结构主要涵盖内容1.数据(data)——所有能被计算机识别、存储和处理的符号的集合（包括数字、字符、声音、图像等信息

）。

2.数据元素(dataelement)——是数据的基本单位，具有完整确定的实际意义(又称元素、结点，顶点、记录等）。3.数据对象(dataobject)——由性质相同(类型相同)的数据元素组成的集合。数据对象是数据的一个子集。基本概念和术语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是无穷集。基本概念和术语2.1.3数据结构主要涵盖内容

集合线性结构树形结构图状结构4.数据结构(datastructure)——

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

数据元素之间的关系称为结构。基本概念和术语2.1.3数据结构主要涵盖内容四类基本结构：集合结构：

仅同属一个集合线性结构:

一对一（1:1)

树

结

构:

一对多（1:n)

图

结

构:

多对多

(m:n)非线性线

性逻辑结构可细分为4类：

指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。数据的逻辑结构2.1.3数据结构主要涵盖内容

1.线性表

2.栈线性结构3.队列,双队列

4.数组逻辑结构5.字符串

非线性1.树,二叉树结构2.图

数据的逻辑结构分类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)}

解：

上述表达