首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知3个带头结点的线性链表A、B、C中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点),编写算法对链表A进行如下操作:使操作后的链表A中仅留下3个表中均包含的数据元素的结点,且没有值相同的结点,并释放所有无用结点。限定算法的时间复杂度为O
已知3个带头结点的线性链表A、B、C中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点),编写算法对链表A进行如下操作:使操作后的链表A中仅留下3个表中均包含的数据元素的结点,且没有值相同的结点,并释放所有无用结点。限定算法的时间复杂度为O
admin
2019-08-01
38
问题
已知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<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->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/f3Ci777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列各组古代民族,其语言都属于印欧语系的是()。
试述明代一条鞭法的主要内容和历史意义。
迈锡尼文明使用的文字是
中国共产党主张和平解决西安事变的主要目的是()。
阅读下面史料,回答问题:材料一各缔约国主力舰替换总吨位按照标准排水量计算不得超过如下:合众国525000吨;英帝国525000吨;法国175000吨;意大利175000吨;日本315000吨。
1941年~1942年,中共在根据地建设中,为争取抗战胜利奠定物质基础的措施是()。
(1)页面长度为1KB=210B,因此页内偏移地址占10位。主存大小为16KB=214B,所以物理地址占14位。0AC5H=0000101011000101B,除去后10位,得到页号为2,则查找页表可知物理块号为4,所以物理地址是0100101100
编写判定给定的二叉树是否是二叉排序树的函数。
关于死锁的银行家算法是围绕“安全状态”的概念工作的。当系统预测到不安全状态时,就拒绝分配资源,但是,银行家算法要求的条件并不是必要的。例如,某系统有12个资源供进程P0、P1、P2使用。目前的分配情况如下:(1)请说明系统处于不安全状态;(2
计算机系统中存储器为何采用分级结构?
随机试题
按照规定,必须报国务院批准的有【】
患儿,2岁。生长发育落后,生后3个月出现发绀、哭闹,活动后发绀加重,有杵状指。医生考虑该患儿为法洛四联症,为确诊首选的检查是
下列哪些情形国家应当承担赔偿责任?()
根据工程建设过程,生态影响类项目环保验收调查时段一般分为()时段。
下列关于塑料格栅和玻纤网的不同点的叙述中,正确的是()。
四岁儿童显著的心理特征有()。
战国时期,首先变法的是()。
符号互动论的基本假设不包括()。
人类社会发展的一般规律决定了社会形态的更替和历史发展的基本趋势。但是,由于社会发展的复杂性和曲折性,社会形态更替在遵循一般规律的同时,也会表现出一些特殊的形式。具体体现在
Eachone____________________(满足不同的观众的需求)whilebothhaveastrongfollowingfromlargegroupsoffans.
最新回复
(
0
)