2. 考研
  3. 已知一个线性表，其中的数据元素类型均为整型。现有两个单链表La和Lb，其中La只能存储偶数而Lb只能存储奇数。现想利用La和Lb来存储此线性表。请完成以下问题： (1)给出算法的主要思想； (2)写出算法的实现函数； (3)总结所用算法的时间和

已知一个线性表，其中的数据元素类型均为整型。现有两个单链表La和Lb，其中La只能存储偶数而Lb只能存储奇数。现想利用La和Lb来存储此线性表。请完成以下问题： (1)给出算法的主要思想； (2)写出算法的实现函数； (3)总结所用算法的时间和

admin2014-07-18  80
问题 已知一个线性表，其中的数据元素类型均为整型。现有两个单链表La和Lb，其中La只能存储偶数而Lb只能存储奇数。现想利用La和Lb来存储此线性表。请完成以下问题：
  (1)给出算法的主要思想；
  (2)写出算法的实现函数；
  (3)总结所用算法的时间和空间复杂度。
选项
答案(1)依次遍历线性表，如果线性表中的数据是偶数则插入La中，如果是奇数，那么就插入Lb中。 (2)算法的函数如下： void decompose(LinkList&L，LinkList&La，LinkList &Lb) ／／含头结点 { LNode*p，*q； p=L->next； La=L： La->next=La： Lb->next=Lb；／／空的循环链表 while(p!=NULL){ q=p->ilext； if(p->data％2==0){／／偶数则插入La中 p->next=La->next； La->next=p； }else{／／奇数则插入Lb中 p->next=Lb->next； Lb->next=p； } p=q； } } (3)遍历链表的时间复杂度为O(n)，算法实现过程中使用的辅助空间为常量，空间复杂度为O(1)。
解析
转载请注明原文地址:https://www.kaotiyun.com/show/taxi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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