首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知3个带头结点的线性链表A、B、C中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点),编写算法对链表A进行如下操作:使操作后的链表A中仅留下3个表中均包含的数据元素的结点,且没有值相同的结点,并释放所有无用结点。限定算法的时间复杂度为O
已知3个带头结点的线性链表A、B、C中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点),编写算法对链表A进行如下操作:使操作后的链表A中仅留下3个表中均包含的数据元素的结点,且没有值相同的结点,并释放所有无用结点。限定算法的时间复杂度为O
admin
2017-11-14
71
问题
已知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
学硕统考专业
相关试题推荐
下列对春秋时期各国称霸的顺序描述错误的选项是()
下列不属于战时共产主义政策内容的是()。
十六国时期的历史,可以划分为前后两个时期,其分界线是()。
以下选项不属于希腊城邦的形成方式和途径的是()。
1901年6月,发表《立宪法议》,首先提出君主立宪要求的是()。
1905年至1907年间,围绕中国究竟是采用革命手段还是改良方式这个问题,革命派与改良派进行论战的舆论阵地是()。
在阿拉伯()统治时期,阿拉伯军队曾与当时中国的唐朝军队发生冲突。
文艺复兴运动兴起的时间是()。
第一次国共合作采取了共产党员以个人身份加入国民党的“党内合作”方式。最早提出这种方式的是()。
42.设有带头结点的循环双链表表示的线性表L=(a1,a2,……,an-1,an)。设计在时间和空间上都尽可能高效的算法,将L改造成L=(a1,a2,……,an,……a4,a2)。要求:(1)给出算法的基本设计思想。(2)根据设计思想,
随机试题
(2021年威海)教师应该尊重学生的人格,不得歧视学生,不得对学生实施_______或者其他侮辱人格尊严的行为,不得侵犯学生的合法权益。
计数器的内部电路主要是由单稳态触发器构成。()
关于胰岛素在糖尿病患者治疗中的使用,下列各项正确的有
掌中间隙感染手术切口一般不超过远侧掌横纹,以免损伤
诊断盆腔脓肿最可靠的方法
一般海上旅客运输的运送期间为( )。
内部收益率是指使得投资净现值大于零的贴现率。()
Aneight-year-oldchildheardherparentstalkingaboutherlittlebrother.Allsheknewwasthathewasverysickandtheyhad
代位继承是指被继承人的子女先于被继承人死亡时,由被继承人子女的晚辈直系血亲代替先死亡的长辈直系血亲继承被继承人遗产的一项法定继承制度。根据以上定义,下列属于代位继承的是()。
我国《劳动法》适用于一定范围的劳动者,以下适用于《劳动法》的是()。
最新回复
(
0
)