数据结构基本概念

第一课

本课主题：数据结构的基本概念和术语

教学目的：了解数据结构的基本概念，理解常用术语

教学重点：基本概念：数据、数据元素、数据结构(逻辑结构和存储结构)

教学难点：数据元素间的四种数据结构

教学内容：

一、基本概念和术语

1．数据（Data）：是人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的抽象描述。（在计算机领域中：能被计算机输入、存储、处理、输出的一切信息）

例：下表中李明的数学考试成绩为60分，60就是该同学的成绩数据

再例如我们在网络上看的电视节目、下载的mp3歌曲等等图像、声音文件等。

2．数据元素（Data Element简称元素）：数据的基本单位，也称节点（node）或记录（record）。可以再由不可分割的数据项组成。

⏹数据记录（Data Record）：数据处理领域组织数据的基本单位。

3.数据对象(Data Object):是性质相同的数据元素的集合。如上例：一个班级的成绩表可以看作一个数据对象。

4.数据处理（Data Processing ）:指对数据进行检索、插入、删除、合并、拆分、排序、统计、简单计算、转换、输入、输出等操作过程。

5.数据结构（Data Structure ）:是指互相之间存在着一种或多种关系的数据元素的集合。 在任何问题中，数据元素之间都不会是孤立的，在它们之间都存在着这样或那样的关系，这种数据元素之间的关系称为结构。

(1).数据结构又分为数据的逻辑结构和数据的存储结构这两个方面，我们时常把数据的逻辑

结构简称为数据结构，而在讨论数据的存储结构时则必须指明是数据的存储结构。

⏹ 数据的逻辑结构—只抽象反映数据元素的逻辑关系，独立于计算机，是数据本身所

固有的。

⏹ 数据的存储（物理）结构—数据的逻辑结构在计算机存储器中的实现，必须依赖于

计算机。

(2).数据结构从逻辑结构划分为： ⏹ 集合结构

集合结构是指数据中各元素之间没有任何次序。如一个单位的所有职工，可以认为他们之间没有任何次序，为集合结构。

⏹ 线性结构

线性结构是指数据中各元素之间具有1对1的先后次序关系。如学生成绩表中，各个成绩记录之间是按照学生的学号的先后次序排列的。所以，成绩表结构是线性结构。

⏹ 树结构

树结构是指数据中各元素之间具有1对多的先后次序关系，并且只有一个元素称为树根结点，其余均为树枝结点和树叶结点。如在一个企业的组织机构中，总经理只有一个，相当于是树根；它下属多个部门，每个部门又各有一个部门经理，相当于是树枝；每个部门又有多名员工，属于部门经理领导，相当于是树叶。所以，企业的组织结构是一个树结构。

⏹ 图结构

图结构是指数据中各元素之间具有多对多的关系。这是数据结构中最复杂的结构。如在一个城市交通图中，所有道路连接成一个复杂的图结构，交叉路口就是图中的顶点，每条道路就是图中的边，从一个交叉路口可以到达与其连接的其他交叉路口。

(a) 集合结构

(b) 线性结构

(c)

树结构

(d) 图结构

(3).数据结构从存贮结构划分为：

⏹顺序存贮（向量存贮）

所有元素存放在一片连续的存贮单元中，逻辑上相邻的元素存放到计算机内存仍然相邻。

⏹链式存贮

所有元素存放在可以不连续的存贮单元中，但元素之间的关系可以通过地址确定，逻辑上相邻的元素存放到计算机内存后不一定是相邻的。

⏹索引存贮

使用该方存放元素的同时，还建立附加的索引表，索引表中的每一项称为索引项，索引项的一般形式是：（关键字，地址），其中的关键字是能唯一标识一个结点的那些数据项。

⏹散列存贮

通过构造散列函数，用函数的值来确定元素存放的地址。

(4).数据结构的描述

数据结构可用二元组B=(K,R)的形式来描述。

其中，K={a1,a2,…,an}为元素集合，K={ki|1≤i≤n,n≥0}

R={r1,r2,…,rm}为关系的集合, R={rj| 1≤j≤m,m≥0}

说明：1、n=0，则K为空集，B无结构。

2、m=0，R为空集，K中元素之间不存在任何关系，彼此独立。

3、K上的关系r是序偶集合，表示：(x,y）→无向；<x,y> →有向。（其中x为y的直接前趋；y为x的直接后继）。

例1-5 设有一个线性表(a1,a2,a3,a4,a5)，它的抽象描述可表示为D=(K,R),其中K={a1,a2,a3,a4,a5},R={<a1,a2>,<a2,a3>,<a3,a4>,<a4,a5>}，则它的逻辑结构用下图描述

(5). 数据类型（Data Type）：对数据的取值范围、每一数据的结构以及允许施加的操作

的一种描述。

数据类型分类：

⏹简单类型：每个数据都无法再分割。（整型、实型等）

⏹结构类型：结构类型中的数据可以分解为若干简单类型或结构数据。（数组、记录、

结构体、串、文件等）

(6). 抽象数据类型（Abstract Data Type-ADT）:由一组数据结构和在该组数据结构上的一组操作所组成。

在定义抽象数据类型中的数据部分和操作部分时，要求只定义数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现。（可通过C++中的类类型来描述）描述抽象数据类型的一般格式：

ADT <抽象数据类型名> is

Data:

<数据描述>

Operations: