使用cpp语言实现两个表合并成一个有序表,要求:使用链表储存,两个处理流程方式,抽象数据类型独立实现,写出完整可直接运行的代码并分析各代码性能
时间: 2024-05-02 16:17:55 浏览: 14
以下是使用链表实现两个有序表合并为一个有序表的CPP代码:
```cpp
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
class LinkedList {
private:
Node* head;
public:
LinkedList() {
head = NULL;
}
void insert(int value) {
Node* newNode = new Node;
newNode->data = value;
newNode->next = NULL;
if (head == NULL) {
head = newNode;
} else {
Node* temp = head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
}
void display() {
Node* temp = head;
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
void merge(LinkedList& list1, LinkedList& list2) {
Node* temp1 = list1.head;
Node* temp2 = list2.head;
while (temp1 != NULL && temp2 != NULL) {
if (temp1->data < temp2->data) {
insert(temp1->data);
temp1 = temp1->next;
} else {
insert(temp2->data);
temp2 = temp2->next;
}
}
while (temp1 != NULL) {
insert(temp1->data);
temp1 = temp1->next;
}
while (temp2 != NULL) {
insert(temp2->data);
temp2 = temp2->next;
}
}
};
int main() {
LinkedList list1, list2, mergedList;
int n1, n2, num;
cout << "Enter the number of elements in list1: ";
cin >> n1;
cout << "Enter the elements of list1: ";
for (int i = 0; i < n1; i++) {
cin >> num;
list1.insert(num);
}
cout << "Enter the number of elements in list2: ";
cin >> n2;
cout << "Enter the elements of list2: ";
for (int i = 0; i < n2; i++) {
cin >> num;
list2.insert(num);
}
mergedList.merge(list1, list2);
cout << "Merged list: ";
mergedList.display();
return 0;
}
```
该代码使用了链表来储存元素,并使用了抽象数据类型LinkedList来实现链表的各种操作。在merge方法中,我们遍历两个链表list1和list2,并将它们的元素按照升序插入到新的链表mergedList中。
该代码的时间复杂度取决于两个链表的长度,因此时间复杂度为O(n1 + n2),其中n1和n2分别为链表list1和list2的长度。空间复杂度为O(n1 + n2),因为我们需要额外开辟一个链表来存储合并后的结果。
相关推荐
![](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)
![](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)