首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知3个带头结点的线性链表A、B、C中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点),编写算法对链表A进行如下操作:使操作后的链表A中仅留下3个表中均包含的数据元素的结点,且没有值相同的结点,并释放所有无用结点。限定算法的时间复杂度为O
已知3个带头结点的线性链表A、B、C中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点),编写算法对链表A进行如下操作:使操作后的链表A中仅留下3个表中均包含的数据元素的结点,且没有值相同的结点,并释放所有无用结点。限定算法的时间复杂度为O
admin
2019-08-15
46
问题
已知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 i //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一>deLta) //(处理)重复结点不链入链表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表尾 elsef //处理原链表A未到尾而链表B或链表C到尾的情况 pre->next=null: //置链表A表尾标记 while(pa!=null){U=pa;pa=pa一>next;free(u);} //删除原链表A剩余元素 } } } } 提示:留下3个链表中的公共数据,首先查找链表A和链表B中公共数据,再去链表C中找有无该数据。要消除重复元素,应记住前驱,要求时间复杂度为O(m+n+p),在查找每个链表时,指针不能回溯。 算法实现时,链表A、链表B和链表C均从头到尾(严格地说链表B、链表C中最多一个到尾)遍历一遍,算法时间复杂度符合O(m+n+p)。算法主要有while(pa&&pb&&p)。
解析
转载请注明原文地址:https://kaotiyun.com/show/jlCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
书院制度,始于唐而盛于宋,根据所学知识。回答问题:南宋书院的复起,是由朱熹开始的。他重建白鹿洞书院,亲自到书院讲学,还亲手制定()
宗教问题已成为某些国家和地区之间冲突的主要原因。信仰“真主”安拉,以《古兰经》为经典的宗教是()
1946年3月5日,英国前首相丘吉尔在富尔敦发表了(),发出第一个明白无误的“冷战”信号。
某计算机有8个主设备需要竞争总线的使用权,其设备号为0~7。现欲设计其判优控制方法,试回答下述问题。(1)集中式总线判优控制与分布式总线判优控制的区别是什么?(2)若采用集中式判优控制,则在链式查询、计数器定时查询和独立请求三种方式下,
一棵:BS’r树共7个结点,值分别为1、2、3、4、5、6、7,形态为满二叉树,()不是插入序列。
在一个按字节编址的计算机中,若数据在存储器中以小端方案存放。假定int型变量i的地址为08000000H,i的机器数为01234567H,地址:08000000H单元的内容是()。
现代操作系统中,文件系统都有效地解决了重名问题,允许不同的文件可以有相同的文件名。那么,实现该功能的主要方法是()。
浮点数加、减运算过程一般包括对阶、尾数运算、规格化、舍入和判溢出等步骤。设浮点数的阶码和尾数均采用补码表示,且位数分别为5位和7位(均含2位符号位)。若有两个数x=27×29/32,Y=25×5/8,则用浮点加法计算x+Y的最终结果是____。
图1-2是某存储芯片的引脚图,请回答:(1)这个存储芯片的类型(是RAM还是ROM)?这个存储芯片的容量?(2)若地址线增加一根,存储芯片的容量将变为多少?(3)这个芯片是否需要刷新?为什么?刷新和重写有什么区别?(
生成多项式为x3+x+1,则数据信息10101的CRC编码是()。
随机试题
急性有机磷中毒的患者,医嘱给予阿托品静脉注射,在给药后患者最可能出现
制备黑膏药时,乳香、没药应在哪道工序中加入
药品零售企业的特殊性表现在( )。
患者女,65岁。有高血压病史10年。最近稍事活动即出现胸闷、心悸、气急症状,该患者的心功能为()
患者,男性,68岁。高血压8年,冠心病心绞痛3年,血脂一直偏高,近1个月心前区疼痛发作频繁,含服硝酸甘油效果欠佳。今日与人发生争吵时,胸痛20分钟不缓解,伴大汗,急诊入院。责任护士通过病史护理评估后,应考虑患者可能的重要病情变化是
属于客观资料的是
某大型工业项目的主厂房工程,发包人通过公开招标选定了承包人,并依据招标文件和投标文件,与承包人签订了施工合同。合同中部分内容如下所述。(1)合同工期160天,承包人编制的初始网络进度计划,如图3—1所示。由于施工工艺要求,该计划中C、E、I三项工作施
诉讼时效是从( )之日起计算。
下表为中国某一时期制定和修改的法律。制定和修改这些法律的主要目的是()。
—What’s______populationofChina?—AsfarasIknow,Chinahas______populationofabout1.3billion.
最新回复
(
0
)