专栏首页C语言入门到精通数据结构 | 每日一练(45)

数据结构 | 每日一练(45)

数据结构

合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下

——老子

1

每日一练

1.顺序结构线性表 LA 与 LB 的结点关键字为整数。LA 与 LB 的元素按非递减有序,线性表空间足够大。试

用类 PASCAL 语言给出一种高效算法,将 LB 中元素合到 LA 中,使新的 LA 的元素仍保持非递减有序。高效

指最大限度的避免移动元素。

正确答案

ps:||代表注释

1.[题目分析]顺序存储结构的线性表的插入,其时间复杂度为O(n),平均移动近一半的元素。线性表LA和LB合并时,若从第一个元素开始,一定会造成元素后移,这不符合本题“高效算法”的要求。另外,题中叙述“线性表空间足够大”也暗示出另外合并方式,即应从线性表的最后一个元素开始比较,大者放到最终位置上。设两线性表的长度各为m和n ,则结果表的最后一个元素应在m+n位置上。这样从后向前,直到第一个元素为止。

PROC Union(VAR LA:SeqList;LB:SeqList)∥LA和LB是顺序存储的非递减有序线性表,本算法将LB合并到LA中,元素仍非递减有序。

m:=LA.last;n:=LB.last;∥m,n分别为线性表LA和LB的长度。

k:=m+n; ∥k为结果线性表的工作指针(下标)。

i:=m;j:=n; ∥i,j分别为线性表LA和LB的工作指针(下标)。

WHILE(i>0)AND(j>0) DO

IF LA.elem[i]>=LB.elem[j]

THEN[LA.elem[k]:=LA.elem[i];k:=k-1;i:=i-1;]

ELSE[LA.elem[k]:=LB.elem[j];k:=k-1;j:=j-1;]

WHILE(j>0) DO [LA.elem[k]:=LB.elem[j];k:=k-1;j:=j-1;]

LA.last:=m+n;

ENDP;

[算法讨论]算法中数据移动是主要操作。在最佳情况下(LB的最小元素大于LA的最大元素),仅将LB的n个元素移(拷贝)到LA中,时间复杂度为O(n),最差情况,LA的所有元素都要移动,时间复杂度为O(m+n)。因数据合并到LA中,所以在退出第一个 WHILE循环后,只需要一个 WHILE循环,处理LB中剩余元素。第二个循环只有在LB有剩余元素时才执行,而在LA有剩余元素时不执行。本算法利用了题目中“线性表空间足够大”的条件,“最大限度的避免移动元素”,是“一种高效算法”。

如果您觉得本篇文章对您有作用,请转发给更多的人,点一下好看就是对小编的最大支持!

-end-

本文分享自微信公众号 - C语言入门到精通(gh_780327809188)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-04-29

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数据结构 | 每日一练(49)

    1.已知线性表(a1 a2 a3 …an)按顺序存于内存,每个元素都是整数,试设计用最少时间把所有值为负

    闫小林
  • 6.7 回溯法与树的遍历

    1、在程序设计中,有相当一类求一组解、或求全部解或求最优解的问题,大都是利用试探和回溯的搜索技术求解。

    闫小林
  • 2.1 线性表的类型定义

    1、线性表是最常用且最简单的一种数据结构,简言之,一个线性表是n个数据元素的有限序列。

    闫小林
  • 前端开发,关键技术点杂烩

    缓存:ETag Expire Last-Modified 三者合用,Expire 可以让浏览器完全不发起 Http 请求,若 F5 发起请求,也可以通过判断 E...

    用户5997198
  • 百度网盘上传也限速?不怕。

    之前发过很多关于百度网盘下载的软件,但是,百度网盘可不是只有下载限速,上传也是限速的。

    课代表
  • 人工智能核爆力:当AI发展到一定程度,人类会消失?(附PPT下载)

    导读:本文选自近期清华大学计算机系60周年系庆之产业论坛上,日本工程院院士、欧盟科学院院士、中国人工智能学会副理事长任福继教授所做的题为“人工智能的未来”的演讲...

    华章科技
  • Java任务调度框架之分布式调度框架XXL-Job介绍

    Java开发中经常会使用到定时任务:比如每月1号凌晨生成上个月的账单、比如每天凌晨1点对上一天的数据进行对账操作,在比如每天凌晨5点给180天未登陆过的用户发送...

    凯哥Java
  • 自制monkey语言编译器:符号系统与代码执行

    望月从良
  • 前端关键技术点杂烩,这些你必须知道

    这里总结一下 WEB 前端面试的常见问题,同时这些问题也是对一些基础的技术概念和思想的理解。对这些基本知识的掌握程度和深度决定了你的技术层级。高级工程师是必须掌...

    用户5997198
  • python 最简单的实现适配器设计模式

    适配器设计模式是懒得改动某些代码,或者某些接口不方便改动的时候,使用一个特定的封装,一些特定的编写办法,使不同的接口可以使用同种调用方式使用。

    1_bit

扫码关注云+社区

领取腾讯云代金券