首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知3个带头结点的线性链表A、B、C中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点),编写算法对链表A进行如下操作:使操作后的链表A中仅留下3个表中均包含的数据元素的结点,且没有值相同的结点,并释放所有无用结点。限定算法的时间复杂度为O
已知3个带头结点的线性链表A、B、C中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点),编写算法对链表A进行如下操作:使操作后的链表A中仅留下3个表中均包含的数据元素的结点,且没有值相同的结点,并释放所有无用结点。限定算法的时间复杂度为O
admin
2017-11-14
30
问题
已知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
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
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) f pre->next=pa;pre=pa;pa=pa一>next;} //结果表中第一个结点 else if(pre一>data==pa一>data) //(处理)重复结点不链入链表A {n=pa;pa=pa一>next;free(n);} 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/e3Ri777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
电子计算机的发展经过了四代,①电子数值积分计算机(ENIAC);②集成电路计算机;③大规模集成电路计算机;④晶体管计算机;⑤人工智能计算机,其先后顺序是()。
巴黎和会上,英国既与法国联合抵制美国称霸世界,又与美国联合反对法国过分削弱德国的要求,英国这样做的目的是()。
1925年爆发的当时世界上罢工时间最长的一次斗争是()。
洋务派创办军事工业的方式是()。
全国高校院系调整的具体时间是()。
材料一材科二(戈尔巴乔夫政府)在制定改革政策方针中存在三个严重问题:第一,仍然以优先发展重工业和机器制造业为主的“加速发展战略”作为发展资本密集型产业的主要战略,已不符合时代潮流。现代经济结构已由资本密集型向技术密集型发展……苏联的经济改革对
第一次国共合作采取了共产党员以个人身份加入国民党的党内合作方式,最早提出这种方式的是()。
在一个HDLC帧的数据中,如果出现了000111111011这样的流,请问发送到信道上它将会变成()。
在一个长度为n(n>1)的带头结点的单链表h上,设有尾指针r(指向尾结点),则执行()操作与链表的长度有关。
在散列表中,当装填因子非常接近1时,线性探测类似于()查找。
随机试题
(2001年第23题)非竞争性抑制剂存在时,酶促反应动力学的特点是
药物的作用机制与干扰叶酸代谢无关的是
重金属的土壤环境容量是指
高速公路施工中按里程来计算监理人员配置,应以()为原则。
用人单位未按照法律规定履行告知义务的,劳动者有权拒绝从事存在职业病危害的作业,用人单位不得因此()。
甲公司起诉乙公司,根据人民法院判决书,乙公司应向甲公司履行义务6年最后一日为2005年1月213,甲公司申请执行的期限应到2006年1月2日。()
某股份有限公司注册资本为1000万元,公司现有法定公积金400万元,任意公积金400万元,现该公司拟以公积金400万元增资派股,下列方案中,符合《公司法》规定的有()。
学校有目的、有计划、系统地对学生进行德育的基本途径是()
A、 B、 C、 D、 A第一排的三个图形分别是由5根火柴、5根火柴和6根火柴组成的,即第一排一共由16根火柴组成。第二排的三个图形分别是由5根火柴、5根火柴和6根火柴组成,也就是说第二排也是由16根火柴组成
(1)将考生文件夹下FIN文件夹中的文件KIKK.HTML复制到考生文件夹下文件夹DOIN中。(2)将考生文件夹下IBM文件夹中的文件CARE.TXT删除。(3)将考生文件夹下WATER文件夹删除。(4)为考生文件夹下FAR文件夹中的文件START
最新回复
(
0
)