请帮我写一段单链表模板程序
时间: 2023-10-06 12:04:29 浏览: 64
好的,以下是一个单链表的模板程序,可以根据需要进行修改:
```c++
#include <iostream>
using namespace std;
//定义单链表节点结构体
template <typename T>
struct ListNode {
T val;
ListNode* next;
ListNode(T x) : val(x), next(nullptr) {}
};
//定义单链表类
template <typename T>
class LinkedList {
public:
LinkedList() : head(nullptr), tail(nullptr), size(0) {}
~LinkedList() {
ListNode<T>* cur = head;
while (cur) {
ListNode<T>* temp = cur;
cur = cur->next;
delete temp;
}
head = tail = nullptr;
size = 0;
}
//在链表尾部添加节点
void add(T x) {
ListNode<T>* node = new ListNode<T>(x);
if (!head) {
head = tail = node;
} else {
tail->next = node;
tail = node;
}
size++;
}
//删除链表中所有值为x的节点
void remove(T x) {
ListNode<T>* cur = head;
ListNode<T>* pre = nullptr;
while (cur) {
if (cur->val == x) {
if (cur == head) {
head = head->next;
} else if (cur == tail) {
tail = pre;
tail->next = nullptr;
} else {
pre->next = cur->next;
}
ListNode<T>* temp = cur;
cur = cur->next;
delete temp;
size--;
} else {
pre = cur;
cur = cur->next;
}
}
}
//打印链表中所有节点的值
void print() {
ListNode<T>* cur = head;
while (cur) {
cout << cur->val << " ";
cur = cur->next;
}
cout << endl;
}
//返回链表的长度
int getSize() {
return size;
}
private:
ListNode<T>* head;
ListNode<T>* tail;
int size;
};
int main() {
LinkedList<int> list;
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.print(); //输出:1 2 3 4
list.remove(2);
list.print(); //输出:1 3 4
cout << "size: " << list.getSize() << endl; //输出:size: 3
return 0;
}
```
该程序定义了一个单链表的模板类,包括添加节点、删除节点、打印链表和返回链表长度等基本操作。其中,ListNode为单链表节点结构体,LinkedList为单链表类,使用模板类实现了支持任意类型的节点值。
阅读全文