首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知3个带头结点的线性链表A、B、C中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点),编写算法对链表A进行如下操作:使操作后的链表A中仅留下3个表中均包含的数据元素的结点,且没有值相同的结点,并释放所有无用结点。限定算法的时间复杂度为O
已知3个带头结点的线性链表A、B、C中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点),编写算法对链表A进行如下操作:使操作后的链表A中仅留下3个表中均包含的数据元素的结点,且没有值相同的结点,并释放所有无用结点。限定算法的时间复杂度为O
admin
2019-08-15
76
问题
已知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
学硕统考专业
相关试题推荐
对1929—1933年的世界经济危机的特点,表述不正确的是()。
三国时期,三国称帝的先后顺序是()。
《中国国民党改组宣言》发表的时间是()。
汉高祖派()出使南越,使得南越王赵佗向汉称臣,实现了汉对南越地区的控制。
某机字长32位,它的存储容量为256MB,按字节编址,则它的寻址范围大小为()。
在一个双链表中,在*p结点之前插入*q结点的操作是()。
一个SPOOUNG系统由输入进程I、用户进程P、输出进程O、输入缓冲区、输出缓冲区组成。进程I通过输入缓冲区为进程P输入数据,进程P的处理结果通过输出缓冲区交给进程O输出。进程间数据交换以等长度的数据块为单位,这些数据块均存储在同一个磁盘上,因此,SPOO
已知一个线性表(38,25,74,63,52,48),表长为16,假定采用散列函数h(key)=key%7,计算散列地址,并存储在散列表中,若采用线性探测方法解决冲突,在该散列表上,进行等概率成功查找的平均查找长度为()。
现有一个解决无向连通图的最小生成树的一种方法如下:将图中所有边按权重从大到小排序为(e1,e2.…,em);i=l;while(所剩边数>=顶点数){从图中删去ei;若图不再连通,则恢复ei;i=i+l;
采用散列函数H(k)===3XkMOD13并用线性探测开放地址法处理冲突,在数列地址空间[0..12]中对关键字序列22,41,53,46,30,13,1,67,51 (1)构造散列表(画示意图); (2)装填因子;
随机试题
函数y=的间断点为________.
去大脑僵直的猫,其主要表现有
不属于大脑半球的分叶是
患儿男,1岁半。发热,咳嗽4天,曾用青霉素肌注治疗无效。昨天起拒食,呕吐,尿量减少。入院查体:体温39.80℃,脉率180次/分,呼吸65次/分。精神萎靡,烦躁不安,口唇发绀,鼻翼扇动,三凹征(+),两肺敞在中小水泡音,肝脏右肋下3cm。血白细胞2.5×l
药学名次“药学服务”翻译成英文是
风险管理的过程不包括( )。
下列会对个人理财业务的发展产生影响的因素有()。
中国古代建筑屋脊上安置戗兽,大致有三个作用()。
两弹一星
丝绸是中国伟大而独特的发明,是中国古老文明的象征。距今有五千多年的历史。在古代中国,丝绸是一种身份的象征,代表着典雅和高贵(nobleness),最早只有帝王才能使用。在古代对外贸易中,丝绸是一种必不可少的高级商品。在现代,丝绸因为其轻薄、柔软、舒适的特点
最新回复
(
0
)