用C++的数据结构知识,写一个顺序表的排序与合并的代码
时间: 2024-10-14 18:05:42 浏览: 5
在C++中,我们通常会使用数组作为基础数据结构来实现顺序表。这里是一个简单的冒泡排序和合并两个已排序顺序表的例子:
首先,我们可以定义一个节点类`Node`和顺序表类`SequentialList`:
```cpp
class Node {
public:
int data;
Node* next;
};
class SequentialList {
private:
Node* head;
int size;
public:
SequentialList() : head(nullptr), size(0) {}
// 插入元素到末尾
void insert(int value) {
if (head == nullptr) {
head = new Node{value, nullptr};
} else {
Node* current = head;
while (current->next != nullptr) {
current = current->next;
}
current->next = new Node{value, nullptr};
}
size++;
}
// 冒泡排序
void bubbleSort() {
if (size > 1) {
bool swapped;
for (int i = 0; i < size - 1; ++i) {
swapped = false;
for (int j = 0; j < size - 1 - i; ++j) {
if (head->data[j] > head->data[j + 1]) {
std::swap(head->data[j], head->data[j + 1]);
swapped = true;
}
}
if (!swapped) break; // 如果一轮下来没交换过,说明已经有序了
}
}
}
// 合并两个已排序列表
static SequentialList merge(SequentialList& list1, SequentialList& list2) {
SequentialList mergedList;
mergedList.head = nullptr;
// 分别处理每个列表为空的情况
if (list1.head && list2.head) {
Node* current1 = list1.head;
Node* current2 = list2.head;
while (current1 && current2) {
if (current1->data <= current2->data) {
mergedList.insert(current1->data);
current1 = current1->next;
} else {
mergedList.insert(current2->data);
current2 = current2->next;
}
}
// 将剩余部分添加到新列表
if (current1) mergedList.insert(current1->data);
if (current2) mergedList.insert(current2->data);
}
return mergedList;
}
};
```
以上代码实现了顺序表的基本操作,包括插入、冒泡排序和合并两个已排序列表。请注意,这个例子中的排序仅限于列表内部,如果需要外部提供已经排序好的顺序表,你需要在合并函数中先对它们分别排序。