### C++ 数据结构 -- 单链表
#### 概述
单链表是一种常见的线性数据结构，在计算机科学中有着广泛的应用。与数组相比，单链表的优势在于它不需要连续的内存空间，因此在动态调整大小时更加灵活。在本篇文章中，我们将详细探讨如何在VS2010环境下使用C++语言实现单链表的基本操作，包括创建、插入、删除等。
#### 基本概念
单链表由一系列节点组成，每个节点包含两部分：数据域和指针域。数据域用于存储实际的数据，而指针域则存储指向下一个节点的地址。链表的第一个节点被称为头节点，最后一个节点的指针域通常为空(NULL)。
#### 创建单链表
代码示例中首先定义了一个结构体`Node`，该结构体包含一个整型数据成员`data`和一个指向自身类型的指针成员`next`。随后定义了一个类型别名`node`，使得可以直接使用`node`来替代原本的结构体类型。接下来定义了一个头结点`first`，并初始化其`next`成员为空，表示链表初始为空。
```cpp
#include<iostream>
#include<Windows.h>
using namespace std;
typedef struct Node {
int data;
struct Node* next;
} node;
typedef node *hnode;
hnode first = new node(); // 头结点
void createLinkList(int a[], int n) {
hnode r, s; // r, s 都是指针类型
r = new node();
r = first;
for (int i = 0; i < n; i++) {
s = new Node();
s->data = a[i];
r->next = s;
r = s;
}
r->next = NULL;
r = first->next;
do {
cout << r->data << " ";
r = r->next;
} while (r); // r->next 这个条件不能输出最后一个元素
}
```
#### 插入节点
为了向链表中插入一个新的节点，需要先找到插入位置前一个节点的指针，然后调整指针使其指向新节点，并将新节点的指针指向原位置的节点。
```cpp
void insertnode(int i, int x) {
hnode s;
hnode p = new node();
p = first;
int j = 0;
while (p && j < i - 1) { // 不要等号，因为从0开始，又在i-1处已经知道第i处的值
p = p->next;
j++;
}
if (!p) {
cout << "!!!当前不存在位置: " << i << endl;
} else {
s = new node();
s->data = x;
s->next = p->next;
p->next = s;
}
hnode r = new node();
r = first->next;
do {
cout << r->data << " ";
r = r->next;
} while (r); // r->next 这个条件不能输出最后一个元素
}
```
#### 删除节点
删除节点的过程需要找到待删除节点的前一个节点，然后将其指针指向待删除节点的下一个节点。需要注意的是，删除操作还需要释放待删除节点占用的内存。
```cpp
int deletenode(int i) {
int ot = -1;
hnode p = new node;
hnode q = new node();
p = first;
int j = 0;
while (p && j < i - 1) {
p = p->next;
j++;
}
if (!p || !p->next) {
cout << i << "位置不存在!!或不能是最后一个结点" << endl;
} else {
q = p->next;
ot = q->data;
p->next = q->next;
delete q;
}
return ot;
}
```
#### 主函数
主函数中通过调用上述函数实现了单链表的创建、插入和删除操作，并展示了结果。
```cpp
void main() {
int a[] = {12, 23, 2, 56, 66, 99, 100, 33};
int lo = sizeof(a) / sizeof(a[0]); // 获取数组长度
createLinkList(a, lo);
int x;
cout << "插入的数值：" << endl;
cin >> x;
cout << endl;
int i;
cout << "插入的位置：" << endl;
cin >> i;
cout << endl;
insertnode(i, x); // 在i处插入x
int k;
cout << "输入要删除的位置：" << endl;
cin >> k;
k = deletenode(k); // 删除i处的元素
cout << k << endl;
system("pause"); // 避免程序运行后立即关闭
}
```
总结来说，通过以上的代码示例我们可以了解到在C++中如何使用指针来实现单链表的操作，这些操作包括链表的创建、节点的插入和删除等。这些基础操作对于理解和掌握更复杂的数据结构至关重要。
