当前位置：文档之家 › 北京工业大学数据结构复习PPT课件

北京工业大学数据结构复习PPT课件

  • 格式：ppt
  • 大小：379.50 KB
  • 文档页数：46

下载文档原格式

  / 46

合集下载

北京工业大学：数据结构与算法分析教学课件第六章树和二叉树

北京工业大学：数据结构与算法分析教学课件第六章树和二叉树
17
插入类
InitBiTree(&T); Assign(T, &e, value); CreateBiTree(&T, definition); InsertChild(T, p, LR, c);
18
删除类
ClearBiTree(&T); DestroyBiTree(&T); DeleteChild(T, p, LR);
42
中（根）序的遍历算法：
若二叉树为空树，则空操作；否则， （1）中序遍历左子树； （2）访问根结点； （3）中序遍历右子树。
43
后（根）序的遍历算法：
若二叉树为空树，则空操作；否则， （1）后序遍历左子树； （2）后序遍历右子树； （3）访问根结点。
44
三、算法的递归描述
void preorder (BiTree T,
章树和二叉树
1
6.1 树的类型定义 6.2 二叉树的类型定义
6.3 二叉树的存储结构 6.4 二叉树的遍历
6.5 线索二叉树 6.6 树和森林的表示方法
6.7 树和森林的遍历 6.8 哈夫曼树与哈夫曼编码
2
6.1 树的类型定义
3
数据对象 D：
D是具有相同特性的数据元素的集合。
数据关系 R：
若D为空集，则称为空树； 否则: (1) 在D中存在唯一的称为根的数据元素root, (2) 当n>1时，其余结点可分为m (m>0)个互
48
void CountLeaf (BiTree T, int& count){ if ( T ) { if ((!T->lchild)&& (!T->rchild)) count++; // 对叶子结点计数 CountLeaf( T->lchild, count); CountLeaf( T->rchild, count); } // if

数据结构期末复习题整理PPT课件

数据结构期末复习题整理PPT课件
显然m=2，n=3，h=2.带入ABCD中显然答案为：B
第8页/共14页
16.观察如图所示的树，回答下列问题。
哪些是H的祖先？ //沿H往上走到根节点所经过的结点都是他的祖先，答案：E,B,A 结点J的兄弟是那些？ //和她同一个双亲的都是兄弟，答案： F,G 树的深度是多少？//就是他的层次 ，答案： 4 树的度是多少？ //某个结点最多有几个孩子，那个数字就是度，答案： 3 结点H和结点J的层次分别是多少？ //答案：4 ,3
A
B
E
C
F
G
D
H
只要是兄弟就放在右边。只要是孩子就放在左边，图中，AEG是兄 弟，所以都放在右边，排成一排。其他的也都是如此排列。
题中问其根节点的右子树有多少结点，其右子树都是根节点在森林 中的兄弟或者兄弟的孩子。所以答案为n2+n3，所以选：D
I J
第6页/共14页
12.二叉树通常有_____存储结构和_____存储结构两类存储结构。
A．x = HS; HS=HS->next
B．x = HS->data
C．HS=HS->next; x = HS->data D．x = HS->data; HS=HS->next
第2页/共14页
16、在一链队中，设f和r分别为队头和队尾指针，则插入s所指结点的运算是（B）
A．f->next=s;f=s B．r->next =s; r=s
解答：A，这句话，是最优二叉树的特点，记下来就好。B，已知二叉树的前序遍
历和后序遍历的确不能确定这棵树，但是却不是因为不能确定根节点，相反的，他只 能确定根节点，而左右孩子却不能确定，所以不能确定这个树。C，前序遍历是根左右， 所以任何结点的子树的后继结点都是直接跟在该结点之后 。D，中序遍历是左根右， 后序遍历是左右根，他们第一个都是左，所以，该选项也是正确的。所以答案选:B

数据结构复习课件

数据结构复习课件

（4）数组的应用 ）
北航计算机系
6
第四章
堆栈和队列
（1）堆栈和队列的基本概念 ）
• 定义 • 基本操作 • 特殊性
（2）堆栈和队列的存储结构 ）
• 顺序存储结构 插入、 插入、删除操作对应的算法设计 • 链式存储结构 插入、 插入、删除操作对应的算法设计
（3）堆栈和队列在解决实际问题中的应用 ）
北航计算机系
文件及其查找
（1）文件的基本概念 ）
• 名词术语 • 文件的逻辑结构和物理结构 • 文件的基本操作 查找、插入、删除、修改、 --- 查找、插入、删除、修改、排序
• • • • 顺序文件的分类 连续顺序文件的顺序查找方法 排序连续顺序文件的折半查找方法 链接顺序文件的查找方法
（2）顺序文件 ）顺序文件
北航计算机系
17
每一种排序方法的的基本原理、规律、特点。 每一种排序方法的的基本原理、规律、特点。 最好和最坏情况下排序过程中进行的元素之间的 比较次数，如插入排序方法、选择排序方法。 比较次数，如插入排序方法、选择排序方法。 某些排序法的排序趟数有何特点。 某些排序法的排序趟数有何特点。
北航计算机系
7
第五章 广义表
（1）广义表的基本概念 ） （2）广义表的存储结构 ） （3）多元多项式的广义表存储方法 ）
北航计算机系
8
第六章 串 （1）串的基本概念 ）
• 串的定义 • 几个名词术语、概念 几个名词术语、
（2）串的基本操作 ） （3）串的存储结构 ）
紧缩格式、 • 顺序存储结构 -- 紧缩格式、非紧缩格式等 • 链式存储结构
顺序、链式、 （2）关于算法 ） 索引、 索引、散列 • 算法的定义与完整算法的特征 • 算法的描述 • SPARKS语言 语言 • 算法分析的基本概念

《复习提纲数据结构》课件

《复习提纲数据结构》课件

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

数据结构ppt课件完整版

数据结构ppt课件完整版

针对有序数据集合，每次通过中间元素将 待查找区间缩小为之前的一半，直到找到 元素或区间为空。
哈希查找
树形查找
通过哈希函数将数据映射到哈希表中，实 现快速查找。
如二叉搜索树、平衡树等，通过树形结构实 现高效查找。
排序算法分类及实现原理
插入排序
将待排序元素逐个插入到已排序序列中，直到所有元素均插入完毕。
由n（n>=0）个具有相同类型 的数据元素（结点）a1，a2，
...，an组成的有序序列。
同一性
每个元素必须是同一类型的数 据。
有序性
元素之间具有一对一的前驱和 后继关系，即除首尾元素外， 每个元素都有一个前驱和一个 后继。
可变性
线性表的长度可变，即可以插 入或删除元素。
顺序存储结构与链式存储结构比较
定义
用一段连续的存储单元依次存储线性 表的数据元素。
优点
可以随机存取表中任一元素，且存取 时间复杂度为O(1)。
顺序存储结构与链式存储结构比较
• 缺点：插入和删除操作需要移动大量元素，时间 复杂度高；需要预先分配存储空间，容易造成空 间浪费。
顺序存储结构与链式存储结构比较
定义
用一组任意的存储单元存储线性 表的数据元素（这组存储单元可 以是连续的，也可以是不连续的
查找操作
查找指定元素的位置。
遍历操作
访问线性表中的每个元素。
销毁操作
释放线性表占用的存储空间。
03
栈和队列
栈定义及特点
栈（Stack）是一种特殊的线性数据结构，其数据的存 取遵循后进先出（LIFO, Last In First Out）的原则。 栈的特点
具有记忆功能，能保存数据的状态。
栈的基本操作包括入栈（push）、出栈（pop）、查 看栈顶元素（top）等。 只能在栈顶进行数据的插入和删除操作。

北工大(数据结构)11-DSch2-List

北工大(数据结构)11-DSch2-List

插入时逻辑结构的变化： <Kp-1,Kp><Kp-1,value>、<value,Kp>
为了保证逻辑上相邻的元素物理上也相邻， 除非 p=n，否则必须移动第p个及后面的元素

插入算法思想
需要考虑
插入位置是否合理?是否有空间?
插入动作：移动、插入、修改长度 算法步骤： 验参（若表已满、插入位置不合法）：失败退出 第n-1到第p个元素（共n-p个 ）后移一位(腾空间)
删除元素
k0 k1 k2
kp-1 kpkp+1...Kn-1 ...
左移n-1-p个
k0 k1 k2 9 3 5 8 2 7 9 3 8 2 7
kp-1kp+1 ... Kn-1…
逻辑结构变化 <kp-1,kp> <kp,kp+1> <kp-1,kp+1>
3、顺序表的删除
template <class T> //算法描述 bool arrList<T>:: del(const int p){ //删除顺序表aList中位置p的元素 if (curLen <=0){ //验参 cout<<“No element to delete\n”<<endl; return false; } if (p<0|| p>curLen-1){ cout<<“deletion is illegal \n”<<endl; return false; } for( int i=p; i< curLen -1; i++ ) aList[i] = aList[ i+1]; //从前向后(p..n-1)处理,每个元素左移一步 curLen--; //表长-1 return true; } 算法分析： T( n) = O(n) 基本操作：移动； 最好：0次（删表尾）；最差：n-1次（删表头）； 平均：i=1i=n pi*(n-i) = i=1i=n (1/n) *(n-i )=(n-1)/2

北京工业大学：数据结构与算法分析教学课件第三章栈和队


4
A stack is a container of objects that are inserted and removed according to the last-in-first-out (LIFO) principle.
5
3.2 栈的应用举例
例一、 数制转换
算法基于原理： N = (N div d)×d + N mod d
else {state = 0;} break; } case”]”: ...
进退栈的次序 是由问题决定的
}
if (StackEmpty(S)&&state) return OK; …... 12
例三、 迷宫求解
通常用的是“试探与回溯求解”的方法
##########
# # $ $ $ #
#
#
# $ $ $ #
1）凡出现左括弧，则进栈；
2）凡出现右括弧，首先检查栈是否空 若栈空，则表明该“右括弧”多余 否则和栈顶元素比较， 若相匹配，则“左括弧出栈” 否则表明不匹配
3）表达式检验结束时， 若栈空，则表明表达式中匹配正确 否则表明“左括弧”有余
11
Status matching(string& exp) {
#define STACK_INIT_SIZE 100;
#define STACKINCREMENT 10;
typedef struct {
t stacksize;
} SqStack;
21
Status InitStack (SqStack &S) {// 构造一个空栈S S.elem=new SElemType[STACK_INIT_SIZE];

北工大 数据结构8 图_2


DestroyGraph 前置条件：图已存在 输入：无 功能：销毁图 输出：无 后置条件：释放图所占用的存储空间 GetVex 前置条件：图已存在 输入：顶点v 功能：在图中查找顶点v的数据信息 输出：顶点v的数据信息 后置条件：图保持不变 endADT
8.2 图的存储结构及实现
是否可以采用顺序存储结构存储图?
v2
A(G) =
1 1 2 3 4 0 0 0 1
2 1 0 0 0
3 1 0 0 0
4 0 0 1 0
v3
v4
有向图，顶点 vi 的出度是邻接矩阵中第 i 行的元素之和。 顶点 vi 的入度是邻接矩阵中第 i 列的元素之和。 例 v1 的出度为 2；入度为 1。
1 2 3 4 5 1 2 3 4 5 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 0 0 1 2 3 4
例无向图 G v1 v3 v4 v5 v2
1 2 A(G) = 3 4 5
1 2 3 4 5 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 0 0
无向图，顶点 vi 的度是邻接矩阵中第 i 行或第 i 列的元素之和。 例 G1中，v1 的度为 2。
例有向图 G v1
aij =
例有向图 G
1
v1
v2
v3
v4
例无向图 G v1 v3 v4 v5 v2
1 2 A(G) = 3 4 5
1 2 3 4 5 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 0 0
优点:
1. 2.
容易判断任意两个顶点之间是否有边或弧。 容易求取各个顶点的度。

数据结构课件PPT


二分查找
二分查找法
将有序数据集分成两个部分，每次取中间位置的值与目标值进行比较，根据比 较结果缩小查找范围，直到找到目标值或确定目标值不存在。
优缺点
查找速度快，但要求数据集必须是有序的。
哈希查找
哈希表
利用哈希函数将数据元素映射到内存中的地址，实现数据的 快速查找。
优缺点
查找速度快，但需要解决哈希冲突问题，并可能存在哈希表 过大或过小的问题。
。
数据结构的基本概念
数据结构的基本概念包括：数据、数据 元素、数据类型、数据结构等。
数据结构是指数据的组织形式，即数据 元素之间的相互关系。
数据类型是指一组具有相同特征和操作 的数据对象（如整数、实数、字符串等 ）。
数据是信息的载体，是描述客观事物的 符号记录。
数据元素是数据的基本单位，一个数据 元素可以由若干个数据项组成。
稳定排序
归并排序是一种稳定的排序算法，即相等的元素在排序后 保持其原有的顺序。
非递归算法
归并排序是一种非递归算法，即通过迭代方式实现算法过 程。
需要额外的空间
归并排序需要额外的空间来存储中间结果和临时变量。
查找算法
06
线性查找
顺序查找
逐一比对数据元素，直到找到目 标值或遍历完整个数据集。
优缺点
简单易懂，但效率较低，适用于 数据量较小的情况。
拓扑排序的应用
拓扑排序是一种对有向无环图进行排序的算法， 它按照拓扑关系将图的节点排列成一个线性序列 。
有向无环图是一种没有环路的有向图，拓扑排序 可以有效地解决有向无环图的排序问题。
拓扑排序的应用非常广泛，包括确定任务的执行 顺序、确定事件的发生顺序等。
拓扑排序的基本思路是从有向无环图的任一节点 开始，删除该节点，并记录下该节点的所有后继 节点的编号，然后按编号从小到大的顺序重复以 上步骤。

北京工业大学 数据结构 期末复习ppt详解.


template <class Elem> Array<Elem>::Array( int sz ) {
size = sz; data = new Elem[size];}
template <class Elem> int Array<Elem>::GetSize( ){
return size; } 3、类模板的用法
n1 wi li i0
第28页，共47页。
建树
100 0
42
0
19 23
0
f
6
8
11
h
18
3
g 7
5
a下标：1
a: 0001
b:10
1
c:1110
58
0
1
29
29
b
2
14
e
0
5
7
c3
d:1111 f:01 g:0000
1 h:001
15
d8
4
第29页，共47页。
与算法有关的典型例题
已知一棵二叉树的前序和中序（后序和 中序）遍历序列，构造对应的二叉树
第1页，共47页。
考试题型
单选：5题，共10分 填空：5题，共10分 简答题：5题，共45分
算法阅读：15分
算法设计：20分
考试要求：闭卷
第2页，共47页。
第1章 概论
DS描述“按一定逻辑关系组织的数据元素的表示及相关操作
数据逻辑结构：线性结构、树形结构和图形结构 数据存储结构：顺序方法、链接方法、索引方法、散列方法
3.
if(root!=NULL){
4.
Visit(root->value( ));
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

.
8
2.1.2 线性表的存储结构
逻辑结构存储空间 的映射
数据存储单元 建立映射 关系存储单元之间关系 建立映射
线性表2类存储结构 1. 顺序存储（定长的一维数组结构、向量型顺序存储结构 ）
为整个元素动态分配连续空间
特点：逻辑相邻物理也相邻
2. 链式存储（变长的线性表存储结构）
按需分配(插入:分配一个结点/删除:回收一结点) 特点：逻辑相邻物理不一定相邻
则应该采用的存储结构是 。
.
12
第3章 栈与队列
栈与队列的定义、ADT定义及基本操作。 栈的应用：会跟踪递归函数执行过程
* 深度（纵向）周游 表达式求值(中缀后缀求值)
*队列的应用：按层周游 注意：熟悉ADT的操作形式，会直接调用抽 象数据类型中定义的操作
.
13
a/(b-c)+d*e# abc-/de*+
template <class Elem> Array<Elem>::Array( int sz ) {
size = sz; data = new Elem[size];}
template <class Elem> int Array<Elem>::GetSize( ){
return size; }
抽象数据类型ADT
算法4个特性：通用性、有效性、确定性、有穷性
算法分析：T(n)、S(n)算法分析的相关概念；最差、最
佳与平均情况的意义
.
2
ADT的定义
三元组表示 ADT=(D,R,P) ADT 抽象数据类型名 {
数据的抽象
数据对象D:<数据对象的定义>
数据关系R :<数据关系的定义>
清楚线性表定义、理解类定义及抽象数据 类型中定义的各个基本操作含义
存储形式：顺序存储结构、链式存储结构
顺序存储结构的特点：
1.逻辑结构与物理结构一致； 2.属于随机存取方式 缺点：插入\删除元素需要移动，平均约一半的元素， 限制了长度变化
链式存储结构的特点：
1.逻辑结构与物理结构不一致；
2.属于顺序存取方式
.
14
后缀表达式求值
循环：依次分析输入序列： 1.输入是操作数：则入栈； 2.输入是运算符：则两次出栈，取操作数2和操 作数1，按照运算符进行计算。将结果入栈。
重复，直至遇到结束符“=” 此时栈顶值就是输入表达式的值。
.
15
第 4 章 字符串(了解）
基本概念 存储结构（顺序、标准类） 基本操作的含义
6
算法指的是（ A. 计算机程序 C. 排序算法
题型举例
）。 B. 解决问题的计算方法 D. 解决问题的有限运算序列
将长度为 n 的单链表接在长度为 m 的单链表之 后的算法时间复杂度为 ( ) 。
A. O( n )
B. O( 1 )
C. O( m )
D. O( m + n )
.
7
第2章 线性表
存储紧凑（逻辑结构由存储相对位置体现，没使用指针，不 用花费附加开销 ）
随机访问（给定下标,常量时间可定位）
链表优点
不限定长度（无需事先了解线性表的长度，允许线性表的长 度有很大变化 ）
不必移动，仅需改指针即可插删（能够适应经常插入删除内 部元素的情况 ）
适用
不能确定长度上限、频繁插删：用链式存储结构
.
16
第5章 二叉树
➢ 定义、性质、存储结构（相应的类定义） ➢ 满二叉树、完全二叉树及扩充二叉树 ➢ 抽象数据类型定义中的基本操作含义 ➢ 深度周游（递归与非递归），广度周游 ➢ 二叉搜索树插入、删除（改进）与检索算法；
template <class Elem> //类模板 Array 可接受任何类型作为参数
class Array { Elem* data;
int size;
//声明类模板Array的类数据
public: Array( int sz ) ;
//函数成员
int GetSize( ) ;
};
2、函数成员定义
3、类模板的用法
Array<int> int_array(100); //Array接收int作参数,
常见上限g(n)的种类(用于比较各算法优劣)
O(1)<O(logn)<O(n)<O(nlogn)<O(n2)
常数阶 对数 线性 对数乘积 平方
按位置频繁进行读取、数据域占用空间小于指针域：用顺序
存储结构
.
11
题型举例
有序的顺序表与无序的顺序表相比，其操作优势 是（ ）。
A. 删除快 B. 插入快
C. 生成快 D. 查找快。
若对线性表进行的主要操作是按下标存取，且很
少插入和删除，则应该采用的存储结构是_____
；若需要频繁地对线性表进行插入和删除时，
.
9
链表—单向、循环、双向
不特殊说明，均带头结点(避免对空表的特殊处理) 算法：（时间复杂性）
✓在有序表中插入/删除结点 ✓给定元素位置，插入/删除相应结点 注意： ✓对循环链表操作时，尾部的判断 ✓双向链表的插入/删除结点 ✓删除结点一定要释放空间
.
10
2.4 线性表实现方法的比较
顺序表优点
考试题型
单选：5题，共10分
填空：5题，共10分
简答题：5题，共45分
算法阅读：15分
算法设计：20分
考试要求：闭卷
.
1
第1章 概论
DS描述“按一定逻辑关系组织的数据元素的表示及相关
操作
数据逻辑结构：线性结构、树形结构和图形结构
数据存储结构：顺序方法、链接方法、索引方法、散列 方法
基本操作P:<基本操作的定义> } ADT 抽象数据类型名
算法的抽象
用C++类模板的声明表示ADT
.
3
ADT定义类模板
类模板代表一类类，不代表具体的类
类模板的定义格式:
template<class Type> //类型参数Type,使用时用具体数据类型代替
class className{
private:
Type dataList;
…
public:
methodName( );
…
};
C++引入模板概念，是想突出数据的逻辑结构而忽略 其具体的数据类型
.
4
声明、定义和使用 C++类模板(2)
类模板：描述了一组相关的类，它们只能通过类型来区分
1、类模板声明：仅提供了类的名称和类的模板参数
<O(n3)<….<O(2n)<O(n!)
立方
指数 阶乘
常数：g(n) = 1
T
对数：g(n) = logn
线性增长： g(n) = n
2n
n2
n
二阶增长： g(n) = n2
g(n) = nlog(n),
log
n <= nlog(n)增长率 <= n2
指数增长： g(n) = an
n
.