数据结构与算法培训教（学）案

1、 .PAGE9 / NUMPAGES9数据结构与算法教案欧训勇电子信息工程学院第一章 绪论课程简要说明数据结构是计算机学科的一门核心专业基础课程，是计算机程序设计的重要理论和实践基础。本课程讨论了软件设计中经常遇到的线性表、堆栈、队列、串、 数组、二叉树、图等典型数据结构的设计方法以与各种典型排序和查找算法的性能和设计方法，并介绍了各种典型数据结构的应用。通过本课程的学习，学生对软件 设计的基本要素和软件的基本结构有了深入理解，并通过算法设计方法学习和上机编程实践，编程能力有了进一步提高。课程要求掌握主要容包括：线性表、堆 栈、队列、串、数组、树、二叉树、图等典型数据结构问题的逻辑结构、存储结

2、构和操作的实现方法，各种典型的排序和查找算法，以与递归算法的设计方法。通过本课程的学习，应使学生掌握各种数据结构的特点：存贮表示、运算方法以与在计算机科学中最基本的应用，培养、训练学生选用合适的数据结构和运用 C语言编写质量高、风格好的应用程序与初步评价算法程序的能力；为编译技术、操作系统和数据库等后续课程的学习以与为应用软件特别是非数值应用软件的开发 打下良好的理论基础和实践基础。要求结合实际问题，学会分析计算机加工的数据对象的特性，能够选择适当的数据结构和存储结构以与相应的算法，并初步掌握算法的简单时间复杂度分析方法，训练掌握各种数据结构的表示方法和实现的算法。(1)知识要求：学生通过学习

3、该课程后主要应掌握以下容：掌握程序设计的基本原理和方法了解对各种抽象数据类型的性质掌握处理各种抽象数据类型的基本算法初步掌握算法的简单时间复杂度分析方法(2)素质要求：学生通过学习该课程后能够运用数据结构的思想，针对不同数据对象的特性，能够选择适当的数据结构和存储结构以与相应的算法，解决实际的问题。(3)能力要求：学生通过学习该课程后能够应用一门程序设计语言进行各种应用系统的设计、开发与维护。第一次（2学时）教学主题或章、节课程导论第一章 绪论(1.1节、1.2节)授课类型理论课 实验课 实习或课程设计 练习课 其他教学过程前面导论 15 分钟，新课 83分钟，布置作业 2 分钟教学方式讲授

4、讨论 阅读 示操作 练习 提问 其他教学资源多媒体课件 演示动画 相关软件 音像 其他教学目的与要求（分掌握、理解、了解三个层次）：本次课程要求学生了解什么是数据结构、数据结构课程的特点、数据结构研究的容是什么，理解在解决问题过程中所涉与问题中数据之间的逻辑关系，掌握本课程所涉与到的基本名词、术语和概念，特别是数据的逻辑结构和存储结构之间的关系与性质。教学容提要：第一部分 前面章节简要回顾（约15分钟）介绍数据结构课程的性质、特点、课程的整体框架介绍、本课程学习过程的说明、以与最终的考核方法。理论课和实验课的要求、所需要的参考教材和习题辅导教材、学好本课程的意义、以与如何学好数据结构这门课程。

5、第二部分 新课（约83分钟）第一章 绪论本章容概述（约3分钟）简述本章基本要求、学习容、重点、以与本章教学容安排1.1 什么是数据结构（约35分钟）提问：什么是数据结构？分析用计算机可以解决那些问题，其发展的背景以与解决问题的整体过程，引出在用计算机解决问题的过程中，需要考虑到数据与数据之间的关系。举例说明：（1）图书检索系统中所涉与到的数据之间的关系线性关系（2）人家对弈问题过程中所涉与到的棋盘与棋盘数据之间的关系树型结构（3）十字路口交通灯颜色设计的问题中数据之间的关系图型结构引出数据结构的定义、研究的容、与其基本概念、发展史和在整个学科中的地位和作用。2 基本概念和术语（约50分钟）（1

6、）通过例子引出几个基本概念（约5分钟）数据：是信息的载体，是描述客观事物的数、字符、以与所有能输入到计算机中并被计算机程序识别和处理的符号的集合, 是计算机程序加工的”原料”。数据对象：数据对象是具有一样性质的数据元素的集合。举例说明。数据元素：数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。有时一个数据元素可以由若干数据项(Data Item)组成。举例说明。数据项：数据项是数据不可分割的最小标识单位。举例说明。 说明几者之间的关系和区别。引出数据元素之间的关系、数据结构的定义。（2）数据之间的按照关系不同的分类（约5分钟）集合：数据元素之间无特殊关系； 线性结构：数据元素之间存

7、在着一个对一个的关系；树型结构：数据元素之间存在着一个对多个的关系；图型结构。数据元素之间存在着多对多的关系。（3）数据结构的形式定义（二元组定义）（约10分钟）Data_Structure = （D, S）其中，D 是数据元素的有限集（即一个数据对象），S 是该对象中所有数据成员之间的关系的有限集合。举例说明：以复数为例，说明复数类的数据结构形式定义方式。以一个事务管理的程序为例，说明该程序中数据之间的关系，（4）数据的逻辑结构定义、逻辑结构的分类（约10分钟）数据的逻辑结构从逻辑关系上描述数据，可以看作是从具体问题抽象出来的数据模型，与数据的存储无关，也与数据元素本身的形式、容、相对位置无

8、关；举例说明；（5）数据的物理结构定义、物理结构的分类（约15分钟）数据结构在计算机中的表示(或称映象）称为数据的存储结构，又称为物理结构。它包括数据元素的表示和关系的表示。物理结构的分类：着重讲解顺序存储结构和链式存储结构，并说明二者之间的不同，举例说明。综合比较数据逻辑结构和物理结构之间的关系，并举例说明。（6）数据类型的定义和分类（约5分钟）数据类型是一个值的集合和定义在这个值集上的一组操作的总称。数据类型可分两类：原子类型和结构类型。小结（约2分钟）容回顾、重点、难点。第三部分 布置作业（约2分钟） 习题练习。重点和难点： 重点：数据结构所涉与的基本概念、数据结构的分类，数据的逻辑结构

9、和物理结构、他们之间的关系。参考资料：数据结构题集严蔚敏等编著，清华大学数据结构学习指导与习题详解凤琴等编，清华大学数据结构（C语言篇）习题与解析春葆编，清华大学注意事项与心得： 注意把握时间。注：表中选项打“”第二次（2学时）教学主题或章、节前面章节简要回顾1.3抽象数据类型、1.4 算法与其分析授课类型理论课 实验课 实习或课程设计 练习课 其他教学过程前面章节复习 5 分钟，新课 93 分钟，布置作业 2 分钟教学方式讲授 讨论 阅读 示操作 练习 提问 其他教学资源多媒体课件 演示动画 相关软件 音像 其他教学目的与要求（分掌握、理解、了解三个层次）：了解抽象数据类型的定义、表示和实现

10、方法。理解算法设计的五个要素和基本要求；掌握算法效率的度量方法，着重学习算法的时间复杂度分析。教学容提要：第一部分 前面章节简要回顾（约5分钟）前面第一节、第二节容的简要回顾。第二部分 新课（约93分钟）本次容概述（约3分钟）简述本次课的基本要求、学习容、重点、以与容安排1.3 抽象数据类型（约35分钟）由数据类型定义引入抽象数据类型的定义。抽象数据类型：由用户定义，用以表示应用问题的数据模型，指一个数学模型以与定义在此数学模型上的一组操作。 抽象数据类型的定义方式： ADT 抽象数据类型名 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作：基本操作的定义 ADT 抽象数据类型名抽

11、象数据类型的表示与实现，举例说明：三元组的表示与实现。类C语言的一些共同的约定。1.4算法和算法分析（约55分钟） 一、算法的基本概念（约10分钟）（1）算法的定义：是对特定问题求解步骤的一种描述,是一个有穷的指令集，这些指令表示一个或多个操作。（2）算法的特性(要素) 有穷性：算法应在执行有穷步后结束,且每一步都在有穷时间完成 确定性：每步定义都是确切、无歧义的 可行性：算法中描述的操作应能通过执行有限次已经实现的基本运算实现 输入：有0个或多个输入 输出：有一个或多个输出(处理结果)。（3）算法设计的要求 正确性：不含有语法错误；对于各种合法的输入数据能够得到满足规格说明要求的结果。 可读

12、性：要求程序有较好的人机交互性,有助于人们对算法的理解。 健壮性：对输入的非法数据能作出适当的响应或处理。 效率与低存储需求：主要指算法的执行时间和所需的最大存储空间，这两方面主要和问题的规模有关。二、算法效率的度量（约45分钟）（1）衡量算法的方法（约5分钟） 算法的后期测试：在算法中的某些部位插装时间函数 time ( )测定算法完成 某一功能所花费时间。 算法的事前估计：空间复杂度、时间复杂度（2）算法的时间效率度量方法（时间复杂度）（约30分钟）依据的算法选用何种策略、问题的规模、书写程序的语言、编译程序所生成目标代码的质量、硬件的速度。一个特定算法“运行工作量”大小，只依赖于问题的规

13、模（通常用整数n表示），或者说，它是问题规模的函数。一个算法所耗费的时间，应该是该算法中每条语句的执行时间之和，而每条语句的执行时间又是该语句的执行次数（频度）与该语句执行一次所需时间的乘积。语句的频度指的是该语句重复执行的次数。举例说明。（a） +x; s=0； +x 的频度为1 （b） for (i=1; i=n; +i) +x; s+=x; +x的频度为n（c） for (j=1;j=n;+j) for (k=1;k=n;+k) +x; s+=x; +x的频度为n2我们假定，每条语句一次执行的时间都是一样的，为单位时间。这样我们对时间的分析就可以独立于软硬件系统。时间复杂度是问题规模的函

14、数T( n )。设解决一个问题的规模为n ，基本操作被重复执行的次数是n的一个函数 f（n），假如，随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率一样，则可记作： T (n) = O(f(n) 其中T（n）叫算法的渐进时间复杂度，简称时间复杂度， O是Order（数量级）的首字母，意思是T（n）与f（n）只差一个常数倍。 举例说明时间复杂度的计算方法：例对 n 个整数的序列进行选择排序。其中序列的“长度” n 为问题的规模。void selectSort ( int a , int n ) /对n个整数a0,a1,an-1按递增顺序排序 for ( int i = 0; i n-

15、1; i+ ) int k = i; /从ai查到an-1, 找最小整数, 在ak for ( int j = i+1; j n; j+ ) if ( aj ak ) k = j; int temp = ai; ai = ak; ak = temp; （3）算法的空间效率度量方法（空间复杂度）（约5分钟）空间复杂度是对一个算法在运行过程中临时占用存储空间大小的度量，记作：S(n) = O(g(n)表示随着问题规模n的增大，算法运行所需存储量的增长率与g(n)的增长率一样。算法的存储量包括： 输入数据所占空间； 程序本身所占空间； 辅助变量所占空间 小结（约3分钟）容回顾、重点、难点。第三部分 布置作业（约2分