首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知3个带头结点的线性链表A、B、C中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点),编写算法对链表A进行如下操作:使操作后的链表A中仅留下3个表中均包含的数据元素的结点,且没有值相同的结点,并释放所有无用结点。限定算法的时间复杂度为O
已知3个带头结点的线性链表A、B、C中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点),编写算法对链表A进行如下操作:使操作后的链表A中仅留下3个表中均包含的数据元素的结点,且没有值相同的结点,并释放所有无用结点。限定算法的时间复杂度为O
admin
2019-08-15
21
问题
已知3个带头结点的线性链表A、B、C中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点),编写算法对链表A进行如下操作:使操作后的链表A中仅留下3个表中均包含的数据元素的结点,且没有值相同的结点,并释放所有无用结点。限定算法的时间复杂度为O(m+n+p),其中m、n和p分别为3个表的长度。
选项
答案
typedef struct LNode{ int data; struct LNode * next ; } * Linkedlist: LinkedList Common(LinkedList A,B,C){ //链表A、链表B和链表C是三个带头结点且结点元素值非递减排列的有序表 //本算法使链表A仅留下三个表均包含的结点,且结点值不重复,释放所有结点 Linkedlist*pa,* pb,*pc,*pre,*u: pa=A一>next;pb=B一>next;pc=C一>next i //pa,pb,pc分别是链表A,B,C的工作指针 pre=A; //pre是链表A中当前结点的前驱结点的指针 while(pa&&pb&&pc){ //当链表A,B和C均不空时,查找三链表共同元素 while(pa&&pb) if(pa一>data<pb一>data){u=pa;pa=pa一>next;free(u);}//结点元素值小时,后移指针 else if(pa一>data>pb一>data)pb=pb一>next: else if(pa&&pb){ //处理链表A和B元素值相等的结点 while(pc&&pc一>data<pa一>data)pc=pc一>next; if(pc){ //pc当前结点值与pa当前结点值不等,pa后移指针 if(pc->data>pa一>data){u=pa;pa=pa一>next;free(u);} else{ //pc、pa和pb对应结点元素值相等 if(pre==A) {pre一>next=pa;pre=pa;pa=pa一>next;} //结果表中第一个结点 else if(pre一>data==pa一>deLta) //(处理)重复结点不链入链表A {u=pa;pa=pa一>next;free(u);} else{pre一>next=pa;pre=pa;pa=pa一>next;} //将新结点链入链表A pb=pb一>next;pc=pc一>next; //链表的工作指针后移 }//else pc,pa和pb对应结点元素值相等 } if(pa==null)pre一>next=null; //原链表A已到尾,置新链表A表尾 elsef //处理原链表A未到尾而链表B或链表C到尾的情况 pre->next=null: //置链表A表尾标记 while(pa!=null){U=pa;pa=pa一>next;free(u);} //删除原链表A剩余元素 } } } } 提示:留下3个链表中的公共数据,首先查找链表A和链表B中公共数据,再去链表C中找有无该数据。要消除重复元素,应记住前驱,要求时间复杂度为O(m+n+p),在查找每个链表时,指针不能回溯。 算法实现时,链表A、链表B和链表C均从头到尾(严格地说链表B、链表C中最多一个到尾)遍历一遍,算法时间复杂度符合O(m+n+p)。算法主要有while(pa&&pb&&p)。
解析
转载请注明原文地址:https://jikaoti.com/ti/W3GjFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下面哪部经典是我国最早的官方史书?()
国民党政府宣布民盟为“非法团体”,民盟总部被迫解散的时间是()。
汉高祖派()出使南越,使得南越王赵佗向汉称臣,实现了汉对南越地区的控制。
一个客户机利用FTP协议从服务器上下载文件,如下图所示为整个过程中协议交换的过程,请回答如下问题:(1)该协议层图中第四层协议是什么?(2)如果FTP客户端采用了LIST命令来获得FTP服务器上的文件列表,该列表采用什么端口传输?
一个SPOOUNG系统由输入进程I、用户进程P、输出进程O、输入缓冲区、输出缓冲区组成。进程I通过输入缓冲区为进程P输入数据,进程P的处理结果通过输出缓冲区交给进程O输出。进程间数据交换以等长度的数据块为单位,这些数据块均存储在同一个磁盘上,因此,SPOO
已知4位有效信息为1010,试根据下列要求进行编码。(1)按配偶原则将其编码为扩展的海明码,要求能发现两位错并纠正一位错。(2)将其编码为循环冗余校验码,生成多项式G(x)=1011。
有n个生产者进程向1个有限的缓冲区不断地发送消息,这些消息通过缓冲区分发到m个消费者,缓冲区的大小只可以存放1条消息。生产者和消费者的工作遵循如下规则:(1)生产者和消费者对缓冲区的访问互斥;(2)对每1条放入缓冲区的消息,所有消费者都
某计算机的CPU主频为500MHz,CPI为5(即执行每条指令平均需5个时钟周期)。假定某外设的数据传输率为0.5MB/s,采用中断方式与主机进行数据传送,以32位为传输单位,对应的中断服务程序包含18条指令,中断服务的其他开销相当于2条指令的执行时间。请
已知一个带有表头结点的单链表,结点结构为:假设该链表只给出了头指针list。在不改变链表的前提下,请设计一个尽可能高效的算法,查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功,算法输出该结点的data值,并返回1;否则,只返回0。要求:描述算
随机试题
Iwenttoseemyparents_______NationalDay.()
dTMP是由下列哪种核苷酸直接转变
A.螺旋甾烷醇型B.达玛烷型C.齐墩果烷型D.乌索烷型E.羽扇豆烷型人参皂苷Ro是
某市检察院张某在办理一起受贿案件时,发现犯罪嫌疑人之一系其堂妹,故申请回避并经检察长同意。下列关于张某在申请回避前所取得的证据和进行的诉讼行为效力问题的表述,哪一项是正确的?()
某企业上年度全部资金来源包括普通股1640万元、长期债券1600万元、长期借款40万元,资金成本分别为20%、13%和12%。本年年初企业发行长期债券1200万元,年利率为14%,筹资费用率为2%,企业的股票价格变为每股38元。假设企业下年度发放股利每股5
风险缓释的目的在于降低未来风险发生时所带来的损失,()就是最常用、最重要的风险缓释措施。
下列历史事件按时间顺序排列正确的一组是()。
如果经计算机处理后,结果超过计算机可表示的数据范围,则称为_________。如超过最大值,则称为_________,如果超过最小值,则称为_______。
有如下程序:#includeusingnamespacestd;intmain(){int*p;*p=9;cout
•Youwillhearabusinesspresentationabout3simplesellingtactics.•Asyoulisten,forquestions1—12,completethenotes,
最新回复
(
0
)