首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知3个带头结点的线性链表A、B、C中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点),编写算法对链表A进行如下操作:使操作后的链表A中仅留下3个表中均包含的数据元素的结点,且没有值相同的结点,并释放所有无用结点。限定算法的时间复杂度为O
已知3个带头结点的线性链表A、B、C中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点),编写算法对链表A进行如下操作:使操作后的链表A中仅留下3个表中均包含的数据元素的结点,且没有值相同的结点,并释放所有无用结点。限定算法的时间复杂度为O
admin
2017-11-14
79
问题
已知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) f pre->next=pa;pre=pa;pa=pa一>next;} //结果表中第一个结点 else if(pre一>data==pa一>data) //(处理)重复结点不链入链表A {n=pa;pa=pa一>next;free(n);} 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/e3Ri777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
1956年,苏共二十大后,匈牙利大党员和群众强烈要求克服个人崇拜,扩大民主,实行经济改革,一些由知识分子、大学生和干部组成的社团组织纷纷成立,其中最有影响者是()。
苏联“十四大”、“十五大”后经济建设的核心内容是()
与前两次工业革命相比,第三次科技革命在能源结构上的主要变化是()
1925年爆发的当时世界上罢工时间最长的一次斗争是()。
19世纪中期,德意志资产阶级迫切要求实现国家的统一,其首要的目的是()。
1534年英国议会宣布英国教会断绝与罗马教廷一切关系的文件是()。
某系统中n个相互独立的生产者进程为一个消费者进程提供数据,假设每个生产者提供的数据写入各不相同的缓冲区,且生产者写缓冲区的速度比消费者读缓冲区的速度快,则缓冲区个数的最优值应为()。
一棵:BS’r树共7个结点,值分别为1、2、3、4、5、6、7,形态为满二叉树,()不是插入序列。
在采用线性探测法处理冲突所构成的散列表上进行查找,可能要探测多个位置,在查找成功的情况下,所探测的这些位置的键值()。
随机试题
显示溶血存在的检验是
下列哪项不属于《金匮要略》所述的四饮范畴:
禁用于高钾血症病人的利尿药是()
关于已设定的行政许可的评价,下列哪些说法是正确的?()
下列选项中不宜采用自耦变压器的情况有哪些?
关于单代号绘制的基本规则的说法,错误的是()
下列有关存货会计处理的表述中,正确的有()。
资料1某公司2009~2015年的D产品销售量资料如下:资料2:D产品设计生产能力为4000吨,计划生产3300吨,预计单位产品的变动成本为200元,计划期的固定成本费用总额为123750元,该产品适用的消费税税率为5%,计划成本利润率必须达到25%
张先生,男,35岁,干部。身高180cm,体重76公斤,胸围136cm。请计算张先生午餐需要碳水化合物()。
下列关于归责与免责的说法,正确的是()。
最新回复
(
0
)