C++编程实现顺序表,要求顺序表的定义至少包含(1)创建顺序表(2)顺序表的按位查找(3)顺序表的按位插入和按位删除(4)按位获取某个元素等功能;然后实现两个顺序表的并操作(不允许重复元素)和两个有序顺序表的合并操作(允许重复元素)。
时间: 2024-10-05 14:04:07 浏览: 16
在C++中,我们可以使用结构体或类来实现顺序表。这里是一个简单的示例,包含顺序表的定义和一些基本操作:
```cpp
#include <iostream>
using namespace std;
// 定义顺序表结构
class SequenceList {
private:
int *data; // 存储数据的指针
int size; // 序列长度
int capacity; // 最大容量
public:
// 创建顺序表
SequenceList(int capacity_ = 10) : data(new int[capacity_]), size(0), capacity(capacity_) {}
// 初始化列表为空
void init() {
size = 0;
}
// 按位查找
bool find(int key) const {
for (int i = 0; i < size; ++i) {
if (data[i] == key) return true;
}
return false;
}
// 按位插入
void insert(int index, int value) {
if (index >= size || index < 0) {
cout << "Invalid insertion index!" << endl;
return;
}
if (size == capacity) {
resize(capacity *= 2); // 如果已满,扩容
}
memmove(data + index + 1, data + index, sizeof(int) * (size - index)); // 移动元素
data[index] = value;
++size;
}
// 按位删除
void remove(int index) {
if (index >= size || index < 0) {
cout << "Invalid removal index!" << endl;
return;
}
memmove(data + index, data + index + 1, sizeof(int) * (size - index));
--size;
}
// 获取元素
int get(int index) const {
if (index < 0 || index >= size) {
throw out_of_range("Index out of range!");
}
return data[index];
}
// 释放内存
~SequenceList() {
delete[] data;
}
// 扩容函数
void resize(int new_capacity) {
int* temp = new int[new_capacity];
for (int i = 0; i < size; ++i) {
temp[i] = data[i];
}
delete[] data;
data = temp;
capacity = new_capacity;
}
// 并操作(不允许重复元素)
void merge_unique(const SequenceList& other) {
for (int i = 0; i < other.size; ++i) {
if (!find(other.data[i])) {
insert(size, other.data[i]);
}
}
}
// 合并两个有序顺序表(允许重复元素)
void merge_sorted(const SequenceList& other) {
int i = 0, j = 0;
while (i < size && j < other.size) {
if (data[i] <= other.data[j]) {
insert(i, data[i++]);
} else {
insert(i, other.data[j++]);
}
}
while (j < other.size) {
insert(j, other.data[j++]); // 插入剩余元素
}
}
};
// 示例
int main() {
SequenceList list1(5);
list1.init();
list1.insert(0, 10);
list1.insert(2, 20);
SequenceList list2(5);
list2.init();
list2.insert(0, 5);
list2.insert(1, 15);
// 并操作
list1.merge_unique(list2);
// 合并有序列表
SequenceList ordered_list1(5);
ordered_list1.init();
ordered_list1.insert(0, 1);
ordered_list1.insert(2, 3);
ordered_list1.insert(4, 5);
SequenceList ordered_list2(5);
ordered_list2.init();
ordered_list2.insert(1, 2);
ordered_list2.insert(3, 4);
ordered_list1.merge_sorted(ordered_list2);
return 0;
}
```