文档介绍：算法与数据结构
教材：《数据结构(C语言版)》。严蔚敏，吴伟民编著。清华大学出版社。
参考文献：
1 《数据结构》。张选平，雷咏梅编，严蔚敏审。机械工业出版社。
2 《数据{ <k1, k3>，<k1, k8>，<k2, k3>，<k2, k4>，<k2, k5>，<k3, k9>，<k5, k6>，<k8, k9>，<k9, k7>，<k4, k7>，<k4, k6> }
画出这逻辑结构的图示，并确定那些是起点，那些是终点
数据结构的形式定义
图1-3 四类基本结构图
整理ppt
10
数据结构的存储方式
数据元素之间的关系可以是元素之间代表某种含义的自然关系，也可以是为处理问题方便而人为定义的关系，这种自然或人为定义的 “关系”称为数据元素之间的逻辑关系，相应的结构称为逻辑结构。
数据结构在计算机内存中的存储包括数据元素的存储和元素之间的关系的表示。
元素之间的关系在计算机中有两种不同的表示方法：顺序表示和非顺序表示。由此得出两种不同的存储结构：顺序存储结构和链式存储结构。
顺序存储结构：用数据元素在存储器中的相对位置来表示数据元素之间的逻辑结构(关系)。
整理ppt
11
链式存储结构：在每一个数据元素中增加一个存放另一个元素地址的指针(pointer )，用该指针来表示数据元素之间的逻辑结构(关系)。
例：设有数据集合A={,,,-,} ，两种不同的存储结构。
顺序结构：数据元素存放的地址是连续的；
链式结构：数据元素存放的地址是否连续没有要求。
数据的逻辑结构和物理结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。
在C语言中，用一维数组表示顺序存储结构；用结构体类型表示链式存储结构。
整理ppt
12
数据结构的三个组成部分：
逻辑结构：数据元素之间逻辑关系的描述
D_S=（D，S）
存储结构：数据元素在计算机中的存储及其逻辑关系的表现称为数据的存储结构或物理结构。
数据操作：对数据要进行的运算。
本课程中将要讨论的三种逻辑结构及其采用的存储结构如图1-4所示。
整理ppt
13
数据的逻辑结构
非线性结构
集合
图状结构
有向图
无向图
树形结构
一般树
二叉树
线性结构
一般线性表
线性表推广
广义表
数组
串
受限线性表
栈和队列
图1-5 数据逻辑结构层次关系图
图1-4 逻辑结构与所采用的存储结构
线性表
树
图
顺序存储结构
链式存储结构
复合存储结构
逻辑结构
物理结构
整理ppt
14
数据类型(Data Type)：指的是一个值的集合和定义在该值集上的一组操作的总称。
数据类型是和数据结构密切相关的一个概念。在C语言中数据类型有：基本类型和构造类型。
数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。
数据类型
整理ppt
15
数据结构的主要运算包括：
⑴ 建立(Create)一个数据结构；
⑵ 消除(Destroy)一个数据结构；
⑶ 从一个数据结构中删除(Delete)一个数据元素；
⑷ 把一个数据元素插入(Insert)到一个数据结构中；
⑸ 对一个数据结构进行访问(Access)；
⑹ 对一个数据结构(中的数据元素)进行修改(Modify)；
⑺ 对一个数据结构进行排序(Sort)；
⑻ 对一个数据结构进行查找(Search)。
数据结构的运算
整理ppt
16
抽象数据类型(Abstract Data Type ，简称ADT)：是指一个数学模型以及定义在该模型上的一组操作。
ADT的定义仅是一组逻辑特性描述，与其在计算机内的表示和实现无关。因此，不论ADT的内部结构如何变化，只要其数学特性不变，都不影响其外部使用。
ADT的形式化定义是三元组：ADT=(D，S，P)
其中：D是数据对象，S是D上的关系集，P是对D的基本操作集。
抽象数据类型
整理ppt
17
ADT的一般定义形式是：
ADT <抽象数据类型名>{
数据对象： <数据对象的定义>
数据关系： <数据关系的定义>
基本操作： <基本操作的定义>
} ADT <抽象数据类型名>
其中数据对象和数据关系的定义用伪码描述。
基本操作的定义是：