用C++,设有两条有序链表(即 data 域元素的关键字由前往后不断增大),试设计算法,将这两 条链表合并为一条新的有序链表,原链表不变。两条链表中 data 域关键字相同的元素只选 取一个存储到新的有序链表中,不同的元素都存储到新的有序链表中。 要求: ➢ 直接编写链表的友元函数完成该功能。 ➢ 链表的 data 域可存储用户自定义类对象。 ➢ 编写测试 main()函数测试线性表的正确性
时间: 2023-05-30 15:03:37 浏览: 36
假设有两个有序链表A和B,我们可以按照以下步骤将它们合并为一个新的有序链表C:
1. 创建一个新的空链表C。
2. 定义三个指针:pA指向链表A的头结点,pB指向链表B的头结点,pC指向链表C的头结点。
3. 依次比较pA和pB指向的节点的data域大小,将较小的节点插入到链表C的末尾,并将指针pC指向新的节点。
4. 如果pA或pB指向的节点为空,将另一个链表的剩余节点直接插入到链表C的末尾。
5. 返回链表C的头结点。
以下是完整的代码实现:
#include<iostream>
using namespace std;
template<typename T>
class Node{
public:
T data;
Node<T> *next;
Node(T d=0,Node<T> *n=NULL):data(d),next(n){}
};
template<typename T>
class LinkedList{
public:
LinkedList():head(NULL){}
~LinkedList();
void insert(T d);
void print();
friend LinkedList<T> merge(LinkedList<T>& A, LinkedList<T>& B){
LinkedList<T> C;
Node<T>* pA=A.head,*pB=B.head,*pC=C.head;
while(pA&&pB){
if(pA->data<pB->data){
if(!pC){
C.head=pC=new Node<T>(pA->data);
}else{
pC->next=new Node<T>(pA->data);
pC=pC->next;
}
pA=pA->next;
}else if(pA->data>pB->data){
if(!pC){
C.head=pC=new Node<T>(pB->data);
}else{
pC->next=new Node<T>(pB->data);
pC=pC->next;
}
pB=pB->next;
}else{
if(!pC){
C.head=pC=new Node<T>(pA->data);
}else{
pC->next=new Node<T>(pA->data);
pC=pC->next;
}
pA=pA->next;
pB=pB->next;
}
}
if(pA){
if(!pC){
C.head=pA;
}else{
pC->next=pA;
}
}else if(pB){
if(!pC){
C.head=pB;
}else{
pC->next=pB;
}
}
return C;
}
private:
Node<T> *head;
};
template<typename T>
LinkedList<T>::~LinkedList(){
Node<T> *p=head,*q;
while(p){
q=p->next;
delete p;
p=q;
}
}
template<typename T>
void LinkedList<T>::insert(T d){
if(!head){
head=new Node<T>(d);
}else{
Node<T> *p=head;
while(p->next){
p=p->next;
}
p->next=new Node<T>(d);
}
}
template<typename T>
void LinkedList<T>::print(){
Node<T> *p=head;
while(p){
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
}
int main(){
LinkedList<int> A,B;
A.insert(1);
A.insert(3);
A.insert(5);
A.insert(7);
B.insert(2);
B.insert(4);
B.insert(6);
B.insert(8);
LinkedList<int> C=merge(A,B);
C.print();
return 0;
}
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)