数据结构第02级

《数据结构第02级》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构教案63-----教学内容：第一章概论§1．1基本概念和术语§1．2学习数据结构的意义班级：02级基本要求：1、熟悉各名字、术语的含义。2、掌握基本概念，特别是数据的逻辑结构、存储结构、数据结构三个概念以及三个概念之间的关系。重点：逻辑结构、存储结构、数据结构三个概念以及三个概念之间的关系。难点：逻辑结构概念的正确理解教学过程：第一章概论程序设计的实质是数据表示和数据处理。而这种表示和处理应通过一个渐进的过程逐步完成。数据结构课程主要讨论这个过程中的一些基本问题。以其中的设计阶级为核心，同时涉及编码阶段和分析阶段若干基本问题。本章主要介绍数据结构有关的基本概念、基本思想、

2、基本原理及实际背景。本章学习要点是：1、熟悉各名字、术语的含义，掌握基本概念，特别是数据的逻辑结构、存储结构、数据结构三个概念以及三个概念之间的关系，2、了解评价算法的主要标准3、掌握时间复杂度的估算方法§1．1基本概念和术语数据：计算机加工处理的对象。数据元素：数据的基本单位。作为一个整体加以考虑和处理。数据项：不可分割的最小标识单位。数据、数据项、数据元素反映了数据组织的三个层次。在数据结构课程中，对一个问题主要讨论如下图表示的渐进过程。机外表示执行部分数学模型非形式算法机外表示处理要求建模求精---在此要特别强调：在非数值总是上，数学模型不再是数学方程。63数据结构教案63

3、-----给定一个问题，不仅要描述数据，更重要的要描述元素间的关系，即：数学模型中体现的数据元素之间的邻接关系。逻辑关系：数据元素之间的关联方式或邻接关系。逻辑结构：数据逻辑关系的总体，即数据的组织形式。集合无关系的关系线性结构表树型结构树网状结构图依元素间关系的不同特性分类描述非数值计算问题的数学模型（逻辑结构）是诸如：表、树、图……。注意：（1）、逻辑结构与数据元素本身的形式、内容无关。（2）、逻辑结构与数据元素的相对位置无关。（3）、逻辑结构与所包含的结点个数无关。存储结构：数据以及数据元素之间关系在计算机中和存储形成。存储数据涉及到以下二个方面：（1）数据元素本身（2）数

4、据元素之间的关系（在本课程中只考虑语言上的实现）有四种基本的存储结构：（1）顺序存储方式（2）链式存储方式（3）索引存储方式（4）散列存储方式§1．2学习数据结构的意义举例1：电话号码的查询问题举例2：多叉路口交通灯的控制问题通过以上两个例子，说明解决一个总是的关键步骤是：选取合适的数据结构表示问题才能写出有效的算法。作业：Page10的1、2、363数据结构教案63-----教学内容：§1．3算法的描述和分析班级：计算机02级基本要求：1、了解评价算法的主要标准2、掌握时间复杂度的估算方法重点：时间复杂度的含义难点：时间复杂度的估算教学过程：§1．3算法的描述和分析算法：求解给

5、定问题所需的所有处理和处理规则的描述。描述工具：程序伪语言算法非形式算法本教材在授课时采用C语言来描述算法的实现。评价标准：正确性易读性时间效率空间效率健壮性高效性随着输入量的增加时间、空间的增长速度事先分析算法：a)所选策略因素：b)问题的规模c)书写程序的语言系统环境d)编译程序所产生机器代码的质量e)机器指令的执行速度对一个问题时间效率的衡量不需要精确值，只要反映求解同一问题的不同算法的计算量之间的差异。从以上因素分析得：算法运行的时间只依赖于问题的规模，它是问题规模的一个函数。计算量的估算方法：标准操作重复次数T（n）=标准操作重复执行的次数（一般是问题规模的一个函数）6

6、3数据结构教案63-----T（n）-----算法的时间复杂性（度）O（T（n））-------时间复杂性的量级（级别）例1：x=x+1O(1)fori=1tondoforj=1tondox=x+1O(n2)fori=1tondox=x+1O(n)(a)(b)(c)例1．4例1．6结论：给定一个问题，我们所关心的不是具体的数，而是T（n）~n的变化趋势。常见的量级有：O（1）、O（log2n）、O（n2）、O（2n）作业：Page11的1.763数据结构教案63-----教学内容：第二章线性表§2．1线性表的逻辑结构§2．2线性表的顺序实现班级：计算机系02级基本要求：1、了解线

7、性表的逻辑结构特性是数据元素之间存在线性关系，在计算机中表示这种关系的不同方法得到不同的两种不同的存储结构。2、熟练掌握顺序存储结构的语言描述。3、熟练掌握线性表在顺序存储结构上实现基本运算。4、知道线性表的优点和不足。重点：顺序存储结构的语言描述基本运算在顺序存储结构上实现难点：机外表示到机内表示的描述（语言级的语言描述）函数参数教学过程：第二章线性表本章主要介绍线性结构和线性表的基本概念、线性表的两种常用的存储结构以及常见运算的实现。本章要点：1、了解线性表的逻辑结构特性是数