数据结构 第01局：绪论

总目录

---

前言

本文介绍数据结构基本概念。
一、数据结构概念
二、抽象数据类型
三、算法基本概念

环境

1.语言：C语言
2.参考书：《数据结构(C语言版)》

一、数据结构概念

数据(data)：对客观事物的符号表示。例如：数据库中的数据。

数据元素(data element)：数据的基本单位。例如：表的记录。

数据项(data item)：数据的最小单位，一个数据元素由若干个数据项组成。例如：记录的字段。

数据对象(data object)：性质相同的数据元素的集合，是数据的子集。例如：表。

数据结构(data structure)

(1).概念：相互之间存在一种或多种特定关系的数据元素的集合。

(2).结构：数据元素之间的关系称为结构，有下列4类基本结构：

• 集  合：无关系；

• 线性结构：一对一；

• 树形结构：一对多；

• 图状结构：多对多；

(3).表示：数据结构是一个二元组

    Data_Structure = (D,S)

  其中：D是数据元素的有限集，S是D上关系的有限集。

逻辑结构：结构定义中的关系描述的是数据元素的逻辑关系，因此又称为数据的逻辑结构。

物理结构：结构在计算机中的表示(映像)称为数据的物理结构或存储结构。

位(bit)：计算机中表示信息的最小单位。例如：二进制数的一位。

结点(node)：由若干位组合起来形成的位串称为结点或元素。例如：8位二进制数表示字符。

顺序映像：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。对应顺序存储结构。

非顺序映像：借助指示元素存储地址的指针(pointer)表示数据元素之间的关系。对应非顺序存储结构。

二、抽象数据类型

数据类型(data type)：是值的集合和定义在这个值集上的一组操作的总称。例如：C语言中整型变量，
其值集为某个区间上的整数，定义在其上的操作为加、减、乘、除和取模等算数运算。

原子类型：其值不可分解。例如：C语言中基本类型(整型、字符型等)、指针类型、空类型。

结构类型：其值可分解，由若干元素按某种结构组成。例如：数组。

抽象数据类型(Abstract Data Type，简称ADT)

(1)概念：一个数学模型以及定义在该模型上的一组操作。

(2)类型：抽象数据类型也是由值域和定义在该值域上的一组操作组成。按值的不同特性，分为以下3种类型：

• 原子类型：属原子类型的变量的值不可分解。例如：数位为100的整数。

• 固定聚合类型：属该类型的变量，其值由确定数目的成分按某种结构组成。例如：复数。

• 可变聚合类型：和固定聚合类型相比较，构成可变聚合类型的“值”的成分的数目不确定。例如：有序整数序列，其中序列是可变的。

(3).表示：抽象数据类型是一个三元组

    (D,S,P)

  其中：D是数据对象，S是D上关系集，P是对D的基本操作集。

(4)格式：

其中，数据对象和数据关系的定义用伪码描述，基本操作的定义格式为：

(5)抽象数据类型三元组的定义：

多形数据类型：指其值的成分不确定的数据类型。例如：上图中的Triplet，元素e1，e2，e3可以是整型或字符或字符串。

三、算法基本概念

算法

(1)概念：算法(algorithm)是对特定问题的求解步骤的一种描述。

(2)特性：

• 有穷性：算法总是在执行有穷步后结束，且每一步都可在可接受的时间内完成；

• 确定性：算法每条指令必须有确切含义，不能产生二义性。并且，在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。

• 可行性：算法是可行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。即每步不能出异常。

• 输入：算法有零个或多个输入，这些输入取自于某个特定的对象的集合。

• 输出：算法有一个或多个输出，这些输出是与输入有某些特定关系的量。

(3)设计要求：

• 正确性：算法应当满足具体问题的需求。

• 可读性：算法主要是为了人的阅读和交流，其次才是机器执行。

• 健壮性：当输入数据非法时，算法也能适当地做出反应或进行处理，而不是产生莫名其妙的输出结果。

• 效率与地存储量要求：效率是指算法执行的时间。存储量需求是指算法执行过程中所需要的最大存储空间。

(4)算法效率度量：暂略...(此知识点会在后续文章介绍，写过一些算法后，理解容易些)

后语

本文是对《数据结构(C语言版)》绪论篇概念的总结，后续会用C语言将书本内容作实现，下篇介绍线性表，待续...

---

总目录