首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知3个带头结点的线性链表A、B、C中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点),编写算法对链表A进行如下操作:使操作后的链表A中仅留下3个表中均包含的数据元素的结点,且没有值相同的结点,并释放所有无用结点。限定算法的时间复杂度为O
已知3个带头结点的线性链表A、B、C中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点),编写算法对链表A进行如下操作:使操作后的链表A中仅留下3个表中均包含的数据元素的结点,且没有值相同的结点,并释放所有无用结点。限定算法的时间复杂度为O
admin
2019-01-16
44
问题
已知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) {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/WeRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
《共产党宣言》的主要内容不包括()。
阅读材料,回答问题:材料一:战后美国对一些新兴工业部门、重大科研项目、现代化公共设施等投入大量资金,如美国时发展原子能工业的投资,从1945年到1970年共计达175亿美元。美国还通过国家力量来扩张国外市场,从50年代中期起,为加强国际市场的竞争力,政府
简述梭伦改革的主要内容和历史意义。
关于1957年的整风运动,下列不属于其内容的是()。
唐代在广州设立管理对外商务的是()。
试析第三次科学技术革命对人类社会和历史进程的影响。
第一次国共合作采取了共产党员以个人身份加入国民党的“党内合作”方式,最早提出这种方式的是()。
毛泽东提出“政权是由枪杆子中取得的”论段是在()。
()时,为补充兵力,开拓财源,“料民于太原”(今山西西南部)。料民就是清查民数,以便于征兵,结果引起奴隶和平民的反抗。这表明西周王朝已失去了对社会的控制力量。
在一个长度为n(n>1)的带头结点的单链表h上,设有尾指针r(指向尾结点),则执行()操作与链表的长度有关。
随机试题
调经的具体原则中没有
下列哪项不是甘味的作用
某单位新建员互集体宿舍,室内地面标高±0.000m,室外地面标高-0.450m,地上7层,局部8层,一层至七层为标准层,每层建筑面积1200m2,七层屋面面层标高+21.000m,八层为设备用房,建筑面积290m2,八层屋面面层标高+25.000m。根据现
某公司为增值税一般纳税企业,主要生产和销售甲产品,适用增值税税率17%,所得税税率25%,不考虑其他相关税费。该公司2011年发生以下业务。(1)销售甲产品一批,该批产品的成本16万元,销售价格40万元,专用发票注明增值税税额6.8万元,产品已经
货币当局对外汇市场不进行干预,听任汇率随外汇市场的供求变化而自由升跌的汇率制度是()。
提出了教师成长公式“经验+反思=成长”的人是()。
在CSMA/CD协议中,下列指标与冲突时间没有关系的是()。
A.knowingB.sourceC.knowledgeD.consultE.helpF.latestG.unnecessaryH.vitalI.qualitiesJ.switchK.acquain
Thelocaleducationauthoritycompiledalistof"potentialsecurityproblems"oncampuslastweek.Theyincludefireaccidents,
Therearethreetheoriesaboutthebirthofmoon.Inthefirst,themoonisthoughttohaveformed【S1】______inspace,afterwhi
最新回复
(
0
)