《计算机网络各章各界难点》由会员分享，可在线阅读，更多相关《计算机网络各章各界难点（135页珍藏版）》请在金锄头文库上搜索。
1、第一章 概论本章主要介绍数据结构中常用的基本概念和术语以及学习数据结构的意义。要求了解本章介绍的各种基本概念和术语，掌握算法描述和分析的方法。5本章重点是了解数据结构的逻辑结构、存储结构及数据的运算三方面的概念及相互关系。难点是算法时间复杂度的分析方法和抽象数据类型的概念。511 什么是数据结构作为一门课程，数据结构是计算机专业的核心课程,数据结构的研究不仅涉及到计算机硬件的研究范围，而且和计算机软件的研究有密切的关系，无论是编译程序还是操作系统，都涉及到数据元素在存储器中的分配问题。其介于数学、计算机硬件和计算机软件三者之间。程序设计的实质就是选择一个好的数据结构与一个好的算法。一个好的算法
2、在很大程度上依赖于所选的数据结构，选择一个恰当的数据结构是程序设计的关键步骤，所以说数据结构不仅是应用软件的基础、而且是系统软件设计的基础。本课程所介绍的数据结构在应用软件、系统软件设计各种中有着广泛的应用。512 基本概念和术语1.数据、数据元素、数据项（1）数据是信息的载体，它能够被计算机识别、和加工处理。它是计算机加工的原料。（2）数据元素是数据的基本单位，它是对客体的完整描述。有些情况下，数据元素也称为元素、结点、顶点、记录。（3）数据项是数据的具有独立含义的最小标识单位，它是对客体属性的描述。数据是一个全集的概念，数据元素是数据这一全集中的元素，数据元素可以由一个数据项或多个数据项构
3、成。2.数据结构、逻辑结构、存储结构（1）逻辑结构是指元素之间的逻辑关系。在不引起混淆的情况下，我们常常将逻辑结构称为数据结构。（2）存储结构是指数据元素及其关系在计算机上的表示（也称为存储映像）。（3）数据的运算是指对数据施加的操作。（4）数据结构是指数据及数据之间存在的一种或多种特定关系。虽然至今为止，计算机界尚未给出数据结构的标准定义，但它一般包括以下三方面的内容：数据的逻辑结构、数据存储结构及数据的运算。3. 逻辑结构的类别数据的逻辑结构可分为两大类：(1)线性结构：线性结构是指若数据结构是非空集合，则其有且仅有一个终端结点和一个开始结点，其它结点有且仅有一个直接前趋和一个直接后继，开
4、始结点没有直接前趋，终端结点没有直接后继。线性表、栈和队列、串均为线性结构。(2)非线性结构：是指若数据结构是非空集合，则每个结点可以有多个直接前趋区和直接后继。数组、广义表、树和图均为非线性结构。非线性结构又可分为三类:树型结构,图状结构和集合型结构。4. 存储结构的四种存储方法（1）顺序存储方法在一片地址连续的存储单元中，把逻辑上相邻的数据元素存储在物理位置上也相邻的存储单元里，元素间的逻辑关系由存储单元的相邻关系来体现。由此得到的存储结构称为顺序存储结构。（2）链式存储方法元素间的逻辑关系由附加的指针字段来表示。存储单元的地址不要求连续，但存储一个数据元素时既要存储数据元素又要存储与本元
5、素有关联的数据元素的地址。由此得到的存储结构称为链式存储结构。（3）索引存储方法该方法是在存储数据元素的同时，建立一张附加的索引表，用索引表中的索引项来指示各数据元素的存储位置。索引项的一般形式为：关键字，地址。若每个数据元素在索引表中都有一个索引项则该索引表称为稠密索引。若一组数据元素在索引表中只对应一个索引项则称该索引表为稀疏索引。（4）散列存储方法该方法的基本思想是建立数据元素的关键字与存储位置之间的映像关系，从而根据关键字值计算出该数据元素的存储位置。5. 数据类型所谓数据类型是一个值得集合以及在这些值上定义的一组操作的总称。按值是否可分解可将数据类型划分为两类：其值不可分解的称为原子
6、类型，其值可分解为若干个成分的称为结构类型。6. 抽象数据类型(DAT)是指抽象数据的组织和与之相关的操作，它可以看作是数据的逻辑结构及其在逻辑结构上定义的操作。它是描述问题的模型，独立于具体实现。它的优点是将数据和操作封装在一起，使得用户程序只能通过在DAT里定义的操作来访问其中的数据，从而实现了信息隐藏。513 算法的描述和分析1算法及算法的特点算法：是对特定问题求解步骤的描述,即一系列将输入转换为输出的指令的有限序列。算法的特性：（1）有穷性：一个算法必须总是在执行有限步之后结束，每一步都可在有限时间内完成。（2）确定性：算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。并且，
7、在任何条件下，算法只有唯一的一条执行路径。（3）可行性：一个算法是能行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。（4）输入：一个算法可以有零个或多个数输入，这些输入取之于特定的对象的集合。（5）输出：一个算法有一个或多个输出。这些输出是同输入有某种特定关系的量。2算法的描述和算法评价（1）算法的描述方法一个算法可以用自然语言、标准程序设计语言、流通图以及伪代码(伪语言)来说明。唯一的要求是该说明必须精确地描述计算过程。一般而言，描述算法最合适的语言是界于自然语言和程序设计语言之间的伪语言，它的控制结构类似于、Pascal等程序语言，但其中可使用任何表达能力强的方法使
8、算法表达更加清晰和简洁，而不致于陷入具体的程序语言的某些细节(教材采用C语言描述算法)。（2）算法的评价标准正确性：算法应当满足具体问题的要求。其正确性评价分为4个层面(详见教材).可读性：算法应当易于理解、易于调试、易于维护、易于扩充等健壮性：当输入数据是非法时，算法也能适当地作出反应或进行处理，而不会产生莫名其妙的输出结果。时间特性和空间特性：执行算法所耗费的时间和执行算法所占用的空间。通常，空间特性和时特性难以兼顾，要提高算法的时间特性往往以牺牲空间特性为代价，要提高算法的空间特性往往以牺牲时间特性为代价。3算法的分析（本教材主要讨论时间特性，有时讨论空间特性）（1）语句的频度：算法中语
9、句执行的次数。（2）问题的规模：算法求解问题的输入量。例如，矩阵乘法问题的规模是矩阵的阶，图论问题的规模是顶点数或边数。（3）时间复杂度和渐进时间复杂度：一个算法的时间复杂度是该算法的时间耗费，它是该算法求解问题规模n的函数。通常，我们用算法中各语句的频度和来表示算法的时间耗费。当问题的规模趋向无穷大时，我们将时间复杂度的数量级称为算法的渐进时间复杂度。例如两个n阶矩阵相乘算法如下算法 语句频度void mat_mult(int ann,int bnn,int cnn) int i,j,k；for (i=0;in;i+) n+1For (j=0;jn;j+) n(n+1)cIj=0; n2fo
10、r (k=0;kn;k+) n2(n+1)cij=cij+aik*bkj; n3 该算法的时间复杂度为： T(n)=2n3+3n2+2n+1当n趋向无穷大时n3与T(n)是同阶的（同数量级），所以，算法的渐进时间复杂度为： T(n)=O(n3)在算法分析时，评价一个算法的时间性能时主要标准是算法时间复杂度的数量级，即算法的渐进时间复杂度。因此，往往对算法的渐进时间复杂度和时间复杂度不作区分，简称为时间复杂度。算法的时间复杂度不仅仅依赖于问题的规模，也取决于输入实例的初始状态。平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。最坏时间复杂度是指最坏情况下，算法的期望
11、运行时间，一般而言，不作特殊说明，时间复杂度即指最差时间复杂度。4常见的时间复杂度常量阶O(1)、对数阶O(log2n)、线性阶O(n)、平方阶O()、立方阶O()多项式阶OO（）. 、指数阶O(2n)5课堂练习阅读程序题，估计时间复杂度x=0 ；y=0；for(k=1；k=n； k+)x=x+1；for(i=1 ；i=n ；i+)for(j=1 ；j=n；y+；解:一般情况下，对步进循环语句只需考虑循环体中语句的执行次数，而忽略循环控制语句等成分。因此，算法中y+；语句的频度为n2，所以该序段的时间复杂度是平方阶。()2.阅读程序题，估计时间复杂度x=0；for( i=1， j=1； i+j
12、=n ；i+，j+)x+；解：循环体 x+；语句的执行频度n/2 ，算法的时间复杂度 T(n)=O(f(n)=O(n)3.阅读程序题，估计时间复杂度x=1；for(i=1； i=n； i+ )f or(j=1；j=i；j+)for(k=1，k=j ；k+)x+；解：循环体 x+；语句的执行频度f(n)=n(n+1)(2n+1)/6+n(n+1)/2/2算法的时间复杂度 (n)=O()5返回页首第二章 线性表本章目的是介绍线性表的逻辑结构和存储结构，以及定义在逻辑结构上的各种基本运算和这些基本运算在存储结构上的实现（即算法）。要求学生在掌握这些内容的基础上，能够针对具体应用问题的要求和性质，选择
13、恰当的存储结构设计出相应的有效上算法，解决与线性表相关的实际问题。5本章重点是熟练掌握顺序表和单链表上实现的各种基本算法及相关的时间性能分析。难点是能够使用本章所学到的基本知识设计有效算法解决与线性表相关的应用问题。521线性表的逻辑结构1线性表：是由n(n0)各数据元素a1，a2，an组成的有限序列。其中，数据元素的个数定义为表长。当n0时线性表称为空表，非空线性表通常记为(a1，a2，an)例子(见教材)。2线性表的逻辑特征：线性表是一种线性结构。对于非空线性表，有且仅有一个开始结点，它没有直接前趋，仅有一个直接后继；有且仅有一个终端结点，它没有直接后继，仅有一个直接前趋；其它结点有且仅有
14、一个直接前趋和一个直接后继。元素间的逻辑关系是线性的。3线性表的基本运算：（1）InitList(L)线性表的初始化，即构造一个空表。（2）ListLength(L)求表长，即求线性表L中的元素个数。空表的长度为0。（3）GetNode(L,i)取线性表中的第i元素，要求 1iListLength(L)。（4）Locate(L,x)在线性表L中查找值为x的元素，并返回该元素在线性表L中的位置（5）InsertList(L,x,i)在线性表的第i个位置插入新元素x。插入后的表长加1。（6）DeleteList(L,i)删除线性表L的第i个元素，删除后的表长减1。上述运算并不是线性表的全部运算。对于实际问题中涉及的其他更为复杂的运算，可以用基本运算的组合来实现。522线性表的顺序表示和实现1顺序表示（1）顺序表示：采用顺序存贮方法，把线性表中的元素按逻辑次序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表即为线性表的顺序标示,简称为顺序表。（2）顺序表的特点：逻辑上相邻
