首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知3个带头结点的线性链表A、B、C中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点),编写算法对链表A进行如下操作:使操作后的链表A中仅留下3个表中均包含的数据元素的结点,且没有值相同的结点,并释放所有无用结点。限定算法的时间复杂度为O
已知3个带头结点的线性链表A、B、C中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点),编写算法对链表A进行如下操作:使操作后的链表A中仅留下3个表中均包含的数据元素的结点,且没有值相同的结点,并释放所有无用结点。限定算法的时间复杂度为O
admin
2019-08-01
40
问题
已知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
学硕统考专业
相关试题推荐
洪武八年,朱元璋仿照元朝的办法,印造(),命令民间通行,形成了钱、钞并用的货币制度。
罗马法的集大成《查士丁尼民法大全》产生的时间是在()。
罗斯福新政的中心措施是对()的调整。
西汉的主要赋税形式中,征收对象是儿童的是()。
1941年~1942年,中共在根据地建设中,为争取抗战胜利奠定物质基础的措施是()。
《中国国民党改组宣言》发表的时间是()。
设磁盘的扇区大小为4KB,磁盘转速为15000r/min,磁盘平均寻道时间为4ms,最大数据传输速率为40MB/s,磁盘控制器开销时问为1ms,计算读写一个扇区所需平均时间(不考虑I/O请求队列中的等待时间)。
操作数地址存放在寄存器的寻址方式叫()。
某微程序计算机具有12条微指令v1~V12,每条微指令所包含的微命令信号如表3—4所示。表3—4中,a~n分别对应14种不同的微命令,假设一条微命令长20位,其中操作控制字段为8位,控存容量为1K×20位。要求:采用“不译法”与“分段直接编码法”混
某计算机有8个主设备需要竞争总线的使用权,其设备号为0~7。现欲设计其判优控制方法,试回答下述问题。集中式总线判优控制与分布式总线判优控制的区别是什么?
随机试题
A.肠鸣音亢进B.肠鸣音消失C.金属音D.震水音E.肠鸣音减弱麻痹性肠梗阻可有
也许在很多人看来,有时诚信似乎很傻,很没有意义,因为诚信往往会伴随自身利益的失去。可是,也许下一个因丧失诚信而受害的人,就会是你或你身边的人。或许违约失信可以获得一些蝇头小利,可是当花失去香味时,再美丽的花朵也难逃凋亡的命运。诚信正是如此。诚信是中华民族的
A.theyspentontheirweddingB.ItcanbesmallC.ItreallywasD.Yes,that’strueE.Iwouldn’twantasmallweddingF.Il
下列关于初级卵母细胞描述正确的是哪项
A.公正B.权利C.廉洁奉公D.医德评价E.医患关系属于医学伦理学基本原则的是
下述黏膜组织中,何处无黏膜下层
甲公司委托乙公司购买1台机器,双方约定:乙公司以自己的名义购买机器:机器购买价格为20万元;乙公司的报酬为8000元。双方未约定其他事项。乙公司接受委托后,积极与丙公司交涉协商,最终乙公司以自己的名义从丙公司处购得该种机器1台,价款为19.5万元.乙公司
[2012年第48题]近期国际金融危机对于毕业生的就业影响非常大,某高校就业中心的陈老师希望广大同学能够调整自己的心态和预期。他在一次就业指导会上提出,有些同学对自己的职业定位还不够准确。如果陈老师的陈述为真,则以下哪项不一定为真?Ⅰ.不是所有的人对自
二次型f(x1,x2,x3)=x12+4x22+3x32-4x1x2+2x1x3+8x2x3的秩等于()。
Accordingtothepassage,themassmediapresentuswith______.Whatistheauthor’sfinaljudgmentonhowmasscommunications
最新回复
(
0
)