计算机网络各章各界难点课案.docx

第一章概论◎教学目的和要求◎重点和难点◎第一节◎第二节◎第三节◎课堂练习※教学目的和要求本章主要介绍数据结构中常用的基本概念和术语以及学习数据结构的意义。要求了解本章介绍的各种基本概念和术语，掌握算法描述和分析的方法。5※重点和难点本章重点是了解数据结构的逻辑结构、存储结构及数据的运算三方面的概念及相互关系。难点是算法时间复杂度的分析方法和抽象数据类型的概念。5※第一节1．1 什么是数据结构作为一门课程，数据结构是计算机专业的核心课程,数据结构的研究不仅涉及到计算机硬件的研究范围，而且和计算机软件的研究有密切的关系，无论是编译程序还是操作系统，都涉及到数据元素在存储器中的分配问题。其介于数学、计算机硬件和计算机软件三者之间。程序设计的实质就是选择一个好的数据结构与一个好的算法。一个好的算法在很大程度上依赖于所选的数据结构，选择一个恰当的数据结构是程序设计的关键步骤，所以说数据结构不仅是应用软件的基础、而且是系统软件设计的基础。本课程所介绍的数据结构在应用软件、系统软件设计各种中有着广泛的应用。5※第二节1．2 基本概念和术语1.数据、数据元素、数据项（1）数据是信息的载体，它能够被计算机识别、和加工处理。它是计算机加工的原料。（2）数据元素是数据的基本单位，它是对客体的完整描述。有些情况下，数据元素也称为元素、结点、顶点、记录。（3）数据项是数据的具有独立含义的最小标识单位，它是对客体属性的描述。数据是一个全集的概念，数据元素是数据这一全集中的元素，数据元素可以由一个数据项或多个数据项构成。2.数据结构、逻辑结构、存储结构（1）逻辑结构是指元素之间的逻辑关系。在不引起混淆的情况下，我们常常将逻辑结构称为数据结构。（2）存储结构是指数据元素及其关系在计算机上的表示（也称为存储映像）。（3）数据的运算是指对数据施加的操作。（4）数据结构是指数据及数据之间存在的一种或多种特定关系。虽然至今为止，计算机界尚未给出数据结构的标准定义，但它一般包括以下三方面的内容：数据的逻辑结构、数据存储结构及数据的运算。3. 逻辑结构的类别数据的逻辑结构可分为两大类：(1)线性结构：线性结构是指若数据结构是非空集合，则其有且仅有一个终端结点和一个开始结点，其它结点有且仅有一个直接前趋和一个直接后继，开始结点没有直接前趋，终端结点没有直接后继。线性表、栈和队列、串均为线性结构。(2)非线性结构：是指若数据结构是非空集合，则每个结点可以有多个直接前趋区和直接后继。数组、广义表、树和图均为非线性结构。非线性结构又可分为三类:树型结构,图状结构和集合型结构。4. 存储结构的四种存储方法（1）顺序存储方法在一片地址连续的存储单元中，把逻辑上相邻的数据元素存储在物理位置上也相邻的存储单元里，元素间的逻辑关系由存储单元的相邻关系来体现。由此得到的存储结构称为顺序存储结构。（2）链式存储方法元素间的逻辑关系由附加的指针字段来表示。存储单元的地址不要求连续，但存储一个数据元素时既要存储数据元素又要存储与本元素有关联的数据元素的地址。由此得到的存储结构称为链式存储结构。（3）索引存储方法该方法是在存储数据元素的同时，建立一张附加的索引表，用索引表中的索引项来指示各数据元素的存储位置。索引项的一般形式为：关键字，地址。若每个数据元素在索引表中都有一个索引项则该索引表称为稠密索引。若一组数据元素在索引表中只对应一个索引项则称该索引表为稀疏索引。（4）散列存储方法该方法的基本思想是建立数据元素的关键字与存储位置之间的映像关系，从而根据关键字值计算出该数据元素的存储位置。5. 数据类型所谓数据类型是一个值得集合以及在这些值上定义的一组操作的总称。按值是否可分解可将数据类型划分为两类：其值不可分解的称为原子类型，其值可分解为若干个成分的称为结构类型。6. 抽象数据类型(DAT)是指抽象数据的组织和与之相关的操作，它可以看作是数据的逻辑结构及其在逻辑结构上定义的操作。它是描述问题的模型，独立于具体实现。它的优点是将数据和操作封装在一起，使得用户程序只能通过在DAT里定义的操作来访问其中的数据，从而实现了信息隐藏。5※第三节1．3 算法的描述和分析1．算法及算法的特点算法：是对特定问题求解步骤的描述,即一系列将输入转换为输出的指令的有限序列。算法的特性：（1）有穷性：一个算法必须总是在执行有限步之后结束，每一步都可在有限时间内完成。（2）确定性：算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。并且，在任何条件下，算法只有唯一的一条执行路径。（3）可行性：一个算法是能行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。（4）输入：一个算法可以有零个或多个数输入，这些输入取之于特定的对象的集合。（5）输出：一个算法有一个或多个输出。这些输出是同输入有某种特定