大学计算机基础（第6版）（微课版） 课件 第6章 算法与数据结构.pptx

第6章算法与数据结构;程序;主要内容;主要内容;算法(algorithms):

是为了求解问题而给出的有限的指令序列，每条指令表示一个或多个操作。——解决问题的步骤

程序

是算法的一种实现，计算机按照程序逐步执行算法，实现对问题的求解。

;;6.1.2算法的特点;算法设计者在构思和设计了一个算法之后，必须清楚准确地将所设计的求解步骤记录下来，即描述算法。

常用的描述算法的方法有

自然语言

流程图

程序设计语言

伪代码等。

下面以计算10个数的平均值算法为例进行介绍;自然语言;流程图;程序设计语言;伪代码;6.1.4算法复杂度分析;撇开与计算机硬件、软件有关的因素，可以认为一个特定算法“运行工作量”的大小，只依赖于问题的规模n，即输入量的大小。如：

对一个长度是n一维数组排序，问题规模为n

对一个m*n的二维数组进行排序，问题规模为m*n

算法执行时间T是问题规模的函数，计为T(n).

;#includestdio.h

intmain(){

floatsum=0,x;

inti=1,n;

scanf(%d”,n);

while(i=10){

scanf(%f,x);

sum=sum+x

i=i+1;

}

printf(%f,sum/10);

return0;

};时间复杂度：

算法的执行时间(所有语句的语句频度之和）;例2:算法的时间复杂度分析;算法的空间复杂度;辅助空间的统计;6.2数据结构基础;数值计算问题实例：计算课程平均成绩;非数值计算问题实例：确定学生名次;非数值计算问题实例：微信联系人管理;6.2.2数据结构的几个基本概念;数据结构（DataStructure）:

相互之间存在一定关系的数据的集合。

是数据及其元素之间相互关系的表示。

逻辑结构：数据元素之间一般存在某种特定的关系，这种关系称为数据的逻辑结构。

物理结构（存储结构）：数据结构在计算机内存中的表示形式。包括数据元素的表示和其关系的表示。;逻辑结构;线性结构实例;树结构：;图结构;;数据的存储结构;顺序（sequential）存储;链式（linked）存储;6.2.5几种常见的数据结构;线性表及其基本操作;顺序表;顺序表中查找第i个数据元素;顺序表中插入第i个数据元素;顺序表中删除第i个数据元素;单链表及基本操作;单链表中查???第i个数据元素;单链表中插入第i个数据元素;单链表中删除第i个数据元素;双链表;双链表中插入第i个数据元素;双链表中删除第i个数据元素;栈;;栈的操作特性：后进先出;例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？;;;;队列;;二叉树;;结点的度：结点所拥有的子树的个数。;叶子结点：度为0的结点，也称为终端结点。

分支结点：度不为0的结点，也称为非终端结点。;孩子、双亲：树中某结点子树的根结点称为这个结点的孩子结点，这个结点称为它孩子结点的双亲结点；

兄弟：具有同一个双亲的孩子结点互称为兄弟。;结点所在层数：根结点的层数为1；对其余任何结点，若某结点在第k层，则其孩子结点在第k+1层。

树的深度：树中所有结点的最大层数，也称高度。;层序编号：将树中结点按照从上层到下层、同层从左到右的次序依次给他们编以从1开始的连续自然数。;特殊的二叉树;满二叉树

在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上。;满二叉树;

;在满二叉树中，从最后一个结点开始，连续去掉任意个结点，即是一棵完全二叉树。;1.叶子结点只能出现在最下两层，且最下层的叶子结点都集中在二叉树的左部；

2.完全二叉树中如果有度为1的结点，只可能有一个，且该结点只有左孩子。

3.深度为k的完全二叉树在k-1层上一定是满二叉树。;;【性质1】在二叉树的第k层上最多有2k-1个结点（k≥1）

;【性质2】深度为m的二叉树最多有2m-1个结点（m≥1）;【性质3】在任意一棵二叉树中，若度为0的结点（即叶子结点）的个数为n0，度为2的结点数为n2，则n0=n2+1。;性质3：在一棵二叉树中，如果叶子结点数为n0，度为2的结点数为n2，则有:n0＝n2＋1。;在有n个结点的满二叉树中，有多少个叶子结点？;性质4：具有n个结点的完全二叉树的深度为log2n+1。;;性质5：对一棵具有n个结点的完全二叉树中从1开始按层序编号，则对于任意的序号为i（1≤i≤n）的结点（简称为结点i），有：

（1）如果i＞1，

则结点i的双亲结点的序号为i/2；如果i＝1，

则结点i是根结点，无