《数据结构与算法（C语言） 教案 第01章 数据结构与算法.docx》由会员分享，可在线阅读，更多相关《数据结构与算法（C语言） 教案 第01章 数据结构与算法.docx（13页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、千锋教育数据结构与算法（C语言篇）教学设计课程名称：数据结构与算法（C语言篇）授语年级：授课学期：教师娓名：2020年03月01日(1)解决问题的算法有很多，为了测试某算法效率的高低，需要尽可能 多地编写算法程序与之进行比拟测试，而设计编写算法程序需要大量的时间 和精力。(2)程序运行时间受计算机硬件等环境因素影响，有时会掩盖算法本 身的优劣。例如，八核处理器明显比单核处理器处理程序的速度要快。(3)算法测试数据设计困难，效率高的算法在测试数据规模小时表现 不明显。2 .事前分析法事前分析法指的是设计算法程序之前，根据统计方法对算法进行估算。 一个好的算法所消耗的时间，应该是算法中每条语句执行
2、的时间之和；每条 语句的执行时间是该语句的执行次数与该语句执行一次所需时间的乘积。算法的时间复杂度在134节中的例1-5、例1-6、例1-7中，变量n称为问题规模，算法 中语句的执行次数称为时间频度，记为T(n)。例1-5和例1-7中，当n不断 变化时，时间频度T(n)也会不断变化。如果有某个辅助函数f(n),并且存在一个正常数c使得f(n)XcT(n)恒 成立，那么记作T(nO(f(n)o通常将O(f(n)称为算法的渐进时间复杂度，简 称时间复杂度。使用0()计算时间复杂度的记法称为大0记法。一般情况 下，随着n的增大，T(n)增长最慢的算法为最优算法。利用上述时间复杂度的公式，分别计算例1
3、-5、例1-6、例1-7中算法的 时间复杂度，具体分析如下。(辅助函数f(n)获取执行次数，正常数c视为 单次执行时间，可以忽略。)(1)例1-5的算法时间为2Xn+5,那么f(n)=2n+5。当问题规模n变为 无穷大时，该算法的执行时间可估算为n,使用大。记法表示时间复杂度为 O(n)o(2)例1-6的算法时间为3,贝1J f(n)=3o此值相较于无穷大的n值可忽 略不计，因此使用大0记法表示时间复杂度为0(1)。( 0(1)表示执行次数 或时间是一个常数，不随着n的变化而变化)(3)例 1-7 的算法时间为 3Xn2+3Xn+3,那么 f(n)=3(n 2+n+l)。当问 题规模n变为无穷
4、大时，该算法的执行时间可估算为n 2 ,使用大0记法 表示时间复杂度为0(n2)。通常情况下,将0(1)、0(n)、0(n2)分别称为常数阶、线性阶、平方阶。 除此之外，还有对数阶、指数阶等其他阶。L常数阶例中的算法时间为3,根据上述时间复杂度计算方法可知，该算法的时 间复杂度没有最高阶项，就是一个常数。使用平面直角坐标系表示常数阶， 如下图。问题规模n.线性阶例中的算法时间为2n+5,根据上述时间复杂度计算方法可知，随着问 题规模n变大，时间复杂度成线性增长。使用平面直角坐标系表示线性阶， 如下图。问题规模n2 .平方阶例中的算法执行时间为3(n2+n+l),根据上述时间复杂度计算方法可 知
5、，随着问题规模n变大，时间复杂度线性增长变快。使用平面直角坐标系 表示平方阶，如下图。问题规模n算法的空间复杂度了解算法的空间复杂度之前，需要先理解算法存储量的概念。算法的存 储量指的是算法执行过程中所需的最大存储空间，其主要包括3个局部：输 入/输出数据所占空间、程序代码所占空间、程序运行临时占用空间。L输入输出数据所占空间算法的输入/输出数据所占用的存储空间是由要解决的问题决定的，是 通过参数表由调用函数传递而来的，它不会随着算法的不同而改变，因此在 算法比拟时不予考虑。2 .程序代码所占空间算法的程序代码所占用的存储空间与程序的长度成正比，要压缩这局部 存储空间，就必须编写出较短的程序。
6、程序代码本身所占空间对不同算法来 说不会有数量级的差异。3 .程序运行临时占用空间根据程序在运行过程中临时占用存储空间的不同，可以将算法分为两 类。(1)原地算法：只占用较小的临时空间，且占有量不会随着问题规模n 的改变而改变。(2)非原地算法：占用临时空间的大小与问题规模n有关，n越大占用 的临时空间越大。通过计算算法存储量可以得到算法的空间复杂度，算法空间复杂度的计 算公式记作S(nO(f(n),其中，n为问题的规模，f(n)为关于n所占存储空 间的函数。随着问题规模n的增大，算法存储量的增长率与f(n)的增长率相 同。习题教材第1章习题课程名称第1章数据结构与算法计划 学时2学时内容分析
7、本章主要介绍数据结构的概念、逻辑结构与物理结构、算法的概念教学目标 与教学要求要求学生了解数据结构的概念与专业术语、了解数据的逻辑结构与物理 结构、了解算法的概念与特性教学重点逻辑结构与物理结构、算法的概念教学难点逻辑结构与物理结构、算法的概念教学方式课堂讲解及ppt演示教学过程第一课时(数据结构的概念、逻辑结构与物理结构)0了解数据结构与算法i.讲述数据结构与算法内容，引出本课时主题。数据结构是计算机专业的一门基础课，其主要研究程序设计中的操作对 象及它们之间的关系。算法指的是解决问题的策略，只要有符合一定规范的 输入，在有限时间内就能获得所要求的输出。虽然数据结构与算法属于不同 的研究课题
8、，但优秀的程序设计离不开二者的相辅相成。因此，本章将主要 介绍数据结构与算法的基本概念，包括数据结构的基本术语、数据的结构分 类以及算法的各种特性。2.明确学习目标(1)能够了解数据(2)能够了解数据元素与数据项(3)能够了解数据对象(4)能够掌握数据结构(5)能够掌握逻辑结构(6)能够掌握物理结构0知识讲解数据数据(Data)在计算机科学中是指计算机操作的对象，是输入到计算机 中被计算机程序处理的符号集合。例如，一个读取终端输入的程序，其操作 的对象可能是字符串，那么字符串就是计算机程序处理的数据。数据不仅可 以是整型、字符型等数值类型，也可以是音频、图片、视频等非数值类型。综上所述，数据的
9、本质就是符号，且这些符号都满足以下特定的需求。(1)可以输入到计算机中。(2)可以被计算机程序处理。其中数值类型的数据可以被执行数值计算，而非数值类型的数据可以被 执行非数值的处理，例如，音频、图片、视频等资源在计算中都是被编码转换为字符数据来处理的。 数据元素与数据项数据元素(Data Element)是组成数据的基本单位。数据的基本单位是 一种抽象的概念，并没有具体的数值化标准。例如，可以将公司看作一个数 据元素，也可以将员工视为一个数据元素。数据元素由数据项组成，并且数据项是数据不可分割的最小单位。例如, 将公司看作一个数据元素，那么行政部、人事部、财务部都可以视为该元素的 数据项，也可
10、以将董事长、经理、总监作为该元素的数据项。 数据对象数据对象(Data Object)指的是具有相同性质的数据元素的集合，是 数据的子集。相同性质指的是数据项的数量与类型的相同。例如，每一个人 都有姓名、年龄、性别、出生地址这些数据项。在实际开发应用中，处理相同性质的数据元素时，默认将数据对象简称 为数据。也就是说，“数据”在数据结构这一课题中代指数据对象，即具有相 同性质的多个数据元素。 数据结构结构(Structure)通常指的是数据元素之间的特定关系。因此，数据结 构(Data Structure)通常指的是相互之间存在一种或多种特定关系的数据 元素的集合。数据结构主要研究的是数据的逻辑
11、结构与数据的物理(存储)结构以及 它们之间的相互关系。其目的是对这种结构设计相应的算法，确保经过运算 后得到的新结构仍保持原来的结构类型。 逻辑结构按照数据元素之间存在的逻辑关系的不同数学特性，通常可以将逻辑结 构分为4种类型。1 .线性结构线性结构中的数据元素之间是一对一的关系，即数据元素存在依次排列 的先后次序关系，且只有一个起始数据元素和一个终止数据元素，如下图。生活中的城市公交路线类似于上述结构，其站点就是数据元素，每一条 公交线路都有一个起点和终点，中间各站都按先后次序排列。2 .树形结构树形结构中的数据元素之间存在一对多的关系，即层次关系或分支关 系。这种结构只有一个起始数据元素(
12、称为树根)，其他数据元素称为树叶, 如下图。o o o3 .图形结构图形结构中的数据元素之间存在多对多的网络关系，即数据元素之间相 互连接成网状，如下图。4 .集合结构集合结构中的数据元素除了同属一个集合外，没有其他关系，各个元素 是“平等”的，该结构类似于数学中的集合，如下图。物理结构物理结构即存储结构，主要指的是数据的逻辑结构在实际的计算机内存 中存储的形式。通常数据的物理结构有以下4种类型。5 .顺序存储顺序存储指的是将相邻的数据元素存放在计算机地址连续的存储单元 中，如下图。起始地址结束地址计算机内存6 .链式存储链式存储不同于顺序存储，在顺序存储中，逻辑上相邻的数据元素在内 存中也是
13、相邻的，而链式存储中，逻辑上相邻的数据元素在内存中不一定相 邻。简单地说，链式存储中的数据元素可以存储在内存的任意位置。如图所 示,C语言程序通过指针指向地址的方式来连接不同存储位置上的数据元素。起始地址起始地址逻辑上相邻存储位置不相邻结束地址7 ,索引存储索引存储指的是在存储数据元素的同时建立索引列表，存储元素之间的 关系。这是一种为了加速检索而创立的存储结构。例如，一所大学在安排学 生宿舍时，一定不能按照学生的学号依次分配宿舍，学号并不考虑性别，也 就是说不可能采用顺序存储；其次，也不能是链式存储，因为学号只是学生 的一个标识，没有其他意义。因此，为学生分配宿舍可采用索引存储，即建 立一个
14、索引列表记录学号与宿舍关系，根据索引列表即可找到与学号对应的 宿舍。8 .散列存储散列存储指的是根据数据元素的关键字直接计算出该数据元素的存储 位置。其基本的设计思想是以数据元素的关键字K为自变量，通过一个确定 的函数关系f (称为散列函数)，计算出对应的函数值f(K),将这个值解释 为数据元素的存储地址，最后将数据元素存入f(K)所指的存储位置上。查找 时只需根据要查找的关键字用同样的函数计算地址，然后到相应的地址提取 要查找的数据元素。第二课时(算法的概念)V内容回顾1 .回顾上节内容，引出本课时主题。上节已经介绍了数据、数据元素与数据项、数据对象、数据结构、逻辑 结构、物理结构，下面将介
15、绍算法的描述、算法的特性、算法的设计要求、算法效率的度量方法、算法的时间复杂度和算法的空间复杂度。2 .明确学习目标(1)能够掌握算法的描述(2)能够掌握算法的特性(3)能够掌握算法的设计要求(4)能够掌握算法效率的度量方法(5)能够掌握算法的时间复杂度(6)能够掌握算法的空间复杂度 4知识讲解算法的描述算法可以用自然语言、数学语言、约定的符号语言或计算机程序语言来 描述。例如，“从3个整数中选出最大的1个整数输出”这一问题，可采用 以下3种方法来描述。L自然语言描述（1）输入3个整数a、b、Co（2）先从前两个整数a、b中选出较大的一个整数，设为X。（3）从x、c中选出较大的整数，设为y。（
16、4）输出y的值。使用自然语言描述算法通俗易懂，但算法整体的数据流向不够清晰。2 .符号语言描述描述算法的符号语言有很多种类型，其中比拟有特点的是程序流程图， 如下图。开始）3 .计算机程序语言描述计算机程序语言有很多，本次使用C语言，如例所示。23int main(intargc, constchar *argv )4(5int a, b,c, X；6scanf (%d%d %d”，&a,&b, &c);/*读取终端输入整数a、b、c的值*/7if(a b)/*比照大小，将较大值赋值给x */8x = a99else10x = b;11if (x c)/*比照X与C的大小，即可得到最大值*/1
17、2printf(M%dnnz x);13else14printf(%dn, c);15return 0;16)#include 1算法的特性算法有5个基本的特性：输入、输出、有穷性、确定性、可行性。L输入一个算法可以有多个或没有输入，具体的输入量取决于算法中的数据对 象。有些算法的输入需要在执行过程中进行，有些算法那么将输入嵌入到算法 之中，如例所示。1 #include 23 int main(int argc, const char *argv )4 5 int count = 0, i;67 for (i = 0; i 100; i+)8 count = count + i;9 prin
18、tf (%dn, count);10 return 0;11 )2输出一个算法必须有一个或多个输出，这些输出是算法对输入进行运算后的 结果。如果一个算法没有输出，那么算法没有任何意义。3 .有穷性有穷性指的是算法在执行有限次数的操作后自动停止，不会出现无限循 环的情况，且每次操作都可以在有限时间内完成。简单地说，算法运行一定 有结束的时刻。1 #include 23 int main(int argc, const char *argv )4 (5 int s = 0, i = 0, n;6 scanf(%d, &n);78 while (i 算法的设计要求同一个问题可以有很多种算法。判断一个
19、算法是否为最优算法，可以从 以下4个方面分析。L正确性算法的正确性指的是算法能正确反映问题的需求，经得起一切可输入数 据的测试。算法的正确性包括以下4个层次。(1)算法程序无语法错误。(2)算法程序对于合法的输入数据能够产生满足要求的输出结果。(3)算法程序对于非法的输入数据能够产生满足规格的说明。(4)算法程序对于极端的输入数据能够产生满足要求的输出结果。6 .可读性可读性指的是算法的设计应该尽可能简单，便于阅读、理解。7 .健壮性健壮性指的是算法可以对不合法的输入数据做出处理，而不是产生异常 或极端的结果。8 .高效率高效率指的是算法的执行时间要尽量短，对存储空间的使用要尽可能 少。在满足前3个要求的前提下，高效率是表达算法优异的重要指标。算法效率的度量方法由133节可知，高效率算法应该具备运行时间短和存储量低的特点。 接下来介绍如何对算法效率进行测试。L事后统计法事后统计法指的是通过设计好的测试程序和数据，对不同算法程序的运 行时间进行比拟，从而确定算法效率的高低。通常情况下，不采用事后统计法进行算法效率测试，其原因如下。