《2022年自考数据结构课后习题答案借鉴 .pdf》由会员分享，可在线阅读，更多相关《2022年自考数据结构课后习题答案借鉴 .pdf（27页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、自考数据结构课后习题答案本章的重点是了解数据结构的逻辑结构、存储结构、 数据的运算三方面的概念及相互关系，难点是算法复杂度的分析方法。需要达到 层次的基本概念和术语有：数据、数据元素、数据项、数据结构。特别是数据结构的逻辑结构、存储结构及数据运算的含义及其相互关系。数据结构的两大类逻辑结构和四种常用的存储表示方法。需要达到 层次的内容有算法、算法的时间复杂度和空间复杂度、最坏的和平均时间复杂度等概念，算法描述和算法分析的方法、对一般的算法要能分析出时间复杂度。对于基本概念，仔细看书就能够理解，这里简单提一下：数据就是指能够被计算机识别、存储和加工处理的信息的载体。数据元素是数据的基本单位，有时
2、一个数据元素可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。如整数这个集合中，10 这个数就可称是一个数据元素. 又比如在一个数据库( 关系式数据库) 中，一个记录可称为一个数据元素，而这个元素中的某一字段就是一个数据项。数据结构的定义虽然没有标准，但是它包括以下三方面内容：逻辑结构、存储结构、和对数据的操作。这一段比较重要，我用自己的语言来说明一下，大家看看是不是这样。比如一个 表( 数据库 ) ，我们就称它为一个数据结构，它由很多记录 ( 数据元素 ) 组成，每个元素又包括很多字段 ( 数据项) 组成。那么这张表的逻辑结构是怎么样的呢? 我们分析数据结构都是从结点 ( 其实也就
3、是元素、记录、顶点，虽然在各种情况下所用名字不同，但说的是同一个东东) 之间的关系来分析的，对于这个表中的任一个记录( 结点 ) ，它只有一个 直接前趋 ， 只有一个 直接后继 ( 前趋后继就是前相邻后相邻的意思) ， 整个表只有一个开始结点 和一个 终端结点 ，那我们知道了这些关系就能明白这个表的逻辑结构了。而存储结构 则是指用 计算机语言 如何表示结点之间的这种关系。如上面的表， 在计算机语言中描述为连续存放在一片内存单元中，还是随机的存放在内存中再用指针把它们链接在一起，这两种表示法就成为两种不同的存储结构。( 注意，在本课程里，我们只在高级语言的层次上讨论存储结构。) 第三个概念就是对
4、数据的运算 ，比如一张表格，我们需要进行查找，增加，修改，删除记录等工作，而怎么样才能进行这样的操作呢? 这也就是数据的运算，它不仅仅是加减乘除这些算术运算了，在数据结构中， 这些运算常常涉及算法问题。弄清了以上三个问题，就可以弄清数据结构这个概念。通常我们就将数据的逻辑结构 简称为 数据结构 ，数据的逻辑结构分两大类：线性结构 和 非线性结构 ( 这两个很容易理解) 数据的存储方法有四种：顺序存储方法、链接存储方法、索引存储方法和散列存储方法。下一个是 难点 问题，就是算法的描述和分析，主要是算法复杂度 的分析方法及其运用。首先了解一下几个概念。一个是时间复杂度 ，一个是 渐近时间复杂度。前
5、者是某个算法的时间耗费，它是该算法所求解问题 规模 n 的函数，而后者是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。当我们评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度，因此， 在算法分析时，往往对两者不予区分，经常是将渐近时间复杂度T(n)=O(f(n)简称为时间复杂度，其中的f(n) 一般是算法中频度最大的语句频度。此外， 算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。但是我们总是考虑在最坏的情况名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - -
6、 第 1 页，共 27 页 - - - - - - - - - 下的时间复杂度。以保证算法的运行时间不会比它更长。常见的时间复杂度，按数量级递增排列依次为：常数阶 O(1) 、对数阶 O(log2n) 、 线性阶 O(n) 、 线性对数阶O(nlog2n) 、平方阶 O(n2) 、立方阶 O(n3) 、k 次方阶 O(nk) 、指数阶 O(2n) 。时间复杂度的分析计算请看书本上的例子，然后我们通过做练习加以领会和巩固。size=+3数 据 结 构 习 题 一1.1 简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。 数据 ：指能够被计算机识别、存储和
7、加工处理的信息载体。 数据元素 ：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。数据元素有时可以由若干 数据项 组成。 数据类型 ：是一个值的集合以及在这些值上定义的一组操作的总称。 数据结构 ：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容: 数据的 逻辑结构 、存储结构和数据的运算 。 逻辑结构 ：指各数据元素之间的逻辑关系。 存储结构 ：就是数据的逻辑结构用计算机语言的实现。 线性结构 ：数据逻辑结构中的一类，它的特征是若结构为非空集，则该结构有且只有一个开始结点 和一个 终端结点，并且所有结点都最多只有一个直接前趋 和一个 直接后继 。线性
8、表就是一个典型的线性结构。 非线性结构 ：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。1.2 试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。 例如有一张学生成绩表，记录了一个班的学生各门课的成绩。按学生的姓名为一行记成的表。这个表就是一个数据结构。每个记录( 有姓名，学号，成绩等字段) 就是一个结点，对于整个表来说，只有一个开始结点( 它的前面无记录) 和一个终端结点( 它的后面无记录) ， 其他的结点则各有一个也只有一个直接前趋和直接后继( 它的前面和后面均有且只有一个记录) 。这几个关系就确定了这个表的逻辑结构。那么我们怎样把这个表
9、中的数据存储到计算机里呢? 用高级语言如何表示各结点之间的关系呢? 是用一片连续的内存单元来存放这些记录( 如用数组表示 ) 还是随机存放各结点数据再用指针进行链接呢? 这就是存储结构的问题，我们都是从高级语言的层次来讨论这个问题的。( 所以各位赶快学C语言吧 ) 。最后，我们有了这个表( 数据结构 ) ，肯定要用它，那么就是要对这张表中的记录进行查询，修改，删除等操作，对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算问题了。1.3 常用的存储表示方法有哪几种? 常用的存储表示方法有四种: 顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元
10、的邻接关系来体现。由此得到的存储表示称为顺序存储结构。 链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构。 索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 27 页 - - - - - - - - - 散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。1.4 设三个函数f,g,h分别为 f(n)=100n
11、3+n2+1000 , g(n)=25n3+5000n2 , h(n)=n1.5+5000nlgn 请判断下列关系是否成立：(1) f(n)=O(g(n) (2) g(n)=O(f(n) (3) h(n)=O(n1.5) (4) h(n)=O(nlgn) (1) 成立。 这里我们复习一下渐近时间复杂度的表示法T(n)=O(f(n)，这里的 O是数学符号，它的严格定义是若 T(n) 和f(n) 是定义在正整数集合上的两个函数，则T(n)=O(f(n)表示存在正的常数C 和size=+1nsize=-30 , 使得当nsize=+1nsize=-30 时都满足0T(n) Cf(n) 。 用容易理解
12、的话说就是这两个函数当整型自变量n 趋向于无穷大时，两者的比值是一个不等于0 的常数 。这么一来，就好计算了吧。第(1) 题中两个函数的最高次项都是n3,因此当 n时，两个函数的比值是一个常数，所以这个关系式是成立的。 （2）成立。 （3）成立。 （4）不成立。1.5 设有两个算法在同一机器上运行，其执行时间分别为100n2 和 2n, 要使前者快于后者，n 至少要多大 ? 15 最简单最笨的办法就是拿自然数去代呗。假定n 取为 10，则前者的值是10000，后者的值是1024, 小于前者，那我们就加个5，用 15 代入得前者为22500，后者为 32768，已经比前者大但相差不多，那我们再减
13、个1，用 14 代入得，前者为 19600, 后者为 16384，又比前者小了，所以结果得出来就是n 至少要是15. 1.6 设 n 为正整数，利用大O记号，将下列程序段的执行时间表示为n 的函数。(1) i=1; k=0 while(iN) k=k+10*i;i+; T(n)=n-1 T(n)=O(n) 这个函数是按线性阶递增的(2) i=0; k=0; do k=k+10*i; i+; while(iN); TD td=1,1,56%T(n)=n T(n)=O(n) 这也是线性阶递增的名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - -
14、- - 名师精心整理 - - - - - - - 第 3 页，共 27 页 - - - - - - - - - (3) i=1; j=0; while(i+j=n) if (i1 while (x=(y+1)*(y+1) y+; T(n)=n1/2 T(n)=O(n1/2) 最坏的情况是y=0，那么循环的次数是n1/2 次，这是一个按平方根阶递增的函数。(5) x=91; y=100; while(y0) if(x100) x=x-10;y-; else x+; T(n)=O(1) 这个程序看起来有点吓人，总共循环运行了1000次，但是我们看到n 没有 ? 没。这段程序的运行是和n 无关的，就
15、算它再循环一万年，我们也不管他，只是一个常数阶的函数。1.7 算法的时间复杂度仅与问题的规模相关吗? No, 事实上，算法的时间复杂度不仅与问题的规模相关，还与输入实例中的元素取值等相关，但在最坏的情况下，其时间复杂度就是只与求解问题的规模相关的。我们在讨论时间复杂度时，一般就是以最坏情况下的时间复杂度为准的。1.8 按增长率由小至大的顺序排列下列各函数：2100, (2/3)n， (3/2)n， nn , , n! ，2n ，lgn ,nlgn, n(3/2)，n 分析如下： 2100 是常数阶； (2/3)n和 (3/2)n是指数阶 , 其中前者是随n 的增大而减小的； nn 是指数方阶；
16、n 是方根阶 , n! 就是n(n-1)(n-2). 就相当于n 次方阶； 2n 是指数阶， lgn是对数阶 ,nlgn是对数方阶 , n(3/2)是 3/2 次方阶。根据以上分析按增长率由小至大的顺序可排列如下： (2/3)n 2100 lgn n n(3/2) nlgn (3/2)n 2n n! 10) if(x100)x=x-10;y-; else x+; A. O(1) B.O(x) C.O(y) D.O(n) 【数据结构】第二章串讲+复习要点size=+3第二章线性表本章的 重点 是掌握 顺序表 和单链表 上实现的各种基本算法及相关的时间性能分析，难点 是使用本章所学的基本知识设计有
17、效算法 解决与线性表相关的应用问题。要求达到 层次的内容有: 线性表的逻辑结构特征；线性表上定义的基本运算，并利用基本运算构造出较复杂的运算。要求达到 层次的内容有：顺序表的含义及特点，顺序表上的插入、删除操作及其平均时间性能分析，解决简单应用问题。链表如何表示线性表中元素之间的逻辑关系；单链表、双链表、循环链表链接方式上的区别；单链表上实现的建表、查找、 插入和删除等基本算法及其时间复杂度。循环链表上尾指针取代头指针的作用，以及单循环链表上的算法与单链表上相应算法的异同点。双链表的定义和相关算法。利用链表设计算法解决简单应用问题。要求达到 层次的内容就是顺序表和链表的比较，以及如何选择其一作
18、为其存储结构才能取得较优的时空性能。线性表 的逻辑结构特征 是很容易理解的， 如其名， 它的逻辑结构特征就好象是一条线，上面打了一个个结，很形象的，如果这条线上面有结，那么它就是非空表，只能有一个开始结点 ，有且只能有一个终端结点 ，其它的结前后所相邻的名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 27 页 - - - - - - - - - 也只能是一个结点(直接前趋 和直接后继 ) 。关于线性表上定义的基本运算，主要有构造空表、求表长、取结点、查找、插入、删除等。线
19、性表 的逻辑结构 和存储结构 之间的关系。在计算机中，如何把线性表的结点存放到存储单元中，就有许多方法，最简单的方法就是按顺序存储 。就是按线性表的逻辑结构次序依次存放在一组地址连续的存储单元中。在存储单元中的各元素的物理位置和逻辑结构中各结点相邻关系是一致的。在顺序表中实现的基本运算主要讨论了插入 和删除 两种运算。 相关的算法我们通过练习掌握。对于顺序表的插入和删除运算，其平均时间复杂度均为O(n) 。线性表的 链式存储结构 。它与顺序表不同， 链表 是用一组 任意的存储单元来存放线性表的结点，这组存储单元可以分布在内存中任何位置上。因此， 链表中结点的逻辑次序和物理次序不一定相同。所以为
20、了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还存储了其后继结点的地址信息( 即指针或链 ) 。 这两部分信息组成链表中的结点结构。一个单链表由头指针的名字来命名。对于单链表，其操作运算主要有建立单链表 ( 头插法、尾插法和在链表开始结点前附加一个头结点 的算法 )、查找 ( 按序号和按值 ) 、插入 运算、 删除 运算等。以上各运算的平均时间复杂度均为O(n). 其主要时间是耗费在查找操作上。循环链表 是一种首尾相接的链表。也就是终端结点的指针域不是指向NULL 空而是指向开始结点( 也可设置一个头结点) ，形成一个环。采用循环链表在实用中多采用尾指针表示单循环链表。这样做的好处是查
21、找头指针和尾指针的时间都是 O(1)，不用遍历整个链表了。判别链表终止的条件也不同于单链表，它是以指针是否等于某一指定指针如头指针或尾指针来确定。双链表 就是双向链表，就是在单链表的每个结点里再增加一个指向其直接前趋的指针域prior,这样形成的链表就有两条不同方向的链。使得从已知结点查找其直接前趋 结点可以和查找其直接后继 结点的时间一样缩短为O(1) 。双链表 一般也由头指针head 惟一确定。双链表也可以头尾相链接构成双( 向) 循环链表。关于顺序表和链表的比较，请看下表：具体要求顺序表链表基于空间适于线性表长度变化不大，易于事先确定其大小时采用。适于当线性表长度变化大，难以估计其存储规
22、模时采用。基于时间由于顺序表是一种随机存储结构，当线性表的操作主要是查找时，宜采用。链表中对任何位置进行插入和删除都只需修改指针，所以这类操作为主的线性表宜采用链表做存储结构。若插入和删除主要发生在表的首尾两端，则宜采用尾指针表示的单循环链表。size=+3第二章线性表复习要点名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 27 页 - - - - - - - - - 本章复习要点是：线性表的逻辑结构特征、常见的线性表的六种基本运算，并可以根据这些基本运算组合得到更复杂的
23、运算。顺序表的特征、顺序表中结点地址的计算。顺序表上实现的基本运算( 算法 ) ：主要是插入和删除的算法。顺序表的算法应该掌握。算法时间复杂度要记住。单链表的特征、图形表示法。单链表的各种算法实现，并能运用这些算法解决一些简单问题；循环链表的特征、双链表的特征以及它们的主要算法实现。可能出的题型有：填空题、简答题、应用题和算法题. 如：在双链表中插入运算的时间复杂度为：(.) A.O(1) B.O(n) C.O(lgn) D.O(nlgn) 请问头指针，开始结点和头结点的区别与联系。关于单链表上进行排序的算法设计。第二章 (线性表 ) 习题参考答案一、基础知识题2.1 试描述头指针、头结点、开
24、始结点的区别、并说明头指针和头结点的作用。2.1 答：开始结点是指链表中的第一个结点，也就是没有直接前趋的那个结点。链表的头指针是一指向链表开始结点的指针( 没有头结点时 ) ，单链表由头指针唯一确定，因此单链表可以用头指针的名字来命名。头结点是我们人为地在链表的开始结点之前附加的一个结点。有了头结点之后， 头指针指向头结点，不论链表否为空，头指针总是非空。而且头指针的设置使得对链表的第一个位置上的操作与在表其他位置上的操作一致( 都是在某一结点之后 ) 。2.2 何时选用顺序表、何时选用链表作为线性表的存储结构为宜? 2.2 答：在实际应用中， 应根据具体问题的要求和性质来选择顺序表或链表作
25、为线性表的存储结构，通常有以下几方面的考虑：1. 基于空间的考虑。 当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。2. 基于时间的考虑。 若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之，若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。2.3 在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素? 2.3. 答：在
26、等概率情况下， 顺序表中插入一个结点需平均移动n/2 个结点。 删除一个结点需平均移动(n-1)/2个结点。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 27 页 - - - - - - - - - 具体的移动次数取决于顺序表的长度n 以及需插入或删除的位置i 。 i 越接近 n 则所需移动的结点数越少。2.4 为什么在单循环链表中设置尾指针比设置头指针更好? 2.4. 答：尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设
27、一带头结点的单循环链表，其尾指针为rear ， 则开始结点和终端结点的位置分别是rear-next-next 和 rear, 查找时间都是O(1) 。若用头指针来表示该链表，则查找终端结点的时间为O(n) 。2.5 在单链表、双链表和单循环链表中，若仅知道指针p 指向某结点，不知道头指针，能否将结点*p 从相应的链表中删去 ?若可以，其时间复杂度各为多少? 2.5 答：我们分别讨论三种链表的情况。1. 单链表。当我们知道指针p 指向某结点时，能够根据该指针找到其直接后继，但是由于不知道其头指针，所以无法访问到p 指针指向的结点的直接前趋。因此无法删去该结点。2. 双链表。由于这样的链表提供双向
28、链接，因此根据已知结点可以查找到其直接前趋和直接后继，从而可以删除该结点。其时间复杂度为O(1) 。3. 单循环链表。根据已知结点位置，我们可以直接得到其后相邻的结点位置( 直接后继 ) ，又因为是循环链表，所以我们可以通过查找，得到p 结点的直接前趋。因此可以删去p 所指结点。其时间复杂度应为O(n) 。2.6 下述算法的功能是什么? LinkList Demo(LinkList L) / L 是无头结点单链表 ListNode *Q,*P; if(L&L-next) Q=L;L=L-next=L; while (P-next) P=P-next; P-next=Q; Q-next=NULL
29、; return L; / Demo2.6 答：该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。二、算法设计题2.7 设线性表的n 个结点定义为 (size=+2a0,size=+2a1,.size=+2an-1)， 重写顺序表上实现的插入和删除算法： InsertList 和 DeleteList. 答：开始结点是指链表中的第一个结点，也就是没有直接前趋的那个结点。链表的头指针是一指向链表开始结点的指针( 没有头结点时 ) ，单链表由头指针唯一确定，因此单链表可以用头指针的名字来命名。名师资料总结 - - -精品资料欢
30、迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 27 页 - - - - - - - - - 头结点是我们人为地在链表的开始结点之前附加的一个结点。有了头结点之后， 头指针指向头结点，不论链表否为空，头指针总是非空。而且头指针的设置使得对链表的第一个位置上的操作与在表其他位置上的操作一致( 都是在某一结点之后 ) 。2.8 试分别用顺序表和单链表作为存储结构，实现将线性表(a0,a1,.an-1)就地逆置的操作，所谓 就地 指辅助空间应为 O(1) 。解：按题意，为将线性表逆置，但辅助空间不能随表的规模增
31、大。我们分别讨论顺序表和单链表的情况：1. 顺序表：要将该表逆置，可以将表中的开始结点与终端结点互换，第二个结点与倒数第二个结点互换，如此反复，就可将整个表逆置了。算法如下：/ 表结构定义同上void ReverseList( Seqlist *L) Datatype t ; file:/设置临时空间用于存放data int i; for ( i=0 ; i length/2 ; i+) t = L-data; file:/交换数据L - data i = L - data L - length - 1 - i ; L - data L - length - 1 - i = t ;
32、 2. 链表：也是可以用交换数据的方式来达到逆置的目的，但是由于是单链表，数据的存取不是随机的，因此算法效率太低，我们可以利用指针的指向转换来达到表逆置的目的。算法是这样的：/ 结构定义略LinkList ReverseList( LinkList head ) / 将 head 所指的单链表逆置ListNode *p ,*q ;/设置两个临时指针变量if( head-next & head-next-next) file:/当链表不是空表或单结点时p=head-next; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - -
33、名师精心整理 - - - - - - - 第 9 页，共 27 页 - - - - - - - - - q=p-next; p - next=NULL; file:/将开始结点变成终端结点while (q) file:/每次循环将后一个结点变成开始结点p=q; q=q-next ; p-next = head- next ; head-next = p; return head; return head; file:/如是空表或单结点表，直接返回head 2.9 设顺序表 L是一个递增有序表，试写一算法，将x 插入 L 中，并使 L 仍是一个有序表。解：因已知顺序表 L是递增
34、有序表，所以只要从头找起找到第一个比它大(或相等)的结点数据，把 x 插入到这个数所在的位置就是了。算法如下：void InsertIncreaseList( Seqlist *L , Datatype x ) int i; for ( i=0 ; i length & L-data i next & p-next-datax ) p=p-next; s=(ListNode *)malloc(sizeof(ListNode); s-data=x; s-next=p-next; p-next=s; return L; 2.11 写一算法在单链表上实现线性表的ListLength(L)运算。解：求
35、单链表长只能用遍历的方法了，从头数到尾，总能数出来吧。算法如下：int ListLength ( LinkList L ) int len=0 ; ListNode *p; p=L; file:/设该表有头结点while ( p-next ) p=p-next; len+; return len; 2.12 已知 L1 和 L2 分别指向两个单链表的头结点，且已知其长度分别为m和 n。试写一算法将这两个链表连接在一起，请分析你的算法的时间复杂度。解：算法如下 : LinkList Link( LinkList L1 , LinkList L2 ) file:/将两个单链表连接在一起
36、名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 27 页 - - - - - - - - - ListNode *p , *q ; p=L1; q=L2; while ( p-next ) p=p-next; file:/查找终端结点p-next = q-next ; file:/将 L2的开始结点链接在 L1 之后return L1 ; 本算法的主要操作时间花费在查找L1 的终端结点上，与 L2的长度无关，所以本算的法时间复杂度为：m+1=O(m) 2.1
37、3 设 A 和 B是两个单链表， 其表中元素递增有序。试写一算法将A和 B归并成一个按元素值递减有序的单链表C，并要求辅助空间为O(1) ，请分析算法的时间复杂度。解：根据已知条件，A和 B是两个递增有序表，所以我们可以以A表为基础，按照插入单个元素的办法把B表的元素插入A表中，完成后，将表逆置就得到了一个按元素值递减有序的单链表C了。算法如下：LinkList MergeSort ( LinkList A , LinkList B ) / 归并两个递增有序表为一个递减有序表ListNode *pa , *pb , *qa , *qb ; pa=A; pb=B ; qa=A-next; qb=
38、B-next; while ( qa & qb) if ( qb-data data ) / 当 B中的元素小于A中当前元素时，插入到它的前面pb=qb; qb=qb-next ;/ 指向 B中下一元素pa-next=pb; pb-next=qa; pa=pb; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 27 页 - - - - - - - - - else if ( qb-data = pa-data & qb-data data) / 当 B中元素大于等于A中
39、当前元素/ 且小于等于A中后一元素时，/ 将此元素插入到A的当前元素之后pa=qa; qa=qa-next; / 保存 A的后一元素位置pb=qb; qb=qb-next; / 保存 B的后一元素位置pa-next=pb; file:/插入元素pb-next=qa; else / 如果 B中元素总是更大, 指针移向下一个A元素pa=qa; qa=qa-next; if ( qb ) / 如果 A表已到终端而B表还有结点未插入 / 将 B表接到 A表后面pa-next=qb; LinkList C=ReverseList ( A );/ 调用前面2.8 题所设计的逆置函数return C;
40、 file:/返回新的单链表C, 已是递减排列 该算法的时间复杂度分析如下：算法中只有一个while 循环，在这个循环中，按照最坏的情况是B元素既有插到A 的最前的，也有插到最后的，也就是说需要把A中元素和B中元素全部检查比较过，这时的所费时间就是m+n. 而新链表的长度也是m+n+1 ( 有头结点) ，这样逆置函数的执行所费时间为m+n+1.所以可得整个算法的时间复杂度为：m+n+m+n+1=2(m+n)+1= O(m+n) - 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第
41、 13 页，共 27 页 - - - - - - - - - 为验证本题，晓津设计了一个程序，清单如下：/ListStruct.h 将链表结构存为头文件typedef char DataType; file:/假设结点的数据类型是字符型typedef struct node file:/结点类型定义DataType data; struct node *next;/结点的指针域ListNode; typedef ListNode * LinkList; / 以下是源文件 / 在 VC+ 中运行通过。#include #include #include ListStruct.h #i
42、nclude LinkList CreatList (void) file:/用尾插法建立带头结点的单链表char ch; LinkList head = (LinkList)malloc(sizeof( ListNode); file:/生成头结点ListNode *s , *r; r=head;/尾指针亦指向头结点while (ch=getchar()!=n) s=(ListNode *) malloc (sizeof(ListNode); s-data=ch; r-next=s; r=s; r-next=NULL; return head; void OutList( Lin
43、kList L) ListNode *p; p=L; while (p-next) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 27 页 - - - - - - - - - cout next-data next; cout next & head-next-next) file:/当链表不是空表或单结点时 p=head-next; q=p-next; p - next=NULL; file:/将开始结点变成终端结点while (q) file:/
44、每次循环将后一个结点变成开始结点p=q; q=q-next ; p-next = head- next ; head-next = p; return head; return head; file:/直接返回 head LinkList MergeSort ( LinkList A , LinkList B ) / 归并两个递增有序表为一个递减有序表ListNode *pa , *pb , *qa , *qb ; pa=A; pb=B ; qa=A-next; qb=B-next; while ( qa & qb) 名师资料总结 - - -精品资料欢迎下载 - - - - - - -
45、- - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 27 页 - - - - - - - - - if ( qb-data data ) / 当 B中的元素小于A中当前元素时，插入到它的前面pb=qb; qb=qb-next ;/ 指向 B中下一元素pa-next=pb; pb-next=qa; pa=pb; else if ( qb-data = pa-data & qb-data data) / 当 B中元素大于等于A中当前元素/ 且小于等于A中后一元素时，/ 将此元素插入到A的当前元素之后pa=qa; qa=qa-next; / 保存
46、A的后一元素位置pb=qb; qb=qb-next; / 保存 B的后一元素位置pa-next=pb; file:/插入元素pb-next=qa; else / 如果 B中元素总是更大, 指针移向下一个A元素pa=qa; qa=qa-next; if ( qb ) / 如果 A表已到终端而B表还有结点未插入 / 将 B表接到 A表后面pa-next=qb; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 27 页 - - - - - - - - - LinkLis
47、t C=ReverseList ( A );/ 调用前面2.8 题所设计的逆置函数return C; file:/返回新的单链表C, 已是递减排列 void main() LinkList A, B, C; A=CreatList(); OutList (A); B=CreatList(); OutList (B); C=MergeSort (A ,B); OutList (C); - 以下是一位学友鲁周航提供的算法：我的算法思路为：当A 、B都不空时，各取A、B表中的第一个结点比较，哪个值小，就把它用头插法插入C表。（利用原来的头结点，始终是取第一个结点比较）继续取值比较。当A表为空，
48、或B表为空，则把剩余结点用头插法插入C表。void LinkList(Nodetype *A,Nodetype *B, Nodetype *C) / 假设 A和 B已建立， C表的头结点已初始化Nodetype *p, *q; p=A-Next; q=B-Next; while(p&q)/两表中都有数 if(p-DataData)/如 A中的结点值大于B中结点值 A-Next=p-Next;/A指向 A表的下一个结点p-Next=C-Next;/把 P的结点用头插法，插入C表。C-Next=p; p=A-Next;/P指向 A表的第一个结点，继续比较 else 名师资料总结 - - -精品资料
49、欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 27 页 - - - - - - - - - B-Next=q-Next;/算理同上面q-Next=C-Next; C-Next=q; q=B-Next; if(p)/如 A表还有结点，则把剩余结点，用头插法插入C表 while(p) A-Next=p-Next; p-Next=C-Next; C-Next=p; p=A-Next; else if(q)/如 B表还有结点，则把剩余结点，用头插法插入B表 while(q) B-Next=q-Next; q
50、-Next=C-Next; C-Next=q; q=B-Next; free(A);/释放原头结点空间free(B); 你的算法要排表两次，第一次为插入，第二次为逆序。2.14 已知单链表L 是一个递增有序表，试写一高效算法，删除表中值大于min 且小于 max的结点 ( 若表中有这样的结点 ) ，同时释放被删结点的空间，这里min 和 max 是两个给定的参数。请分析你的算法的时间复杂度。解：要解这样的问题，我们首先想到的是拿链表中的元素一个个地与max和 min 比较， 然后删除这个结点，其实因为已知名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - -