首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知3个带头结点的线性链表A、B、C中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点),编写算法对链表A进行如下操作:使操作后的链表A中仅留下3个表中均包含的数据元素的结点,且没有值相同的结点,并释放所有无用结点。限定算法的时间复杂度为O
已知3个带头结点的线性链表A、B、C中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点),编写算法对链表A进行如下操作:使操作后的链表A中仅留下3个表中均包含的数据元素的结点,且没有值相同的结点,并释放所有无用结点。限定算法的时间复杂度为O
admin
2019-08-15
20
问题
已知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 i //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一>deLta) //(处理)重复结点不链入链表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表尾 elsef //处理原链表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/jlCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
三国时期,魏、蜀、吴三国灭亡的历史顺序是()。
1918年美国总统威尔逊提出“十四点原则”,内容有“海洋上的航行有绝对自由”、“取消一切经济障碍和确立贸易条件的平等”、“成立一个一般性的各国联合组织”。其最终目的是()。
1870年普鲁士军队侵人巴黎,法国人民组织国民自卫军誓保卫巴黎,参加国民自卫军的大部分是()。
制瓷业是光彩夺目的一个手工业部门,北宋的制瓷业的重心在黄河流域和中原地区。回答问题:北宋的四大名窑是()
隋唐五代时期是中国古代商品经济发展史上的一个重要阶段,种类多,交换规模大,交换方式多。试回答问题:我国银行最早的雏形是唐朝时期出现的()
某32位机(机器字长32位)的一台外设通过32位总线与系统内存相连。CPU每秒执行100条指令,平均每条指令需要5个机器周期,其中3个周期必须访问内存,内存读写需一个机器周期,假定CPU在95%的时间内持续执行“背景程序”,且这段时间内不执行I/O指令。现
在二叉树的顺序存储中,每个结点的存储位置与其父结点、左右子树结点的位置都存在一个简单的映射关系,因此可与三叉链表对应。若某二叉树共有n个结点,采用三叉链表存储时,每个结点的数据域需要d个字节,每个指针域占用4个字节,若采用顺序存储,最后一个结点下标为k(起
已知一个线性表(38,25,74,63,52,48),表长为16,假定采用散列函数h(key)=key%7,计算散列地址,并存储在散列表中,若采用线性探测方法解决冲突,在该散列表上,进行等概率成功查找的平均查找长度为()。
设二维数组A[6][10],每个数组元素占用4个存储单元,若按行优先顺序存放的数组元素,a[0][O]的存储地址为860,则a[3][5]的存储地址为()。
设某计算机系统有一块CPU、一台输入设备、一台打印机。现有两个进程同时进入就绪状态,且进程A先得到CPU运行,进程B后运行。进程A的运行轨迹为:计算50ms,打印信息100ms,再计算50ms,打印信息100ms,结束。进程B的运行轨迹为:计算50ms,输
随机试题
关于颏孔的叙述,下列哪项是正确的()
“诚斋体”指谁的诗()
下列加横线字属于名词作状语的一项是()
A、 B、 C、 D、 D
咽部分为__________、__________和__________三部分。
在生育年龄妇女的卵巢切片中,不容易见到的结构是
维生素是维持动物体正常生理代谢和机能所必需的一类低分子化合物,其作用是其他物质所无法替代的。对钙磷代谢及动物骨骼生长有重要影响的维生素是
以下不属于商业银行资本作用的是()。
从案例分析中,你认为物流企业服务的基本内容有哪些?你认为TNT提供的物流服务对惠普的竞争力而言,其作用体现在哪些方面?
阅读下列说明,回答问题1至问题3,将解答填入对应栏内。【说明】某监理单位承担了某网络工程项目全过程的监理工作。在项目实施过程中,发生了如下事件。事件1:该项目的分项工程之一的机房建设可分解为15个工作(箭头线表示),根据工作的逻辑关系绘出
最新回复
(
0
)