首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知3个带头结点的线性链表A、B、C中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点),编写算法对链表A进行如下操作:使操作后的链表A中仅留下3个表中均包含的数据元素的结点,且没有值相同的结点,并释放所有无用结点。限定算法的时间复杂度为O
已知3个带头结点的线性链表A、B、C中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点),编写算法对链表A进行如下操作:使操作后的链表A中仅留下3个表中均包含的数据元素的结点,且没有值相同的结点,并释放所有无用结点。限定算法的时间复杂度为O
admin
2019-08-01
69
问题
已知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; //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->data) //(处理)重复结点不链入链表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表尾 else{ //处理原链表A未到尾而链表B或链表C到尾的情况 pre->next=null: //置链表A表尾标记 while(pa!=null){u=pa;pa=pa->next;free(u);}//删除原链表A剩余元素 } } } }
解析
转载请注明原文地址:https://kaotiyun.com/show/f3Ci777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
俄国在向帝国主义过渡的过程中.其被称为()。
中国政府第一次公开提出和平解决台湾问题的方针是在()。
在下列四本部书中有可能记载“甘薯所在,局面便有半年之粮,民间渐次广种”一语的只能是()。
毛泽东参与重庆谈判的主要目的是()。
中世纪战争史上有过两次君士坦丁堡陷落,分别简述其发生的时间、征战的双方、导致的历史变动。
甲骨文的发现是19世纪20世纪之交中国考古学最重要的发现之一,为重新认识三代的历史与文化奠定了基础,开辟了坦途,可称之为中国文化史的里程碑。根据所学知识回答问题:在甲骨文的研究流域,对甲骨文研究作出了重大贡献,被后人称为“甲骨四堂”的四位学者是(
1628年出版了《心血运动论》一书,论证了血液在全身的循环运动,使生理学发展为科学的是()。
已知某CPU有16根地址线、8根数据线,并用MREQ作为访存控制信号(低电平有效)。现有下列存储芯片:1K×4位ROM、2K×4位ROM、4K×8位ROM、4K×8位RAM、8K×4位RAM、8K×8位RAM和非门、与非门、或非门若干,如下图所
已知4位有效信息为1010,试根据下列要求进行编码。(1)按配偶原则将其编码为扩展的海明码,要求能发现两位错并纠正一位错。(2)将其编码为循环冗余校验码,生成多项式G(x)=1011。
随机试题
申诉人和控告人的义务与责任有:(1)______。(2)______。(3)______。
A产生络合物,妨碍吸收B增强毒性C产生沉淀,降低疗效D抑制药物活性E引发药源性疾病石膏、龙骨等中药与洋地黄类药物联合用
关于法院采取诉讼财产保全与诉前财产保全措施时,申请人是否需要提供担保的说法,正确的是( )。
已知:某公司20×8年销售收入为3000万元,销售净利率为8%,净利润的70%分配给投资者。20×8年12月31日的资产负债表(简表)如下:该公司预计20×9年销售净利率和利润留存率保持20×8年的水平,预计销售收入比上年增长40%。为实现这一目
《中华人民共和国合同法》第101条规定:“有下列情形之一,难以履行债务的,债务人可以将标的物提存:(一)债权人无正当理由拒绝受领;(二)债权人下落不明;(三)债权人死亡未确定继承人或者丧失民事行为能力未确定监护人;(
张珊:不同于“刀”“枪”“箭”“戟”,“之”“乎”“者”“也”这些字无确定所指。李思:我同意。因为“之”“乎”“者”“也”这些字无意义,因此,应当在现代汉语中废除。以下哪项最可能是李思认为张珊的断定所蕴含的意思?
[*]
阅读以下说明,回答问题1至问题5,将解答填入答题纸对应的解答栏内。[说明]某企业实施数据机房建设项目,机房位于该企业业务综合楼二层,面积约50平方米。机房按照国家B类机房标准设计,估算用电量约50kW,采用三相五线制电源输入,双回路向机房设备供电,对电
MoaifyCommand命令建立的文件的默认扩展名是()。
提高国民素质
最新回复
(
0
)