C++实现顺序表 |holyya.com

C++实现顺序表

2023-07-06 22:47:16 深夜i -- --

C++ 实现顺序表

顺序表是一种数据结构，它可以存储相同类型的元素，并按照一定的顺序进行访问。在C++中，可以使用数组和指针来实现顺序表。

数组是一种非常适合存储一组相同类型的数据的结构。使用数组实现顺序表，可以通过数组的索引来访问元素。下面是一个简单的示例代码：


const int MAX_SIZE = 100;
template <typename T>
class Array{
private:
T data[MAX_SIZE];
int length;
public:
Array(): length(0) {}
void append(const T& value) {
if (length >= MAX_SIZE) {
throw std::overflow_error("array overflow");
}
data[length++] = value;
}
T& operator[](int index) {
if (index < 0 || index >= length) {
throw std::out_of_range("index out of range");
}
return data[index];
}
int size() const {return length;}
};

在此代码中，`Array`类是一个模板类，可以存储任意类型的数据。该类使用了一个名为`data`的数组来存储数据，数组的长度为`MAX_SIZE`，默认情况下数据长度为0。`append`方法用于添加数据，如果数组已满则抛出异常；`operator[]`方法用于访问元素，如果索引不在有效范围内，则抛出异常；`size`方法用于返回数组的大小。

指针也是实现顺序表的一种常用方法。使用指针实现顺序表，可以直接访问内存地址，不必使用索引。下面是一个基于指针的示例代码：


template <typename T>
class List{
private:
struct Node{
T data;
Node* next;
Node(): next(nullptr) {}
Node(const T& v): data(v), next(nullptr) {}
};
Node* head;
int length;
public:
List(): length(0), head(nullptr) {}
~List() {
clear();
}
void append(const T& value){
Node* node = new Node(value);
if (head == nullptr)
head = node;
else {
Node* t = head;
while (t->next != nullptr)
t = t->next;
t->next = node;
}
length++;
}
void clear(){
Node* t = head;
while (t != nullptr) {
Node* p = t->next;
delete t;
t = p;
}
head = nullptr;
length = 0;
}
T& operator[](int index) {
if (index < 0 || index >= length) {
throw std::out_of_range("index out of range");
}
Node* t = head;
for (int i = 0; i < index; i++)
t = t->next;
return t->data;
}
int size() const {return length;}
};

在此代码中，`List`类也是一个模板类，可以存储任意类型的数据。该类使用了一个名为`Node`的结构体来存储数据，并通过指针`next`来指向下一个节点。`head`指针指向链表的头节点，`length`表示链表的长度。`append`方法用于添加数据，`clear`方法用于清空数据，`operator[]`方法用于访问元素，`size`方法用于返回链表的长度。

总而言之，顺序表是一种十分常用的数据结构，通过不同的实现方式，可以用来存储不同类型的数据。除了数组和指针，C++中还有许多其他的方式可以实现顺序表，如STL中的vector和deque。在实际应用中，需要根据不同情况选择最合适的实现方式。

上一篇: idea打包java可执行jar包

下一篇: 结合的规则

评论区

()

相似文章