用C++,设有两条有序链表(即 data 域元素的关键字由前往后不断增大),试设计算法,将这两 条链表合并为一条新的有序链表,原链表不变。两条链表中 data 域关键字相同的元素只选 取一个存储到新的有序链表中,不同的元素都存储到新的有序链表中。 要求: ➢ 直接编写链表的友元函数完成该功能。 ➢ 链表的 data 域可存储用户自定义类对象。 ➢ 编写测试 main()函数测试线性表的正确性
时间: 2023-05-29 20:06:22 浏览: 37
//定义链表节点类
class Node{
public:
Node(int data){m_data = data; m_next = NULL;}
int m_data;//数据域
Node* m_next;//指针域
};
//定义链表类
class List{
public:
List(){m_head = NULL;}//构造函数
void add(int data);//添加节点
void print();//打印链表
friend List merge(List& list1, List& list2);//友元函数,合并两个链表
private:
Node* m_head;//头节点指针
};
//添加节点
void List::add(int data){
Node* node = new Node(data);//创建新节点
if(m_head == NULL){//链表为空
m_head = node;
}else{//链表不为空
Node* p = m_head;
while(p->m_next != NULL){//遍历到最后一个节点
p = p->m_next;
}
p->m_next = node;//将新节点添加到最后一个节点的后面
}
}
//打印链表
void List::print(){
Node* p = m_head;
while(p != NULL){
cout << p->m_data << " ";
p = p->m_next;
}
cout << endl;
}
//合并两个链表
List merge(List& list1, List& list2){
List result;//创建新链表
Node* p1 = list1.m_head;
Node* p2 = list2.m_head;
while(p1 != NULL && p2 != NULL){
if(p1->m_data < p2->m_data){//将较小值添加到新链表中
result.add(p1->m_data);
p1 = p1->m_next;//指向下一个节点
}else if(p1->m_data > p2->m_data){
result.add(p2->m_data);
p2 = p2->m_next;
}else{
result.add(p1->m_data);
p1 = p1->m_next;
p2 = p2->m_next;
}
}
//将剩余的节点添加到新链表中
while(p1 != NULL){
result.add(p1->m_data);
p1 = p1->m_next;
}
while(p2 != NULL){
result.add(p2->m_data);
p2 = p2->m_next;
}
return result;//返回新链表
}
int main(){
List list1;
list1.add(1);
list1.add(3);
list1.add(5);
List list2;
list2.add(2);
list2.add(4);
list2.add(6);
List result = merge(list1, list2);
result.print();//打印新链表
list1.print();//打印原链表1
list2.print();//打印原链表2
return 0;
}
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![apk](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)