清华大学严蔚敏版数据结构讲义PPT

8次
4358 3485 6552 5145 1354 3625 7272 2420 4707
n-i次
…
第n-1趟 排序结束
25
第25页/共58页
第10章 内部排序
10.3 交换类排序
①冒泡排序（相邻比逆法）
void BubbleSort(RecordType r[ ],int length)
{ n=length;
数
据
结
有序序列a[1..i-1]
构
a[i]
无序序列 a[i..n-1]
有序序列a[1..i]
无序序列 a[i+1..n-1]
7
第7页/共58页
第10章 内部排序 10.2 插入类排序
实现“一趟插入排序”可分三步进行：
1．在a[1..i-1]中查找a[i]的插入位置，
数
a[1..j].key a[i].key < a[j+1..i].key；
low = 1; high = i-1;
while (low<=high)
数
{
据
结
构
m= (low+high)/2;
if (L.r[0].key < L.r[m].klse low = m+1;
18
第18页/共58页
第10章 内部排序 10.2 插入类排序
③希尔排序 （又称缩小增量排序）
数 { R[1]，R[1+d]，R[1+2d]，…，R[1+kd] }
据 { R[2]，R[2+d]，R[2+2d]，…，R[2+kd] }
结
…
构 { R[d]，R[2d]，R[3d]，…，R[kd]，R[(k+1)d] }

1.1 数据结构讨论的范畴 1.2 基本概念 1.3 算法和算法的量度
1.1 数据结构讨论的范畴
Niklaus Wirth：
Algorithm + Data Structures = Programs
程序设计:
算法: 数据结构:
为计算机处理问题编制 一组指令集
处理问题的策略
问题的数学模型
例如: 数值计算的程序设计问题
结构静力分析计算 ─━ 线性代数方程组
全球天气预报 ─━ 环流模式方程 (球面坐标系)
非数值计算的程序设计问题
例一: 求一组(n个)整数中的最大值 算法: ? 基本操作是“比较两个数的大小” 模型：？ 取决于整数值的范围
例二：计算机对弈
算法：? 对弈的规则和策略 模型：? 棋盘及棋盘的格局
例三：足协的数据库管理
S 是 D上关系的有限集。
数据的存储结构
—— 逻辑结构在存储器中的映象
“数据元素”的映象 ？
“关系”的映象 ？
数据元素的映象方法：
用二进制位(bit)的位串表示数据元素 (321)10 = (501)8 = (101000001)2 A = (101)8 = (001000001)2
关系的映象方法：（表示x, y的方法）
抽象数据类型的表示和实现
抽象数据类型需要通过固有数据 类型(高级编程语言中已实现的数据 类型)来实现。
例如，对以上定义的复数。
// -----存储结构的定义
typedef struct { float realpart； float imagpart；
}complex；
// -----基本操作的函数原型说明
顺序映象
以相对的存储位置表示后继关系 例如:令 y 的存储位置和 x 的存储位置之间差一个常量 C

❖基本思想：通过一趟排序，将待排 序记录分割成独立的两部分，其中 一部分记录的关键字均比另一部分 记录的关键字小，则可分别对这两 部分记录进行排序，以达到整个序 列有序
❖排序过程：对r[s……t]中记录进行一趟
快速排序，附设两个指针i和j，设枢轴记录 rp=r[s]，x=rp.key
初始时令i=s,j=t
一趟排序：13 27 48 55 4 49 38 65 97 76 取d2=3 二趟分组：13 27 48 55 4 49 38 65 97 76
二趟排序：13 4 48 38 27 49 55 65 97 76 取d3=1 三趟分组：13 4 48 38 27 49 55 65 97 76
三趟排序：4 13 27 38 48 49 55 65 76 97
i=8 20 (6
i=8 20 (6
13 30 39 42 70 85 ) 20
13 30 39 m
13 30 39 mj 13 30 39
s mj
42 70 42 70 42 70
85 ) 20 j 85 ) 20
85 ) 20
13 30 39 42 70 85 ) 20 js
13 20 30 39 42 70 85 )
第九章 内部排序
• 分类：
•内部排序：全部记录都可以同时调入内存进行的排序。
•外部排序：文件中的记录太大，无法全部将其同时调入内存进行的排 序。
• 定义：设有记录序列：{ R1、R2 ……….. Rn } 其相应的关键字 序列为： { K1、K2 ……….. Kn }; 若存在一种确定的关系： Kx <= Ky <= … <= Kz则将记录序列 { R1、R2 ……….. Rn } 排成按 该关键字有序的序列： { Rx、Ry ……….. Rz } 的操作，称之为 排序。

数据结构的形式定义为：数据结构是一个二元 组：
Data-Structure=(D，S)
其中：D是数据元素的有限集，S是D上关系的 有限集。
例 复数的数据结构定义如下：
Complex=(C，R)
其中：C是含两个实数的集合﹛C1，C2﹜，分 别表示复数的实部和虚部。R={P}，P是定义在 集合上的一种关系{〈C1，C2〉}。
当n取得很大时，指数时间算法和多项 式时间算法在所需时间上非常悬殊。因
此，只要有人能将现有指数时间算法中
的任何一个算法化简为多项式时间算法， 那就取得了一个伟大的成就。
有的情况下，算法中基本操作重复执行的次数 还随问题的输入数据集不同而不同。例如：
Void bubble-sort(int a[]，int n)
（1）有穷性 一个算法必须总是在执行有穷步 之后结束，且每一步都在有穷时间内完成。
（2）确定性 算法中每一条指令必须有确切的 含义。不存在二义性。且算法只有一个入口和 一个出口。
（3）可行性 一个算法是可行的。即算法描述 的操作都是可以通过已经实现的基本运算执行 有限次来实现的。
4）输入 一个算法有零个或多个输入，这些输 入取自于某个特定的对象集合。
对一个算法要作出全面的分析可分成两用人 才个阶段进行，即事先分析和事后测试
事先分析 求出该算法的一个时间界限函数
事后测试 收集此算法的执行时间和实际占用 空间的统计资料。
定义：如果存在两个正常数c和n0，对于所有的 n≧n0，有︱f(n) ︳≦c｜g(n) ︳
则记作 f(n)=O(g(n))
姓名 王小林 陈红 刘建平 张立立 ……..
学号 790631 790632 790633 790634 ……..

InfoType *info;
}VNode,AdjList[MAX_V];
}ArcNode;
typedef struct //图的邻接表类型
{ AdjList vertices; //存储图中所有顶点的数组
int vexnum,arcnum; //存储图的顶点数目和边(弧)的数目
int kind; //图的种类标志
返回
表结点
adjvex nextarc info
表头结点
data firstarc
typedef struct ArcNode typedef struct
{ int adjvex;
{ VertexType data;
struct ArcNode *nextarc; ArcNode *firstarc;
}ArcCell,AdjMatrix[MAX_V][MAX_V];
typedef struct
{ VertexType vex[MAX_V]; //顶点信息数组(如顶点编号等)
AdjMatrix arcs;
//图的邻接矩阵
int vexnum,arcnum; //图的顶点数和边(弧)的数目
GraphKind kind;//图的种类标志
A CB F DE G (a) 有向图G1
A BC D EF (b) 无向图G2
返回
2 几个常用术语 可以证明,对于具有n个顶点的无向图的边和具有n个
顶点的有向图的弧的最大数目分别为n(n-1)/2和n(n-1)。 称具有n(n-1)/2条边的无向图为完全图(completed
grahp)。 称具有n(n-1)条弧的有向图为完全有向图 称边或弧的数目e<nlogn的图为稀疏图(sparse

一般情况下，
假设含n个记录的序列为{ R1, R2, …， Rn } 其相应的关键字序列为 { K1, K2, …，Kn }
这些关键字相互之间可以进行比较，即在
它们之间存在着这样一个关系 ：
Kp1≤Kp2≤…≤Kpn
按此固有关系将上式记录序列重新排列为
{ Rp1, Rp2, …，Rpn }
的操作称作排序。
有序序列区 无 序 序 列 区
经过一趟排序
有序序列区 无 序 序 列 区
03.07.2020
.
11
基于不同的“扩大” 有序序列长 度的方法，内部排序方法大致可分 下列几种类型：
插入类 交换类 选择类
归并类 其它方法
03.07.2020
.
12
#待de排fin记e M录A的XS数IZ据E 类10型00定// 待义排如顺下序:表最大长度
03.07.2020
.
15
3. 选择类
从记录的无序子序列中“选择” 关键字最小或最大的记录，并将它 加入到有序子序列中，以此方法增 加记录的有序子序列的长度。
03.07.2020
.
16
4. 归并类
通过“归并”两个或两个以上的 记录有序子序列，逐步增加记录有 序序列的长度。
5. 其它方法
03.07.2020
.
5
03.07.2020
10.1 概述
10.2 插入排序
10.3 快速排序
10.4 堆排序 10.5 归并排序
10.6 基数排序
10.7 各种排序方法的综合比较
03.07.2020
10.8 外. 部排序
6
10.1 概 述
一、排序的定义 二、内部排序和外部排序 三、内部排序方法的分类

① 集合：结构中的数据元素除了“同属于一个集合” 外，没有其它关系。
② 线性结构：结构中的数据元素之间存在一对一的 关系。
③ 树型结构：结构中的数据元素之间存在一对多的 关系。
④ 图状结构或网状结构：结构中的数据元素之间存 在多对多的关系。
图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> } 画出这逻辑结构的图示，并确定那些是起点，那些是终点
<基本操作名>(<参数表>) 初始条件： <初始条件描述> 操作结果： <操作结果描述>
– 初始条件：描述操作执行之前数据结构和参数应 满足的条件;若不满足，则操作失败，返回相应的出 错信息。

排序算法的时间复杂度
时间复杂度是衡量算法效率的重要指标，常见的 排序算法的时间复杂度有O(n^2)、O(nlogn)、 O(n)等。
查找的基本概念和算法
查找的基本概念
查找是指在一个已经有序或部分 有序的数据集合中，找到一个特 定的元素或一组元素的过程。
常见查找算法
常见的查找算法包括顺序查找 、二分查找、哈希查找等。
先进先出（FIFO）的数据 处理。
并行计算中的任务调度。
打印机的打印任务管理。
二叉树的层序遍历（宽度 优先搜索，BFS）。
04
树和图
树的基本概念和性质
树的基本概念
树是一种非线性数据结构，由节 点和边组成，其中节点表示实体 ，边表示实体之间的关系。
树的性质
树具有层次结构，节点按照层次 进行排列，每个节点最多只能有 一个父节点，除了根节点外。
isEmpty：判断队列是否为空。
enqueue：向队尾添加一个元素。
front 或 peek：查看队首元素。
dequeue：删除队首的元素。
栈和队列的应用
栈的应用 后进先出（LIFO）的数据处理。
括号匹配问题。
栈和队列的应用
队列的应用
深度优先搜索（DFS）。 表达式求值。
01
03 02
栈和队列的应用
数据结构严蔚敏ppt( 完整版)
contents
目录
• 绪论 • 线性表 • 栈和队列 • 树和图 • 排序和查找 • 数据结构的应用案例分析
01
绪论
数据结构的基本概念
总结词
数据结构是计算机存储和组织数据的方式，是算法和数据操 作的基础。
详细描述
数据结构是计算机科学中研究数据的组织和存储方式的学科 ，它决定了数据在计算机中的表示和关系。数据结构不仅包 括数据的逻辑结构，还涉及到数据的物理存储方式以及数据 的操作方式。

2021/3/12
Page 2
单关键字文件
❖ 文件中的记录只有一个唯一标识记录的主关键字。
多关键字文件
❖ 文件中的记录除了含有一个主关键字外，还含有若干个次关键字。
记录的属性
❖ 记录中所有非关键字的数据项。
记录的逻辑结构
❖ 记录在用户或应用程序员面前呈现的方式，是用户对数据的表示和 存取方式。
文件的检索方式
❖ 顺序存取：存取下一个逻辑记录。 ❖ 直接存取；存取第i个逻辑记录。 ❖ 按关键字存取：
简单查询、区域查询、函数查询、布尔查询
Data Structure
2021/3/12
Page 4
文件的修改
❖ 记录的插入、删除、修改。
文件的物理结构
❖ 文件在外存上的组织方式。 ➢ 顺序组织 ➢ 随机组织 ➢ 链组织
记录的物理结构
❖ 数据在物理存储器上存储的方式，是数据的物理表示和组织。
Data Structure
2021/3/12
Page 3
物理记录
❖ 计算机用一条I/0命令进行读写的基本数据单位（物理块）。 ❖ 物理记录和逻辑记录之间可能存在下列三种关系：
➢ 一个物理记录存放一个逻辑记录； ➢ 一个物理记录包含多个逻辑记录； ➢ 多个物理记录表示一个逻辑记录。
项。索引项指出该记录的物理地址。最后，索引表按关键字排序。 ❖ 只能存储在磁盘存储设备上。
Data Structure
2021/3/12
Page 8
物理记录号 职工号 姓名 职务 其他
101
29 张珊 程序员
103
05 李四 维修员
104
02 王红 程序员
105
38 刘淇 穿孔员

选择排序的基本思想
在未排序序列中找到最小（或最大）元素，存放到排序 序列的起始位置，然后，再从剩余未排序元素中继续寻 找最小（或最大）元素，然后放到已排序序列的末尾。 以此类推，直到所有元素均排序完毕。
2024/3/26
33
交换排序和归并排序
交换排序的基本思想
通过不断地交换相邻的两个元素（如果它们的顺序错 误）来把最小的元素“浮”到数列的一端。具体实现 时，从第一个元素开始，比较相邻的两个元素，如果 前一个比后一个大，则交换它们的位置；每一对相邻 元素做同样的工作，从开始第一对到结尾的最后一对 ；这步做完后，最后的元素会是最大的数；针对所有 的元素重复以上的步骤，除了最后一个；持续每次对 越来越少的元素重复上面的步骤，直到没有任何一对 数字需要比较。
图的基本操作
创建图、添加顶点、添加边、删除顶点、删除边 等
2024/3/26
27
图的存储结构
01
邻接矩阵表示法
用一个二维数组表示图中顶点间的 关系，适用于稠密图
十字链表表示法
用于有向图，可以方便地找到任一 顶点的入边和出边
03
2024/3/26
02
邻接表表示法
用链表表示图中顶点间的关系，适 用于稀疏图
入栈操作将元素添加到栈顶，出栈操作将栈顶元素删 除，取栈顶元素操作返回栈顶元素但不删除，判断栈
是否为空操作检查栈中是否有元素。
2024/3/26
12
栈的表示和实现
栈可以用数组或链表来实现。
用数组实现时，需要预先分配一块连续的内存空间，用一个变量指示栈顶位置。入栈和出栈操作都可以 通过移动栈顶位置来实现。
22
二叉树的定义和基本操作
二叉树的定义
二叉树是一种特殊的树，每个节点最 多有两个子节点，分别称为左子节点 和右子节点。