【数据结构_1】基本概念和术语!

一.数据结构的研究内容

通常用计算机解决一个问题的步骤：将具体问题抽象为数据模型，根据这个数据模型设计算法，根据算法用某一种语言来编程，调试，运行。

具体问题抽象为数据模型的实质：分析问题，提取操作对象，找出操作对象之间的关系，用数学语言描述——>数据结构

二.数据,数据元素,数据项,数据对象

1.数据（Data）

• 是能够被输入到计算机且能被计算机处理的各种符号的集合
• 信息的载体
• 是对客观事物符号化的表示
• 能够被计算机识别，存储和加工
• 数据被分为数值型数据（整数，实数等）和非数值型数据（文字，图像，图形，声音等）

2.数据元素（Data Element）

• 是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理
• 也简称为元素，或称为记录，结点或顶点
• 一个数据元素可由若干个数据项组成

3.数据项（Data Item）

• 构成数据元素的不可分割的最小单位

4.数据对象（Data Object）

• 性质相同的数据元素的集合

例如：正整数数据对象的集合N={1,2,3,4,5.....}

三.数据结构的内容及两个层次

• 数据元素不是孤立存在的，它们之间存在着某种关系，数据元素相互之间的关系称为结构。
• 是指相互之间存在一种或多种特定关系的数据元素集合。
• 或者说，数据结构是带结构的数据元素的集合。

数据结构包括以下三个方面的内容：

1. 数据元素之间的逻辑关系，也称为逻辑结构。
2. 数据元素及其关系在计算机内存中的表示 （又称为映像）， 称为数据的物理结构或数据的存储结构。
3. 数据的运算和实现，即对数据元素可以施加的操作以及这些操作在相应的存储结构上实现。

1.逻辑结构

• 描述数据结构元素之间的逻辑关系。
• 与数据的存储无关，独立于计算机。
• 是从具体问题抽象出来的数据模型。

(1)逻辑结构的种类

划分方法1：线性结构，非线性结构

线性结构：有且仅有一个开始和一个终端结点，并且所有结点都最多只有一个直接前趋，和一个直接后继。例如：线性表，栈，队列，串

非线性结构：一个结点可能有多个直接前趋和直接后继。例如：树，图

---

划分方法2：集合结构，线性结构，树形结构，图形结构（网状结构）

集合结构：结构中的数据元素之间除了同属一个集合的关系外，无任何其他关系。

线性结构：结构中的数据元素之间存在着一对一的线性关系。

树形结构：结构中的数据元素之间存在着一对多的层次关系。

图形结构或网状结构：结构中的数据元素之间存在着多对多的任意关系。

2.物理结构（存储结构）

• 数据元素及其关系在计算机存储器中的结构（存储方式）。
• 是数据结构在计算机中的表示。

(1)物理结构的种类

• 顺序存储结构（重点）
• 链式存储结构（重点）
• 索引存储结构
• 散列存储结构

顺序存储结构：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示，C语言中用数组来实现顺序存储结构。

链式存储结构：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示，C语言中用指针来实现链式存储结构。

索引存储结构：在存储节点信息的同时，还建立附加的索引表。index

散列存储结构：根据结点的关键字直接计算出该结点的存储地址。

3.逻辑结构与存储结构的关系

• 存储结构是逻辑关系的映像与元素本身的映像。
• 逻辑结构是数据结构的抽象，存储结构是数据结构的实现。
• 两者综合起来就建立了数据元素之间的结构关系。

四.数据类型和抽象数据类型(ADT)

(1)基本概念

数据类型：C语言中提供int,char,float,double等基本数据类型，数组，结构，共用体，枚举等结构数据类型，还有指针，空（void）类型，用户也可以使用typedef自己定义数据类型。数据类型=值的集合+值集合上的一组操作

数据类型的作用：约束变量或常量的取值范围，约束变量或常量的操作。

抽象数据类型：是指一个数学模型以及定义在此数学模型上的一组操作。由用户定义，从问题抽象出数据模型（逻辑结构）。还包括定义在数据模型上的一组抽象运算（相关操作）。不考虑计算机内的具体存储结构与运算的具体实现算法。

抽象数据类型的定义格式：

ADT 抽象数据类型名{
数据对象：<数据对象的定义>
数据关系：<数据关系的定义>
基本操作：<基本操作的定义>
}ADT 抽象数据类型名
//其中数据对象，数据关系的定义用伪代码描述

基本操作定义格式：

基本操作名(参数表)
初始条件：<初始条件描述>
操作结果：<操作结果描述>

参数表：赋值参数，只为操作提供输入值。引用参数 ，以&打头，除可提供输入值外，还将返回操作结果。

初始条件：描述操作执行之前数据结构和参数应满足的条件，若不满足。则操作失败，并返回相应出错信息。若初始条件为空，则省略。

操作结果：说明操作正常完成之后，数据结构的变化状况和应返回的结果。

(2)抽象数据类型定义举例

Circle的定义

ADT Circle{
操作对象：D={r,x,y|r,x,y均为实数}
数据关系：R={<r,x,y>|r是半径,<x,y>是圆心坐标}
基本操作：
Circle(&C,r,x,y)
操作结果：构造一个圆。
double Area(C)
初始条件：圆已存在。
操作结果：计算面积。
double Circumference(C)
初始条件：圆已存在。
操作结果：计算周长。
  ...
}ADT Circle

复数的定义

ADT Complex{
D={r1,r2|r1,r2都是实数}
R={<r1,r2>|r1是实数,r2是虚数}
assign(&Z,v1,v2)
初始条件：空的复数Z已存在
操作结果：构造复数Z,r1,r2分别被赋以参数v1,v2的值。
destroy(&Z)
初始条件：复数C已存在
操作条件：复数C被销毁
GetReal(Z,&realPart)
初始条件：复数已存在
操作结果：用realPart返回复数Z的实数值
GetImag(Z,&ImagPart)
初始条件：复数已存在
操作结果：用ImagPart返回复数Z的虚部值
  ...
}ADT Complex

---

持续更新【数据结构】系列！有需要的请移步​​秃头程序媛主页​​！