目录
| 序号 | 基本操作 | 描述 |
|---|---|---|
| 1 | initial() | 构造/初始化链表 |
| 2 | insert() | 插入元素 |
| 3 | delete() | 删除元素 |
| 4 | find() | 按值查找，如存在返回地址，不存在返回null |
| 5 | size() | 获取链表大小，即链表中元素的个数 |
| 6 | getValue() | 取值，链表不支持下标访问（当然可以实现，但也是通过指针实现的），所以用指针取出指向的节点的值 |
| 7 | empty() | 判空 |
| 8 | reverse() | 反转 |
| 9 | destory() | 销毁链表 |
2.3.1 初始化
2.3.2 插入元素
这里的插入操作和初始化链表时的插入操作一样，都是通过改变节点指针的指向实现的。
其中，为了防止指针断开后，后面的链表丢失，不要先执行3，要按照123的顺序，把新节点插入后再断开原有节点的指针。
例程如下：
bool insert_pos(node* p_head, int pos, int data)
{
// 建议记录链表长度并判断，否则需要调用时保证插入位置有效，避免访问越界
if (p_head == NULL || pos > p_head->data)
{
printf("插入位置无效.\n");
return false;
}
node* p_tmp = p_head;
// 首先找到要插入位置的上一个结点
for (int i = 0; i < pos; i++)
{
p_tmp = p_tmp->next;
}
// 创建插入结点c
node* p_new = (node*)malloc(sizeof(node));
p_new->data = data;
// 向链表中插入结点
p_new->next = p_tmp->next;
p_tmp->next = p_new;
p_head->data++;
return true;
}
2.3.3 删除元素
删除元素即将要删除的节点跳过，再释放该节点的内存。
由于单链表只能单向访问，所以遍历时不只是要找到要删除的节点，还要找到它的直接前驱节点，使其直接前驱节点的指针域存储其直接后继节点的地址。
遍历时，使用双指针的办法，一个指向要删除的节点，一个指向其直接前驱节点，如下图：
然后，令其直接前驱节点指向其直接后继节点（跳过要删除的节点），p_pre->next = p_pre->next->next; 如下图：
最后，释放要删除的节点的内存，free(p_del); ，如下图：
例程如下：
按索引删除：
bool delete_index(node* p_head, int index)
{
if (p_head == NULL || index > p_head->data)
{
printf("没有该结点\n");
return false;
}
// 遍历到被删除结点的直接前驱结点
node* p_pre = p_head;
for (int i = 0; i < index; i++)
{
p_pre = p_pre->next;
}
node* p_del = p_pre->next; // 单独设置一个指针指向被删除结点，以防丢失
p_pre->next = p_del->next; // 删除某个结点的方法就是更改前一个结点的指针域
p_head->data--;
free(p_del); // 手动释放该结点，防止内存泄漏
return true;
}
按值删除，删除链表中所有数据域值为del的节点：
bool delete_value(node* p_head, int del)
{
if (p_head == NULL || p_head->next == NULL)
{
printf("链表为空\n");
return false;
}
node* p_pre = p_head;
node* p_del = p_pre->next;
int i = 0;
while (p_del != NULL)
{
while (p_del->data != del)
{
p_pre = p_pre->next;
if (p_pre->next != NULL)
{
p_del = p_pre->next;
}
else if (i == 0)
{
printf("链表中不存在该值\n");
return false;
}
else
{
return true;
}
}
i++;
p_pre->next = p_del->next;
free(p_del);
p_del = p_pre->next;
p_head->data--;
}
return true;
}
2.3.4 查找元素
查找元素有很多优秀的算法，这里只介绍顺序查找。
顺序查找即依次遍历每个节点，检查该节点是否为要查找的节点，直到找到要找的节点或遍历结束。
例程如下：
返回第一个找到的节点：
bool find_first(node* p_head, int value, int* index)
{
if (p_head == NULL || p_head->next == NULL)
{
printf("链表为空\n");
*index = -1;
return false;
}
node* p_tmp = p_head;
int i = 0;
while (p_tmp->next)
{
p_tmp = p_tmp->next;
if (p_tmp->data == value)
{
*index = i;
return true;
}
i++;
}
*index = -1;
return false;
}
返回最后一个找到的节点：
bool find_last(node* p_head, int value, int* index)
{
*index = -1;
if (p_head == NULL || p_head->next == NULL)
{
printf("链表为空\n");
return false;
}
node* p_tmp = p_head;
int i = 0;
while (p_tmp->next)
{
p_tmp = p_tmp->next;
if (p_tmp->data == value)
{
*index = i;
}
i++;
}
if (*index == -1)
{
return false;
}
else
{
return true;
}
}
返回所有找到的节点：
typedef struct Array
{
int size;
int* array;
} array;
bool find_all(node* p_head, int value, array* p_result)
{
if (p_head == NULL || p_head->next == NULL)
{
printf("链表为空\n");
p_result->size = 0;
return false;
}
node* p_tmp = p_head;
int* p_array = (int*)malloc(sizeof(int) * p_tmp->data);
int i = 0;
int size = 0;
int index = -1;
while (p_tmp->next)
{
p_tmp = p_tmp->next;
if (p_tmp->data == value)
{
p_array[size] = i;
size++;
}
i++;
}
p_result->size = size;
if (size == 0)
{
return false;
}
p_result->array = (int*)malloc(sizeof(int) * size);
for (int i = 0; i < size; i++)
{
p_result->array[i] = p_array[i];
}
free(p_array);
return true;
}
2.3.5 获取链表大小
可以使用头节点记录链表的大小，然后通过头指针访问头节点的数据域，或封装成函数。
bool size(node* p_head, int* size)
{
if (p_head == NULL)
{
return false;
}
*size = p_head->data;
return true;
}
2.3.6 访问节点/取值
链表不能像数组一样随机访问，无论是通过值访问还是按照索引访问，都需要依次遍历节点，直到找到目标节点。
bool get_value(node* p_head, int index, int* value)
{
if (p_head == NULL || p_head->next == NULL)
{
printf("链表为空\n");
return false;
}
node* p_tmp = p_head;
for (int i = 0; i < p_head->data; i++)
{
p_tmp = p_tmp->next;
if (i == index)
{
*value = p_tmp->data;
return true;
}
}
return false;
}
2.3.7 链表判空
bool empty(node* p_head)
{
if (p_head == NULL || p_head->next == NULL)
{
return true;
}
return false;
}
2.3.8 反转链表
2.3.9 清空链表/销毁链表
清空链表：释放链表除头节点以外的所有节点内存（即删除这些节点）。
销毁链表：释放链表的所有节点内存（包括头节点），并将头指针置空；
清空链表：
node* amendElem(node* p_head, int add, int newElem)
{
node* p_tmp = p_head;
p_tmp = p_tmp->next; // tamp指向首元结点
// temp指向被删除结点
for (int i = 1; i < add; i++)
{
p_tmp = p_tmp->next;
}
p_tmp->data = newElem;
return p_head;
}
销毁链表：
void destory(node** p_head_addr)
{
node* p_head = *p_head_addr;
if (p_head == NULL)
{
return;
}
node* p_tmp = p_head;
while (p_head != NULL)
{
p_head = p_head->next;
free(p_tmp);
p_tmp = p_head;
}
*p_head_addr = NULL;
}