数据结构教学方法探讨-陈越 共44页PPT资料

curr parent
curr parent p curr 33
30 of 151
31 of 151
int Insert(BiTreeNode **root, DataType item) { BiTreeNode *current, *parent = NULL, *p;
current = *root; while(current != NULL) { if(current->data.key == item.key) return 0;
if(S.list[mid].key == x. key)
return mid;
//查找成功
else if (S.list[mid].key < x.key)
low = mid + 1;
else
high = mid - 1;
}
return -1;
//查找失败
}
算法效率分析
15 of 151
1次比较就查找成功的元素有1个（20），即中间值； 2次比较就查找成功的元素有2个（21），即1/4处（或3/4）处； 3次比较就查找成功的元素有4个（22），即1/8处（或3/8）处… 4次比较就查找成功的元素有8个（23），即1/16处（或3/16）处… …… 则第m次比较时查找成功的元素会有（2m-1）个； 为方便起见，假设表中全部n个元素＝ 2m-1个，此时就不讨论第m 次比较后还有剩余元素的情况了。
子树或右子树中去找；
while(p != NULL) ③直到结点不存在
{
if(p->data.key == item.key) return 1;
if(item.key > p->data.key) p = p->rightChild;

INSERT(L,x,i)
DELETE(L,i)
2020/5/10
数据结构
22
顺序表的特点： 用物理位置上的邻接关系表示结点间的逻辑关系
顺序表的优点： （1）无须增加额外的存储空间表示结点间的逻辑关系。
（2）可以方便地随机存取表中任一结点。
顺序表的缺点： （1）插入和删除运算不方便，通常须移动大量结点，效率 较低。 （2）难以进行连续的存储空间的预分配，尤其是当表变化 较大时。
数据结构
15
第一章 概 论
本章要求:
1、掌握数据、数据元素、数据结构等基本概念。 2、掌握数据逻辑结构和物理结构的分类。 3、学会算法分析的基本方法。
2020/5/10
数据结构
16
第二章 线性表
本章要学习的主要内容 1、线性表的逻辑结构及基本运算 2、线性表的顺序存储结构 3、线性表的链式存储结构：单链表、循环链表、双 链表、静态链表 4、顺序表和链表的比较
2.数据元素(Data Element): 数据的基本单位, 即数据集合中的一个个体。也称元素、 结点、顶点、记录
数据元素由数据项(data item)组成
数据项:是具有独立含义的最小标识单位 关键字（key)：唯一能识别一个数据元素的数据项。
2020/5/10
数据结构
4
3、数据类型(Data Type): 是具有相同性质的计算机数据的集合及在这个
顺序表是一种随机存取结构
2020/5/10
数据结构
20
4、顺序表的描述：
typedef int datetype; #define maxsize 1024 typedef struct { datatype data[maxsize];

pos len
堆分配存储特点：仍用一组连续的存储单元来存放串，
但存储空间是在程序执行过程中动态分配而得。
思路：利用malloc函数合理预设串长空间。
有的语言允许对串常量命名，以使程序易读、易写。 【例】C++中，可定义串常量path
const char path[]="dir/bin/appl";
5
练1：串是由
字符组成的序
列，一般0记个或多个
为 S=’a1a2……an’
练2：现。有以下4个字符串：
a =‘BEI’
b =‘JING’ c = ‘BEIJING’
数据结构课程的内容
第4章 串 （String）
1. 定义 2. 逻辑结构 3. 存储结构 4. 运算规则 5. 实现方式
4.1 串类型的定义
4.2 串的表示和实现 4.3 串的模式匹配算法
4.1 串类型的定义
串即字符串，是由零个或多个字符组成的有限序列，是数据 元素为单个字符的特殊线性表。
记为： s =‘ a1 , a2 , …….. , an’ (n≥0 )
讨论：想存放超长字符串怎么办？——静态数组有缺陷！
改用动态分配的一维数组—— “堆”！
例：用顺序存储方式实现求子串函数SubString(&Sub, S, pos,
len)
将串S中从第pos个字符开始长度为len的字符序列复 制到串Sub中（注：串Sub的预留长度与Ssub, SString S, int pos, int len )
d
= ‘问B：EI①JI他NG们’各自的长度？ a =3，b =4，c = 7，d=8
② a是哪个串的子串？在主串中的位置是多少？

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

计。
+ 采用教材：李春葆主编的《数据结构教程》 （C#语言描述），清华大学出版社出版。
+
2
课程定位
+
本课程为计算机软件专业技术人员提供必要
的专业基础知识和技能训练。通过本课程的学习，
使学生熟练掌握计算机程序设计中常见的各种数
据的逻辑结构、存储结构及相应的运算，初步掌
握算法的时间复杂度分析和空间复杂度分析的技
术，并能根据计算机加工的数据特性运用数据结
构的知识和技巧设计出更好的算法和程序，并进
一步培养良好的程序设计及编写风格。
3
课程目标： + 通过本课程学习，学生掌握数据结构相关的
基础知识和基本技能，了解这些知识与技能在实 践中的应用，使学生学会如何把现实世界的问题 转化为计算机内部的表示和处理。培养科学的认 知理念、认知方法和实事求是、勇于实践的学习 态度；培养科学、独立的思考和辨识能力；培养 学生爱岗敬业，细心踏实、勇于创新的职业精神。
11
评分内容 平时表现（出勤）
平时作业及测试
标准
1.无故旷课一次扣2分 2.事假、病假一次扣1分
1.选择4次作业，按时交作业者3-5分 2.只交2次作业，2-3分，未交0分 3.平时测试（2次）：全部完成5分；完成部分2-4分；未完 成0分。
技能考核
1.课上给出操作任务90%以上完成者，28-30分； 2.完成80%-90%，学习态度认真者25-27分； 3.完成50%-80%，18-24分； 4.完成<50%，态度认真，18分 5.未参加者，0分
+ （3）社会能力：学会如何把现实世界的问题转 化为计算机内部的表示和处理。学会组织数据， 选择合适的逻辑结构和存储结构。

依据数据集中可能出现的最坏情况估算出的时间复杂度 称为最坏时间复杂度。
五、平均时间复杂度
在假设数据集的分布是等概率的条件下，估算出的时间 复杂度称为平均时间复杂度。
例：顺序查找
2020/3/11
数据结构
14
第一章 概 论
五、空间复杂度S(n)： 算法所耗费的存储空间，仍是问题规模n的函数。
2020/3/11
2020/3/11
数据结构
25
typedef int datatype; typedef struct node {datatype data; struct node *next; } linklist; linklist *head, *p;
说明：•区分指针变量和结点变量 :p ,*p •结点的动态分配和释放
2020/3/11
数据结构
11
第一章 概 论
1.4 算法分析
一、算法评价五要素 （1）正确性 （2）执行算法所耗费的时间 （3）执行算法所耗费的空间 （4）可读性 （5）健壮性
2020/3/11
数据结构
12
第一章 概 论
二、算法的时间复杂度
•一个算法所耗费的时间:该算法中每条语句的执行时间之和。 •每条语句的执行时间：该语句的执行次数乘以该语句执行一次 所需时间。 •频度：语句重复执行的次数 •算法的时间耗费T(n)=每条语句的执行的时间
2020/3/11
数据结构
8
例：一个学生成绩表： •是一个数据结构 •每行是一个结点（或记录），由学号、姓名、各科成绩 及平均成绩等数据项组成。 •逻辑关系：线性结构 •存储结构： •表的运算：
2020/3/11
数据结构
9
第一章 概 论

2020/2/15
数据结构
17
2.1 线性表的概念及运算
一、逻辑结构 1.描述: 线性表是由n (n>=0)个数据元素(点)a1,a2,….,ai,….,an
组成的有限序列。其中，数据元素的个数n定义为表长。 当n=0时称为空表，非空的线性表(n>0)记为： (a1,a2,….,ai,…..,an)
2020/2/15
数据结构
11
第一章 概 论
1.4 算法分析
一、算法评价五要素 （1）正确性 （2）执行算法所耗费的时间 （3）执行算法所耗费的空间 （4）可读性 （5）健壮性
2020/2/15
数据结构
12
第一章 概 论
二、算法的时间复杂度
•一个算法所耗费的时间:该算法中每条语句的执行时间之和。 •每条语句的执行时间：该语句的执行次数乘以该语句执行一次 所需时间。 •频度：语句重复执行的次数 •算法的时间耗费T(n)=每条语句的执行的时间
2020/2/15
数据结构
23
一、链表
2.3 线性表的链式存储
1、 链式存储：用一组任意的存储单元存储线性表, 逻辑上 相邻的结点在物理位置上不一定相邻，结点间 的逻辑关系由存储结点时附加的指针字段表示
2、链表：采用链式存储方法的线性表称为链表。
2020/2/15
数据结构
24
2.3.1 单链表
1、单链表的特点：每个结点只有一个链域，指向其直接后继 （尾结点除外）。
依据数据集中可能出现的最坏情况估算出的时间复杂度 称为最坏时间复杂度。
五、平均时间复杂度
在假设数据集的分布是等概率的条件下，估算出的时间 复杂度称为平均时间复杂度。
例：顺序查找

最小生成树问题
最小生成树问题是图论中的另一类重要问题。 Kruskal算法和Prim算法是解决最小生成树问题的 常用算法。
图的匹配问题
图的匹配问题是图论中的一个经典问题，主要研 究如何在图中找到最大的匹配或者完美匹配。匈 牙利算法是解决图的匹配问题的常用算法。
06
查找与排序算法
查找算法分类及思想
• 选择排序实现原理：在未排序序列中找到最小（大）元素，存放到排序序列的 起始位置；再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序 序列的末尾；重复第二步，直到所有元素均排序完毕。
• 交换排序实现原理：以冒泡排序为例，比较相邻的元素。如果第一个比第二个 大，就交换他们两个；对每一对相邻元素作同样的工作，从开始第一对到结尾 的最后一对。在这一点，最后的元素应该会是最大的数；针对所有的元素重复 以上的步骤，除了最后一个；持续每次对越来越少的元素重复上面的步骤，直 到没有任何一对数字需要比较。
03
栈和队列
栈定义及特点
栈的特点 具有后进先出的特性，即最后进入栈的元素最先出栈
。
栈（Stack）是一种特殊的线性数据结构，其元 素的添加和移除遵循后进先出（LIFO, Last In First Out）的原则。
只能在栈顶进行元素的添加和删除操作。
栈基本操作
01
02
03
04
入栈（Push）：在栈顶 添加一个元素。
二叉树遍历方法
01
02
03
04
前序遍历
先访问根节点，然后遍历左子 树，最后遍历右子树。
中序遍历
先遍历左子树，然后访问根节 点，最后遍历右子树。
后序遍历
先遍历左子树，然后遍历右子 树，最后访问根节点。

(b)入队3个元素(c)出队3个元素
(b) d, e, b, g入队
利用一组连续的存储单元(一维数组)依次存放从队 在循环队列中进行出队、入队操作时，队首、队尾指
队列示意图
在非空队列里，队首指针始终指向队头元素，而队
(b) d, e, b, g入队
8
Q.rear
a5
a4
Q.front
(d)入队2个元素
a1, a2, … , an
的指修针改 和是队依列先中进元先素出的Q的变.re原化a则情r 进况行。的，如图所示。
a3
Q.front
a2
a1
首到队尾的各个元素，称为顺序队列。
(c)
d, e出队Q.front
Q.front
◆出队：首先删去front所指的元素，然后将队首指针front+1，并
◆rear所指的单元始终为空(a。)空队列
i
i, j, k入队
(e)
1
2
3
k
r
01
j5
2
front
43
i
b, g出队
(f )
r, p,
p rear
s, t入队
循环队列操作及指针变化情况
入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针 ，故队空和队满时头尾指针均相等。因此，无法通过front=rear来 判断队列“空”还是“满”。解决此问题的方法是：约定入队前，
数据结构与算法
1算法基础 2数据结构
3栈
4队列
5链表 6树和二叉树
7查找
4队列
✓队列的基本概念 ✓队列运算
✓循环队列及其运算
4队列
1.队列的基本概念