单链表的实现c++模板机制
时间: 2023-05-29 11:06:02 浏览: 72
单链表的实现可以通过结构体和指针来实现。具体实现步骤如下:
1. 定义链表节点结构体
```c
typedef struct ListNode {
int val;
struct ListNode* next;
} ListNode;
```
2. 定义链表结构体
```c
typedef struct LinkedList {
ListNode* head;
ListNode* tail;
} LinkedList;
```
3. 定义链表操作函数
```c
// 创建链表
LinkedList* createLinkedList() {
LinkedList* list = (LinkedList*)malloc(sizeof(LinkedList));
list->head = NULL;
list->tail = NULL;
return list;
}
// 销毁链表
void destroyLinkedList(LinkedList* list) {
ListNode* cur = list->head;
while (cur != NULL) {
ListNode* next = cur->next;
free(cur);
cur = next;
}
free(list);
}
// 添加节点到链表末尾
void addNode(LinkedList* list, int val) {
ListNode* node = (ListNode*)malloc(sizeof(ListNode));
node->val = val;
node->next = NULL;
if (list->head == NULL) {
list->head = node;
list->tail = node;
} else {
list->tail->next = node;
list->tail = node;
}
}
// 删除链表中第一个值等于 val 的节点
void removeNode(LinkedList* list, int val) {
ListNode* prev = NULL;
ListNode* cur = list->head;
while (cur != NULL) {
if (cur->val == val) {
if (prev == NULL) {
list->head = cur->next;
} else {
prev->next = cur->next;
}
free(cur);
break;
}
prev = cur;
cur = cur->next;
}
}
```
4. 使用链表
```c
int main() {
LinkedList* list = createLinkedList();
addNode(list, 1);
addNode(list, 2);
addNode(list, 3);
removeNode(list, 2);
destroyLinkedList(list);
return 0;
}
```
模板机制可以用来实现通用的链表操作函数。例如,可以使用模板机制实现添加节点的函数:
```c
template<typename T>
void addNode(LinkedList* list, T val) {
ListNode* node = (ListNode*)malloc(sizeof(ListNode));
node->val = val;
node->next = NULL;
if (list->head == NULL) {
list->head = node;
list->tail = node;
} else {
list->tail->next = node;
list->tail = node;
}
}
```
这样就可以添加任意类型的节点了。例如:
```c
LinkedList* list = createLinkedList();
addNode(list, 1);
addNode(list, "hello");
destroyLinkedList(list);
```