首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知3个带头结点的线性链表A、B、C中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点),编写算法对链表A进行如下操作:使操作后的链表A中仅留下3个表中均包含的数据元素的结点,且没有值相同的结点,并释放所有无用结点。限定算法的时间复杂度为O
已知3个带头结点的线性链表A、B、C中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点),编写算法对链表A进行如下操作:使操作后的链表A中仅留下3个表中均包含的数据元素的结点,且没有值相同的结点,并释放所有无用结点。限定算法的时间复杂度为O
admin
2019-08-01
64
问题
已知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
学硕统考专业
相关试题推荐
日本关东军认为()事件是军事干涉东北的最好借口。日本驻沈阳总领事林久治郎向辽宁省政府提出正式抗议。
试述明代一条鞭法的主要内容和历史意义。
院系调整
下列长征事件的正确顺序是()。 ①四渡赤水②召开遵义会议③吴起镇会师④飞夺泸定桥
“瓜步之战”发生在下列哪两个政权之间?()
1854年,英国外交大臣致函英国驻华公使说:“为了适应外商对农业产品已增加了的需要,新的贸易市场尚待开辟。”1856年,法国外长则指令法国驻华代办强调“商业关系的推广”,并强调“这是一个关系到至高无上权益的问题”。这说明()。
从“鲁尔危机”的发生到《道威斯计划》的实施,西方国际关系变化对当时有关国家的影响是()。①美国势力进一步向欧洲渗透②英国达到了限制法国、保持均势的目的③德国获得重建经济的有利时机④法国扩充实力争霸欧洲的计划遭
以下()协议完成了从网卡到IP地址的映射。
已知4位有效信息为1010,试根据下列要求进行编码。(1)按配偶原则将其编码为扩展的海明码,要求能发现两位错并纠正一位错。(2)将其编码为循环冗余校验码,生成多项式G(x)=1011。
采用散列函数H(k)=3×kMOD13并用线性探测开放地址法处理冲突,在数列地址空间[0..12]中对关键字序列22,41,53,46,30,13,1,67,51;(1)构造散列表(画示意图);(2)装填因子;(3)等概
随机试题
A.茵陈蒿汤B.茵陈五苓散C.茵陈术附汤D.鳖甲煎丸E.逍遥散治疗阳黄湿重于热,应首选()
适用《联合国国际货物销售合同公约》的情况是【】
不属于二氢吡啶类药物鉴别反应的是
胃脘痛如针刺,痛处固定不移,属于胃脘疼痛,喜温恶冷,属于
经营者进行价格活动,应当遵循法律、法规,执行( )。经营者不得( )。
关于清末变法修律,下列哪些选项是正确的?(卷一/2011年第57题)
票据的基本当事人包括()。
丕平献土
[说明]某政府机关的电子政务一期工程包括网络平台建设和应用系统开发,通过公开招标,确定工程的总承建单位是公司A。A公司自行决定,将其中一部分核心软件开发工作分包给其下属公司B,而公司B又将部分软件开发工作分包给了公司C。
Thevoluntarydecisiontolabelseemstohavebeenrewarded.
最新回复
(
0
)