C++给出一个线性表ADT的例子
时间: 2024-09-10 07:07:42 浏览: 29
在C++中,线性表可以通过数组或链表来实现。这里给出一个简单的基于数组的线性表ADT(Abstract Data Type)示例。
```cpp
#include <iostream>
using namespace std;
template <typename T>
class LinearList {
private:
T* data; // 存储线性表元素的数组
int capacity; // 线性表的容量
int length; // 线性表当前长度
public:
// 构造函数
LinearList(int cap = 100) : capacity(cap), length(0) {
data = new T[capacity];
}
// 析构函数
~LinearList() {
delete[] data;
}
// 在线性表的第i个位置插入元素e
void insert(int i, T e) {
if (length >= capacity) {
// 如果当前长度大于等于容量,则无法插入
return;
}
if (i < 1 || i > length + 1) {
// 如果插入位置不合法,则不进行插入
return;
}
for (int j = length; j >= i; j--) {
data[j] = data[j - 1]; // 后移元素
}
data[i - 1] = e; // 插入新元素
length++; // 长度增加
}
// 删除线性表第i个位置的元素,并将其保存在e中
void remove(int i, T& e) {
if (i < 1 || i > length) {
// 如果删除位置不合法,则不进行删除
return;
}
e = data[i - 1]; // 取出元素
for (int j = i; j < length; j++) {
data[j - 1] = data[j]; // 前移元素
}
length--; // 长度减少
}
// 获取线性表的长度
int getLength() const {
return length;
}
// 打印线性表中的所有元素
void display() const {
for (int i = 0; i < length; i++) {
cout << data[i] << " ";
}
cout << endl;
}
};
int main() {
LinearList<int> myList;
myList.insert(1, 10); // 插入元素10在第1个位置
myList.insert(2, 20); // 插入元素20在第2个位置
myList.insert(3, 30); // 插入元素30在第3个位置
myList.display(); // 打印线性表:10 20 30
int removedElement;
myList.remove(2, removedElement); // 删除第2个位置的元素
cout << "Removed Element: " << removedElement << endl; // 输出被删除的元素:20
myList.display(); // 打印线性表:10 30
return 0;
}
```
这个例子中定义了一个模板类`LinearList`,它可以存储任何类型的元素。类中包含了构造函数、析构函数、插入元素、删除元素、获取长度和打印线性表的方法。这是一个线性表ADT的基本实现。