链表类设计与实现c++
时间: 2023-12-14 07:05:21 浏览: 33
链表是一种常见的数据结构,它在计算机科学中被广泛应用。链表由一个个节点组成,每个节点保存着数据以及指向下一个节点的指针。链表可以用来实现栈、队列等数据结构。
下面是链表的设计与实现(C语言):
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构体
typedef struct node {
int data; // 数据
struct node *next; // 指向下一个节点的指针
} Node;
// 定义链表结构体
typedef struct {
Node *head; // 头节点
int length; // 链表长度
} List;
// 初始化链表
void initList(List *list) {
list->head = NULL;
list->length = 0;
}
// 在链表尾部插入节点
void appendNode(List *list, int data) {
Node *newNode = (Node*)malloc(sizeof(Node)); // 创建新节点
newNode->data = data;
newNode->next = NULL;
if (list->head == NULL) {
// 如果链表为空,则将新节点作为头节点
list->head = newNode;
} else {
// 否则在尾节点后插入新节点
Node *p = list->head;
while (p->next != NULL) {
p = p->next;
}
p->next = newNode;
}
list->length++;
}
// 在链表中查找节点
Node* findNode(List *list, int data) {
Node *p = list->head;
while (p != NULL) {
if (p->data == data) {
return p;
}
p = p->next;
}
return NULL;
}
// 删除链表中的节点
void deleteNode(List *list, int data) {
Node *p = list->head;
Node *prev = NULL;
while (p != NULL) {
if (p->data == data) {
// 找到要删除的节点
if (prev == NULL) {
// 如果要删除的是头节点,则将头指针指向下一个节点
list->head = p->next;
} else {
// 否则将前一个节点的指针指向下一个节点
prev->next = p->next;
}
free(p); // 释放内存
list->length--;
return;
}
prev = p;
p = p->next;
}
}
// 输出链表中的数据
void printList(List *list) {
Node *p = list->head;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
int main() {
// 创建一个链表并初始化
List list;
initList(&list);
// 在链表尾部插入节点
appendNode(&list, 1);
appendNode(&list, 2);
appendNode(&list, 3);
appendNode(&list, 4);
// 输出链表中的数据
printList(&list); // 输出 1 2 3 4
// 在链表中查找节点
Node *node = findNode(&list, 3);
if (node != NULL) {
printf("Found node: %d\n", node->data); // 输出 Found node: 3
} else {
printf("Node not found.\n");
}
// 删除链表中的节点
deleteNode(&list, 2);
// 输出链表中的数据
printList(&list); // 输出 1 3 4
return 0;
}
```
以上就是链表的基本设计与实现。需要注意的是,在访问链表节点时要确保节点非空,否则会导致程序崩溃。同时,删除节点时应该释放节点所占用的内存。