清华大学-数据结构 PPT课件

30
树形数据结构的查找算法
二叉排序树的查找
从根节点开始，若查找值小于当前节点 值，则在左子树中查找；若大于当前节 点值，则在右子树中查找。
VS
平衡二叉树的查找
在保持二叉排序树特性的基础上，通过旋 转操作使树保持平衡，提高查找效率。
2024/3/26
31
散列表的查找算法
散列函数的设计
将关键字映射为散列表中位置的函数。
过指针来表示。
链式存储的特点
逻辑上相邻的元素在物理位置上 不一定相邻；每个元素都包含数
据域和指针域。
链式存储的优缺点
优点是插入和删除操作不需要移 动元素，只需修改指针；缺点是
存储密度小、空间利用率低。
2024/3/26
11
线性表的基本操作与实现
插入元素
在线性表的指定位 置插入一个元素。
查找元素
在线性表中查找指 定元素并返回其位 置。
自然语言处理的应用
在自然语言处理中，需要处理大量的文本数据，数据结构中的字符 串、链表、树等可以很好地支持文本的处理和分析。
41
数据结构在计算机网络中的应用
2024/3/26
路由算法的实现
计算机网络中的路由算法需要大量的数据结构支持，如最短路径 树、距离向量等。
网络流量的控制
在计算机网络中，需要对网络流量进行控制和管理，数据结构中的 队列、缓冲区等可以很好地支持流量的控制。
37
06
数据结构的应用与拓展
2024/3/26
38
数据结构在算法设计中的应用
01
作为算法设计的基 础
数据结构为算法提供了基本操作 和存储方式，是算法实现的重要 基础。
02
提高算法效率

p->data=x;
p->next=top; top=p;
修改栈顶指针
return top;
} 25
链栈的出栈操作
an出栈，使工作指针q 指向要出栈结点，然
后修改栈顶指针: top=top->next
26
链栈出栈操作
LinkStack *pop( LinkStack *top)
{ LinkStack *q; if(!top) /*说明指针top指向NULL*/ {printf(“\n链栈是空的!”); return NULL;} q=top; top=top->next; free(q); return top;
29
void conversion(int N, int r)
解题思路如下：
{ int x=N,y=r; SeqStack *s; /*是顺序栈*/
N是十进制数，要将N 转换成r进制数
s=initStack( ); /*构造一个顺序栈*/ while(N!=0) { push(s, N %r ); /*将N%r入栈*/
}
17
例3.1 用main函数以及display函数，调试上述各种栈的基
本操作算法。
#define Maxsize 50
typedef int datatype;
typedef struct{
{datatype stack[Maxsize]; int top；
}SeqStack；
void display(SeqStack *s) /*显示栈中所有元素值*/
15
顺序栈的入栈操作——例如用堆栈存放（A，B，C，D）
高地址M 低地址L
top
top D

//判集合this与R相等
friend istream& operator >> (istream& in,
bitSet<T>& R);
//输入
friend ostream& operator << (ostream& out,
bitSet<T>& R);
//输出
private:
int setSize;
bitVector = new int [vectorSize]; //分配空间
assert (bitVector != NULL); //检查存储分配是否成功
for (int i = 0; i < vectorSize; i++) //初始化
bitVector[i] = R.bitVector[i];
//集合大小
int vecterSize;
//位数组大小
unsigned short *bitVector;
//存储集合元素的位数组
};
11
使用示例
Set s1, s2, s3, s4, s5; int index, equal; for (int k = 0; k < 10; k++) { //集合赋值
清华大学计算机系 数据结构（用面向对象方法与
C++语言描述）第二版3
殷人昆
1
数据结构电子教案
第六章 集合与字典
殷人昆 王 宏
2
第六章 集合与字典
• 集合及其表示 • 并查集与等价类 • 字典 • 跳表 • 散列
3
集合及其表示

第2页/共18页
数据结构课程的地位
• 是介于数学、计算机硬件和计算机软件三 者之间的一门核心课程数据结构课程的地 位。
关系
数学
对象
对象
关系
软件
硬件
关系
操作
操作
第3页/共18页
• 数据结构是一门研究非数值计算的程序设 计问题中计算机的操作对象及其之间关系 与操作的学科。是介于数学、计算机硬件 和计算机软件三者之间的一门核心课程， 属于计算机学科中的一门综合性专业基础 课程。
第5页/共18页
选修课课程设置与数据结构的关系
数据结构基础
计算机科学基础
算法与数 据结构Ⅱ
文件处理 (数据库)
算法设计与分析
软件工程
系统模拟
图形学
第6页/共18页
数值计算解决问题的一般步骤：
• 数学模型→选择计算机语言→编出程序 →测试→最终解答。
• 数值计算的关键是：如何得出数学模型 （方程）？
第8页/共18页
求解非数值计算的问题的步骤：
• 主要考虑的是设计出合适的数据结构及相 应的算法。即首先要考虑对相关的各种信 息如何表示、组织和存储？
• 可以认为：数据结构是一门研究非数值计 算的程序设计问题中计算机的操作对象以 及它们之间的关系和操作的学科。
第9页/共18页
数据结构课程的特点
• 数据结构课程是计算机专业基础课，主 要训练学生在系统开发中的数据设计、 算法设计与分析及数据组织的能力，它 是后续多门课程，如数据库、操作系统、 编译原理、网络系统基础等的基础，对 于从事计算机系统开发的人员，是必修 课程之一。
• 自觉预习、遵守纪律、认真听课、及时复 习；
• 按时、独立、认真地完成每次作业； • 完成作业方式：

float GetReal( cpmplex Z )；
// 返回复数 Z 的实部值 float Getimag( cpmplex Z )； // 返回复数 Z 的虚部值
void add( complex z1, complex z2, complex &sum )； // 以 sum 返回两个复数 z1, z2 的和
―数据抽象” 和“数据封装”
数据抽象 用ADT描述程序处理的实体
时，强调的是其本质的特征、其所能 完成的功能以及它和外部用户的接口 （即外界使用它的方法）。
数据封装 将实体的外部特性和其内部
实现细节分离，并且对外部用户隐藏
其内部实现细节
抽象数据类型的描述方法
ADT =（D，S，P）
其中: D 是数据对象， S 是 D 上的关系集， P 是对 D 的基本操作集。
又如，在 2 行 3 列的二维数组中六个元素 {a1, a2, a3, a4, a5, a6} 之间存在着两个关系: ―行” 的次序关系:
row = {<a1,a2>,<a2,a3>,<a4,a5>,<a5,a6>}
a1 a2 a3 a4 a5 a6
―列” 的次序关系:
col = {<a1,a4>,<a2,a5>,<a3,a6>}
InitComplex(z1,8.0,6.0);
InitComplex(z2,4.0,3.0);
Add(z1,z2,z3);
Multiply(z1,z2,z4);
if (Division (z4,z3,z)) {
GetReal (z, RealPart);
GetImag (z, ImagPart);

叶子不会下沉，所以建堆过程应该从倒数第二层最右边一棵子树的根开始
建堆起点（数组下标起止）
树根r在数组 内的下标是0
a0
下一个子r递堆减起点
就是它的兄弟
子树根r的右
子树根r孩的子左下标 叶孩子子下下标标范围
a1
a3
n是节点总数
n 2
1
a4
a5
a2 起点
起点 a6
a7
a8 a9
a10 a11
a12 a13
int ttoottaall;
int grade;
char num[20];
stuGRADE AAA[[12[0390]]];
int SUBtotal;
char name[20];
struct node *left,*right;
student B[20];
};
};
};
大作业（三）--参考作业评判
数据结构
2012.2
课程大纲
第1讲 数据结构—应用、概念、以及课程基础 第2讲 线性表--链表、队列 第3讲 堆栈、非线性数据结构-二叉树 第4讲 二叉树、堆 第5讲 堆、哈夫曼树 第6讲 检索操作 第7讲 分块检索与哈希表 第8讲 排序 第9讲 算法分析与图的基本概念 第10讲 图结构 第11讲 图应用 第12讲 高级数据结构内容--索引技术
得庞大；
2. 平衡处理的很好。
3. 层次遍历不错，这次删除了线索化 二叉树的内容，有条件的同学可以 自己做。
4. 统计界面不错。
十字链参考
堆结构 局部有序：有序关系仅限定在
父亲与孩子之间，任何一个节 点与其兄弟之间的关键码值大
a1
小都没有必然的联系
一堆元素有顺序 的聚集在一起

//取顶点 i 的值
virtual E getWeight (int v1, int v2); //取边上权值
virtual int getFirstNeighbor (int v);
//取顶点 v 的第一个邻接顶点
146-14
virtual int getNextNeighbor (int v, int w); //取邻接顶点 w 的下一邻接顶点
};
146-23
template <class T, class E> int Graphmtx<T, E>::getFirstNeighbor (int v) { //给出顶点位置为v的第一个邻接顶点的位置, //如果找不到, 则函数返回-1
virtual bool removeEdge (int v1, int v2); //在图中删去边(v1,v2)
};
146-15
邻接矩阵 (Adjacency Matrix)
• 在图的邻接矩阵表示中，有一个记录各个顶 点信息的顶点表，还有一个表示各个顶点之 间关系的邻接矩阵。
• 设图 A = (V, E) 是一个有 n 个顶点的图, 图的 邻接矩阵是一个二维数组 A.edge[n][n]，定义：
const int DefaultVertices = 30; //最大顶点数(=n)
template <class T, class E>
class Graph {
//图的类定义
protected:
int maxVertices;
//图中最大顶点数
int numEdges;
//当前边数
int numVertices;
146-17

指针
1345
元素1
1400
1346
元素4
∧
…….
……..
…….
1400
元素2
1536
…….
……..
…….
1536
元素3
1346
10
数据结构的三个方面： 数据的逻辑结构
线性结构
线性表 栈 队
ቤተ መጻሕፍቲ ባይዱ
非线性结构 树形结构 图形结构
数据的存储结构 顺序存储 链式存储
数据的运算：检索、排序、插入、删除、修改等
11
char name[20]; float score; }STUDENT; STUDENT stu1,stu2, *p;
12
写在最后
经常不断地学习,你就什么都知道。你知道得越多,你就越有力量 Study Constantly, And You Will Know Everything. The More
图状结构——多个对多个，如图
7
数据的逻辑结构—只抽象反映数据元素的逻辑关系
数据的存储（物理）结构—数据的逻辑结构在计算 机存储器中的实现
存储结构分为： 顺序存储结构——借助元素在存储器中的相对位置来表示
数据元素间的逻辑关系 链式存储结构——借助指示元素存储地址的指针表示数据
元素间的逻辑关系
数据的逻辑结构与存储结构密切相关
1
课程内容：
计算机软件的基础知识———数据结构与算法
课时安排：
数据结构——48学时 上机——16学时
教材：
数据结构 严蔚敏 清华 参考书：数据结构 刘自强 武汉理工大
2
第一章 绪言
❖ 1.1 什么是数据结构
程序=数据结构+算法

2013-9-10 4
完全二叉树的性质和顺序存储结构 （1）具有 n 个结点的完全二叉树的高度 = log2 ( n + 1 ) – 1 （2）若将一棵按前述原则编号的完全二叉树，按其编号顺序存入一 个一维数组中，则有： 结点 i 的左子结点下标 = 2* i + 1 < n 结点 i 的右子结点下标 = 2* i + 2 < n 结点 i 的父结点下标 = ( i – 1 ) / 2 的下取整值 另外注意：根结点（下标为0）无父结点 由上可知，完全二叉树的父——左子、父——右子之间的 关系可以通过相应结点的下标之间的简单数学关系完全地表示 出来，因此可以采用顺序存储结构来存储完全二叉树。（参见 教材 6.3.1 数组表示） 顺序存储结构用于动态性较小的完全二叉树的存储不失为 一种简单有效的方法，但不通用。树型数据结构一般采用链式存 储方式来存储。
2013-9-10 11
6.4 二叉树遍历(Binary Tree Traversal ) 操作
遍历：按照某种顺序不重复地访问遍二叉树中的所有结点。此处的 访问可以是输出、修改等操作，根据实际需要而定。 遍历操作可以从一种非线性结构中得到相应的线性序列。 有不同顺序的遍历操作，对于二叉树有三种遍历操作：
2013-9-10 5
6.3.2 二叉树的链式存储结构——二叉（三叉）链表结构
二叉链表结构： 左子指针 数据元素 右子指针
leftChild
data
rightChild
三叉链表结构：
左子指针 数据元素
leftChild data father
右子指针
rightChild
父指针
2013-9-10
6
二叉链表结构的二叉树结点（简称二叉树结点）的类定义： template <class Type> class BinaryTree;//二叉树类声明 template <class Type> class BinTreeNode//二叉树结点类定义 { friend class BinaryTree<Type>;//二叉树类是二叉树结点类的友元 public: BinTreeNode( ): leftChild(NULL),rightChild(NULL) { } //构造函数 BinTreeNode( Type item,BinTreeNode<Type> * left = NULL, BinTreeNode<Type> * right = NULL):data(item), leftChild(left),rightChild(right) { }//构造函数 … //其他成员函数 private: BinTreeNode<Type> * leftChild , * rightChild ; //左子指针、右子指针 Type data;//数据元素 }

ASL=(1+2+2+3+3+3+3)=17/7≈2.43。 从结果可知，平衡二叉树的查找性能优于二叉排序树30 。
旋转
-1 A
2C
平衡处理
1B
0B 0A
0B
0A
0C
图 8-8 LR 型平衡处理
25
RR型的处理(右右型)
如图8-9所示，在A的右孩子B上插入一个右孩子C， 使A的平衡因子由-1变成-2，成为不平衡的二叉排序树。 这时的平衡处理为：将A逆时针旋转，成为B的左子树， 而原来B的左子树则变成A的右子树，待插入结点C成为 B的右子树。
例：对关键字序列4,5,7,2,1,3,6，试用二叉排序树和 平衡二叉树两种方法查找，给出查找6的次数及成功的 平均查找长度。 分析：由于关键字序列的顺序己经确定，故得到的二叉 排序树和平衡二叉树都是唯一的。得到的平衡二叉树见 图8-12，得到的二叉排序树见图8-13。
29
04
4
02
06
2
5
01 03 05 07
10
例：假设给定有序表中关键字为 8,17,25,44,68,77,98,100,115,125 ， 将 查 找 K=17 和 K=120的情况描述为图8-1及图8-2所示。
[ 8 17 25 44 68 77 98 10 115 125 ]
low
high
(a) 初始情形
[ 8 17 25 44 ] 68 44 98 100 115 125
数据结构(下)
1
第8章查找 第9章 排序 第10章 索引与散列
2
第8章 查找
3
一、查找的基本概念
查找，也称为检索。查找某人的地址、电话号码；

③ 可行性： 一个算法是能行的。即算法描述的操作 都可以通过已经实现的基本运算执行有限次来实现。
④ 输入： 一个算法有零个或多个输入，这些输入 取自于某个特定的对象集合。
⑤ 输出： 一个算法有一个或多个输出，这些输出 是同输入有着某些特定关系的量。
一个算法可以用多种方法描述，主要有：使用自 然语言描述；使用形式语言描述；使用计算机程序设计 语言描述。
初始化赋值查找修改插入删除求长度等初始化赋值查找修改插入删除求长度等以下将对几种主要的操作进行讨论以下将对几种主要的操作进行讨论statusinitsqlistsqliststatusinitsqlistsqlistlelemarrayelemtypelelemarrayelemtypemallocmaxsizesizeofelemtypemallocmaxsizesizeofelemtypereturnerrorreturnerrorreturnokreturnok在线性表在线性表i1i1i1i1个位置上插入一个新结点个位置上插入一个新结点使其成使其成为线性表为线性表i1i1i1i1将线性表将线性表个结点后移一个位个结点后移一个位将结点将结点插入到结点插入到结点i1i1之后之后线性表长度加线性表长度加算法描述算法描述statusinsertsqlistsqliststatusinsertsqlistsqlistelemtypeelemtypei0illength1returnerrori0illength1returnerror线性表溢出线性表溢出returnerrorlelemarrayj1lelemarrayj
算法与数据结构
教材：《数据结构 (C 语言版 ) 》。严蔚敏，吴伟民
编
著。清华大学出版社。
参考文献：
1 《数据结构》 。张选平，雷咏梅 编， 严蔚敏 审。 机械工业出版社。

以链式结构存储的线性表称之为以链式结构存储的线性表称之为linkedlistlinkedlist70存储地址数据域指针域15头指针h15null20141413132727线性表王李钱线性表王李钱表示意图表示意图71存放数据元素的结点至少包含两个域数据域和指针域数据域存放元素的数据指针域存放其后继元素的存储地址指针域中存放的信息称为指针或链n个结点连接成一个链表称为线性表的链式存储结构73typedeftypedefstructstructlnodelnodeelemtypeelemtypedatadata数据域数据域structstructlnodelnodenextnext
—— C语言版
清华大学出版社
2009年9月
第1章 概 论
o 什么是数据结构 o 为什么要学习数据结构 o 算法和算法分析
1.1 什么是数据结构
1.1.1 数据和数据元素
数据（data）是信息的载体，是对客观事物的符 号表示，它能够被计算机识别、存储和加工处理。
数据——在计算机科学中指所有能输入到计算机中并被计 算机程序处理的符号的总称。如图像、数、字符、声音、 视频等都可以通过编码而由计算机处理，因此它们也属于 数据的范畴。
一般，我们把算法运行的时间定义 成函数T(n)，一个算法所耗费的时间 将随输入数据量n的增大而增大，n是 该算法输入数据的规模，这个数据规 模不是某一个具体的输入。T(n)的单 位是不确定的，一般把它看成是在一 个特定的计算机上执行的指令条数。
当讨论一个程序的运行时间 T(n)时， 注重的不是T(n)的具体值，而是它的增长 率。即求出T(n)随输入数据量n而增长的 趋势(极限) 。
通常有如下的函数关系排序： c< log2 n< n< n log2 n< n2< n3< 10 n

在数组 B 中没有存放。因此，找它的对称元
素A[j][i]。A[j][i]在数组 B 的第 (2*n-j-1) * j / 2 + i 的位置中找到。
23
三对角矩阵的压缩存储
a00 a01 0 0
0
0
A a0010
a11
a21 0
a12
a22 0
0
a23 an2n3
0
0 an2n2
0
0
an2n1
13
三维数组
• 各维元素个数为 m1, m2, m3 • 下标为 i1, i2, i3的数组元素的存储地址：
（按页／行／列存放）
LOC ( i1, i2, i3 ) = a + ( i1* m2 * m3 + i2* m3 + i3 ) * l
前i1页
总元素
个数
第i1页 第 i2 行 前i2行 前 i3 列
• 动态定义的数组，其维界不在说明语句中显 式定义，而是在程序运行中创建数组对象时 通过 new 动态分配和初始化，在对象销毁时 通过 delete 动态释放。
• 用一维内存来表示多维数组，就必须按某种 次序将数组元素排列到一个序列中。
10
二维数组的动态定义和初始化
#include <iostream.h> ………… int **A; int row = 3, col = 3; int i, j; A = new int *[row]; for (i = 0; i < row; i++)
前i行元素总数 第i行第j个元素前元素个数
22
若 i j，数组元素A[i][j]在数组B中的存放位
置为
n + (n-1) + (n-2) + + (n-i+1) + j-i = = (2*n-i+1) * i / 2 + j-i = = (2*n-i-1) * i / 2 + j 若i > j，数组元素A[i][j]在矩阵的下三角部分，