概述
单链表是最基本的数据结构之一，它由一系列节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。单链表的特点是动态存储和灵活的元素插入、删除操作。本文将通过 C++ 实现单链表的基本操作：创建、查询、插入、删除、头插、尾插、打印等，帮助大家了解如何在 C++ 中实现和操作链表。
链表节点结构
在 C++ 中，链表的基本单元是节点（Node）。每个节点包含两个部分：
data：节点存储的数据。
next：指向下一个节点的指针。
我们定义一个结构体 LNode 来表示链表的节点：
typedef int Datatype;
typedef struct LNode {
Datatype data;
struct LNode* next;
} Node, *Linklist;
链表的创建
我们可以通过头插法来创建链表。头插法是将新的节点插入到链表的头部，即将新节点的 next 指针指向当前的头节点，然后更新头节点为新节点。
Linklist CreateList(Linklist& L, int n) {
L = (Linklist)malloc(sizeof(Node)); // 创建一个新的头节点
L->next = NULL; // 初始化头节点的 next 为 NULL
for (int i = 0; i < n; i++) {
Linklist p = (Linklist)malloc(sizeof(Node)); // 创建新节点
scanf("%d", &p->data); // 输入数据
p->next = L->next; // 将新节点的 next 指向当前头节点
L->next = p; // 更新头节点
}
return L;
}
链表的插入操作
链表的插入操作可以在指定的位置插入一个新节点。在 InsertList 函数中，我们首先找到插入位置的前一个节点 p，然后创建新节点 q，将 p->next 指向 q，q->next 指向原来的节点。
int InsertList(Linklist& L, int i, Datatype& e) {
Linklist p = L;
int j = 0;
while (p && j < i - 1) {
p = p->next;
j++;
}
if (!p || j > i)
return ERROR;
Linklist q = (Linklist)malloc(sizeof(Node));
q->data = e;
q->next = p->next;
p->next = q;
return OK;
}
链表的删除操作
删除操作的基本思想是：找到待删除节点的前一个节点 p，然后将 p->next 指向待删除节点的下一个节点。删除操作之后需要释放被删除节点的内存。
int DeleteList(Linklist& L, int i, Datatype& e) {
Linklist p = L;
int j = 0;
while (p && j < i - 1) {
p = p->next;
j++;
}
if (!p || j > i)
return ERROR;
Linklist q = p->next;
p->next = q->next;
e = q->data;
free(q);
return OK;
}
查询操作
查询操作是根据给定的值在链表中查找元素。如果找到该元素，返回其在链表中的位置；如果找不到，返回 0。
int LocateElem(Linklist& L, Datatype e) {
Linklist p = L->next;
int i = 1;
while (p && p->data != e) {
p = p->next;
i++;
}
if (!p)
return 0;
return i;
}
头插与尾插操作
头插法：每次插入的新节点都会插入到链表的头部，更新头节点的指针。
void insert_front(Linklist& L, Datatype e) {
Linklist p = (Linklist)malloc(sizeof(Node));
p->data = e;
p->next = L->next;
L->next = p;
}
尾插法：每次插入的新节点都会插入到链表的尾部。我们首先找到链表的最后一个节点，再将新节点插入。
void insert_back(Linklist& L, Datatype e) {
Linklist p = L;
while (p->next != NULL) {
p = p->next;
}
Linklist q = (Linklist)malloc(sizeof(Node));
q->data = e;
q->next = NULL;
p->next = q;
}
打印链表
打印链表的操作是遍历链表并输出每个节点的数据。
void PrintList(Linklist& L) {
Linklist p = L->next;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
主函数与菜单
主函数中实现了一个简单的菜单，用户可以选择执行链表的各种操作：新建链表、查询、插入、删除、打印、头插、尾插和退出。
int main() {
Linklist L = NULL;
cout << "------------------单链表基本操作------------------" << endl;
cout << "1.新建 2.查询 3.插入 4.删除 5.打印 6.头插 7.尾插 8.退出" << endl;
int n;
while (true) {
cout << "请选择操作: ";
scanf("%d", &n);
switch (n) {
case 1: {
cout << "请输入链表长度：";
int m;
scanf("%d", &m);
CreateList(L, m);
cout << "创建成功！" << endl;
break;
}
case 2: {
cout << "请输入要查询的元素：";
int e;
scanf("%d", &e);
int m = LocateElem(L, e);
if (m == 0) {
cout << "未找到该元素！" << endl;
}
else {
cout << "该元素在第" << m << "个位置！" << endl;
}
break;
}
case 3: {
cout << "请输入要插入的位置和元素：";
int i, e;
scanf("%d%d", &i, &e);
if (InsertList(L, i, e) == OK) {
cout << "插入成功！" << endl;
}
else {
cout << "插入失败！" << endl;
}
break;
}
case 4: {
cout << "请输入要删除的位置：";
int i;
scanf("%d", &i);
int e;
if (DeleteList(L, i, e) == OK) {
cout << "删除成功！删除的元素为：" << e << endl;
}
else {
cout << "删除失败！" << endl;
}
break;
}
case 5:
PrintList(L);
break;
case 6: {
cout << "请输入要插入的元素：";
int e;
scanf("%d", &e);
insert_front(L, e);
cout << "头插成功！" << endl;
break;
}
case 7: {
cout << "请输入要插入的元素：";
int e;
scanf("%d", &e);
insert_back(L, e);
cout << "尾插成功！" << endl;
break;
}
case 8:
return 0;
default:
cout << "请输入正确的操作！" << endl;
}
}
return 0;
}
总结
通过本文的实现，我们学习了如何使用 C++ 实现单链表的基本操作。链表是一个非常灵活的数据结构，支持高效的插入和删除操作。希望通过这篇文章，大家能够更深入理解链表的工作原理，并能够根据实际需求进行修改和优化。
