首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知3个带头结点的线性链表A、B、C中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点),编写算法对链表A进行如下操作:使操作后的链表A中仅留下3个表中均包含的数据元素的结点,且没有值相同的结点,并释放所有无用结点。限定算法的时间复杂度为O
已知3个带头结点的线性链表A、B、C中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点),编写算法对链表A进行如下操作:使操作后的链表A中仅留下3个表中均包含的数据元素的结点,且没有值相同的结点,并释放所有无用结点。限定算法的时间复杂度为O
admin
2019-01-16
49
问题
已知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剩余元素 } } } } 提示:留下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/sYRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
林则徐的反英国侵略的策略思想不包括()。
《共产党宣言》的主要内容不包括()。
阅读材料,回答问题:材料一:战后美国对一些新兴工业部门、重大科研项目、现代化公共设施等投入大量资金,如美国时发展原子能工业的投资,从1945年到1970年共计达175亿美元。美国还通过国家力量来扩张国外市场,从50年代中期起,为加强国际市场的竞争力,政府
《关于建国以来党的若干历史问题的决议》
简述路德“唯信称义”与加尔文“预定论”的关系与区别。
下列关于隋唐时期货币表述准确的是()。①隋朝使用五铢钱②开元年间开始统一使用开元通宝③开元通宝是唐朝的通用货币④开元通宝是唐代以后历代王朝货币的范式
格拉古兄弟改革
某计算机采用微程序控制方式,微指令字长32位,采用字段直接编码的控制方式,共有55个微命令,可分为6个互斥组,分别包含1、3、7、8、12、24个微命令。另外,该机共有5个可判定的外部条件,采用断定方式形成后续微指令地址。(1)设计该机微指令的格式,
下图所示为双总线结构机器的数据通路,IR为指令寄存器,PC为程序计数器(具有自增功能),M为主存(受R/W信号控制),AR为地址寄存器,DR为数据缓冲寄存器,ALU由加、减控制信号决定完成何种操作,控制信号G控制的是一个门电路。另外,线上标注有小圈表示有控
系统总线中地址线的功能是用于选择()。
随机试题
糖尿病合并中度肾功能不全时应选用的降糖药为
下列哪项提示无排卵
在常规格式下,在Excel单元格中输入3/4,则单元格中的数据为()。
下列各项中,属于检查性控制的有()。
一列火车的车身长800米,行驶的速度是每小时60千米,铁路上有两座隧洞且长度相等。火车从车头进入第一个隧洞到车尾离开第一个隧洞用2分钟,从车头进入第一个隧洞到车尾离开第二个隧洞共用6分钟。两座隧洞之间相距多少千米?()
完成全面建成小康社会和实现现代化的历史性任务,重点和难点都在()。
发生重大突发事件时,根据安全第一的原则,首先应考虑将现场人员疏散至安全区域,以免造成更大的人员伤亡。以下关于火灾安全疏散的建议,错误的是()。
A、B、C三人从法学院毕业后,一人去了律师事务所,一人去了法院,一人去了检察院。甲、乙、丙三人做了以下猜测:甲:“A去了律师事务所,B去了法院。”乙:“A去了法院,C去了律师事务所。”丙:“A去了检察院,B去了律师事务所。”如果甲、乙、丙三人的猜测都只对了
AspartofeffortstoreduceilliteracyandpromoteEducationForAll(EFA)goals,theLagosStateAgencyforMassEducationha
WhatarethetwoseasoningsusedbymostAmericans?
最新回复
(
0
)