计算机网络各章各界重点难点教程.docx

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