首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知3个带头结点的线性链表A、B、C中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点),编写算法对链表A进行如下操作:使操作后的链表A中仅留下3个表中均包含的数据元素的结点,且没有值相同的结点,并释放所有无用结点。限定算法的时间复杂度为O
已知3个带头结点的线性链表A、B、C中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点),编写算法对链表A进行如下操作:使操作后的链表A中仅留下3个表中均包含的数据元素的结点,且没有值相同的结点,并释放所有无用结点。限定算法的时间复杂度为O
admin
2019-01-16
53
问题
已知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
学硕统考专业
相关试题推荐
唐代在广州设立管理对外商务的是()。
春秋战国时期,提出“祸兮福之所倚,福兮祸之所伏”的思想家是()。
阅读材料,回答以下问题:一、大清帝国之皇统,万世不易。二、皇帝神圣,不可侵犯。三、皇帝权以宪法规定为限。四、皇帝继承之顺序,于宪法规定之。五、宪法由资政院起草议决,皇帝颁布之。六、宪政改正提案权,属于国会。七、上院议员,由国民于法定特别资格公选之。八、总
根据下列史料,说明朝鲜社会性质发生了怎样的变化。第四款朝鲜釜山之草粱项设有日本公馆,久为两国人民通商之地。从今日起,改革从前惯例及岁遣船等事,以此次新订条款为标准,办理贸易事务,朝鲜政府开放第五款所载两口岸,准日本人民往来通商,随意在该两地租借地
雍正帝为了证明清朝统治的合理性以及自己即位的合法性,颁布了()。
以下()协议完成了从网卡到IP地址的映射。
某系统中n个相互独立的生产者进程为一个消费者进程提供数据,假设每个生产者提供的数据写入各不相同的缓冲区,且生产者写缓冲区的速度比消费者读缓冲区的速度快,则缓冲区个数的最优值应为()。
某机字长32位,总线数据线宽度是16位,一个总线周期占用4个时钟周期,总线时钟频率为10MHz,则总线带宽是()。
某中央处理器的数据通路如图所示。MDR为内存数据寄存器,PC为程序计数器,IR为指令寄存器。所有的单线箭头为控制微命令。(1)请说明图中部件X的名称和功能、寄存器Y的名称和功能。(2)请解释:为什么要设置T暂存器?(3)假定指
下图所示为双总线结构机器的数据通路,IR为指令寄存器,PC为程序计数器(具有自增功能),M为主存(受R/W信号控制),AR为地址寄存器,DR为数据缓冲寄存器,ALU由加、减控制信号决定完成何种操作,控制信号G控制的是一个门电路。另外,线上标注有小圈表示有控
随机试题
血中哪一种激素出现高峰可作为排卵的标志【】
呼吸基本节律产生于
气随血脱者为气不摄血者为
采用科目汇总表账务处理程序,()是其登记总分类账的直接依据。
《中国共产党历史》一书中写道:“通过这次会议,新中国初步打破美国的孤立和遏制政策,拓展了国际和平统一战线,为国内建设创造了有利的周边环境。”这次会议指的是()。
下列选项中,不是“百日维新”中的教育改革活动的是
Charles:Whattimeareyouleaving?Brown:I’mgoingtotrytoleaveby10:00.Charles:Takecareand______.Brown:Goodbye.Hope
以下关于通用对话框的叙述中,错误的是
Specialisationcanbeseenasaresponsetotheproblemofanincreasingaccumulationofscientificknowledge.Bysplittingupt
Lookatthestatementsbelowandthetextaboutsomestrategiescompaniescanusetostaycompetitiveontheoppositepage.
最新回复
(
0
)