首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知3个带头结点的线性链表A、B、C中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点),编写算法对链表A进行如下操作:使操作后的链表A中仅留下3个表中均包含的数据元素的结点,且没有值相同的结点,并释放所有无用结点。限定算法的时间复杂度为O
已知3个带头结点的线性链表A、B、C中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点),编写算法对链表A进行如下操作:使操作后的链表A中仅留下3个表中均包含的数据元素的结点,且没有值相同的结点,并释放所有无用结点。限定算法的时间复杂度为O
admin
2019-01-16
21
问题
已知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
学硕统考专业
相关试题推荐
唐朝官营手工业中,每年服役二十天,在政府“趋役不尽及别有和雇”的情况下,可“纳资代役”的是()。
论述赫鲁晓夫改革的背景、主要内容及作用。
简述路德“唯信称义”与加尔文“预定论”的关系与区别。
基辅罗斯国家对居民征税的方式是()。
1984年,《中共中央关于经济体制改革的决定》中强调,商品经济的充分发展是社会经济发展不可逾越的阶段,市场调节的辅助性作用不可缺少,并指出要有步骤地逐步缩小指令性计划的范围。这表明当时我国()
下列著作被人们称为17世纪物理学、数学的百科全书,并标志着经典力学体系的完成的是()。
西汉的主要赋税形式中,征收对象是儿童的是()。
格拉古兄弟改革
[*]对应的微指令如下:ADD01XX1010000010XX10010000XX1001001001MOV00XX10100010XX1101001001
给定序列{3,5,7,9,11,13,15,17),(1)按表中元素的顺序依次插入一棵初始为空的二叉排序树,画出插入完成后的二叉排序树,并求在等概率情况下查找成功的平均查找长度。(2)按表中元素的顺序构造一棵平衡二叉树,并求其在等概率情
随机试题
只属于纸质图书数字化加工环节的是()。
A.高血压病B.脑静脉畸形C.脑动脉瘤D.长骨骨折E.风湿性心脏病脑出血最常见的原因是
食后脘腹胀满,朝食暮吐,暮食朝吐,吐出宿谷不化,吐后即觉舒适,神疲乏力,面色少华,舌淡苔薄,脉细无力。应诊为
复式记账的基本理论依据是资产=负债+所有者权益。( )
以下事项中,决定资产评估价值的最主要因素是( )。
保险产品的功能主要有()。
我国的商业银行全部都是国有和由国家参股的银行。()
净现值法的优点有()。
《中华人民共和国教育法》第七十九条规定,在国家教育考试中作弊的,有权宣布考试无效的机构是()。
某LinuxDHCP服务器dhepd.conf的配置文件如下:ddns-update-stylenone;subnet192.168.0.0netmask255.255.255.0{range192.168.0.200192.168.0.254:i
最新回复
(
0
)