实验11_9_链表归并
时间: 2023-11-11 10:04:31 浏览: 71
链表归并是指将两个有序链表合并成一个有序链表的过程。实验11_9的目的是通过链表归并的实现,加深对链表操作的理解和应用。
具体实现步骤如下:
1. 定义一个链表结构体Node,包含一个整型数据域和一个指向下一个节点的指针域。
2. 定义一个链表归并函数merge,输入参数为两个链表的头节点指针head1和head2,输出参数为归并后的链表头节点指针head3。
3. 在merge函数内部,定义一个临时节点指针p,将其指向头节点较小的那个链表的头节点,将头节点较大的那个链表的头节点赋值给head3。
4. 在while循环中,判断p的指针域是否为空,如果为空,则将p的指针域指向头节点较大的那个链表的头节点,并将该链表的头节点指针head3赋值给p。
5. 在while循环中,判断p所指向的节点的数据域与另一个链表头节点的数据域的大小关系,将p的指针域指向数据域较小的节点。
6. 在while循环结束后,将剩余的节点直接接到归并后的链表尾部。
完整代码如下:
```
#include<iostream>
using namespace std;
struct Node{
int data;
Node* next;
};
Node* merge(Node* head1,Node* head2){
if(head1==NULL) return head2;
if(head2==NULL) return head1;
Node* head3=NULL;
Node* p=NULL;
if(head1->data<head2->data){
p=head1;
head1=head1->next;
}
else{
p=head2;
head2=head2->next;
}
head3=p;
while(head1!=NULL&&head2!=NULL){
if(head1->data<head2->data){
p->next=head1;
head1=head1->next;
}
else{
p->next=head2;
head2=head2->next;
}
p=p->next;
}
if(head1!=NULL) p->next=head1;
if(head2!=NULL) p->next=head2;
return head3;
}
int main(){
Node* head1=new Node;
Node* head2=new Node;
Node* p1=head1;
Node* p2=head2;
int n,m;
cout<<"请输入第一个链表的长度:";
cin>>n;
cout<<"请输入第一个链表的元素:";
for(int i=0;i<n;i++){
int x;
cin>>x;
Node* node=new Node;
node->data=x;
p1->next=node;
p1=node;
}
cout<<"请输入第二个链表的长度:";
cin>>m;
cout<<"请输入第二个链表的元素:";
for(int i=0;i<m;i++){
int x;
cin>>x;
Node* node=new Node;
node->data=x;
p2->next=node;
p2=node;
}
Node* head3=merge(head1->next,head2->next);
cout<<"合并后的链表为:";
while(head3!=NULL){
cout<<head3->data<<" ";
head3=head3->next;
}
cout<<endl;
return 0;
}
```
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)