第9章 计算机软件技术基础.pptx

第9章 计算机软件技术基础;本章内容;9.1 数据结构基础;9.1.1 数据结构的基本概念;1、数据结构的定义;2、数据的逻辑结构;3、数据的存储结构;4、数据的类型;4、数据的运算;9.1.2 算法;1、算法的定义及特性;2、算法设计的要求;2、算法的复杂度;9.1.3 线性表;线性表的特点：;2、线性表的基本操作;3、线性表的顺序存储;元素an;4、线性表的链式存储;data;9.1.4 栈; 举例1：家里吃饭的碗，通常在洗干净后一 个一个地落在一起存放，在使用时，若一个一 个地拿，一定最先拿走最上面的那只碗，而最 后拿出最下面的那只碗。 举例2：在建筑工地上，使用的砖块从底 往上一层一层地码放，在使用时，将从最上面 一层一层地拿取。 ;2、栈的基本运算;3、栈的存储结构;9.1.5 队列; 举例1：到医院看病，首先需要到挂号处 挂号，然后，按号码顺序救诊。 举例2：乘坐公共汽车，应该在车站排 队，车来后，按顺序上车。 ;2、队列的基本运算;3、队列的存储结构;9.1.6 树和二叉树;树形结构;A; 相关术语： 父结点、根结点、子结点、叶子结点、结点的度、树的度、 树的深度、子树。;2、二叉树;二叉树的五种基本形态; （2）、二叉树的类型 完全二叉树 除最后一层外，每一层上的结点数都达到最大值；在最后一层上只缺少右边的若干结点。;满二叉树 除最后一层外，每一层上的所有结点都有两个子结点。 即在第K层上有2k-1个结点。; （3）、二叉树的性质 （1）在二叉树的K层上，最多有2k-1(k=1)个结点； （2）深度为m的二叉树最多有2m-1个结点； （3）在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点数多一个； （4）具有n个结点的二叉树，其深度至少为[log2n]+1，其中[log2n]表示取不大于log2n的最大整数。;完全二叉树还有两个性质： 1）具有n个结点的完全二叉树的深度为[log2n]+1。 2）对于有n个结点的完全二叉树中的所有结点按从上到下，从左到右的顺序进行编号，则对任意一个结点i （1≤i≤n），都有： 如果i=1，则结点i是这棵完全二叉树的根，没有双亲；否则其双亲结点的编号为 「 i/2 」。 如果2in，则结点i没有左??子；否则其左孩子结点的编号为2i。 如果2i+1n，则结点i没有右孩子；否则其右孩子结点的编号为2i+1。 ; （4）、二叉树的存储 二叉树通常采用链式存储结构。; （5）、二叉树的遍历 1）、前序遍历（DLR） 访问根结点，按前序遍历左子树，按前序遍历右子树。 2）、中序遍历（LDR） 按中序遍历左子树，访问根结点，按中序遍历右子树。 3）、后序遍历（LRD） 按后序遍历左子树，按后序遍历右子树，访问根结点。 ; 下面我们再给出一种遍历二叉树的方法： 对一棵二叉树中序遍历时，若我们将二叉树严格地按左子树的所有结点位于根结点的左侧，右子树的所有结点位于根右侧的形式绘制，就可以对每个结点做一条垂线，映射到下面的水平线上，由此得到的顺序就是该二叉树的中序遍历序列。 ;D G B A E C H F ;遍历算法;9.1.7 查找;2、查找的方法 （1）顺序查找 下列两种情况只能用顺序查找： 1）如果线性表为无序表，则不管是顺序存储结构还是链式存储结构，都只能用顺序查找。 2）即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。;基本思想：从一端开始向另一端，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功；反之，查找不成功。查找成功示例： (34, 44, 43, 12, 53, 55,73, 64, 77)，key = 64查找不成功示例：  (34, 44, 43, 12, 53, 55,73, 64, 77)，key = 88;（2）二分法查找 只适用于顺序存储的有序表。;9.1.8 排序;2、排序的分类 （1）直接插入排序 每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。 （2）交换排序 两两比较待排序记录的关键字，发现两个记录的顺序相反时即进行交换，直到没有反序的记录为止。 交换排序基本思想的主要排序方法有冒泡排序和快速排序。;冒泡