实现顺序表的建立、清空、插入、删除、查找、修改、打印等等运算
时间: 2024-10-12 14:15:51 浏览: 0
顺序表是一种基础的数据结构,它通过连续的内存空间存储元素。以下是实现顺序表的一些基本操作:
1. **建立(创建)**:首先分配一段连续的内存空间,然后逐个初始化每个位置的值。例如,在C++中可以这样创建:
```cpp
template <typename T>
class List {
private:
T* data;
size_t capacity;
size_t size;
public:
List(size_t initial_capacity = 0);
// 其他构造函数...
};
```
2. **清空(Clear)**:将所有元素设置为默认值(如`T()`),并调整大小为0,释放多余的内存:
```cpp
void clear() {
for (size_t i = 0; i < size; ++i) {
data[i] = T(); // 默认值
}
size = 0;
if (capacity > 0 && capacity != size) {
resize(0); // 如果有剩余空间,进一步缩小容量
}
}
```
3. **插入(Insert)**:通常在指定位置插入新元素,需要移动后续元素:
```cpp
void insert(int index, const T& value) {
if (index >= size) {
resize(size * 2); // 扩容如果超出界限
}
memmove(data + index + 1, data + index, sizeof(T) * (size - index));
data[index] = value;
++size;
}
```
4. **删除(Delete)**:移除指定位置的元素,可能需要调整后续元素:
```cpp
void remove(int index) {
if (index < size) {
memmove(data + index, data + index + 1, sizeof(T) * (size - index - 1));
--size;
if (size < capacity / 4) { // 缩小容量,防止浪费
resize(capacity / 2);
}
}
}
```
5. **查找(Find)**:遍历列表直到找到特定值或结束:
```cpp
int find(const T& value) const {
for (size_t i = 0; i < size; ++i) {
if (data[i] == value) return i;
}
return -1; // 如果未找到,返回-1
}
```
6. **修改(Modify)**:找到指定索引处的元素并更新其值:
```cpp
void modify(int index, const T& newValue) {
if (index < size) {
data[index] = newValue;
} else {
throw std::out_of_range("Index out of range");
}
}
```
7. **打印(Display)**:遍历列表并输出元素值:
```cpp
void display() const {
for (size_t i = 0; i < size; ++i) {
std::cout << data[i] << " ";
}
std::cout << '\n';
}
```