数据结构授课教案.doc

授课教案第章 数据结构概论 本章主要介绍以下内容：　　 1.数据结构研究的主要内容　 　2.数据结构中涉及的基本概念　　 3.算法的概念、描述方法以及评价标准课时分配：??? 1、2两个学时，3两个学时重点、难点：??? ADT、算法的概念、描述方法以及评价标准 第一节 数据结构研究的主要内容 1．当今计算机应用的特点　　 所处理的数据量大且具有一定的关系；　　 对其操作不再是单纯的数值计算，而更多地是需要对其进行组织、管理和检索。2．应用举例1--学籍档案管理??? 假设一个学籍档案管理系统应包含如下表所示的学生信息。????? 学生基本情况 学 号 姓 名 性 别 出生年月 ...... 李 军 男 80.12 ...... 王颜霞 女 81.2 ....... 孙 涛 男 80.9 ...... 单晓宏 男 81.3 ...... ...... ...... ...... ...... ...... 　 　 　 　 　 ??? 特点：??? （1）每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格；??? （2）表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的线性结构；??? （3）对它的操作通常是插入某个学生的信息，删除某个学生的信息，更新某个学生的信息，按条件检索某个学生的信息等等。3．应用举例2--输出n个对象的全排列???? 输出n个对象的全排列可以使用下图所示的形式描述。4．应用举例2--输出n个对象的全排列5．结论??? 计算机的操作对象的关系更加复杂，操作形式不再是单纯的数值计算，而更多地是对这些具有一定关系的数据进行组织管理，我们将此称为非数值性处理。要使计算机能够更有效地进行这些非数值性处理，就必须弄清楚这些操作对象的特点，在计算机中的表示方式以及各个操作的具体实现手段。这些就是《数据结构》这门课程研究的主要内容。 第二节 基本概念和术语 ??? 数据：数据是对客观事物的符号表示。在计算机科学中其含义是指所有能够输入到计算机中并被计算机程序处理的符号集合。??? 数据元素：数据元素是数据集合中的一个实体，是计算机程序中加工处理的基本单位。??? 数据元素按其组成可分为简单型数据元素和复杂型数据元素。简单型数据元素由一个数据项组成，所谓数据项就是数据中不可再分割的最小单位；复杂型数据元素由多个数据项组成，它通常携带着一个概念的多方面信息。??? 数据结构：简单地说，就是相互之间存在一种或多种特定关系的数据元素的集合。常见的数据结构有：线性结构、树形结构和图形结构。===》（集合关系）??? 逻辑结构：数据结构中所说的关系实际上是指数据元素之间的逻辑关系，又称此为逻辑结构。??? 存储结构（物理结构）：是指数据结构在计算机存储器中的具体实现。与孤立的数据元素表示形式不同，数据结构中的数据元素不但要表示其本身的实际内容，还要表示清楚数据元素之间的逻辑结构。??? 常见的存储结构????(1)顺序存储结构：特点是借助于数据元素的相对存储位置来表示数据元素之间的逻辑结构；????(2)链式存储结构：特点是借助于指示数据元素地址的指针表示数据元素之间的逻辑结构。 　 第三节 算法 　 1．算法的概念??? 算法是解决某个特定问题的一种方法或一个有限过程。 ??? 计算机对数据的操作可以分为数值性和非数值性两种类型。在数值性操作中主要进行的是算术运算；而在非数值性操作中主要进行的是检索、排序、插入、删除等等。2．设计算法的基本过程（1）通过对问题进行详细地分析，抽象出相应的数学模型；（2）确定使用的数据结构，并在此基础上设计对此数据结构实施各种操作的算法；（3）选用某种语言将算法转换成程序；（4）调试并运行这些程序。???? ??? 算法应该具有下列五个特性（1）有穷性：一个算法必须在执行有穷步之后结束。（2）确定性：算法中的每一步，必须有确切的含义，在他人理解时不会产生二义性。 （3）动态性：算法中描述的每一步操作都可以通过已有的基本操作执行有限次实现。（4）输入：一个算法应该有零个或多个输入。（5）输出：一个算法应该有一个或多个输出。这里所说的输出是指与输入有某种特定关系的量。 ???? ???? 举例:???? 问题：按从小到大的顺序重新排列x，y，z三个数值的内容。???? 算法：????? （1）输入x，y，z三个数值；????? （2）从三个数值中挑选出最小者并换到x中；????? （3）从y，z中挑选出较小者并换到y中；????? （4）输出排序后的结果。3．算法的描述