首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知3个带头结点的线性链表A、B、C中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点),编写算法对链表A进行如下操作:使操作后的链表A中仅留下3个表中均包含的数据元素的结点,且没有值相同的结点,并释放所有无用结点。限定算法的时间复杂度为O
已知3个带头结点的线性链表A、B、C中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点),编写算法对链表A进行如下操作:使操作后的链表A中仅留下3个表中均包含的数据元素的结点,且没有值相同的结点,并释放所有无用结点。限定算法的时间复杂度为O
admin
2019-01-16
34
问题
已知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
学硕统考专业
相关试题推荐
下列属于克里斯提尼改革内容的是()。
秦统一过程中,最先和最后灭掉的国家是()。
阅读史料回答以下问题:天既哀大地生人之多艰,黑帝乃降精而救民患,为神明,为圣王,为万世作师,为万民作保,为大地教主。生于乱世,乃据乱世而立三世之法,而垂精太平。乃因其所生之国,而立三世之义,而注意于大地远近、大小若一之大一统。乃立元以统天,以天为
试析第三次科学技术革命对人类社会和历史进程的影响。
周王室的两大官僚系统是()。
晚清时期清帝年号的正确排序是
()时,为补充兵力,开拓财源,“料民于太原”(今山西西南部)。料民就是清查民数,以便于征兵,结果引起奴隶和平民的反抗。这表明西周王朝已失去了对社会的控制力量。
编写判定给定的二叉树是否是二叉排序树的函数。
写出单总线结构计算机中指令MOVER1,R2(含义是将寄存器R1中内容写入寄存器R2中)的操作步骤。
下图是三个计算机局域网A,B和C,分别包含10台,8台和5台计算机,通过路由器互联,并通过该路由器接口d联入因特网。路由器各端口名分别为a、b、c和d(假设端口d接入IP地址为61.60.21.80的互联网地址)。LANA和LANB公用一个C类IP地址
随机试题
以科学发展为主题,以加快转变经济发展方式为主线,是关系我国发展全局的战略抉择。加快转变经济发展的实质就是要()
子宫峡部在妊娠晚期可以扩张到
A.滑石B.车前子C.萹蓄D.木通E.栀子三仁汤的组成中包含的药物是()
A.丹参饮B.通窍活血汤C.参附龙牡汤加味D.瓜蒌薤白半夏汤E.乌头赤石脂丸合苏合香丸
男,20岁。左侧阴囊有坠胀感,站立时患侧阴囊及睾丸低于右侧,阴囊表面可见扩张、迂曲之静脉。医师查体见阴囊有蚯蚓团状软性包块,平卧可使症状减轻或消失。进行精索静脉曲张术后,恢复良好,拆线时间应为术后()
根据党的十九大报告内容,下列有关新时代党的建设总要求的说法错误的是:
设a是常数,则级数()
【B1】【B19】
WhatdoesHelenthinkaboutthebooksonJeremy’sreadinglist?ChooseFOURanswersfromtheboxandwritethecorrectletter,A
BorninNorthCarolinain1862,WilliamSidneyPorter,thismasterofshortstoriesismuchbetterknownunderhispenname"O.
最新回复
(
0
)