首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知3个带头结点的线性链表A、B、C中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点),编写算法对链表A进行如下操作:使操作后的链表A中仅留下3个表中均包含的数据元素的结点,且没有值相同的结点,并释放所有无用结点。限定算法的时间复杂度为O
已知3个带头结点的线性链表A、B、C中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点),编写算法对链表A进行如下操作:使操作后的链表A中仅留下3个表中均包含的数据元素的结点,且没有值相同的结点,并释放所有无用结点。限定算法的时间复杂度为O
admin
2019-08-15
61
问题
已知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://kaotiyun.com/show/jlCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列各组条约的时间排列顺序正确的是()。①《布列斯特条约》②《色佛尔条约》③《九国公约》④《洛桑条约》
德国纳粹党消灭资产阶级民主制的关键性事件是()。
甲骨文的发现是19世纪20世纪之交中国考古学最重要的发现之一,为重新认识三代的历史与文化奠定了基础,开辟了坦途,可称之为中国文化史的里程碑。根据所学知识回答问题:()选拓龟板,印成(),这成为甲骨文的第一部著录之作,此后,甲骨学逐渐成为
下列内容,与垄断组织出现有关的是()。①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展,在某种程度上适应了生产力发展的需要③干预、控制国家的政治、经济生活④积极向外扩张,从经济上瓜分世界
“一战”期间,中国民族资本主义迅速发展的重要作用是()。
在一个HDLC帧的数据中,如果出现了000111111011这样的流,请问发送到信道上它将会变成()。
若二叉树的前序序列为DABCEFG,中序序列为BACDFGE,则其层次序列为()。
IEEE754标准规定的64位浮点数格式中,符号位为1位,阶码为11位,尾数为52位。则它所能表示的最小规格化负数为()。
OSI模型中完成路径选择功能的层次是()。
CSMA/CA是如何实现“冲突避免”的?
随机试题
留置权消灭的原因有()。
PowerPoint提供的幻灯片母版有哪几种?其各自作用是什么?
龋齿的治疗方法
下列关于唾液腺分泌管的描述.不正确的是
合同法律关系的主体不包括()。
甲公司是一家上市的股份有限公司。甲公司与乙公司均为增值税一般纳税人,销售货物适用的增值税税率均为17%,销售无形资产适用的增值税税率为6%,适用的所得税税率均为25%。甲公司对乙公司股权投资的有关资料如下:(1)2×15年10月10日,甲公司取得乙公司1
著名历史学家费正清在《伟大的中国革命》中描绘了这样一个农民形象:“…普通农民大概一半是自耕农,一半兼做佃农。不管怎样,他和他的家人在相隔不远的三四块田地里劳动,带着锄头和镰刀来来回回,主要为他们自己的生存干活……还可以种点卖钱的作物。”这反映了自耕农(
根据图表,以下不正确的一项是()。
AWE:
TheUniversityBookstoreisaself-supportinguniversity-ownedorganization,whichwasfoundedin1921.Itprovidesstudents,fa
最新回复
(
0
)