《数据结构选讲各章的要点幻灯片.ppt》由会员分享，可在线阅读，更多相关《数据结构选讲各章的要点幻灯片.ppt（27页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构选讲各章的要点2023/4/111第1页，共27页，编辑于2022年，星期六第一章第一章 绪绪 论论l 数据结构的基本概念数据结构的基本概念 由由某某一一数数据据对对象象及及该该对对象象中中所所有有数数据据成成员员之之间间的的关关系系组成。记为：组成。记为：Data_Structure=D,R 数据的逻辑结构和物理结构。数据的逻辑结构和物理结构。l 算法设计目标和算法效率度量算法设计目标和算法效率度量 算算法法的的正正确确性性；算算法法运运行行的的时时间间因因素素和和空空间间因因素素（高效性）。（高效性）。2023/4/112第2页，共27页，编辑于2022年，星期六第二章第二章 线性
2、表线性表l 线性表的逻辑结构及其基本操作线性表的逻辑结构及其基本操作 插入、删除、定位、插入、删除、定位、.l 线性表的存储结构线性表的存储结构 顺序存储、链式存储；顺序存储、链式存储；各自的优缺点如何？各自的优缺点如何？l 循环链表、双链表、静态链表循环链表、双链表、静态链表2023/4/113第3页，共27页，编辑于2022年，星期六第三章第三章 堆栈和队列堆栈和队列n n堆栈和队列的定义堆栈和队列的定义 （LIFO,FIFO）n n堆栈和队列的基本操作堆栈和队列的基本操作 进栈、退栈、取栈顶元素；进栈、退栈、取栈顶元素；进队、出队。进队、出队。n n循环队列循环队列 队头、队尾指针如何变
3、化？队头、队尾指针如何变化？队空、队满的判断条件？队空、队满的判断条件？2023/4/114第4页，共27页，编辑于2022年，星期六第三章第三章 堆栈和队列（续）堆栈和队列（续）n n迷宫问题迷宫问题 要解决的问题：要解决的问题：要解决的问题：要解决的问题：1 1 1 1、如何从某一坐标点出发搜索其四周的邻点？如何从某一坐标点出发搜索其四周的邻点？如何从某一坐标点出发搜索其四周的邻点？如何从某一坐标点出发搜索其四周的邻点？2 2 2 2、如何存储搜索路径？如何存储搜索路径？如何存储搜索路径？如何存储搜索路径？3 3 3 3、如何防止重复到达某坐标点？如何防止重复到达某坐标点？如何防止重复到达
4、某坐标点？如何防止重复到达某坐标点？4 4 4 4、如何输出搜索路径？如何输出搜索路径？如何输出搜索路径？如何输出搜索路径？2023/4/115第5页，共27页，编辑于2022年，星期六第四章第四章 递归递归n n递归的定义递归的定义递归的定义递归的定义 在链表中寻找等于给定值的结点，在链表中寻找等于给定值的结点，在链表中寻找等于给定值的结点，在链表中寻找等于给定值的结点，并打印其数值？并打印其数值？n n汉诺塔问题汉诺塔问题 解决汉诺塔问题的递归算法。解决汉诺塔问题的递归算法。解决汉诺塔问题的递归算法。解决汉诺塔问题的递归算法。递归工作栈的描述递归工作栈的描述递归工作栈的描述递归工作栈的描述
5、 每每每每一一一一次次次次递递递递归归归归调调调调用用用用时时时时，需需需需要要要要为为为为过过过过程程程程中中中中使使使使用用用用的的的的参参参参数数数数、局局局局部部部部变变变变量量量量等等等等另另另另外外外外分分分分配配配配存存存存储储储储空空空空间间间间。每每每每层层层层递递递递归归归归调调调调用用用用需需需需分分分分配配配配的的的的空空空空间形成递归工作记录，按后进先出的栈组织。间形成递归工作记录，按后进先出的栈组织。间形成递归工作记录，按后进先出的栈组织。间形成递归工作记录，按后进先出的栈组织。2023/4/116第6页，共27页，编辑于2022年，星期六第四章第四章 递归（续）递
6、归（续）n n广义表的定义与表示方法广义表的定义与表示方法 n n(0)个表元素组成的有限序列。个表元素组成的有限序列。特性：有次序性、可递归、有长度、特性：有次序性、可递归、有长度、特性：有次序性、可递归、有长度、特性：有次序性、可递归、有长度、可共享、有深度。可共享、有深度。可共享、有深度。可共享、有深度。广义表链表表示法。广义表链表表示法。2023/4/117第7页，共27页，编辑于2022年，星期六第五章第五章 树和二叉树树和二叉树n树和二叉树的定义及一些基本操作树和二叉树的定义及一些基本操作 根、叶结点、子女结点、双亲结点、兄弟结点、根、叶结点、子女结点、双亲结点、兄弟结点、结点的度
7、、树的高度、结点的度、树的高度、二叉树的五种形态。二叉树的五种形态。求双亲结点、求孩子结点、树的遍历、求双亲结点、求孩子结点、树的遍历、n二叉树的性质及对应的存储方式二叉树的性质及对应的存储方式 二叉树各层的最大结点数？二叉树各层的最大结点数？满二叉树和完全二叉树的定义？满二叉树和完全二叉树的定义？具有具有n个结点的完全二叉树的高度？个结点的完全二叉树的高度？二叉树的存储方式：数组表示和链表表示。二叉树的存储方式：数组表示和链表表示。2023/4/118第8页，共27页，编辑于2022年，星期六第五章第五章 树和二叉树（续）树和二叉树（续）n二叉树的三种遍历方式二叉树的三种遍历方式 前前序遍历
8、：序遍历：根结点根结点左子树左子树右子树右子树 中中序遍历：序遍历：左子树左子树根结点根结点右子树右子树 后后序遍历：序遍历：左子树左子树右子树右子树根结点根结点 例子：例子：2023/4/119第9页，共27页，编辑于2022年，星期六第五章第五章 树和二叉树（续）树和二叉树（续）试编写一个计算二叉树叶结点数量的算法。试编写一个计算二叉树叶结点数量的算法。int leafs(bitree*t)int n1,n2;if (t=NULL)return(0);if (t-lchild=NULL&t-rchild=NULL)return(1);else n1=leafs(t-lchild);n2=l
9、eafs(t-rchild);return(n1+n2);2023/4/1110第10页，共27页，编辑于2022年，星期六第五章第五章 树和二叉树（续）树和二叉树（续）n二叉树与森林的相互转换二叉树与森林的相互转换 左孩子左孩子左孩子左孩子-右兄弟表示法右兄弟表示法2023/4/1111第11页，共27页，编辑于2022年，星期六第五章第五章 树和二叉树（续）树和二叉树（续）n树和二叉树的几种典型应用树和二叉树的几种典型应用1 1、线索二叉树线索二叉树lchildltagrtagdatarchild标志位如果为标志位如果为0 0，表示指针指向孩子结点，为，表示指针指向孩子结点，为1 1表示指
10、针为线索。表示指针为线索。例：对下面的二叉树进行中序线索化。例：对下面的二叉树进行中序线索化。2023/4/1112第12页，共27页，编辑于2022年，星期六第五章第五章 树和二叉树（续）树和二叉树（续）2 2、二叉排序树的定义二叉排序树的定义3 3、赫夫曼树赫夫曼树 赫夫曼树赫夫曼树的构造方法和的构造方法和赫夫曼编码赫夫曼编码的构造方法，的构造方法，WPLWPL（带权路径长度）的计算（带权路径长度）的计算2023/4/1113第13页，共27页，编辑于2022年，星期六第六章第六章 查找查找n n评价查找方法的一个重要标准评价查找方法的一个重要标准评价查找方法的一个重要标准评价查找方法的一
11、个重要标准 ASLASL（平均查找长度）：（平均查找长度）：n n顺序查找顺序查找 查查找找过过程程：从从表表的的一一端端开开始始逐逐个个进进行行记记录录的的关关键字和给定值的比较。键字和给定值的比较。（监视哨的设置监视哨的设置）n n折半查找折半查找折半查找折半查找 查查找找过过程程：每每次次将将待待查查记记录录所所在在区区间间缩缩小小一一半半。（适用于采用顺序存储结构的有序表适用于采用顺序存储结构的有序表）注注意意：对对指指示示查查找找区区间间上上界界、下下界界和和中中点点的的指指针（针（low、high和和mid）的修改。）的修改。2023/4/1114第14页，共27页，编辑于2022
12、年，星期六第六章第六章 查找（续）查找（续）n n分块查找分块查找分块查找分块查找 查找过程：将表分成几块，块内无序，块间有序；查找过程：将表分成几块，块内无序，块间有序；查找过程：将表分成几块，块内无序，块间有序；查找过程：将表分成几块，块内无序，块间有序；先确定待查记录所在块，再在块内查找。（先确定待查记录所在块，再在块内查找。（先确定待查记录所在块，再在块内查找。（先确定待查记录所在块，再在块内查找。（适用适用适用适用于分块有序表于分块有序表于分块有序表于分块有序表）ASL最大最大最小最小两者之间两者之间表结构表结构有序表、无序表有序表、无序表 有序表有序表分块有序表分块有序表存储结构存
13、储结构顺序存储结构顺序存储结构线性链表线性链表顺序存储结构顺序存储结构 顺序存储结构顺序存储结构线性链表线性链表查找方法比较查找方法比较顺序查找顺序查找折半查找折半查找分块查找分块查找2023/4/1115第15页，共27页，编辑于2022年，星期六第六章第六章 查找（续）查找（续）n n哈希查找哈希查找 基基本本思思想想：在在记记录录的的存存储储地地址址和和它它的的关关键键字字之之间间建建立立一一个个确确定定的的对对应应关关系系；这这样样，不不经经过过比比较较，一次存取就能得到所查元素的查找方法。一次存取就能得到所查元素的查找方法。哈哈希希函函数数的的构构造造方方法法：直直接接定定址址法法、
14、数数字字分分析析法法、平方取中法、折叠法、除留余数法、随机数法。平方取中法、折叠法、除留余数法、随机数法。2023/4/1116第16页，共27页，编辑于2022年，星期六第六章第六章 查找（续）查找（续）处理冲突的方法：处理冲突的方法：1 1、开放定址法开放定址法 Hi=(H(key)+di)MOD m 线性探测再散列：线性探测再散列：di=1,2,3,m-1 二次探测再散列：二次探测再散列：di=1,-1,2,-2,3,k (km/2)伪随机探测再散列：伪随机探测再散列：di=伪随机数序列2 2、再哈希法再哈希法3 3、链地址法链地址法2023/4/1117第17页，共27页，编辑于202
15、2年，星期六第七章第七章 排序排序n n插入排序插入排序插入排序插入排序 基基本本原原理理：每每步步将将一一个个待待排排序序的的对对象象，按按其其关关键键字字大大小小，插插入入到到前前面面已已经经排排好好序序的的一一组组对对象象适当位置上，直到对象全部插入为止。适当位置上，直到对象全部插入为止。1 1、直接插入排序直接插入排序 基基 本本 过过 程程：当当 插插 入入 第第i个个 对对 象象 时时，前前 面面 的的R1,R2,Ri-1已已经经排排好好序序，此此时时，用用Ri的的关关键键字字与与Ri-1,Ri-2,的的关关键键字字顺顺序序进进行行比比较较，找找到到插插入入位位置置即即将将Ri插插
16、入入，原原来来位位置置上上对对象象向向后顺移。后顺移。2023/4/1118第18页，共27页，编辑于2022年，星期六第七章第七章 排序（续）排序（续）2、希尔排序希尔排序 基基本本过过程程：设设待待排排序序的的对对象象序序列列有有n个个对对象象，首首先先取取一一个个整整数数gapn作作为为间间隔隔，将将全全部部对对象象分分为为gap个个子子序序列列，所所有有距距离离为为gap的的对对象象放放在在同同一一个个序序列列中中，在在每每一一个个子子序序列列中中分分别别施施行行直直接接插插入入排排序序，然然后后缩缩小小间间隔隔gap，如如取取gap=gap/2，重重复复上上述述的的子子序序列列划划分
17、分和和排排序序工工作作，直直到到最最后后取取gap为为1为止。为止。2023/4/1119第19页，共27页，编辑于2022年，星期六第七章第七章 排序（续）排序（续）n n交换排序交换排序交换排序交换排序 基基本本原原理理：两两两两比比较较待待排排序序的的对对象象的的关关键键字字，如如果果发发生生逆逆序序，则则交交换换之之，直直到到全全部部对对象象都都排排好序为止。好序为止。1、起泡排序起泡排序 基基基基本本本本过过过过程程程程：在在在在当当当当前前前前的的的的排排排排序序序序范范范范围围围围之之之之内内内内，自自自自右右右右至至至至左左左左对对对对相相相相邻邻邻邻的的的的两两两两个个个个结
18、结结结点点点点依依依依次次次次进进进进行行行行比比比比较较较较，让让让让值值值值较较较较大大大大的的的的结结结结点点点点往往往往下下下下移移移移(下下下下沉沉沉沉)，让让让让值值值值较较较较小小小小的的的的结结结结点点点点往往往往上上上上移移移移(上上上上冒冒冒冒)。每每每每趟趟趟趟起起起起泡泡泡泡都都都都能能能能保保保保证证证证值值值值最最最最小小小小的的的的结结结结点点点点上上上上移移移移至至至至最最最最左左左左边边边边，下下下下一一一一遍遍遍遍的的的的排排排排序序序序范范范范围围围围为为为为从从从从下下下下一结点到一结点到一结点到一结点到RnRnRnRn。2023/4/1120第20页，
19、共27页，编辑于2022年，星期六第七章第七章 排序（续）排序（续）2、快速排序快速排序 基基本本过过程程：取取待待排排序序的的结结点点序序列列中中某某个个结结点点的的值值作作为为控控制制值值，采采用用某某种种方方法法把把这这个个结结点点放放到到适适当当的的位位置置，使使得得这这个个位位置置的的左左边边的的所所有有结结点点的的值值都都小小于于等等于于这这个个控控制制值值，而而这这个个位位置置的的右右边的所有结点的值都大于等于这个控制值。边的所有结点的值都大于等于这个控制值。2023/4/1121第21页，共27页，编辑于2022年，星期六第七章第七章 排序（续）排序（续）n n选择排序选择排序
20、 基基本本原原理理：将将待待排排序序的的结结点点分分为为已已排排序序(初初始始为为空空)和和为为未未排排序序两两组组，依依次次将将未未排排序序的的结结点点中中值值最小的结点插入已排序的组中。最小的结点插入已排序的组中。1、直接选择排序直接选择排序 基基基基本本本本过过过过程程程程：在在在在一一一一组组组组对对对对象象象象RiRiRiRi到到到到RnRnRnRn中中中中选选选选择择择择具具具具有有有有最最最最小小小小关关关关键键键键字字字字的的的的对对对对象象象象；若若若若它它它它不不不不是是是是这这这这组组组组对对对对象象象象中中中中的的的的第第第第一一一一个个个个对对对对象象象象，则则则则将
21、将将将它它它它与与与与这这这这组组组组对对对对象象象象中中中中的的的的第第第第一一一一个个个个对对对对象象象象对对对对调调调调；删删删删除除除除具具具具有有有有最最最最小小小小关关关关键键键键字字字字的的的的对对对对象象象象，在在在在剩剩剩剩下下下下的的的的对对对对象象象象中中中中重重重重复复复复上上上上述述述述两两两两步步步步，直直直直到到到到剩剩剩剩余余余余对对对对象象象象只有一个为止。只有一个为止。只有一个为止。只有一个为止。2023/4/1122第22页，共27页，编辑于2022年，星期六第七章第七章 排序（续）排序（续）2、堆排序堆排序 基基本本过过程程：根根据据初初始始输输入入，形
22、形成成初初始始堆堆。通通过过一系列的对象交换和堆的重新调整来进行排序。一系列的对象交换和堆的重新调整来进行排序。堆是如何定义的？堆是如何定义的？如何建堆？如何建堆？2023/4/1123第23页，共27页，编辑于2022年，星期六第七章第七章 排序（续）排序（续）n n归并排序归并排序 基基本本原原理理：通通过过对对两两个个有有序序结结点点序序列列的的合合并并来实现排序。来实现排序。基基本本过过程程：将将待待排排序序列列R1R1到到RnRn看看成成n n个个长长度度为为1 1的的有有序序子子序序列列，把把这这些些子子序序列列两两两两归归并并，便便得得到到 个个有有序序的的子子序序列列。然然后后
23、再再把把这这 个个有有序序的的子子序序列列两两两两归归并并，如如此此反反复复，直直到到最最后后得到一个长度为得到一个长度为n n的有序序列。的有序序列。2023/4/1124第24页，共27页，编辑于2022年，星期六第七章第七章 排序（续）排序（续）n n基数排序基数排序 基基本本原原理理：采采用用“分分配配”和和“收收集集”的的办办法法，用用对对多多关关键键字字进进行行排排序序的的思思想想实实现现对对单单关关键键字进行排序的方法。字进行排序的方法。2023/4/1125第25页，共27页，编辑于2022年，星期六第七章第七章 排序（续）排序（续）n n内部排序方法的比较和选择内部排序方法的比较和选择若若待待排排序序的的记记录录个个数数n n较较小小时时，可可采采用用简简单单排排序序方方法法。（除除希希尔尔排排序序之之外外的的所有插入排序；起泡排序；直接（简单）选择排序）所有插入排序；起泡排序；直接（简单）选择排序）若若n n较大时，应采用快速排序或堆排序。较大时，应采用快速排序或堆排序。若待排序的记录已基本有序，可采用起泡排序。若待排序的记录已基本有序，可采用起泡排序。2023/4/1126第26页，共27页，编辑于2022年，星期六2023/4/1127第27页，共27页，编辑于2022年，星期六