数据结构 第一章 概论

数据结构 精讲一 第一章 概论¹

1 引言

1. 著名的瑞士计算机科学家沃思教授曾提出： 算法+数据结构=程序。

   这里的数据结构指的是数据的逻辑结构和存储结构，而算法则是对数据运算的描述。由此可见，程序设计的实质是针对实际问题选择一种好的数据结构和设计一个好的算法，而好的算法在很大程度上取决于描述实际问题的数据结构。

2 基本概念和常用术语

2.1. 数据结构包含的内容

1. 常用的术语

   • 数据

     (data）是描述客观事物的数、字符以及能输入计算机中并被计算机处理的符号的集合。例如，一个代数方程的求解程序中所使用的数据是整数和实数，而一个文本编辑程序使用的数据是字符串。随着计算机的发展以及计算机应用领域的扩大，数据的含义也随之拓展了。例如，当今计算机可以处理的图形、图像、声音等也都属于数据的范畴。

   • 数据元素

     (data dement)是数据的**基本单位**。如前例中目录卡片表中的一张卡片(表格中的一行)、树中的一个结点、图中的一个顶点等都是数据元素。有时一个数据元素可由若干个数据项（也称为字段、域、属性)组成，**数据项**是具有独立含义的**最小标识单位**，如图书卡片信息中的登录号、书名、作者等。

   • 数据对象

     (data object)是具有相同性质的数据元素的集合，是数据的一个子集。例如，大写字母数据对象就是集合{ ‘A’, ‘B’，…，’Z’}。

2. 数据元素之间的逻辑（或抽象）关系，也称为数据的逻辑结构。

   

   • 线性结构

     的特征是：数据元素（结点）之间存在着一对一的关系，且结构中仅有一个开始结点和一个终端结点，其余结点都是仅有一个直接前趋和一个直接后继。

     

   • 非线性结构

     的特征是：数据元素之间存在着一对多或多对多的关系，即一个结点可能有多个直接前趋和多个直接后继。该结构包括树形结构、图形结构和网状结构等。

     

3. 数据元素及其关系在计算机内的存储方式，称为数据的存储结构（物理结构）。

   • 数据的存储结构可以用以下四种基本的存储方法实现：

     1. 顺序存储方法

        。顺序存储方法是把逻辑上相邻的结点存储 在物理位置上也相邻的连续存储单元里，由此得到的存储结构称为顺序存储结构。

     2. 链接存储方法

        。链接存储方法是用一组不一定连续的存储单元存储逻辑上相邻的元素，元素间的逻辑关系是由附加的指针域表示的，由此得到的存储结构称为链式存储结构。它通常是借助于程序设计语言中的指针来描述的。

     3. 索引存储方法

        。索引存储方法通常是在存储元素信息的同时，还建立附加的索引表。表中的索引项一般形式是：（关键字，地址）。关键字是能唯一标识一个元素的一个数据项或多个数据项的组合。

     4. 散列存储方法

        。散列存储方法的基本思想是根据元素的关键字直接计算出该元素的存储地址。

     无论怎样定义数据结构，都应该将数据的逻辑结构、存储结构及运算这三方面看成一个整体。因此，存储结构是数据结构不可缺少的一个方面。

4. 数据的运算

   ，即对数据元素施加的操作（行为）

   数据的运算是定义在数据的逻辑结构上的，每种逻辑结构都有一个运算的集合，最常用的运算有：检索、插入、删除、更新、排序等。数据运算是数据结构不可分割的一个方面，在给定了数据的逻辑结构和存储结构之后，按定义的运算集合及其运算性质的不同，可能导致完全不同的数据结构。例如，若对线性表的插入、删除运算限制在表的一端进行，则该线性表称为栈；若对线性表的插入运算限制在表的一端，而删除运算限制在表的另一端，则该线性表称为队列。

3 算法的描述和分析

3.1. 算法描述

1. 算法是由若干条指令组成的有穷序列，其中每条指令表示一个或多个操作。此外，算法还必须满足以下五个准则：
   • 输入

     。算法开始前必须给算法中用到的变量初始化，一个算法的输入可以包含零个或多个数据。

   • 输出

     。算法至少有一个或多个输出。

   • 有穷性

     。算法中每一条指令的执行次数都是有限的，而且每一步都在有穷时间内完成，即算法必须在执行有限步后结束。

   • 确定性

     。算法中每一条指令的含义都必须明确，无二义性。

   • 可行性

     。算法是可行的，即算法中描述的操作都可以通过有限次的基本运算来实现

3.2. 算法分析

1. 所谓一个算法的正确性，是指对于一切合法的输入数据，该算法经过有限时间的执行都能得到正确的结果。此外，应主要考虑如下几点：

   • 执行算法所耗费的时间，即时间复杂性。
   • 执行算法所耗费的存储空间，主要是辅助空间

     ，即空间复杂性。

   • 算法应易于理解、易于编程，易于调试等，即可读性和可操作性。

   在以上几点中，最主要的是 时间复杂性。

2. 时间复杂性

3. 按数量级递增排列，依次为：

   常数阶 O(1)、对数阶 O(log~2~n)、线性阶 O(n)、线性对数阶 O(nlog~2~n)、平方阶〇(n^2^)、立方阶〇(n^3^)、 . . . k 次方阶O(n^k^)、指数阶 O(2^n^)和阶乘阶O(n!)。

4. 类似于时间复杂度，一个算法的空间复杂度 S(n)定义为该算法所耗费的存储空间，它是对一个算法在运行过程中临时占用存储空间大小的度量，是问题规模 n 的函数。

1. 尚德机构 ↩ ↩