数据结构考研讲义

计算机考研基础讲义数据结构基础数据结构是计算机科学中的一门基础课程，它研究的是数据的存储方式和组织方式，以及对数据进行操作和处理的方法。

在计算机考研中，数据结构是一个重要的考点，掌握好数据结构的基础知识对于考研复习和实际编程都有很大的帮助。

本文将介绍数据结构的基础知识，包括常见的数据结构类型和其应用场景。

首先，我们来了解一下数据结构的基本概念。

数据结构可以分为线性结构和非线性结构两种。

线性结构中的元素是一对一关系，如数组、链表等；而非线性结构中的元素存在一对多或多对多关系，如树、图等。

数据结构还可以分为静态结构和动态结构两种。

静态结构指的是一旦创建后就不能再改变其结构，而动态结构则可以根据需要动态地插入、删除元素。

下面，我们来介绍一些常见的数据结构类型及其应用场景。

1. 数组(Array)数组是一种线性结构，元素在内存中是连续存储的，可以通过索引快速访问元素。

数组适用于元素数量固定并且需要频繁访问的场景。

例如，存储学生的成绩、记录时间序列数据等。

2. 链表(Linked List)链表也是一种线性结构，元素在内存中不一定连续存储，而是通过指针相连。

链表适用于需要频繁插入和删除元素的场景，因为插入和删除操作只需要改变指针指向，不需要移动元素。

例如，实现栈和队列、实现高效的内存分配等。

3. 栈(Stack)栈是一种特殊的线性结构，只允许在一端进行插入和删除操作。

栈遵循先进后出(LIFO)的原则，在函数调用、括号匹配、表达式求值等场景中广泛应用。

4. 队列(Queue)队列也是一种特殊的线性结构，允许在一端插入元素，在另一端删除元素。

队列遵循先进先出(FIFO)的原则，常用于处理大量数据的场景，如任务调度、消息传递等。

5. 树(Tree)树是一种非线性结构，由节点和边组成。

树的特点是每个节点最多有一个父节点和多个子节点，节点之间存在层次关系。

树在文件系统、数据库索引、图形算法等方面有广泛的应用。

6. 图(Graph)图也是一种非线性结构，由节点和边组成。

§1.3 数Biblioteka 的逻辑结构三、数据结构的分类
线性结构：除了一个根结点外，其他各结点有
唯一的前驱；除了一个终端结点外，其他各结点 有唯一的后继。
树状结构：除了一个根结点外，各结点有唯一
的前驱；所有的结点都可以有多个后继。
网状结构：各结点可以有多个前驱或多个后继。
§1.4 数据的存储结构
数据结构在计算机中的表示称为数据的存储结构。 数据结构包括结点的值及结点之间的关系，其存储结
{q->link=p->link;p->link=q;} }
§2.3 线性表的链接存储结构及运算
4、删除单链表中的结点X 删除单链表中的结点X ，并由系统收回其占用的存储空 间。过程如下：
（1）设定两指针p 和q ，p 指针指向被删除结点；q 为 跟踪结点，指向被删除结点的前驱结点; （2）p 从表头指针head指向的第一个结点开始向后依 次进行搜索。当p->data等于X 时，被删除结点找到。 （3）修改p 的前驱结点q 的指针域：使被删除结点的 后继结点成为其前驱结点的后继结点，既q->link=p>link，p结点被删除，然后再释放存储空间。
}
§2.2 线性表的顺序存储结构及运算
二、线性表的运算 3、查找运算的算法描述： int fincl(ET x,ET s[],int n) {int j; for (i=0;i<n;i++)
if (x==s[i]) break; if (i==n) return(0); return(i+1) }
§2.3 线性表的链接存储结构及运算
三、循环链表
head
非空表（a) head
空表（b)

树
01
02
03
树的定义
树是一种递归定义的数据 结构，其中每个节点可以 有多个子节点，但只有一 个父节点。
树的性质
树具有层次性、有序性和 无环性等性质。
树的表示方法
树可以使用多种方式表示， 如嵌套结构、邻接矩阵等。
森林
森林的定义
森林是由若干棵树组成的集合， 其中每棵树都是一个独立的数据
结构。
森林的性质
社交网络
社交网络中需要处理大量的用户关系和信息，数 据结构在其中发挥着重要的作用。例如，使用图 数据结构可以表示用户之间的关系，使用哈希表 可以快速查找用户信息。
THANKS FOR WATCHING
感谢您的观看
05 排序与查找
排序算法
• 冒泡排序：通过重复地遍历待排序的数列，比较相邻的两个元素，若它们的顺 序错误则交换它们，直到没有需要交换的元素为止。
• 选择排序：在未排序的序列中找到最小（或最大）的元素，存放到排序序列的 起始位置，然后再从剩余未排序的元素中继续寻找最小（或最大）元素，然后 放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
的中间元素开始，如果中间元素正好是目标值，则搜索过程结束；如果目标值 大于或小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且同 样从中间元素开始比较。 • 哈希查找：通过哈希函数将关键字转化为数组下标，然后在对应的数组下标位 置上进行查找。 • 二叉查找树查找：在二叉查找树中进行查找，从根节点开始，如果当前节点的 关键字等于目标值，则查找成功；如果当前节点的关键字大于目标值，则在左 子树中继续查找；如果当前节点的关键字小于目标值，则在右子树中继续查找 。
• 插入排序：将一个数据插入到已经排好序的有序数据中，从而得到一个新的、 个数加一的有序数据。

802数据结构考研大纲摘要：1.数据结构基本概念与原理2.线性表及其操作3.栈、队列与层次结构4.树与图结构5.算法设计与分析6.排序与查找算法7.数据压缩与存储8.复试科目及招生目录变化正文：一、数据结构基本概念与原理数据结构是计算机科学与技术领域中的一门基础课程，主要研究计算机数据的组织、存储、操作和处理。

本部分内容包括数据结构的基本概念、基本原理和基本方法。

要求掌握数据的逻辑结构、存储结构及其基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。

二、线性表及其操作线性表是一种基本的数据结构，它具有线性特征，元素之间只有一对一的关系。

本部分内容主要涉及线性表的定义、操作及其应用，如插入、删除、查找等。

要求深刻理解线性表的原理，并能应用相关知识点解决实际问题。

三、栈、队列与层次结构栈、队列和层次结构是计算机中常见的数据结构。

栈与队列分别遵循后进先出（LIFO）和先进先出（FIFO）原则，层次结构则主要用于构建树形结构。

本部分内容要求掌握栈、队列的基本操作及其应用，了解层次结构的特点，并能解决相关问题。

四、树与图结构树与图是复杂度较高的数据结构，它们在计算机科学中有着广泛的应用。

树结构具有层次特点，图结构则由节点和边组成。

本部分内容主要研究树与图的遍历、查找、最短路径等问题，要求熟练掌握树与图的基本概念和算法。

五、算法设计与分析算法设计是计算机科学的核心内容，它关注如何高效地解决问题。

本部分内容要求掌握算法设计的基本方法，如贪心、分治、动态规划等，并能对算法进行高效性分析。

六、排序与查找算法排序和查找是计算机中常见的算法，它们在数据处理方面具有重要意义。

本部分内容要求掌握各种排序算法（如冒泡、快速、归并等）和查找算法（如顺序、二分、哈希等），并能根据实际需求选择合适的算法。

七、数据压缩与存储数据压缩与存储技术在计算机领域具有重要应用价值。

本部分内容要求掌握数据压缩的基本原理和方法，如霍夫曼编码、算术编码等，以及数据存储的技术和策略。

目录绪论30。

1 基本概念3第一章线性表51。

1 线性表的定义51。

2 线性表的实现51.2.2 线性表的链式存储结构8第二章栈、队列和数组162。

1 栈162。

2 队列212。

3 特殊矩阵的压缩存储232.3.1 数组232。

3。

2 特殊矩阵24第三章树与二叉树263。

1 树的概念261。

树的定义262．相关术语273.2 二叉树273。

2.1 定义与性质273.2。

2 二叉树的存储293.2.3 二叉树的遍历303。

2。

4 线索二叉树353。

3 树和森林393。

3。

1 树的存储结构393。

3.2 森林和二叉树的转换4013。

3。

3 树和森林的遍历403.4 哈夫曼（Huffman)树和哈夫曼编码42第四章图434.1 图的概念434。

2 图的存储及基本操作444。

2。

1 邻接矩阵444.2。

2 邻接表454.3 图的遍历474。

3。

1 深度优先搜索474。

3。

2 广度优先搜索484。

4 图的基本应用494。

4.1 最小生成树494.4。

2 最短路径504.4.3 拓扑排序534。

4。

4 关键路径54第五章查找565。

1 查找的基本概念565。

2 顺序查找法575。

3 折半查找法585.4 动态查找树表605.4。

1 二叉排序树605.4.2 平衡二叉树635.4.3B 树及其基本操作、B+树的基本概念665.5 散列表675.5。

2 常用的散列函数6825。

5.3 处理冲突的方法695。

5.4 散列表的查找705.5.5 散列表的查找分析71第六章排序726.1 插入排序726.1.1 直接插入排序726。

1.2 折半插入排序736.2 冒泡排序736。

3 简单选择排序746。

4 希尔排序756.5 快速排序766.6 堆排序786.7 二路归并排序806。

8 基数排序816。

9 各种内部排序算法的比较82绪论0。

1 基本概念1、数据结构数据结构是指互相之间存在着一种或多种关系的数据元素的集合.数据结构是一个二元组Data_Structure ＝（D，R），其中，D 是数据元素的有限集，R 是D 上关系的有限集.32、逻辑结构：是指数据之间的相互关系。

数据结构组成
数据结构由数据元素和它们之间的 关系组成，这些关系决定了数据元 素之间的逻辑关系。
数据结构分类
数据结构可以根据不同的分类标准 进行分类，如线性结构和非线性结 构、静态结构和动态结构等。
数据结构的重要性
01
02
03
提高数据处理效率
合理的数据结构能够提高 数据处理的速度和效率， 使得数据处理更加高效。
图的应用
图在计算机科学中有着广泛的应用， 如社交网络、路由算法、搜索引擎等 。
哈希表
哈希表的概念
哈希表是一种通过哈希函数将键映射到 桶中的数据结构，用于快速查找和存储
键值对。
哈希冲突的处理
当两个不同的键被映射到同一个桶时 ，会发生哈希冲突。常见的处理方式
有链地址法和开放地址法。
哈希表的性能分析
哈希表的查找、插入、删除等操作的 时间复杂度主要由哈希函数的设计和 哈希表的负载因子决定。
链式插入
在链式存储结构中，插入操作需要定位到插入位置的节点 ，并在其后插入新节点，同时修改指针。
AVL树的插入
在AVL树中，插入操作需要先找到合适的空位，然后将新 节点插入到该位置，并调整树的结构以保持平衡。
删除操作
顺序删除
在顺序存储结构的线性表中，删除操作需要定位到要删除的元素，然 后将其后一位元素覆盖到要删除的位置，并减少数组长度。
06
数据结构性能分析
时间复杂度分析
时间复杂度概念
时间复杂度是衡量算法执行时间随输入规模 增长而增长的量度，通常用大O表示法表示 。
时间复杂度分类
根据算法的时间复杂度，可以将算法分为线性时间 复杂度、多项式时间复杂度和指数时间复杂度。
时间复杂度分析方法

（２）非线性结构 所谓非线性结构，该结构中的结点之间存在一对多或多对多的关系。它又可以细分为树形结构 和图形结构两类。 所谓树形结构，该结构中的结点之间存在一对多的关系。其特点是每个结点最多只有一个前驱，
— ６—
但可以有多个后继，可以有多个终端结点。非线性结构树形结构简称为树。
ＵＮＩＸ文件系统的系统结构图
三、考试内容及分值分布：
章节 １．绪论 ２．线性表 ３．栈和队列 ４．串 ５．数组和广义表 ６．树 ７．图 ８．查找 ９．排序
重点
√ √
√ √ √ √
难点
必考点
√
√
√
√
√
√
√
√
√
√
√
√
√
√
考试题型 选择
选择、综合分析 选择、综合分析
选择、填空 选择、填空 选择、综合分析 选择、综合分析 选择、综合分析 选择、综合分析
姓名 张斌 刘丽 李英 陈华 王奇 董强 王萍
性别 男 女 女 男 男 男 女
班号 ９９０１ ９９０２ ９９０１ ９９０２ ９９０１ ９９０２ ９９０１
·数据结构（ＤａｔａＳｔｒｕｃｔｕｒｅ） 数据结构是指相互之间存在一种或多种特定 关系的数据元素 集合 结构（Ｓｔｒｕｃｔｕｒｅ）：数据元素相互之间的关系。 在形式上可用二元组表示： Ｄａｔａ＿Ｓｔｒｕｃｔｕｒｅ＝ （Ｄ，Ｓ） Ｄ：数据元素的有限集 Ｓ：Ｄ上关系的有限集 Ｄ ＝ ｛ｋｉ｜１≤ｉ≤ｎ，ｎ≥０｝ ·ｋｉ表示集合 Ｄ中的第 ｉ个结点或数据元素 ·ｎ为 Ｄ中结点的个数 ·若 ｎ＝０，则 Ｄ是一个空集，表示 Ｄ无结构可言，有时也可以认为它具有任意的结构 Ｓ＝｛ｒｊ｜１≤ｊ≤ｍ，ｍ≥０｝ ·ｒｊ表示集合 Ｓ中的第 ｊ个二元关系（简称关系） ·ｍ为 Ｓ中关系的个数 ·若 ｍ＝０，则 Ｓ是一个空集，表明集合 Ｄ中的元结点间不存在任何关系，彼此是独立的 Ｄ上的一个关系 ｒ是序偶的集合，对于 ｒ中的任一序偶 ＜ｘ，ｙ＞（ｘ，ｙ∈Ｄ），我们称序偶的第一结 点为第二结点的直接前驱结点（通常简称前驱结点），称第二结点为第一结点的直接后继结点（通常简 称后继结点）。如在 ＜ｘ，ｙ＞的序偶中，ｘ为 ｙ的前驱结点，而 ｙ为 ｘ的后继结点。 若某个结点没有前驱，则称该结点为开始结点；若某个结点没有后继，则称该结点为终端结点；除

《数据结构》讲义间存在的关系———产生背景。

1.1 什么是数据结构计算机解题步骤：建立数学模型——设计解此数学模型的算法——编制程序——进行测试调整——解答。

其中建立数学模型的实质：找出操作对象之间的关系。

例1. 图书馆书目检索——对应线性关系例2. 博奕树——对应树型关系例3. 交叉路口交通灯管理——对应图状结构。

数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象及它们之间的关系和操作等的学科。

（地位）1.2 数据结构的基本概念和术语1. 数据（Data）数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。

换句话说，数据是对客观事物采用计算机能够识别、存储和处理的形式所进行的描述；是计算机加工处理的对象。

包括数值、字符、声音、图象等。

2. 数据元素（Data Element）数据元素是组成数据的基本单位, 是数据集合的个体，在计算机中通常作为一个逻辑整体进行考虑和处理。

一个数据元素可由若干个数据项组成（Data Item）。

3. 数据对象（Data Object）数据对象是性质相同的数据元素的集合，是数据的一个子集。

例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={′A′，′B′，…，′Z′}，表1-1所示的学籍表也可看作一个数据对象。

由此可看出，不论数据元素集合是无限集（如整数集）、有限集（如字符集），还是由多个数据项组成的复合数据元素（如学籍表），只要性质相同，都是同一个数据对象。

综上1~3所述，再分析数据概念：4. 结构（Data Structure）数据元素相互之间的关系称为结构（ Structure ），有四种基本结构。

(1) 集合结构：结构中的数据元素之间除了同属于一个集合的关系外，无任何其它关系。

(2) 线性结构：结构中的数据元素之间存在着一对一的线性关系。

(3) 树形结构：结构中的数据元素之间存在着一对多的层次关系。

数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。

换句话说，数据是对客观事物采用计算机能够识别、存储和处理的形式所进行的描述；是计算机加工处理的对象。

包括数值、字符、声数据元素是组成数据的基本单位一个数据元素可由若干个数据项组成（）数据对象是性质相同的数据元素的集合，是数据的一个子集。

…}，字母字符数据对象是集合象。

由此可看出，不论数据元素集合是无限集（如整数集）Data Structure）数据元素相互之间的关系称为结构（ Structure ），有四种基本结构。

集合结构：结构中的数据元素之间除了同属于一个集合的关系外，无任何其它关系。

线性结构：结构中的数据元素之间存在着一对一的线性关系。

图状结构或网状结构：结构中的数据元素之间存在着多对多的任意关系。

为数据结构的有限集，S是D上关系的有限集。

表示复数的虚部。

存储结构（又称物理结构）是逻辑结构在计算机中的存储映象，是逻辑结构在计算机中的实现，它包括据元素的表示和关系的表示形式化描述：要存入机器中，建立一从，使S（D逻辑结构与存储结构的关系为：数据结构的内容可归纳为三个部分：逻辑结构、存储结构和运算集合。

按某种逻辑关系组织起来的一批数据，按一定的映象方式把它存放在计算机的存储器中，并在这些数据上定义了一个运算的集合，(Data Type)数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称合，即该类型的取值范围，以及该类型中可允许使用的一组运算。

例如高级语言中的数据类型就是已经实现的从这个意义上讲，数据类型是高级语言中允许的变量种类，计算机中使用的是二进制数，汇编语言中则可给出各种数据的十进制表示，如二进制数据的抽象; 使用者在编程时可以直接使用据抽象，出现了数据类型，(Abstract Data Type)）是指基于一类逻辑关系的数据类型以及定义在这个类型之上的一组操作。

抽象数据类型的定义取决于客观存在的一组逻辑特性，而与其在计算机内如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部使用。

了解索引顺序表
熟练掌握二又排序树的概念，建立（A）,査找（A, P）,删除（A）,计算ASL （C）平衡二叉排序树的概念,建立（A）,判断失去平序的类型,平衡化（A）,计算ASL
（C）
了解B_树，B+树的慨念和特点
知道畑四（数字査找树）
哈希表的概念、特点、构造哈希表（A）,计算ASL和装填因子。（C）
int length;
k
void BubbleSort ( DataType a[], int n ) {
for (i=0; i<n-l;i++) ( change = fasle; for (j=0; j<n-i-1; j卄)
a[j]<_>afj+l]；change = true;
} if ( {change ) break;
数据结构.抽象数据类型、算法 时间更杂度的简单计算（O）掌握儿种说法
数据元索是…，数据项是… 数据结构中关系的四种基本结构 数据结构的形式定义
算法的五个特征
'讪号G表示要求学捉计芹方法,会汁为•本".卜乍］.
5..，树的五.种基本形志
3.线性表
线性表的概念和四个特征
顺序表和单链表的类型定义
在顺序表中査找、插入、删除，灵活這用 在单链表中查找、插入、删除，灵活运用 循环链表及双向链表的定义、插入,删除 算法：
线性结构的特点：①“第--个”②“最后一个”③前驱④后继.6
2
(1)特点
a)逻辑上相邻的元素在物理位置上相邻。
b)随机访问.
(2)类型定义
简而行之，“数如*度”7.，Im
const int MAXSTZE =线性表最大长度；typcdcf struct {

浙江省考研计算机复习资料数据结构与算法精讲解析数据结构与算法是计算机科学与技术领域中的重要基础知识。

对于准备参加浙江省考研计算机专业的同学来说，掌握数据结构与算法的知识是必不可少的。

本文将对浙江省考研计算机复习资料中的数据结构与算法部分进行精讲解析，帮助同学们更好地掌握这一考点。

一、数据结构1. 线性表线性表是最基本的一种数据结构，它包括顺序表和链表两种形式。

顺序表是将元素连续存储在一块内存中，通过下标访问元素；链表是通过指针将元素链接起来，每个元素包含指向下一个元素的指针。

2. 栈与队列栈是一种后进先出（LIFO）的数据结构，插入和删除操作只在栈的一端进行。

队列是一种先进先出（FIFO）的数据结构，插入操作在队尾进行，删除操作在队头进行。

3. 树与二叉树树是由n（n≥1）个节点组成的有限集合，它们之间通过边连接。

二叉树是一种特殊的树形结构，每个节点最多有两个子节点。

4. 图图由若干个顶点和边组成，顶点之间通过边连接。

图可以分为有向图和无向图，有向图的边是有方向的，而无向图的边没有方向性。

5. 查找与排序查找算法用于在数据集合中寻找特定的元素，常见的查找算法包括顺序查找、二分查找和哈希查找。

排序算法用于对数据进行排序，常见的排序算法包括冒泡排序、插入排序和快速排序等。

二、算法1. 递归递归是一种函数自己调用自己的方法，它可以简化问题的解决过程。

在使用递归时，需要确保递归能够结束，以避免出现无限循环。

2. 动态规划动态规划是一种通过拆分问题为子问题，并将子问题的解存储起来，从而避免重复计算的方法。

动态规划常用于求解最优化问题。

3. 贪心算法贪心算法是一种通过每一步选择中都选择当前最优解的方法来求解问题。

虽然贪心算法不能保证得到全局最优解，但对于某些问题，贪心算法可以提供较好的近似解。

4. 回溯算法回溯算法是一种通过不断地尝试所有可能的解，并在得到错误解时进行回退的方法。

回溯算法常用于求解组合、排列、子集等问题。

以下2024年考研数据结构大纲供参考：
一、绪论
1. 数据结构的基本概念
2. 算法与数据结构的关系
3. 算法分析基础
二、线性表
1. 线性表的定义和基本操作
2. 线性单链表、双向链表与循环链表
3. 一维数组和广义表
三、栈和队列
1. 栈和队列的基本概念
2. 栈和队列的顺序存储及其基本操作
3. 栈和队列的链式存储及其基本操作
4. 栈和队列的应用
四、树与二叉树
1. 树的基本概念
2. 二叉树的定义及其性质
3. 二叉树的存储结构及其基本操作
4. 二叉树的遍历
5. 线索二叉树
6. 哈夫曼树及其应用
7. 平衡二叉树
8. B-树和B+树
9. 并查集
五、图
1. 图的基本概念
2. 图的存储结构及其基本操作
3. 图的遍历
4. 最小生成树(MST)
5. 最短路径问题
6. 拓扑排序
7. 关键路径
8. AOV网与拓扑排序
9. AOE网与关键路径
10. 有向无环图(DAG)及相关算法
11. 二分图匹配问题
12. 网络流问题
13. 动态规划在图论中的应用
14. 图的着色问题。

第三章树与二叉树3.1树的概念1.树的定义树（Tree）是n（n≥0）个有限数据元素的集合。

当n＝0时，称这棵树为空树。

在一棵非树T中：1）有一个特殊的数据元素称为树的根结点，根结点没有前驱结点；2）若n>1，除根结点之外的其余数据元素被分成m（m>0）个互不相交的集合T1，T2，…Tm，其中每一个集合Ti（1≤i≤m）本身又是一棵树。

树T1，T2，…，Tm称为这个根结点的子树。

2．相关术语（1）结点的度：结点所拥有的子树的个数称为该结点的度。

（2）叶结点：度为0的结点称为叶结点，或者称为终端结点。

（3）分支结点：度不为0的结点称为分支结点，或者称为非终端结点。

一棵树的结点除叶结点外，其余的都是分支结点。

（4）孩子、双亲、兄弟：树中一个结点的子树的根结点称为这个结点的孩子。

这个结点称为它孩子结点的双亲。

具有同一个双亲的孩子结点互称为兄弟。

（5）路径、路径长度：如果一棵树的一串结点n1,n2,…,nk有如下关系：结点ni是ni+1的父结点（1≤i<k）,就把n1,n2,…,nk称为一条由n1至nk的路径。

这条路径的长度是k-1。

（6）祖先、子孙：在树中，如果有一条路径从结点M到结点N，那么M就称为N的祖先，而N称为M的子孙。

（7）结点的层数：树的根结点的层数为1，其余结点的层数等于它的双亲结点的层数加1。

（8）树的深度：树中所有结点的最大层数称为树的深度。

（9）树的度：树中各结点度的最大值称为该树的度。

（10）有序树和无序树：如果一棵树中结点的各子树从左到右是有次序的，即若交换了某结点各子树的相对位置，则构成不同的树，称这棵树为有序树；反之，则称为无序树。

（11）森林：零棵或有限棵不相交的树的集合称为森林。

自然界中树和森林是不同的概念，但在数据结构中，树和森林只有很小的差别。

任何一棵树，删去根结点就变成了森林。

3.2二叉树3.2.1定义与性质1.二叉树二叉树（Binary Tree）是n个有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。

注：一个抽象数据类型确定了一个模型，但将模型的实 现细节隐藏起来；它定义了一组运算，但将运算 的实现过程隐藏起来。
用抽象数据类型的概念来指导问题的求解过程：
数学模型 非形式算法
抽象数据模型 伪语言程序
数据结构 可执行程序
§ 1.3 抽象数据类型
ADT的定义格式 ADT <ADT名> { 数据对象:<数据对象的定义> 结构关系:<结构关系的定义> 基本操作:<基本操作的定义> }ADT <ADT名>
初始化数据结构；
Destroy( )
销毁数据结构；
Get (i )
查找第 i 个元素；
Insert (i , b ) 在第 i 个位置插入元素 b ；
Delete( i )
删除第 i 个元素；
Traverse( )
遍历整个数据结构
§ 1.3 抽象数据类型
用C语言实现抽象数据类型ADT 用标准C语言表示和实现ADT描述时，主要
§ 1.2 数据结构的基本概念
数 据：描述客观事物的数字、字符以及一切 能够输入到计算机中，并且能够被计 算机程序处理的符号的集合。
数据是一个广义的概念，可以指普通的数据 （可参加算术运算），也可以指符号（源程序、 产品名称等）或数字化了的声音、图形、图像等。
§ 1.2 数据结构的基本概念
数据元素：数据(集合)中的一个个"个体"，是组 成数据的"基本单位"。
a2 d4 d1
a1 d1 d2
list
a1
a2
a4 d5 d3
a3 d3 … d4
a3
…
a30 ∧
§ 1.3 抽象数据类型

《数据结构》讲义（new）第1章C程序设计程序设计＝数据描述＋算法设计，即程序＝数据结构＋算法。

用计算机去解决问题过程：首先用数据结构的知识表示出问题，然后设计出解决问题的算法，最后写出程序在计算机上运行输出问题解决的结果。

本章我们将对C的主要知识作回顾，为学习数据结构奠定基础。

1.1 表达式算术运算：5/3 值为1，2.5/5 值为0.5,10%3 值为1，'A'+1 值为66赋值运算：a=3+5 a值为8，式值为8。

b=a=3+5 a,b值均为8，式值为8。

a+=3 即a=a+3; a-=3; a*=3; a/=3;a%=3.i++ ,++i,即i=i+1;i...,...i.区别：x=i++;与x=++i;关系运算：3==2，式值为0，3！=2，式值为1。

逻辑运算：0<x&&x<=1, x<=0||x>1,!(x<0). 注：“非零”为1。

条件运算：b>=0?a+b:a-b,即a+︱b︱逗号运算: a=6,a*3,a+3 式值为91.2 函数与参数1.2.1传值参数例1.1 输入四个数，输出其中的最大数。

int max(int x,int y) /*x,y是形参*/{int t;if(x>y) t=x; else t=y;return t;}main(){int a,b,c,d,m;scanf(“%d%d%d%d”,&a,&b,&c,&d);m=max(max(a,b),max(c,d)); /*a,b,c,d,max(a,b),max(c,d)是实参,传值调用*/ printf(“%d”,m);}1.2.1传址参数例1.2输入二个数到变量a与b，交换变量a与b的值后输出。

swap(int *x,int *y) /*x,y为传址参数*/{int t;t=*x;*x=*y;*y=t;}main(){int a,b;scanf("%d%d",&a,&b);swap(&a,&b); /*传址调用*/printf("%d %d",a,b);}例1.3 输入n 个数，升序排列后输出。

第四章图4.1图的概念1．图的定义图是由一个顶点集V和一个弧集R构成的数据结构。

2.图的重要术语；（1）无向图：在一个图中，如果任意两个顶点构成的偶对（v,w）∈E是无序的，即顶点之间的连线是没有方向的，则称该图为无向图。

（2）有向图：在一个图中，如果任意两个顶点构成的偶对（v,w）∈E是有序的，即顶点之间的连线是有方向的，则称该图为有向图。

（3）无向完全图：在一个无向图中，如果任意两顶点都有一条直接边相连接，则称该图为无向完全图。

在一个含有n个顶点的无向完全图中，有n(n-1)/2条边。

（4）有向完全图：在一个有向图中，如果任意两顶点之间都有方向互为相反的两条弧相连接，则称该图为有向完全图。

在一个含有n个顶点的有向完全图中，有n(n-1)条边。

（5）稠密图、稀疏图：若一个图接近完全图，称为稠密图；称边数很少（e<nlogn）的图为稀疏图。

（6）顶点的度、入度、出度：顶点的度（degree）是指依附于某顶点v的边数，通常记为TD(v)。

在有向图中，要区别顶点的入度与出度的概念。

顶点v的入度是指以顶点为终点的弧的数目，记为ID(v)；顶点v出度是指以顶点v为始点的弧的数目，记为OD(v)。

TD(v)=ID(v)＋OD(v)。

（7）边的权、网图：与边有关的数据信息称为权（weight）。

在实际应用中，权值可以有某种含义。

边上带权的图称为网图或网络（network）。

如果边是有方向的带权图，则就是一个有向网图。

（8）路径、路径长度：顶点vp到顶点vq之间的路径（path）是指顶点序列vp,vi1,vi2,…,vim,vq.。

其中，（vp,vi1），(vi1,vi2)，…,(vim,.vq)分别为图中的边。

路径上边的数目称为路径长度。

（9）简单路径、简单回路：序列中顶点不重复出现的路径称为简单路径。

除第一个顶点与最后一个顶点之外，其他顶点不重复出现的回路称为简单回路，或者简单环。

（10）子图：对于图G=（V，E），G’=（V’，E’），若存在V’是V的子集，E’是E的子集，则称图G’是G的一个子图。

2.1.1 抽象数据类型线性表的定义
GetElem( L, i, &e ) 初始条件：线性表 L 已存在，1≤i≤LengthList(L)。 操作结果：用 e 返回 L 中第 i 个元素的值。 LocateElem( L, e, compare( ) ) 初始条件：线性表 L 已存在，compare( ) 是元素判定函数。 操作结果：返回 L 中第1个与 e 满足关系 compare( ) 的元素的位序。 若这样的元素不存在，则返回值为0。 ListTraverse(L, visit( )) 初始条件：线性表 L 已存在，visit( ) 为元素的访问函数。 操作结果：依次对 L 的每个元素调用函数 visit( )。 一旦 visit( ) 失败，则操作失败。
2.1.1 抽象数据类型线性表的定义
ADT List { 数据对象：D＝{ ai| ai∈ElemSet, i=1,2,...,n, n≥0 } 数据关系：R1＝{ <ai-1 ,ai >| ai-1 ,ai ∈D, i=2,...,n } 基本操作： {结构初始化} InitList( &L ) 操作结果：构造一个空的线性表 L 。 {销毁结构} DestroyList( &L ) 初始条件：线性表 L 已存在。 操作结果：销毁线性表 L 。
2.1.2 线性表类型的应用
例2-1 已知集合 A 和 B，求两个集合的并集，使 A＝ A∪B，且 B 不再单独存在。 上述集合求并的问题可演绎为：要求对线性表作如 下操作：扩大线性表 LA，将存在于线性表 LB 中 而不存在于线性表 LA 中的数据元素插入到线性 表 LA 中去。 具体操作步骤为： 1．从线性表 LB 中取出一个数据元素； 2．依值在线性表 LA 中进行查询； 3．若不存在，则将它插入到 LA 中。 重复上述三步直至 LB 为空表止。