《数据结构选讲各章的要点》由会员分享，可在线阅读，更多相关《数据结构选讲各章的要点（27页珍藏版）》请在金锄头文库上搜索。
1、2003 All right reserved. Produced by Dr. Luo Xiongn数据结构选讲各章的要点总总 结结Date12003 All right reserved. Produced by Dr. Luo Xiong第一章第一章 绪绪 论论l l 数据结构的基本概念数据结构的基本概念由某一数据对象及该对象中所有数据成员之间 的关系组成。记为：Data_Structure = D, R数据的逻辑结构和物理结构。 l l 算法设计目标和算法效率度量算法设计目标和算法效率度量算法的正确性；算法运行的时间因素和空间因素 （高效性）。Date22003 All right r
2、eserved. Produced by Dr. Luo Xiong 第二章第二章 线性表线性表l l 线性表线性表的逻辑结构及其基本操作的逻辑结构及其基本操作插入、删除、定位、插入、删除、定位、. . . . l l 线性表的存储结构线性表的存储结构顺序存储、链式存储；顺序存储、链式存储；各自的优缺点如何？各自的优缺点如何？ l l 循环链表、双链表、静态链表循环链表、双链表、静态链表Date32003 All right reserved. Produced by Dr. Luo Xiong 第三章第三章 堆栈和队列堆栈和队列n n堆栈和队列的定义堆栈和队列的定义（LIFO, FIFOLI
3、FO, FIFO）n n堆栈和队列的基本操作堆栈和队列的基本操作进栈、退栈、取栈顶元素；进栈、退栈、取栈顶元素；进队、出队。进队、出队。n n循环队列循环队列队头、队尾指针如何变化？队头、队尾指针如何变化？队空、队满的判断条件？队空、队满的判断条件？Date42003 All right reserved. Produced by Dr. Luo Xiong 第三章第三章 堆栈和队列（续）堆栈和队列（续）n n迷宫问题迷宫问题要解决的问题：要解决的问题：1 1、如何从某一坐标点出发搜索其四周的邻点？如何从某一坐标点出发搜索其四周的邻点？2 2、如何存储搜索路径？如何存储搜索路径？3 3、如何防
4、止重复到达某坐标点？如何防止重复到达某坐标点？4 4、如何输出搜索路径？如何输出搜索路径？Date52003 All right reserved. Produced by Dr. Luo Xiong 第四章第四章 递归递归n n递归的定义递归的定义在链表中寻找等于给定值的结点，在链表中寻找等于给定值的结点，并打印其数值？并打印其数值？n n汉诺塔问题汉诺塔问题解决汉诺塔问题的递归算法。解决汉诺塔问题的递归算法。n n递归工作栈的描述递归工作栈的描述每一次递归调用时，需要为过程中使用的参数每一次递归调用时，需要为过程中使用的参数 、局部变量等另外分配存储空间。每层递归调、局部变量等另外分配存储
5、空间。每层递归调 用需分配的空间形成递归工作记录，按后进先用需分配的空间形成递归工作记录，按后进先 出的栈组织。出的栈组织。Date62003 All right reserved. Produced by Dr. Luo Xiong 第四章第四章 递归（续）递归（续）n n广义表的定义与表示方法广义表的定义与表示方法n n ( ( 0 0 ) )个表元素组成的有限序列。个表元素组成的有限序列。特性：有次序性、可递归、有长度、特性：有次序性、可递归、有长度、可共享、有深度。可共享、有深度。广义表链表表示法。广义表链表表示法。Date72003 All right reserved. Produ
6、ced by Dr. Luo Xiong第五章第五章 树和二叉树树和二叉树n树和二叉树的定义及一些基本操作根、叶结点、子女结点、双亲结点、兄弟结点、结点的度、树的高度、二叉树的五种形态。求双亲结点、求孩子结点、树的遍历、n二叉树的性质及对应的存储方式二叉树各层的最大结点数？满二叉树和完全二叉树的定义？具有n个结点的完全二叉树的高度？二叉树的存储方式：数组表示和链表表示。Date82003 All right reserved. Produced by Dr. Luo Xiong第五章第五章 树和二叉树（续）树和二叉树（续）n二叉树的三种遍历方式前序遍历： 根结点左子树右子树中序遍历： 左子树根
7、结点右子树后序遍历： 左子树右子树根结点例子：Date92003 All right reserved. Produced by Dr. Luo Xiong第五章第五章 树和二叉树（续）树和二叉树（续）试编写一个计算二叉树叶结点数量的算法。 int leafs(bitree *t) int n1, n2; if ( t = NULL) return(0);if ( t-lchild = NULL else n1 = leafs( t-lchild );n2 = leafs( t-rchild );return( n1 + n2 ) ; Date102003 All right reserved
8、. Produced by Dr. Luo Xiong第五章第五章 树和二叉树（续）树和二叉树（续）n二叉树与森林的相互转换左孩子左孩子- -右兄弟表示法右兄弟表示法Date112003 All right reserved. Produced by Dr. Luo Xiong 第五章第五章 树和二叉树（续）树和二叉树（续）n树和二叉树的几种典型应用 1、线索二叉树 lchildltagrtagdatarchild标志位如果为0，表示指针指向孩子结点，为1表示指针为线索。例：对下面的二叉树进行中序线索化。Date122003 All right reserved. Produced by Dr
9、. Luo Xiong 第五章第五章 树和二叉树（续）树和二叉树（续）2、二叉排序树的定义 3、赫夫曼树赫夫曼树的构造方法和赫夫曼编码的构造方法，WPL（带权路径长度）的计算Date132003 All right reserved. Produced by Dr. Luo Xiong第六章第六章 查找查找n n评价查找方法的一个重要标准评价查找方法的一个重要标准ASLASL（平均查找长度）：（平均查找长度）：n n顺序查找顺序查找查找过程：从表的一端开始逐个进行记录的关查找过程：从表的一端开始逐个进行记录的关 键字和给定值的比较。键字和给定值的比较。（监视哨的设置监视哨的设置）n n折半查找
10、折半查找查找过程：每次将待查记录所在区间缩小一半查找过程：每次将待查记录所在区间缩小一半 。（。（适用于采用顺序存储结构的有序表适用于采用顺序存储结构的有序表）注意：注意：对指示查找区间上界、下界和中点的指对指示查找区间上界、下界和中点的指 针（针（lowlow、highhigh和和midmid）的修改。）的修改。Date142003 All right reserved. Produced by Dr. Luo Xiong第六章第六章 查找（续）查找（续）n n分块查找分块查找查找过程：将表分成几块，块内无序，块查找过程：将表分成几块，块内无序，块 间有序；先确定待查记录所在块，再在块间有序
11、；先确定待查记录所在块，再在块 内查找。（内查找。（适用于分块有序表适用于分块有序表）ASL最大最小两者之间表结构有序表、无序表 有序表分块有序表存储结构顺序存储结构 线性链表顺序存储结构 顺序存储结构 线性链表查找方法比较顺序查找折半查找分块查找Date152003 All right reserved. Produced by Dr. Luo Xiong第六章第六章 查找（续）查找（续）n n哈希查找哈希查找基本思想：基本思想：在记录的存储地址和它的关键字之在记录的存储地址和它的关键字之 间建立一个确定的对应关系；这样，不经过比间建立一个确定的对应关系；这样，不经过比 较，一次存取就能得到
12、所查元素的查找方法。较，一次存取就能得到所查元素的查找方法。哈希函数的构造方法：哈希函数的构造方法：直接定址法、数字分析直接定址法、数字分析 法、平方取中法、折叠法、除留余数法、随机法、平方取中法、折叠法、除留余数法、随机 数法。数法。Date162003 All right reserved. Produced by Dr. Luo Xiong第六章第六章 查找（续）查找（续）处理冲突的方法：处理冲突的方法： 1 1、开放定址法开放定址法Hi= ( H(key) + di ) MOD m 线性探测再散列： di=1,2,3,m-1 二次探测再散列： di=1,-1,2,-2,3,k (km/
13、2) 伪随机探测再散列：di=伪随机数序列2 2、再哈希法再哈希法3 3、链地址法链地址法Date172003 All right reserved. Produced by Dr. Luo Xiong第七章第七章 排序排序n n插入排序插入排序基本原理：基本原理：每步将一个待排序的对象，按其关每步将一个待排序的对象，按其关 键字大小，插入到前面已经排好序的一组对象键字大小，插入到前面已经排好序的一组对象 适当位置上，直到对象全部插入为止。适当位置上，直到对象全部插入为止。 1 1、直接插入排序直接插入排序基本过程：基本过程：当插入第当插入第i i个对象时，前面的个对象时，前面的 R1,R2,
14、Ri-1R1,R2,Ri-1已经排好序，此时，用已经排好序，此时，用RiRi 的关键字与的关键字与Ri-1, Ri-1, Ri-2,Ri-2,的关键字顺序进行的关键字顺序进行 比较，找到插入位置即将比较，找到插入位置即将RiRi 插入，原来位置插入，原来位置 上对象向后顺移。上对象向后顺移。Date182003 All right reserved. Produced by Dr. Luo Xiong第七章第七章 排序（续）排序（续）2 2、希尔排序希尔排序基本过程：基本过程：设待排序的对象序列有设待排序的对象序列有n n个对象，个对象， 首先取一个整数首先取一个整数gapngapn作为间隔，
15、将全部对象作为间隔，将全部对象 分为分为gapgap个子序列，所有距离为个子序列，所有距离为gapgap的对象放在的对象放在 同一个序列中，在每一个子序列中分别施行直同一个序列中，在每一个子序列中分别施行直 接插入排序，然后缩小间隔接插入排序，然后缩小间隔gapgap，如取，如取 gap=gap/2gap=gap/2，重复上述的子序列划分和排序工，重复上述的子序列划分和排序工 作，直到最后取作，直到最后取gapgap为为1 1为止。为止。Date192003 All right reserved. Produced by Dr. Luo Xiong第七章第七章 排序（续）排序（续）n n交换排
16、序交换排序基本原理：基本原理：两两比较待排序的对象的关键字，两两比较待排序的对象的关键字， 如果发生逆序，则交换之，直到全部对象都排如果发生逆序，则交换之，直到全部对象都排 好序为止。好序为止。 1 1、起泡排序起泡排序基本过程：基本过程：在当前的排序范围之内，自右至左对在当前的排序范围之内，自右至左对 相邻的两个结点依次进行比较，让值较大的结点相邻的两个结点依次进行比较，让值较大的结点 往下移往下移( (下沉下沉) )，让值较小的结点往上移，让值较小的结点往上移( (上冒上冒) )。每。每 趟起泡都能保证值最小的结点上移至最左边，下趟起泡都能保证值最小的结点上移至最左边，下 一遍的排序范围为从下一结点到一遍的排序范围为从下一结点到RnRn 。Date202003 All right reserved. Produced by Dr.
