《计算机网络各章各界重点难点.pdf》由会员分享，可在线阅读，更多相关《计算机网络各章各界重点难点.pdf（136页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 教学目的和要求 重点和难点（第节 第二节 第三节 （课堂练习 教学目的和要求本章主要介绍数据结构中常用的基本概念和术语以及学习数据结构的意义。要求了解本章介绍的各种基本概念和术语，掌握算法描述和分析的方法。（重点和难点本章重点是了解数据结构的逻辑结构、存储结构及数据的运算三方面的概念及相互关系。难点是算法时间复杂度的分析方法和抽象数据类型的概念。第一节1.1什么是数据结构作为一门课程，数据结构是计算机专业的核心课程,数据结构的研究不仅涉及到计算机硬件的研究范围，而且和计算机软件的研究有密切的关系，无论是编译程序还是操作系统，都涉及到数据元素在存储器中的分配问题。其介于数学、计算机硬件和计算机
2、软件三者之间。程序设计的实质就是选择一个好的数据结构与一个好的算法。一个好的算法在很大程度上依赖于所选的数据结构，选择一个恰当的数据结构是程序设计的关键步骤，所以说数据结构不仅是应用软件的基础、而且是系统软件设计的基础。本课程所介绍的数据结构在应用软件、系统软件设计各种中有着广泛的应用。第二节1.2 基本概念和术语1.数据、数据元素、数据项(1)数据是信息的载体，它能够被计算机识别、和加工处理。它是计算机加工的原料。(2)数据元素是数据的基本单位，它是对客体的完整描述。有些情况下，数据元素也称为元素、结点、顶点、记录。(3)数据项是数据的具有独立含义的最小标识单位，它是对客体属性的描述。数据是
3、一个全集的概念，数据元素是数据这全集中的元素，数据元素可以由一个数据项或多个数据项构成。2.数据结构、逻辑结构、存储结构(1)逻辑结构是指元素之间的逻辑关系。在不引起混淆的情况下，我们常常将逻辑结构称为数据结构。(2)存储结构是指数据元素及其关系在计算机上的表示(也称为存储映像)。(3)数据的运算是指对数据施加的操作。(4)数据结构是指数据及数据之间存在的一种或多种特定关系。虽然至今为止，计算机界尚未给出数据结构的标准定义，但它一般包括以下三方面的内容：数据的逻辑结构、数据存储结构及数据的运算。3.逻辑结构的类别数据的逻辑结构可分为两大类：(1)线性结构：线性结构是指若数据结构是非空集合，则其
4、有且仅有一个终端结点和一个开始结点，其它结点有且仅有一个直接前趋和一个直接后继，开始结点没有直接前趋，终端结点没有直接后继。线性表、栈和队列、串均为线性结构。(2)非线性结构：是指若数据结构是非空集合，则每个结点可以有多个直接前趋区和直接后继。数组、广义表、树和图均为非线性结构。非线性结构又可分为三类:树型结构,图状结构和集合型结构。4.存储结构的四种存储方法（1）顺序存储方法在一片地址连续的存储单元中，把逻辑上相邻的数据元素存储在物理位置上也相邻的存储单元里，元素间的逻辑关系由存储单元的相邻关系来体现。由此得到的存储结构称为顺序存储结构。（2）链式存储方法元素间的逻辑关系由附加的指针字段来表
5、示。存储单元的地址不要求连续，但存储一个数据元素时既要存储数据元素又要存储与本元素有关联的数据元素的地址。由此得到的存储结构称为链式存储结构。（3）索引存储方法该方法是在存储数据元素的同时，建立一张附加的索引表，用索引表中的索引项来指示各数据元素的存储位置。索引项的一般形式为：关键字，地址。若每个数据元素在索引表中都有一个索引项则该索引表称为稠密索引。若一组数据元素在索引表中只对应一个索引项则称该索引表为稀疏索引。（4）散列存储方法该方法的基本思想是建立数据元素的关键字与存储位置之间的映像关系，从而根据关键字值计算出该数据元素的存储位置。5 .数据类型所谓数据类型是个值得集合以及在这些值上定义
6、的一组操作的总称。按值是否可分解可将数据类型划分为两类：其值不可分解的称为原子类型，其值可分解为若干个成分的称为结构类型。6.抽象数据类型（DAT）是指抽象数据的组织和与之相关的操作，它可以看作是数据的逻辑结构及其在逻辑结构上定义的操作。它是描述问题的模型，独立于具体实现。它的优点是将数据和操作封装在一起，使得用户程序只能通过在D A T里定义的操作来访问其中的数据，从而实现了信息隐藏。第三节1.3 算法的描述和分析i .算法及算法的特点算法：是对特定问题求解步骤的描述,即一系列将输入转换为输出的指令的有限序列。算法的特性：(1)有穷性：一个算法必须总是在执行有限步之后结束，每一步都可在有限时
7、间内完成。(2)确定性：算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。并且，在任何条件下，算法只有唯一的一条执行路径。(3)可行性：-个算法是能行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。(4)输入：一个算法可以有零个或多个数输入，这些输入取之于特定的对象的集合。(5)输出：一个算法有一个或多个输出。这些输出是同输入有某种特定关系的量。2.算法的描述和算法评价(1)算法的描述方法一个算法可以用自然语言、标准程序设计语言、流通图以及伪代码(伪语言)来说明。唯一的要求是该说明必须精确地描述计算过程。一般而言，描述算法最合适的语言是界于自然语言和程序设计语言
8、之间的伪语言，它的控制结构类似于C、P a s c a l等程序语言，但其中可使用任何表达能力强的方法使算法表达更加清晰和简洁，而不致于陷入具体的程序语言的某些细节(教材采用c语言描述算法)。(2)算法的评价标准正确性：算法应当满足具体问题的要求。其正确性评价分为4个层面(详见教材).可读性：算法应当易于理解、易于调试、易于维护、易于扩充等健壮性：当输入数据是非法时，算法也能适当地作出反应或进行处理，而不会产生莫名其妙的输出结果。时间特性和空间特性：执行算法所耗费的时间和执行算法所占用的空间。通常，空间特性和时特性难以兼顾，要提高算法的时间特性往往以牺牲空间特性为代价，要提高算法的空间特性往往
9、以牺牲时间特性为代价。3.算法的分析(本教材主要讨论时间特性，有时讨论空间特性)(1)语句的频度：算法中语句执行的次数。(2)问题的规模：算法求解问题的输入量。例如，矩阵乘法问题的规模是矩阵的阶，图论问题的规模是顶点数或边数。(3)时间复杂度和渐进时间复杂度：一个算法的时间复杂度是该算法的时间耗费，它是该算法求解问题规模n的函数。通常，我们用算法中各语句的频度和来表示算法的时间耗费。当问题的规模趋向无穷大时，我们将时间复杂度的数量级称为算法的渐进时间复杂度。例如两个n 阶矩阵相乘算法如下算法语句频度vo i d m a t m ul t(i n t a n n ,i n tb n n ,i n
10、 t c n n )i n t i,j,k；f o r (i=0;i n;i+)n+1F o r (j=O;j n;j+)n(n+l)c I j =0;n2f o r (k=0;k n;k+)n2(n+l)c i j =c i j +a i k *b k j ;n3)该算法的时间复杂度为：T (n)=2 n 3+3 n 2+2 n+l当 n 趋向无穷大时n 3 与 T(n)是同阶的(同数量级)，所以，算法的渐进时间复杂度为：T(n)=0(n 3)在算法分析时，评价一个算法的时间性能时主要标准是算法时间复杂度的数量级，即算法的渐进时间复杂度。因此，往往对算法的渐进时间复杂度和时间复杂度不作区分，
11、简称为时间复杂度。算法的时间复杂度不仅仅依赖于问题的规模，也取决于输入实例的初始状态。平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。最坏时间复杂度是指最坏情况下，算法的期望运行时间，般而言，不作特殊说明，忖间复杂度即指最差时间复杂度。4.常见的时间复杂度常量阶0(1)、对数阶0(l o g 2 n)、线性阶0(n)、平方阶0(二)、立方阶0(0)多项式阶0 0.、指数阶 0(2 n)课堂练习课堂练习1 .阅读程序题，估计时间复杂度x=0 ；y=0；f o r(k=l；k =n；k+)x=x+l；f o r (i=l ；i =n ；i+)f o r(j=l ；j
12、 =n；y+；解：一般情况下，对步进循环语句只需考虑循环体中语句的执行次数，而忽略循环控制语句等成分。因此，算法中y+；语句的频度为n:所以该序段的时间复杂度是平方阶。(厂)2.阅读程序题，估计时间复杂度x=0；f o r(i=l,j=l；i+j =n ；i+,j+)x+；解：循 环 体X+；语 句 的 执 行 频 度n/2 ,算法的时间复杂度T(n)=O(f(n)=O(n)3.阅读 程 序 题，估计时间复杂度x=l；f o r(i=l；i =n；i+)f o r(j=l；j =i；j+)f o r (k=L k 本章重点是熟练掌握顺序表和单链表上实现的各种基本算法及相关的时间性能分 析。难点
13、是能够使用本章所学到的基本知识设计有效算法解决与线性表相关的应用 问 题。第一节2.1线性表的逻辑结构i .线性表：是 山n(nO)各 数 据 元 素a l,a 2,，a n组成的有限序列。其 中，数据元素的个数定义为表长。当n=0时线性表称为空表，非空线性表通常记为(a l,a 2,a n)例子(见教材)。2.线性表的逻辑特征：线性表是一种线性结构。对于非空线性表，有且仅有一个开始结点，它没有直接 前 趋，仅有一个直接后继；有且仅有一个终端结点，它没有直接后继，仅有一个直接前趋；其它结点有且仅有一个直接前趋和一个直接后继。元素间的逻辑关系是线 性 的。3.线性表的基本运算：(1)I nitL
14、 ist(L)线性表的初始化，即构造一个空表。(2)L istL e ng th(L)求 表长，即 求 线 性 表L中的元素个数。空 表 的 长 度 为0。(3)G e tN o d e(L,i)取 线 性 表 中 的 第i元 素,要 求1 W iW L istL e ng th(L)。(4)L o c a te(L,x)在 线 性 表L中 查 找 值 为x的元素，并返回该元素在线性表L中的位置(5)I nse r tL ist(L,x,i)在 线 性 表 的 第i个 位 置 插 入新元素X。插 入 后 的 表 长 加1。(6)De le te L ist(L,i)删 除 线 性 表L的 第i
15、个元素，删 除 后 的 表 长 减1。上述运算并不是线性表的全部运算。对于实际问题中涉及的其他更为复杂的运算，可以用基本运算的组合来实现。第二节2.2线性表的顺序表示和实现1.顺序表示(1)顺序表示：采用顺序存贮方法，把线性表中的元素按逻辑次序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表即为线性表的顺序标示，简称为顺序表.(2)顺序表的特点：逻辑上相邻的元素在物理位置上也相邻；顺序表是一种随机存取结构。顺 序 表 中 的 第i个 结 点a i的 存 储 地 址L O C(a i)可通过下式计算：L O C(a i)=L O C(a l)+(i-l)X c I W iW n其 中，
16、L O C(a l)是 开 始 结 点a l的存储地址(即顺序表的基地址)，c是每个结点占用的存储单元数。也就是说，在顺序表中，每个结点的存储地址是该结点在表中的 位 置i的线性函数,只要知道基地址L O C(a l)和 结 点 的 大 小c,就可以在相同时间里求出任意结点的存储地址。由此可见，顺序表是一种随机存储结构。(3)顺序表在程序设计语言上的表示程序设计语言中的一维数组也是采用顺序存储，故可用数组存储线性表中的元素，用一个变量来表示线性表的长度。把这二者结合起来构成结构类型作为顺序表在程序设计语言环境下的实现。定义如下：d e f ine L istsize 1 0 0 顺序表可能的最
17、大存储空间，可根据实际需要法定，现 设 为1 0 0。typ e d e f int d a ta typ e；/d a ta typ e表示数据元素的类型，现 假 设 为int。typ e d e f str uc t d a ta typ e d a ta L istsize ；/一维数组 d a ta 用于存储元素。int le ng th；当前表的长度。S eql i st；Seql i st是我们定义的一个结构类型，可以把它看作是顺序表在程序设计语言上的实现。即线性表的顺序存储结构。我们将在该结构上介绍各种上算法。2.顺序表上基本运算的实现(1)插入算法 i n sertl i st
18、(Seql i st*L,Da ta type x,i n t I)算法思想：判 断 上 溢 和i值 合 法 性，即I W i W n +1；将 第i个 到 第n个元素从后往前依次后移；将元素插入第个位置；表长加1 算法：voi d i n sertl i st(Seql i st*L,Da ta type x,i n t i)将新结插入L 所指的顺序表的第i 个结点之前i n t j;i f(i L-l en gth+l|L-l en gth=L i stsi ze)error(z/posi ti on error or overfl ow);for(j =L-l egth-l;j=i-l;
19、j)L-da ta j+l =L-da ta j ;L-da ta i-l =x;l-l en gth+;)时间特性分析：影响算法时间特性的主要因素是元素的后移，插入位置不同，后移操作的次数也不同。最好情况是在表末插入，不需要移动元素，时间复杂度是0(1);最坏情况是在表头插入，需要移动全部n个元素，最坏时间复杂度是0 (n)；通常，我们通过计算元素的来反映算法时间特性。在长度为n的线性表中第i 个元素前插入一个元素，须移动n-i+1 个元素，考虑不同位置的插入概率p i,移动平均次数(移动次数的数学期望值)为：-I-：血不失一般性，在等概率情况下pi=l/(n+l),所以故，算法平均时间复杂
20、度仍然是0(n)。(2)删除算法 Del etel i st(seql i st*L,i n t i)算法思想：判 断 i 值合法性，即 I W i W n；将 第 i +1 个到第n 个元素从前往后依次前移;表长减l o算法：voi d Del etel i st(Seql i st*L,i n t i)删除L 所指的顺序表的第i 个结点i n t j;i f(i L-l en gth)error(,z posi ti on error);for(j =i;j=L-l en gth-l;j+)L-da ta j-l =L-da ta j+l ;L-da ta i-l =x;l-l en gt
21、h一;)时间特性分析：删除算法的时间复杂度与插入算法的时间度基本相似，最好情况是删除表末元素，不需要移动元素，时间复杂度是0(1);最坏情况是删除表头元素，需要移动 n-1 个元素，最坏时间复杂度是0 (n)在长度为n的线性表中删除第i 个元素，须移动n-i 个元素，考虑不同位置的插入概率p i,移动平均次数(移动次数的数学期望 值)为：J=工 以 吵不失一般性，在等概率情况下pi=(n+l),所以-口,n-1E&=V-(n-z)=,故，算法平均时间复杂度仍然是0(n)。说明：插入算法中结点后移必须从后向前依次进行，删除算法中结点前移必须从前向后依次进行；结点逻辑序号由1开始，存储位置(即向量
22、下标)由0开始，应注意算法中的对应。我们完全可以约定均从0开始将两者统一起来，这样，算法将更简单。插入、删除算法均存在此问题。从时间复杂度分析可以看出，在顺序表上进行插入或删除操作，几乎要平均移动表中一半元素，所以，当表长较大且频繁进行插入和删除操作时不宜采用顺序存储结构。第三节)2.3线性表的链式存储结构线性表的链式存储结构是采用链式存储方法存储线性表所形成的存储结构，简称为链表。链表通常分为三类，即单链表(也称为线性连表)、双向链表和循环链表。1.单链表(1)单链表为了能正确表示结点间的逻辑关系，在存储每个元素(结点值)的同时还必须存储其后继结点的地址信息，这两部分信息组成了链表中的结点结
23、构：其中，data域是数据域，用来存储数据元素(结点值)，next域称为指针域，用来存储结点的直接后继结点的地址。线性表中的每个元素均采用这样的结点结构存储，通过每个结点的指针域将线性表中的个结点按其逻辑顺序链结在一起，所形成的存储结构称为单链表。并引入一个指针变量指向表头结点，称为头指针。头指针唯一的确定一个单链表。为了运算方便，我们通常在开始结点之前引入一个附加结点，称为头结点。引入头结点有如下优点：第一个位置上的操作和在表的其他位置上的操作一致，无须特殊处理；无论是否为空表，头指针总是指向头结点的非空指针，这样，空表和非空表的处理就可以统一为一种模式。不带头结点和带头结点的单链表可用下图
24、表示非空表：卿*_ _ _|凯，*-刎 八2蠢h e a d ，teal 带头结点的空表的判定条件为：head=NULL；带头结点的空表的判定条件为：head-next=NULLo(2)特点表中各结点的存储地址可以是连续的、也可以是不连续的，接点的逻辑次序和物理次序不一定相同；便于进行插入和删除操作。(3)单链表的高级语言描述typedef char datatype;typedef struct node datatype data;struct node*next;Listnode;typedef Listnode*Linklist;这里，我们定义了 Listnode、Linklist等数
25、据类型，前者为结构类型，后者是指向这种结构类型结点的指针类型。通常用Linklist定义头指针变量,代表单链表用Listnode*定义工作指针以实现对单链表中结点的操作。在 C 语言中，分配结点和释放结点的函数：p=(Listnode*)malloc(sizeof(Listnode);free(p);函数malloc()可以动态地分配一个类型为Listnode的结点变量的空间并返回其首地址赋予指针变量p；函数free(p)释放p 所指的结点变量空间。(4)线性表基本运算在单链表上的实现建立单链表单链表分为带头结点和不带头结点两类，建立单链表的方法分为头插法和尾插法两种。【算法1】(不带头结点、
26、头插法)C语言算法见教材【分析】首先建立空表：head=NULL；依次输入线性表元素，生成新结点*s,将新结点插入在开始结点(第个表结点)之前，作为新的开始结点：s-next=head;head=s;；这种建表方法所建链表的结点次序与输入元素次序正好相反，所以，线性表中元素应逆序输入。【算法2】(带头结点、头插法)Linklist greatlistf(viod)建立带头结点的单链表，返回单链表的头指针char ch;Linklist head;定义头指针 headListnode*s;定义工作指针shead=(Listnode*)malloc(sizeof(Listnode);head-ne
27、xt=NULL;建立带头结点的空表ch=getchar();/读入第一个元素while(ch!=,n,)s=(Listnode*)malloc(sizeof(Listnode);创建新结点s-data=ch 将读入的值放入结点的数据s-next=head-next;head-next=s;/完成插入操作ch=getchar();读入下一个元素return(head);返回头指针)【分析】该算法与不带头结点的建表算法的区别在于建立初始空表时，要建立头结点，其它均相同。上述两算法时间复杂度取决于循环体中语句的执行频度，也就是线性表的长度n,所以，时间复杂度为0(n)。【算法3】(尾插法建表，)C语
28、言算法见教材。【分析】不带头结点算法：首先建立空表，设置尾指针初值：head=NULL;r=NULL;；依次输入数据元素，生成新结点*s,若是第一个结点，作特殊处理：h ead=s;r=s;,其他情况，依靠尾指针 r将新结点插入在表末，尾指针后移指向新的表末结点：r-next=s;：r=s;；最后让表尾结点指针域为空。若带头结点，算法简化为：初始设置：首先建立一个带头结点的空表，头指针，尾指针均指向头结点；依次输入数据元素，生成新结点*s,依靠尾指针r 将新结点插入在表末，尾指针后移指向新的表末结点：r-next=s;：r=s;；最后让表尾结点指针域为空。算法的时间复杂度取决于线性表的长度n，
29、为0(n)。查找运算【算法1】按序号查找：已知结点序号i,在单链表中查找，返回该结点在链表中的位置。C语言算法见教材。【分析】在带头结点单链表中查找，首先，引入工作指针变量p 指向头结点和计数变量j 并初始化：p=head;j=O;；然后指针变量p 从前向后扫描链表中各结点，变量j 同时计数，当j=i 时查找成功，指针变量p 所指结点即为所找结点，当p-next=NULL&j!=i或ji时查找失败，说明i 值指定不当(p-next=NULL&j!=i 说明指针变量p 已指向最后结点，尚未到第i 个结点,i 值大于表长n,当ji时，i 小于0)。算法中语句：p=p-next;是链表操作的典型操作
30、，其功能是指针p由所指结点移向其后继结点。时间特性分析：算法时间复杂度取决于循环语句的频度，其和i值有关，在等概率情况下，平均值为：故，时间复杂度为：O(n)【算法2】按值查找：给定特定值k e y,在链表中查找结点值等于特定值key的结点，返回首次找到的结点的位置。C语言算法见教材。【分析】引入工作指针变量p 指向链表的开始结点：p=head-next；依次扫描各结点，查找结点值与特定值key相等的结点，若某结点满足条件，则返回该结点的位置，若无此类结点，则返回 NULLo与按序号查找算法一样，时间复杂度为0(n)。插入运算将值为x 的新结点插入在链表的第i 个结点之前。如下图所示：【分析】
31、算法由三个基本步骤构成：首先将工作指针p 定位于第i-1个结点(p=getnode(head,i-l)；若定位成功，则构成新结点(s=malloc(sizeof(linknode);s-data=x;)；第三步完成插入，借助工作指针P将新结点插入在P 所指结点之后，即第i-1个结点之后(s-next=p-next;p-next=s;)。算法的时间主要耗费在P 指针的定位上，故时间复杂度与按序号查找算法相同,为0(n)。插入位置i 的有效范围是：lWiWn+1。插入操作的两条语句必须按所标次序进行。删除运算将指定的第i 个结点从链表中删除。如下图所示：c 语言算法见教材。【分析】算法由四个基本步
32、骤构成：首先将工作指针P定位于第i-1个结点(p=getnode(head,i-l)；若定位成功,则将辅助指针s指向待删除结点(s=p-next;)；第三步完成删除(p-next=s-next;)；最后释放被删除结点(free(s);),将所占空间归还给系统备用空间，即“存储池”。算法的时间主要耗费在P指针的定位上，故时间复杂度与按序号查找算法相同为0(n)o删除位置的有效范围是：i W i W n。函数g e t n o d e(h e a d,i-l)返回值为N U L L时，说明i n+l,当 i=n+l 将返回最后一个结点的位置，即 p-n e x t=N U L L,所以，可用 p!
33、=N U L L&p-n e x t!=N U L L 来判定 i 值指定的有效性。2 .循环链表循环链表是种首尾相接的链表。在单链表上，将终端结点的指针域指向表头结点(不代头结点时指向开始结点)，就形成了单循环链表。在多种链表的基础上，也可以构成多重循环链表。单循环链表非空表和空表如下图所示：非空表空 赛”,head 3-单循环链表为空的判定条件：h e a d-n e x t=h e a d ；循环链表的特点：从表中任一结点出发，可访问表中每一个结点。链表操作经常在表头和表尾进行，利用循环链表的特点，通常引入尾指针r e a r,以方便操作。这样，表头和表尾操作的时间复杂度均为0(1)基本
34、运算在循环链表上的实现和线性链表基本相同，区别在于终止判定条件，即在线性链表上为p=nu l l(或为p-ne x t=nu l l)改为p=he a d(或p-ne x t=he a d)o初始设置适当注意即可。3.双链表(1)双链表结构在单链表的基础上增加一个指向前趋结点的指针域便形成了双链表。其结点结构如下:prior data(2)双链表的特点：通过前趋指针p r io r 可以快速确定个结点的直接前趋位置(p-p r io r),所需时间是0(1),而这种操作在单链表上实现需从头结点进行查找，所需时间是0(n)。将双链表首尾相接亦可形成双循环链表。(3)基本运算在双链表上的实现删除运
35、算将指定结点从链表中删除。如下图所示：花 -1c语言算法见教材【分析】首先修改指针删除P 所指结点：p-next-prior=p-prior；(2)p-prior-next=p-next;；然后释放P 所指的结点。插入运算将值为x 的新结点插入在链表的指定结点*p 之前。如下图所示C 语言算法见教材【分析】将新结点*s 插入在p 所指结点之前，应修改相应指针如图中标号所示。步骤为：s-prior=p-prior;s-next=p-next;(3)p-prior-next=s;p-prior=s;双链表中完成插入操作的操作步骤可以有多种组合，但应注意不能首先完成步骤，这样将、导致无法找到前趋结点
36、，使后续步骤无法完成。在操作位置已确定的情况下，双链表中插入和删除算法的时间复杂度 为。4.顺序表和链表的比较顺序表和链表各有优缺点，通常从时间特性和空间特性两方面来进行分析。基于空间特性的考虑顺序表的存储空间是静态分配的，要求事先明确规定它的存储规模。链表的存储空间是动态分配的。当线性表的长度变化较大，存储规模难以预先确定时，宜采用链式存储结构；顺序表的存储密度=1,链表的存储密度课堂练习题1.假设以带头结点的单链表作非递减有序线性表的存储结构。请设计一个时间复杂度为0(n)的算法，删除表中所有数值相同的多余元素，并释放结点空间。例如：(7,10,10,21,30,42,42,42,51,7
37、0)经算法操作后变为(7,10,21,30,42,51,70)【分析】算法思想：引入辅助指针p指向表中第一个元素结点；循环与后继结点比较，若相等则删除后继结点，否则，指针后移指向其后继结点，直 到p指向链表的最后一个结点。【答案】算法如下：void dellinklist(Linklist h)p=h-next;while(p!=NULL&p-next!=NULL)s=p-next;if(p-data=s-data)p-next=s-next;free(s);)else p=p-next;end while/dellinklist2.设A和B是两个单链表，其表中元素递增有序。试写一个算法将 A
38、 和 B 归并成一个按元素值递减有序的单链表，并要求辅助空间为0(1),请分析算法的时间复杂度。【答案】算法如下：void llistmerge(Linklist A,Linklist B,Linklist*L)/A和 B 分别指向两个单链表的头结点，合并后头指针由二级指针L带回Listnode*p,*p;*L=A；(*L)-next=NULL;A=A-next;P=B;B=B-next;while(A&B)if(A-datadata)p=A-next;A-next=(*L)-next;(*L)-next=A;A=p；elsep=B-next;B-next=(*L)-next;(*L)-nex
39、t=B;B=p；while(B)p=B-next;B-next=(*L)-next;(*L)-next=B;B=p；while(A)p=A-next;A-next=(*L)-next;(*L)-next=A;A=p；)时间复杂度分析留做课后习题。3.阅读下面的算法Linklist mynode(Linklist L)L 是不带头结点的单链表的头指针if(L&L-next)q=L;L=L-next;p=L;SI:while(p-next)p=p-next;S2:p-next=q;q-next=NULL;)return L;请回答下列问题：(l)说明语句S I的功能；(2)说明语句组S2的功能；(
40、3)用链表表示的线性表为(al,a 2,，a n),写出算法执行后的返回值所表示的线性表。【分析】题目所给算法的功能为：改变链表的结构，将所给单链表的头指针移向第二个结点，将第二个结点作为链表的第一个结点，将原来的第一个结点接在尾结点之后作为新的尾结点。具体过程是：当表不为空或超过一个结点时，q 指向第一个结点，以便于将其追加在表末，头指针L后移，指向第二个结点；p初值指向第一个结点，通过循环语句(S1:所示)最后定位于最后一个结点上；S2:所示语句组完成第一个结点追加在表末操作。【答案】(1)语句S1的功能：通过循环语句将P 定位于最后一个结点上；(2)语句组S2的功能：将 q 第一个结点追
41、加在表末,应将其next域置空。(3)(a2,a 3,，an,a l)4.阅读程序指出程序功能void delnode(linknode*p)p 指向带头结点循环链表中某结点linknode*q;q=p-next;while(q-next!=p)q=q-next;q-data=p-data;q-next=p-next;free(p);【答案】删除循环链表中P所指结点的前趋结点。5.以下函数中，h 是带头结点的双向循环链表的头指针。(1)说明程序的功能；(2)当链表中结点数分别为1和 6(不包括头结点)时，请写出程序中while循环体的执行次数。int f(DListNode*h)(DListN
42、ode*p,*q;int j=l;p=h-next;q=h-prior;while(p!=q&p-prior!=q)if(p-data=q-data)(p=p-next;q=q-prior;)else j=0;return j;)【分析】该算法功能是判断链表中各结点的值是否以链表中间为轴对称相等，即表中第i 个结点和第n-i+l个结点逐一比较，(其中，i=1,2,)若均相同则返回1,否则返回0。算法引入两个指针变量p、q 分别指向表中第一个元素结点和最后一个结点，然后循环逐一将对应元素比较，直到中间位置。【答案】(1)程序功能：该算法功能是判断链表中各结点的值是否以链表中间的结点为轴对称相等。
43、(2)当链表中结点数为1时p=q 直接退出循环，while循环体执行次数为0；当链表中结点数为6 时，while循环体执行次数为3。返回页首第三章栈和队列 教学目的和要求 重点难点 第一节 第二节 (课堂练习 教学目的和要求本章的目的是介绍栈和队列的逻辑结构定义及在两种结构上如何实现栈和队列的基本运算。要求在掌握上和队列的特点的基础上，懂得在什么样的情况下能够使用栈和队列。(重点难点,本章重点是掌握计算和队列的两种存储结构上实现的基本运算，难点是循环队列中对边界条件的处理。第一节,3.1栈3.1.1栈的定义及其运算(1)栈：是限制仅在表的一端进行插入和删除运算的线性表。允许进行插入和删除的这一
44、端称为栈顶，另一端称为栈底。当表中没有元素时称为空栈。(2)栈的特点：从定义不难看出栈具有后进先出(L a s t i n f i r s t o ut)的特点，简称为L I F O表。(3)栈的基本运算：I n i t s t a c k(S)构造一个空栈。S t a c k e m p t y(S)判定栈是否为空，若为空返回t r ue,否则，返回f a l s e S t a c k f ul l (S)判定栈是否已满，若已满返回t r ue,否则，返回f a l s e。该函数只适合于顺序栈。P us h(S,x)进栈操作。若栈不满，则将元素x 压入栈顶。P o p(S)出栈操作。若栈
45、S非空，则删除栈顶元素并将该元素返回。S t a c k t o p(S)读取栈顶元素。若栈S 非空，则返回栈顶元素。3.1.2顺序栈1 .栈的顺序表示与实现由于栈是操作受限制的线性表，所以，线性表的存储结构对栈的也适合。顺序栈类型定义如下：#d e f i n e S t a c k s i z e 1 0 0 /假定预分配的栈空间最多为1 0 0 个元素t yp e d e f c h a r d a t a t yp e;假定栈元素的数据类型为c h a rt e f s t r uc t d a t a t yp e d a t a S t a c k s i z e ;/用一维向量
46、d a t a 作为栈的存储空间i n t t o p;/t o p 为栈顶指针 S e q s t a c k;可以看出栈被定义为结构类型。在实际应用中，可根据具体情况使用结构型变量或指向结构型变量的指针变量来表示栈。2 .栈操作中应注意的问题：(设 S 是指向栈的指针)栈顶指针：S-t o p;栈顶元素：S-d a t a S-t o p ;栈空的判定条件：S-t o p=-l；栈满的判定条件：S-t o p=S t a c k s i z e T；栈中的元素个数：S-t o p+l；若 S是结构型变量则所涉及操作中的S-应改为S.；3 .栈的基本运算在顺序栈上的实现(1)进栈操作(p u
47、s h(S e q s t a c k *S,d a t a t yp e x)基本步骤：若栈不满，则栈顶指针加1：S-t o p+;元素入栈：S-d a t a S-t o p =x；(2)出栈操作(p o p (S e q s t a c k *S)基本步骤：若栈非空，则读取栈顶元素：x=S-d a t a S-t o p ;栈顶指针减1：S-t o p；返回栈顶元素：r e t ur n (x)；【分析】出栈操作和入栈操作是栈的两种重要操作，应注意操作的判定条件。栈的有效使用空间是0到 S t a c k s i z e-1,所以，当 S-t o p=T 时，表示栈空；当 S-t o p
48、=S t a c k s i z e-1 时,表示栈满。时间复杂度均为0(1)。3.1.3链栈1.链栈及类型定义栈以链式存储方式存储所形成的存储结构，称为链栈。就是单链表。其数据类型定义如下：t yp e d e f s t r uc t s t a c k n o d e (d a t a t yp e d a t a;s t r uc t s t a c k n o d e *n e xt;S t a c k n o d e;t yp e d e f s t r uc t S t a c k n o d e *s t o p;L i n k s t a c k;L i n k s t a
49、c k *s;2,链栈操作应注意的问题与链表不同，链栈的插入和删除操作仅限定在表头位置进行，所以，链栈不需要附加头结点.链表的头指针就是链栈的栈顶指针：S-t o p；栈顶元素为：S-t o p-d a t ao空栈的判定条件是：S-t o p=n ul l.；只要系统的备用空间能够分配出存储结点就不会发生上溢。所以，程序员不必考虑链栈栈满的问题。链栈的操作就是单链表的操作，只需注意栈本身的操作要求即可。如：进栈、出栈操作就是在表头进行插入和删除；求栈中的元素个数就是求链表中的结点个数。3.1.4栈的应用举例1 .设计算法判断一个算术表达式的圆括号是否正确配对。(提示：凡 遇 (就进栈，遇 )
50、就退掉栈顶的(表达式扫描完毕，栈应为空)算法int b ra c ke t sma t c h(c h a r a )设算术表达式以字符串形式存储在数组中S e q st a c k*S;I nit st a c k(S);int k=0;w h ile(a k!=,09)if (a k=,()P u sh(S,();e lse if (a k =,)if (S t a c ke mpt y(S)re t u rn 0;e lse P op(S);if (S t a c ke mpt y(S)re t u rn 1;e lse re t u rn 0;2.一个双向栈S是在同一向量空间里实现的两