首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知3个带头结点的线性链表A、B、C中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点),编写算法对链表A进行如下操作:使操作后的链表A中仅留下3个表中均包含的数据元素的结点,且没有值相同的结点,并释放所有无用结点。限定算法的时间复杂度为O
已知3个带头结点的线性链表A、B、C中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点),编写算法对链表A进行如下操作:使操作后的链表A中仅留下3个表中均包含的数据元素的结点,且没有值相同的结点,并释放所有无用结点。限定算法的时间复杂度为O
admin
2019-01-16
41
问题
已知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
学硕统考专业
相关试题推荐
1856年首创转炉炼钢新技术的是()。
真理标准问题大讨论
材料一1870年代初的南部,虽然也不时出现针对黑人的种族暴行,但在日常生活中,黑人基本能与白人同车船、共饭桌、游公园。但这种情况并没有持续多久。随着前白人奴隶主“重新夺回”南部各州政权,许多州在维护社会秩序名义下,制定了各种法律,规定黑人与白人必
有关斯巴达国家建立传说的社会改革是()。
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
下列的网络协议中,()的运输层协议是使用TCP的。
系统总线中地址线的功能是用于选择()。
假定某采用页式虚拟存储管理的计算机系统中,主存储器容量为1GB,被分为262144块物理块,物理块号为0,1,2,……,262143。某进程的地址空间占4页,逻辑页号为0,1,2,3,被分配到主存储器的第20,45,101,58号物理块中。回答:
设有两个子网202.118.133.0/24和202.118.130.0/24,如果进行路由汇聚,得到的网络地址是()。
CISC与RISC的区别表现在()。
随机试题
TheRedCrossis【B1】______organizationwhichcaresforpeoplewhoarein【B2】______ofhelp.AmaninaParishospitalwhonee
资产评估中,某项资产的最大最优用途是指()。
近年来.我国在国际事务中发挥着越来越重要的作用。多边外交力度明显加大。我国对外交往的根本准则是()。
对精神病人应当采取约束。()
孔子特别强调做事情的分寸,“过”和“不及”都是要尽力避免的。孔子提倡仁爱,但他并不认为应当以丧失原则的仁爱之心宽宥所有人的过失。有人问他:“以德报怨,何如?”孔子的回答是:“以直报怨,以德报德。”与这段文字文意不相符的是()。
下列属于互动式的支架的是()。
[*]
以下说法中正确的是( )。
Accordingtoonespeaker,wecouldskip______ifweareshortoftime.
Theageofrequiringretirementincompaniesshouldberaised,andso【M1】______shouldtheagetobeginSocialSecurity.First
最新回复
(
0
)