2. 考研
  3. 已知3个带头结点的线性链表A、B、C中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点)，编写算法对链表A进行如下操作：使操作后的链表A中仅留下3个表中均包含的数据元素的结点，且没有值相同的结点，并释放所有无用结点。限定算法的时间复杂度为O

已知3个带头结点的线性链表A、B、C中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点)，编写算法对链表A进行如下操作：使操作后的链表A中仅留下3个表中均包含的数据元素的结点，且没有值相同的结点，并释放所有无用结点。限定算法的时间复杂度为O

admin2019-01-16  50
问题 已知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一>datadata){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一>datadata)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://www.kaotiyun.com/show/sYRi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)