算法与数据结构教材：《数据结构(C语言版)》。严蔚敏，吴伟民 编著。清华大学出版社。

参考文献：1 《数据结构》 。张选平，雷咏梅 编， 严蔚敏 审。 机械工业出版社。 2 《数据结构与算法分析》。Clifford A. Shaffer著， 张 铭，刘晓丹 译。电子工业出版社。 3 《数据结构习题与解析(C语实言版)》。李春葆。 清华大学出版社。 4 《数据结构与算法》。夏克俭 编著。国防工业出 版社。

第1章

绪 论

目前，计算机已深入到社会生活的各个领域，其应 用已不再仅仅局限于科学计算，而更多的是用于控制， 管理及数据处理等非数值计算领域。计算机是一门研究 用计算机进行信息表示和处理的科学。这里面涉及到两 个问题：信息的表示，信息的处理。

信息的表示和组织又直接关系到处理信息的程序的 效率。随着应用问题的不断复杂，导致信息量剧增与信 息范围的拓宽，使许多系统程序和应用程序的规模很大， 结构又相当复杂。因此，必须分析待处理问题中的对象 的特征及各对象之间存在的关系，这就是数据结构这门 课所要研究的问题。

计算机求解问题的一般步骤编写解决实际问题的程序的一般过程：– 如何用数据形式描述问题?—即由问题抽象出一个

适当的数学模型;– 问题所涉及的数据量大小及数据之间的关系; – 如何在计算机中存储数据及体现数据之间的关系? – 处理问题时需要对数据作何种运算?

– 所编写的程序的性能是否良好?

上面所列举的问题基本上由数据结构这门课程来回答。

1.1 数据结构及其概念《算法与数据结构》是计算机科学中的一门综合性

专业基础课。是介于数学、计算机硬件、计算机软件三 者之间的一门核心课程，不仅是一般程序设计的基础， 而且是设计和实现编译程序、操作系统、数据库系统及 其他系统程序和大型应用程序的重要基础。

1.1.1 数据结构的例子例1:电话号码查询系统设有一个电话号码薄，它记录了N个人的名字和其 相应的电话号码，假定按如下形式安排：(a1, b1),(a2, b2),…(an, bn),其中ai, bi(i=1,2…n) 分别表示某人的 名字和电话号码。 本问题是一种典型的表格问题。如 表1-1,数据与数据成简单的一对一的线性关系。姓名 陈海 李四锋 。。。 电话号码 13612345588 13056112345 。。。

表1-1 线性表结构

例2:磁盘目录文件系统磁盘根目录下有很多子目录 及文件，每个子目录里又可以包 含多个子目录及文件，但每个子 目录只有一个父目录，依此类推：本问题是一种典型的树型结 构问题，如图1-1 ,数据与数据 成一对多的关系，是一种典型的 非线性关系结构—树形结构。

图1-

1

树形结构

例3:交通网络图从一个地方到另外一个地方可以有多条路径。本问 题是一种典型的网状结构问题，数据与数据成多对多的 关系，是一种非线性关系结构。广州佛山 惠州 东莞 中山

深圳珠海

图1-2

网状结构

1.1.2 基本概念和术语数据(Data) :是客观事物的符号表示。在计算机科 学中指的是所有能输入到计算机中并被计算机程序处理 的符号的总称。 数据元素(Data Element) :是数据的基本单位，在 程序中通常作为一个整体来进行考虑和处理。 一个数据元素可由若干个数据项(Data Item)组成。 数据项是数据的不可分割的最小单位。数据项是对客观 事物某一方面特性的数据描述。 数据对象(Data Object):是性质相同的数据元素的集 合，是数据的一个子集。如字符集合C={ A‘,‘B‘,‘C,…} 。

数据结构(Data Structure):是指相互之间具有(存在) 一定联系(关系)的数据元素的集合。元素之间的相互联 系(关系)称为逻辑结构。数据元素之间的逻辑结构有四 种基本类型，如图1-3所示。

① 集合：结构中的数据元素除了“同属于一个集合” 外，没有其它关系。

② 线性结构：结构中的数据元素之间存在一对一的 关系。③ 树型结构：结构中的数据元素之间存在一对多的 关系。 ④ 图状结构或网状结构：结构中的数据元素之间存 在多对多的关系。

图1-3

四类基本结构图

1.1.3 数据结构的形式定义数据结构的形式定义是一个二元组：Data-Structure=(D,S)

其中：D是数据元素的有限集，S是D上关系的有限集。例2:设数据逻辑结构B=(K,R)K={k1, k2, …, k9}

R={ <k1, k3>,<k1, k8>,<k2, k3>,<k2, k4>,<k2, k5>,<k3, k9>, <k5, k6>,<k8, k9>,<k9, k7>,<k4, k7>,<k4, k6> }画出这逻辑结构的图示，并确定那些是起点，那些是终点

数据元素之间的关系可以是元素之间代表某种含义 的自然关系，也可以是为处理问题方便而人为定义的 关系，这种自然或人为定义的 “关系”称为数据元素 之间的逻辑关系，相应的结构称为逻辑结构。

1.1.4 数据结构的存储方式数据结构在计算机内存中的存储包括数据元素的 存储和元素之间的关系的表示。

元素之间的关系在计算机中有两种不同的表示方法： 顺序表示和非顺序表示。由此得出两种不同的存储结构： 顺序存储结构和链式存储结构。– 顺序存储结构：用数据元素在存储器中的相对位

置来表示数据元素之间的逻辑结构(关系)。

– 链式存储结构：在每一个数据元素中增加一个存

放另一个元素地址的指针(pointer ),用该指针来表 示数据元素之间的逻辑结构(关系)。

例：设有数据集合A={3.0,2.3,5.0,-8.5,11.0} ,两种不同的存储结构

。 – 顺序结构：数据元素存放的地址是连续的； – 链式结构：数据元素存放的地址是否连续没有要 求。

数据的逻辑结构和物理结构是密不可分的两个方面， 一个算法的设计取决于所选定的逻辑结构，而算法的实 现依赖于所采用的存储结构。 在C语言中，用一维数组表示顺序存储结构；用结 构体类型表示链式存储结构。

数据结构的三个组成部分： 逻辑结构： 数据元素之间逻辑关系的描述D_S=(D,S)

存储结构： 数据元素在计算机中的存储及其逻辑关系的表现称为数据的存储结构或物理结构。

数据操作： 对数据要进行的运算。本课程中将要讨论的三种逻辑结构及其采用的存储 结构如图1-4所示。

逻辑结构线性表 树 图图1-4

物理结构顺序存储结构

链式存储结构复合存储结构逻辑结构与所采用的存储结构数据的逻辑结构

线性结构 受限线性表 线性表推广 数组 集合 广义表

非线性结构 树形结构 一般树 二叉树 图状结构 有向图 无向图

一般线性表

栈和队列 串

图1-5

数据逻辑结构层次关系图

1.1.5 数据类型数据类型(Data Type):指的是一个值的集合和定 义在该值集上的一组操作的总称。 数据类型是和数据结构密切相关的一个概念。 在C 语言中数据类型有：基本类型和构造类型。

数据结构不同于数据类型，也不同于数据对象，它 不仅要描述数据类型的数据对象，而且要描述数据对象 各元素之间的相互关系。

1.1.6 数据结构的运算数据结构的主要运算包括： ⑴ 建立(Create)一个数据结构； ⑵ 消除(Destroy)一个数据结构； ⑶ 从一个数据结构中删除(Delete)一个数据元素； ⑷ 把一个数据元素插入(Insert)到一个数据结构中； ⑸ 对一个数据结构进行访问(Access); ⑹ 对一个数据结构(中的数据元素)进行修改 (Modify); ⑺ 对一个数据结构进行排序(Sort); ⑻ 对一个数据结构进行查找(Search)。