实现链表类模板,需要创建节点类模板和链表类模板
时间: 2023-07-25 14:36:23 浏览: 99
是的,实现链表类模板需要创建节点类模板和链表类模板。
节点类模板用于表示链表中的每个节点,包含数据和指向下一个节点的指针。节点类模板通常包含一个构造函数,用于初始化节点的数据和指针。例如:
```c++
template <typename T>
class Node {
public:
T data;
Node<T>* next;
Node(const T& d, Node<T>* n = nullptr) : data(d), next(n) {}
};
```
链表类模板用于表示整个链表,包含头指针、尾指针和链表大小等属性,以及添加、删除、清空、查找和打印等操作的方法。例如:
```c++
template <typename T>
class LinkedList {
private:
Node<T>* head;
Node<T>* tail;
int size;
public:
LinkedList() : head(nullptr), tail(nullptr), size(0) {}
~LinkedList() {
Node<T>* curr = head;
while (curr != nullptr) {
Node<T>* temp = curr;
curr = curr->next;
delete temp;
}
size = 0;
}
int getSize() const {
return size;
}
void add(const T& data) {
Node<T>* newNode = new Node<T>(data);
if (head == nullptr) {
head = newNode;
tail = newNode;
} else {
tail->next = newNode;
tail = newNode;
}
size++;
}
bool remove(const T& data) {
Node<T>* prev = nullptr;
Node<T>* curr = head;
while (curr != nullptr) {
if (curr->data == data) {
if (prev == nullptr) {
head = curr->next;
} else {
prev->next = curr->next;
}
if (tail == curr) {
tail = prev;
}
delete curr;
size--;
return true;
}
prev = curr;
curr = curr->next;
}
return false;
}
bool contains(const T& data) const {
Node<T>* curr = head;
while (curr != nullptr) {
if (curr->data == data) {
return true;
}
curr = curr->next;
}
return false;
}
void clear() {
Node<T>* curr = head;
while (curr != nullptr) {
Node<T>* temp = curr;
curr = curr->next;
delete temp;
}
head = nullptr;
tail = nullptr;
size = 0;
}
void print() const {
Node<T>* curr = head;
while (curr != nullptr) {
std::cout << curr->data << " ";
curr = curr->next;
}
std::cout << std::endl;
}
};
```
这个链表类模板实现了添加、删除、清空、判断是否包含某个元素、获取链表大小和打印链表的功能。可以使用该模板来创建任意类型的链表。
阅读全文