2018/10/9
华侨大学数学系 黄建新
1.1 引言
• 众所周知，二十世纪四十年代，电子数字计算机问世的直接原因是解
决弹道学的计算问题。早期，电子计算机的应用范围，几乎只局限于 科学和工程的计算，其处理的对象是纯数值性的信息，通常，人们把 这类问题称为数值计算。 • 近三十年来，电子计算机的发展异常迅猛，这不仅表现在计算机本身 运算速度不断提高、信息存储量日益扩大、价格逐步下降，更重要的 是计算机广泛地应用于情报检索、企业管理、系统工程等方面，已远 远超出了科技计算的范围，而渗透到人类社会活动的一切领域。与此 相应，计算机的处理对象也从简单的纯数值性信息发展到非数值性的 和具有一定结构的信息。
• 为了叙述上的方便和避免产生混淆，通常我们把数据的逻辑结构
统称为数据结构，把数据的物理结构统称为存储结构（ Storage Structure）。
2018/10/9
华侨大学数学系 黄建新

四种基本基本结构： （1）集合：结构中的数据元素之间除了“同属于一个集合”的关 系外，别无其他关系。 （2）线性结构：结构中的数据元素之间存在一个对一个的关系。 如：图书馆的书目检索系统 （3）树形结构：结构中的数据元素存在一个对多个的关系。 如：计算机和人对奕问题 工厂的组织管理 （4）图状结构：结构中的数据元素存在多个对多个的关系。 如：多叉路口的交通灯管理问题 最短路径问题
2018/10/9
华侨大学数学系 黄建新
1.3 什么是数据结构
• 计算机解决一个具体问题时，大致需要经过下列几个步骤：首先
要从具体问题中抽象出一个适当的数学模型，然后设计一个解此 数学模型的算法（Algorithm），最后编出程序、进行测试、调整 直至得到最终解答。寻求数学模型的实质是分析问题，从中提取 操作的对象，并找出这些操作对象之间含有的关系，然后用数学 的语言加以描述。 • 计算机算法与数据的结构密切相关，算法无不依附于具体的数据 结构，数据结构直接关系到算法的选择和效率。 • 运算是由计算机来完成，这就要设计相应的插入、删除和修改的 算法 。也就是说，数据结构还需要给出每种结构类型所定义的各 种运算的算法。 • 直观定义：数据结构是研究程序设计中计算机操作的对象以及它 们之间的关系和运算的一门学科。
2018/10/9
华侨大学数学系 黄建新
1.2 数据结构的发展简史及其 在计算机科学中所处的地位
• 发展史：
1、 “数据结构”作为一门独立的课程在国外是从1968年才开始设 立的。 2、 1968年美国唐·欧·克努特教授开创了数据结构的最初体系，他 所著的《计算机程序设计技巧》第一卷《基本算法》是第一本 较系统地阐述数据的逻辑结构和存储结构及其操作的著作。
2018/10/9
华侨大学数学系 黄建新
基本操作有两种参数：赋值参数只为操作提供输入值；引用参数以& 打头，除可提供输入值外，还将返回操作结果。 例 抽象数据类型三元组的定义： ADT Triplet{ 数据对象：D={e1,e2,e3|e1,e2,e3属于Elemset} 数据关系：R1={<e1,e2>,<e2,e3>} 基本操作： InitTriplet(&T,v1,v2,v3) 操作结果：构造了三元组T,元素e1,e2,和e3分别被赋以 参数v1,v2和v3的值。 DestroyTriplet(&T) 操作结果：三元组T被销毁。 Get（T,I,&e) 初始条件：三元组T已存在，1<=I<=3 操作结果：用e返回T的第I元的值。}
2018/10/9
华侨大学数学系 黄建新


因此，再把电子数字计算机简单地看作是进行数值计算的工具，把 数据仅理解为纯数值性的信息，就显得太狭隘了。现代计算机科学 的观点，是把计算机程序处理的一切数值的、非数值的信息，乃至 程序统称为数据（Data），而电子计算机则是加工处理数据（信息） 的工具。 由于数据的表示方法和组织形式直接关系到程序对数据的处理效率， 而系统程序和许多应用程序的规模很大，结构相当复杂，处理对象 又多为非数值性数据。因此，单凭程序设计人员的经验和技巧已难 以设计出效率高、可靠性强的程序。于是，就要求人们对计算机程 序加工的对象进行系统的研究，即研究数据的特性以及数据之间存 在的关系——数据结构（Date Structure）。
2018/10/9
华侨大学数学系 黄建新
• 地位： 1. “数据结构”在计算机科学中是一门综合性的专业 2. 3.
基础课。 数据结构是介于数学、计算机硬件和计算机软件三 者之间的一门核心课程。 数据结构这一门课的内容不仅是一般程序设计（特 别是非数值性程序设计）的基础，而且是设计和实 现编译程序、操作系统、数据库系统及其他系统程 序的重要基础。
2018/10/9
华侨大学数学系 黄建新
数据的物理结构方面 二种类型：顺序存储结构和非顺序存储结构 顺序存储结构：逻辑上相邻的数据元素存储在物理位置上相比邻 的存储单元里，其关系由存储单元的邻接关系来 体现（向量、数组）。 非顺序存储结构：数据元素在计算机内任意位置上存放，其关系 用指针来链接，称为链式存储结构-链表。 按指针个数分为：单链表、双向链表、多重链表 索引存储结构：按（地址关键字）的偶对集合，关键字是唯一标 识结点；地址指出该结点的存储地址。 散列存储结构：根据结点关键字来直接算出该结点的存储地址。
2018/10/9
华侨大学数学系 黄建新
表 1-1 个人书库
2018/10/9
华侨大学数学系 黄建新
2．结点
• 结点也叫数据元素，它是组成数据的基本单位。在程序中通常把
结点作为一个整体进行考虑和处理。例如，在表1-1所示的个人书 库中，为了便于处理，把其中的每一行（代表一本书）作为一个 基本单位来考虑，故该数据由10个结点构成。 • 一般情况下，一个结点中含有若干个字段（也叫数据项）。例如， 在表1-1所示的表格数据中，每个结点都有登录号、书号、书名、 作者、出版社和价格等六个字段构成。字段是构成数据的最小单 位。
可以表示成数组，存放在内存中；也可以表示成文件，存放在磁 盘上，等等。
2018/10/9
华侨大学数学系 黄建新
5．数据处理
• 数据处理是指对数据进行查找、插入、删除、合并、排序、统计
以及简单计算等的操作过程。在早期，计算机主要用于科学和工 程计算，进入八十年代以后，计算机主要用于数据处理。据有关 统计资料表明，现在计算机用于数据处理的时间比例达到80%以 上，随着时间的推移和计算机应用的进一步普及，计算机用于数 据处理的时间比例必将进一步增大。
2018/10/9
华侨大学数学系 黄建新
6．数据结构（Data Structure）
• 数据结构是研究数据元素（Data Element）之间抽象化的相互关
系和这种关系在计算机中的存储表示（即所谓数据的逻辑结构和 物理结构），并对这种结构定义相适应的运算，设计出相应的算 法，而且确保经过这些运算后所得到的新结构仍然是原来的结构 类型。
2018/10/9
华侨大学数学系 黄建新
第1章 绪论
[目的] 介绍数据结构中常用的基本概念和术语以及学习数据结构的意 义。 [要求]了解本章介绍的各种基本概念和术语，掌握算法描述和分析的方 法。 [重点]了解数据结构的逻辑结构、存储结构及数据的运算三方面的概念 及相互关系。 [难点]算法复杂度的分析方法。
2018/10/9
华侨大学数学系 黄建新
3．逻辑结构
• 结点和结点之间的逻辑关系称为数据的逻辑结构。
• 在表1-1所示的表格数据中，各结点之间在逻辑上有一种线性关系，
它指出了10个结点在表中的排列顺序。根据这种线性关系，可以 看出表中第一本书是什么书，第二本书是什么书，等等。 4．存储结构
• 数据在计算机中的存储表示称为数据的存储结构。 • 在表1-1所示的表格数据在计算机中可以有多种存储表示，例如，
同一个逻辑结构可以有不同的内部存储结构；反之，数据的存 储结构一定要映像数据之间的逻辑关系。
数据结构的形式定义：数据结构是一个二元组 data_structure=(D,S) 其中：D是数据元素的有限集，S是D上关系的有限集。
2018/10/9
华侨大学数学系 黄建新
例1 一种结构 lineority=(K,R） K={k1,k2,k3,k4,k5,k6,k7} R={r} r={<k3,k1>,<k1,k5>,<k5,k6>,<k6,k4>,<k4,k2>,<k2,k 7>} 则有：k3->k1->k5->k6->k4->k2->k7 一种线性结构 例2 tree=(K,R) K={01,02,03,04,05,06,07,08} R={r} r={<01,02>,<01,03>,<02,04>,<02,05>,<03,06>,<03, 07>, <07,08>} 树形结构
2018/10/9
华侨大学数学系 黄建新
1.4 基本概念和术语
1．数据
数据是人们利用文字符号、数字符号以及其他规定的符号对 现实世界的事物及其活动所做的描述。在计算机科学中，数据的含义 非常广泛，我们把一切能够输入到计算机中并被计算机程序处理的信 息，包括文字、表格、图象等，都称为数据。例如，一个个人书库管 理程序所要处理的数据可能是一张如表1-1所示的表格。
Hale Waihona Puke 2018/10/9华侨大学数学系 黄建新
抽象数据类型（Abstract Data Type,ADT)是指一个数学模型 以及定义在该模型上的一组操作，它仅取决于它的一组逻辑特性， 而与其在计算机内部如何表示和实现无关。 一个含抽象数据类型的软件模块通常应包含定义、表示和实现 三个部分。 抽象数据类型的三元组表示 (D S P),其中，D是数据对象，S是 D上的关系集，P是对D的基本操作集。 ADT抽象数据类型名{ 数据对象：<数据对象的定义> 数据关系：<数据关系的定义> 基本操作：<基本操作的定义> }ADT抽象数据类型名 其中，数据对象和数据关系的定义用伪码描述，基本操作的定义 格式为： 基本操作名（参数表） 初始条件：<初始条件描述> 操作结果：<操作结果描述>