1数据结构与算法.ppt

1、第一章 数据结构与算法,2020年9月15日星期二3时13分19秒,2,1.1算法,考点1：算法的基本概念 计算机解题的实际过程是在实施某种算法，这种算法称为“计算机算法”。 解题方案的准确而完整的描述称为算法。,2020年9月15日星期二3时13分19秒,3,1.算法的基本特征,可行性：执行后能得到满意结果。 确定性：算法中每个步骤必须明确定义，不允许多义性。 有穷性：算法必须在有限时间内做完。 拥有足够的情报：确保算法有效还取决于情报是否足够。,2020年9月15日星期二3时13分19秒,4,2.算法的基本要素,算法对数据的运算和操作 算术运算：加、减、乘、除等； 逻辑运算：“与”、“或”

2、、“非”等； 关系运算：“大于”、“小于”、 “等于”、“不等于”等。 数据传输：主要包括赋值、输入、输出操作。,算法组成的基本要素：1、对数据对象的运算操作；2、算法的控制结构。,2020年9月15日星期二3时13分19秒,5,2.算法的基本要素,算法的控制结构： 算法中各操作之间的执行。 算法一般都可以用顺序、选择、循环3种基本控制结构组合而成。,2020年9月15日星期二3时13分19秒,6,3.算法设计的基本方法,列举法：根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验那些需要、那些不需要。,2020年9月15日星期二3时13分19秒,7,3.算法设计的基本方法,归纳法：通

3、过列举少量特殊情况，经过分析，最后找出一般的关系。 通过观察一些简单而特殊的情况，最后总结出一般性的结论。,2020年9月15日星期二3时13分19秒,8,3.算法设计的基本方法,递推：从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。,2020年9月15日星期二3时13分19秒,9,3.算法设计的基本方法,递归：将复杂的问题逐层分解成成简单问题。解决最简单的问题后，再沿原来的分解逆过程逐步进行综合。,2020年9月15日星期二3时13分19秒,10,3.算法设计的基本方法,减半递推技术：分治解决法。 “减半”，是指将问题的规模减半，问题的性质不变， “递推”，是指重复“减半”的过程

4、。,例：10人按高矮排队，一人去与之比较,2020年9月15日星期二3时13分19秒,11,3.算法设计的基本方法,回溯法：有些实际问题很难归纳一组简单的递推公式或直观的求解步骤，也不能进行无限列举。对此问题，一种有效的方法就是“试”。通过对问题的分析，找出一个解决问题的线索。试探、回退在逐步试探。,例：找路,2020年9月15日星期二3时13分19秒,12,4.算法设计的要求,通常一个好的算法应达到如下要求： （1）正确性： 程序不含语法错误； 数入数据能够得到满足规格说明要求的结果； 程序对于特殊输入数据能够得到满足规格说明要求的结果； 程序对于合法的输入数据都能产生满足规格说明要求的结果

5、；,2020年9月15日星期二3时13分19秒,13,4.算法设计的要求,（2）可读性：算法主要是为了方便人的阅读与交流，其次才是执行。,2020年9月15日星期二3时13分19秒,14,4.算法设计的要求,（3）健壮性：当输入数据非法时，算法也能适当作出反应或进行处理，而不会产生莫名其妙的结果。,2020年9月15日星期二3时13分19秒,15,4.算法设计的要求,（4）效率与低存储量需求： 效率指的是程序执行时，对于同一个问题如果有多个算法可以解决，执行时间短的算法效率高；存储量需求指算法执行过程中所需要的最大存储空间。,2020年9月15日星期二3时13分19秒,16,考点2：算法的复杂

6、度,1.算法的时间复杂度 执行算法所需要的计算工作量。 算法工作量=（n） n:问题的规模（整数）；,2020年9月15日星期二3时13分19秒,17,算法的时间复杂度,（1）平均性态 各种特定输入下的基本运算次数的加权平均值来度量的算法,X：所有可能输入中的某个特定输入,X出现的概率,算法在输入X时所执行的运算次数,当规模为n时，算法所执行的基本运算次数,2020年9月15日星期二3时13分19秒,18,算法的时间复杂度,（2）最坏情况复杂性 规模为n时，算法执行的最大次数,2020年9月15日星期二3时13分19秒,19,考点2：算法的复杂度,2.算法的空间复杂度 执行算法所需要的内存空间

7、。 算法程序所占空间+输入初始数据空间+算法执行过程所占空间；,2020年9月15日星期二3时13分19秒,20,1.2数据结构的基本概念,考点3：数据结构的定义 相互之间存在的一种或多种特定关系的数据集合，即数据的组织形式。 研究：逻辑结构、存储关系、数据运算,2020年9月15日星期二3时13分19秒,21,考点3：数据结构的定义,提高数据处理效率： 速度，存储空间。,2020年9月15日星期二3时13分19秒,22,考点3：数据结构的定义,数据：客观事物的符号表示。 数据元素：数据的基本单位。 数据对象：性质相同的数据集合。,2020年9月15日星期二3时13分19秒,23,1.2数据结

8、构的基本概念,1.数据的逻辑结构 反映数据元素之间关系的数据元素集合（数据对象）的表示。 包括：元素的信息、数据元素之间的前后件关系。 结构：集合、线性结构、树形结构、图形结构。四种。,前后件：前驱、后件。,2020年9月15日星期二3时13分19秒,24,数据元素1,数据元素2,数据元素3,线性结构：,A,E,D,C,B,树形结构：,*数据元素B的逻辑结构有两个要素：数据的集合D；数据元素前后的关系R : B=(D,R),2020年9月15日星期二3时13分19秒,25,1.2数据结构的基本概念,2.数据的存储结构 数据逻辑结构在计算机存储空间的存放形式。 一种逻辑结构的数据可以表示成多种存

9、储结构：顺序、链接、索引等。,2020年9月15日星期二3时13分19秒,26,1.2数据结构的基本概念,考点4：数据结构的图形表示 数据结构可以用二元关系表示（B=(D,R)），还可以用图形表示：例如：辈分关系。,父亲,儿子,女儿,方框表示元素；（数据结点/结点） 前件结点； 后件结点； 根节点和终结节点（叶子节点）。,2020年9月15日星期二3时13分19秒,27,1.2数据结构的基本概念,考点5：线性结构和非线性结构 根据复杂程度分为：线性结构和非线性结构。 空数据：一个元素都没有。 非空数据如果满足：有且只有一个根节点；每个节点最多有一个前件节点、也最多有一个后件节点。就是线性结构。

10、,2020年9月15日星期二3时13分19秒,28,1.3线性表与顺序存储结构,考点6：线性表的定义 线性表是n(n=0)个元素构成的有限序列(a1,a2,an)。 （1）有且只有一个根结点a1,它无前件； （2）有且只有一个终端结点an,它无后件； （3）其他所有结点有且只有一个前件，也有且只有一个后件。,2020年9月15日星期二3时13分19秒,29,1.3线性表与顺序存储结构,考点7：线性表的存储结构 线性表的顺序表指的是用一组地址连续的存储单元依次存储线性表的数据元素。,2020年9月15日星期二3时13分19秒,30,1.3线性表与顺序存储结构,考点7：线性表的存储结构,2020年

11、9月15日星期二3时13分19秒,31,1.3线性表与顺序存储结构,对线性表的运算： 插入、删除、查找、排序、分解、合并、复制、逆转。,2020年9月15日星期二3时13分19秒,32,1.3线性表与顺序存储结构,考点8：顺序表的插入运算： 在第i个位置上插入新的结点x: 线性表变化 （a1,ai-1,ai,an）变为 （a1,ai-1,x,ai,an）长度变为n+1。 复杂度的计算：移动次数n-i+1 移动的平均次数（期望值）：Eis(n),备注：,2020年9月15日星期二3时13分19秒,33,1.3线性表与顺序存储结构,备注：,Pi(n-i+1),2020年9月15日星期二3时13分1

12、9秒,34,1.3线性表与顺序存储结构,考点9：顺序表的删除运算： 在第i个位置上删除新的结点ai: 线性表变化 （a1,ai-1,ai,an）变为 （a1,ai-1, ai+1,an）长度变为n-1。 复杂度的计算：移动次数n-i 移动的平均次数（期望值）：Eds(n),备注：,2020年9月15日星期二3时13分19秒,35,备注：,Pi(n-i),2020年9月15日星期二3时13分19秒,36,1.4栈和队列,考点10：栈及基本运算 1.什么是栈？ 特殊的线性表，只能在表的一端进行插入和删除运算的线性表。 假设栈s=(a1,a2,an),则a1称为栈底元素，an成为栈顶元素。,2020

13、年9月15日星期二3时13分19秒,37,1.4栈和队列,考点10：栈及基本运算,进栈,退栈,top,bottom,栈：后进先出表,2020年9月15日星期二3时13分19秒,38,1.4栈和队列,2.栈的顺序存储及其运算,进栈时会发生上溢错误,栈空,栈满,正常,2020年9月15日星期二3时13分19秒,39,1.4栈和队列,考点11：队列及基本运算 1.什么是队列 队列：只允许在一端（对头）删除，在另一端（队尾）插入特殊的线性表。 假设队列q=(a1,a2,an),则a1称为对头元素，an成为队尾元素。,2020年9月15日星期二3时13分19秒,40,队列(queue)的运算示意,一个队

14、列,插入,删除,front,rear,front,rear,front,rear,排头指针指向的是表头节点,2020年9月15日星期二3时13分19秒,41,1.4栈和队列,2.循环队列及其算法 实际应用中一般使用循环队列。 循环队列：将队列的存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间。,front,rear,2020年9月15日星期二3时13分19秒,42,1.4栈和队列,循环队列及其算法,front,rear,0,1,Maxsize-1,Q_front,Q_rear,队列数据,Q_rear= Q_front时队列是“满”或“空”；s=0 “空”;s=1 “非空”,s,202

15、0年9月15日星期二3时13分19秒,43,1.4栈和队列,入队运算和退队运算,0,1,Maxsize-1,Q_front,Q_rear,队列数据,Q_rear= Q_front时队列是“满”或“空”；s=0 “空”;s=1 “非空”,入队运算（可能上溢）,退队运算（可能下溢）,2020年9月15日星期二3时13分19秒,44,1.5线性链表,考点12：线性单链表的结构及其基本运算 1.什么是线性链表？ 线性表顺序存储的缺点：插入删除时移动大量元素；有“上溢”情况；空间不便于动态分配。 线性表链式的基本概念： 单链表（线性链表）：只有一个指针域存放下一个元素地址； 链式存储方式：每个结点有两部

16、分组成，数据域存放数据元素值；指针域存放指针。,数据域 指针域,V(i) NEXT(i),存储序号 i,2020年9月15日星期二3时13分19秒,45,2.线性单链表的存储结构,用一组存储单元来依次存放线性表的结点，用指针pointer或链link指示其后件结点的地址。,data1,next,data2,next,data3,next,.,头指针HEAD,指针为空NULL,2020年9月15日星期二3时13分19秒,46,2.带链的栈和队列,（1）栈也是线性表。带链的栈称为可利用栈。,an,an-1,a1,.,top,0,（2）队列也是线性表。也可以采用链式存储结构。,an,an-1,a1,

17、.,front,0,rear,2020年9月15日星期二3时13分19秒,47,考点13：线性链表的基本运算,插入： 删除： 合并： 分解： 逆转： 复制： 排序： 查找：,2020年9月15日星期二3时13分19秒,48,1.在线性链表中查找指定元素,在链表中，查找是否有结点只等于x的结点，若有的话，则返回到首次找到的其值为x的结点的存储位置；否则返回到NULL。,2020年9月15日星期二3时13分19秒,49,2.线性链表的插入,ai-1,x,ai,HEAD,线性链表插入过程中不发生数据元素移动现象，只要改变有关结点的指针即可，提高了效率。,2020年9月15日星期二3时13分19秒,5

18、0,3.线性链表的删除,ai-1,ai,HEAD,线性链表删除过程中不发生数据元素移动现象，只要改变有关结点的指针即可，提高了效率。,ai+1,2020年9月15日星期二3时13分19秒,51,考点14：线性双向链表的结构及其基本运算,1.什么是双向链表：单链表中查找直接后件元素时间复杂度为O(1)；查找它的直接前件时间复杂度为O(n)；增加一个指针域指向前件元素，可以减少时间复杂度。,HEAD,0,双向链表示意图,2020年9月15日星期二3时13分19秒,52,2.双向链表的基本运算,（1）插入,X,2020年9月15日星期二3时13分19秒,53,2.双向链表的基本运算,（1）删除,X,

19、Y,Z,2020年9月15日星期二3时13分19秒,54,考点15：循环链表的结构及其基本运算,单链表的最后一个结点的指针域为NULL;如果将它改为存放链表中头结点的地址，这样就构成了一个环。,HEAD,HEAD,非空循环链表,空循环链表,2020年9月15日星期二3时13分19秒,55,1.6树与二叉树,考点16：树的定义 树是由n(n=o)个节点组成的有限集合；n=0,空树。有一个根（只有直接后件，没有直接前件）；除根节点外其他结点是子树（仅有一个直接前件，但可以有多个后件）。,A,A,2020年9月15日星期二3时13分19秒,56,考点17：二叉树的定义及其基本性质,1.二叉树的定义

20、二叉树只有一个跟结点，每个结点最多只有两棵树（左子树、右子树）,A,A,2020年9月15日星期二3时13分19秒,57,2.二叉树的基本性质,性质1：在二叉树的第k层上至多有2 个结点（k=1）; 性质2：深度为m的二叉树至多有2-1个结点。 性质3：对任意一棵二叉树，度为0的结点数总比度为2的结点数多1。（n0=n2+1）见后面的图 性质4：具有n个结点的完全二叉树深度至少为log2n+1。(性质2反推),K-1,m,2 =n , log2n=m,m,2020年9月15日星期二3时13分19秒,58,3.满二叉树与完全二叉树,（1）满二叉树k层上有2 个结点 （2）完全二叉树：除最后一层外

21、，其他都满。,K-1,2020年9月15日星期二3时13分19秒,59,4.二叉树的存储结构,数据域，左指针域，右指针域。,L(i),V(i),R(i),2020年9月15日星期二3时13分19秒,60,考点18：二叉树的遍历,所谓遍历：就是按某种次序，访问二叉树中的所有结点，使得每个结点仅被访问一次。 1.前序遍历（根-左-右） 2.中序遍历（左-根-右） 3.后序遍历（左-右-根）,A,B,C,D,E,F,2020年9月15日星期二3时13分19秒,61,1.7查找技术,考点19：顺序查找与二分查找算法 1.顺序查找 从表的一端开始，顺序扫描，依次将扫描的关键字和待寻找的k值比较，若相等，

22、则查找成功；若扫描完毕，仍未找到，则扫描失败。 以下方式只能顺序查找： （1）线性表示无序表；（2）有序线性表采用链式存储结构,最坏的情况下，查找 n 次,2020年9月15日星期二3时13分19秒,62,2.二分法查找,也称折半查找：要求是顺序表，且表中的元素必须按关键字排序。 例如：8，17，25，44，68，77，98，100，115，125,low,high,mid,low,high,mid,low,high,mid,查找k=7,一次比较后：,二次比较后：,最坏的情况下，查找 log2n 次,2020年9月15日星期二3时13分19秒,63,1.8排序技术,排序（sort）或称分类：记

23、录按关键字递增或递减的次序排列。,2020年9月15日星期二3时13分19秒,64,考点20：交换类排序法,1.冒泡排序： 冒泡过程： （1）从表头开始扫描，逐次比较相邻两元素的大小，若前面的大，、则逆序，直到最后。 （2）从后到前者相反。 （3）对剩下的线性表重复以上过程，直到剩下的线性表为空，此时线性表已经变为有序,交换类（冒泡排序、快速排序）最坏的情况下，查找 n(n-1)/2 次,2020年9月15日星期二3时13分19秒,65,例如：,15，3，23，14，21，8 3，15，14，21，8，23 3，14，15，8，21，23 3，14，8，15，21，23 3，8，14，15，21，23,冒泡排序：,2020年9月15日星期二3时13分19秒,66,2.快速排序,任取待排序列中的某个元素（一般为第一个元素）作基准，通过一趟排序，将待排元素分为左右两个子序，左子序列元素排序码均小于或等于基准元素排序码，右子序列元素排序码均大于基准元素排序码。 然后分别对两