首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知3个带头结点的线性链表A、B、C中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点),编写算法对链表A进行如下操作:使操作后的链表A中仅留下3个表中均包含的数据元素的结点,且没有值相同的结点,并释放所有无用结点。限定算法的时间复杂度为O
已知3个带头结点的线性链表A、B、C中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点),编写算法对链表A进行如下操作:使操作后的链表A中仅留下3个表中均包含的数据元素的结点,且没有值相同的结点,并释放所有无用结点。限定算法的时间复杂度为O
admin
2019-08-01
31
问题
已知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://jikaoti.com/ti/hDGjFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
试述明代一条鞭法的主要内容和历史意义。
院系调整
三国时期,魏、蜀、吴三国灭亡的历史顺序是()。
严复翻译的《天演论》一书的出版时间是()。
1628年出版了《心血运动论》一书,论证了血液在全身的循环运动,使生理学发展为科学的是()。
某网络的拓扑结构由下图所示,其中顶点表示路由器。该网络的路由器采用了链路状态路由算法,在某一时刻各个路由器发送的链路状态如下:A:B(1),D(3)B:A(1),D(1),C(3),E(5)C:B(3),D(1)D:A(3),B(1
IEEE754标准规定的64位浮点数格式中,符号位为1位,阶码为11位,尾数为52位。则它所能表示的最小规格化负数为()。
设有A,B,C,D4台主机都处在同一个物理网络中,A主机的IP地址是192.155.28.112,B主机的IP地址是192.155.28.120,C主机的IP地址是192.155.28.135,D主机的IP地址是192.155.28.202。共
试比较脱机I/O和联机I/O。
随机试题
患者发热时高时低,伴头昏乏力,纳少便溏,气短懒言,平常易感冒。自汗,舌淡,脉细弱。该症状属于
男,3l岁。支气管哮喘患者,中度持续发作的支气管哮喘患者应用糖皮质激素的原则是
张三、李四、王五都是河西村的村民。三家毗邻而居,依次是张家、李家、王家。请根据这些情况和下列各问中设定的条件回答问题。假设,张家靠山居住,三家门口仅有一条小路,则下列说法正确的是:()。
对于经常项目与资本项目外汇管理分别有不同的规定,下列选项巾不属于资本项目的是()。
【2014.山东东营】探讨一种新的教学方法是否优于原有教学方法,较适宜采用的课堂研究方法是()。
(2016·江苏)皮亚杰认为,儿童5岁以前是“无律期”,他们通常以“自我中心”的方式来考虑问题。()
劳务派遣是指劳务派遣机构受特定企业委托招聘员工,并与之签订劳动合同,将员工派遣到企业工作,其劳动过程由企业管理,其工资、福利、社会保险费等由企业提供给派遣机构,再由派遣机构支付给员工,并为员工办理社会保险登记和缴费等事务的一种特殊用工形式。根据上
向后弯曲的劳动供给曲线
鸽子走路时,头部并不是有规律地前后移动,而是一直在往前冲。行走时,鸽子脖子往前一探,然后,头部保持静止,等待着身体和爪子跟进。有学者曾就鸽子走路时伸脖子的现象作出假设:在等待身体跟进的时候,暂时静止的头部有利于鸽子获得稳定的视野,看清周围的食物。
ConstantvariationsintheamountofsunlightavailableonEarthatanygivenlocationmakeenergystorageanecessarydesignfe
最新回复
(
0
)