链表02
在上一节中，我们对线性表，链表有了一些基本的了解，现在我们将着重了解线性表
同时，在上一节中我们学习的是链表的尾插法，实际上链表一共有头插法和尾插法俩个大法 (不过本人认为尾插法应该更广泛吧)
头插法:元素插入到链表的头部，即新元素始终都插入在头指针之后
初始链表结构:
┌─────┬─────┐ ┌─────┬─────┐ ┌─────┬─────┐
│ data│ next│ │ data│ next│ │ data│ next│
│ 1 │ ───┼───▶│ 2 │ ───┼───▶│ 3 │ NULL│
└─────┴─────┘ └─────┴─────┘ └─────┴─────┘
▲
│
HEAD
插入新节点(data=0)到头部后:
┌─────┬─────┐ ┌─────┬─────┐ ┌─────┬─────┐ ┌─────┬─────┐
│ data│ next│ │ data│ next│ │ data│ next│ │ data│ next│
│ 0 │ ───┼──▶│ 1 │ ──┼──▶│ 2 │ ──┼──▶│ 3 │ NULL│
└─────┴─────┘ └─────┴─────┘ └─────┴─────┘ └─────┴─────┘
▲
│
HEAD尾插法:元素插入到链表的尾部，即新元素始终都插入在尾指针之前
初始链表结构:
┌─────┬─────┐ ┌─────┬─────┐ ┌─────┬─────┐
│ data│ next│ │ data│ next│ │ data│ next│
│ 1 │ ───┼───▶│ 2 │ ───┼───▶│ 3 │ NULL│
└─────┴─────┘ └─────┴─────┘ └─────┴─────┘
▲ ▲
│ │
HEAD tail
插入新节点(data=4)到尾部后:
┌─────┬─────┐ ┌─────┬─────┐ ┌─────┬─────┐ ┌─────┬─────┐
│ data│ next│ │ data│ next│ │ data│ next│ │ data│ next│
│ 1 │ ───┼──▶│ 2 │ ───┼──▶│ 3 │ ───┼──▶│ 4 │ NULL│
└─────┴─────┘ └─────┴─────┘ └─────┴─────┘ └─────┴─────┘
▲ ▲
│ │
HEAD new tail不过对于示例代码中将依旧采取尾插法的形式，因为目前手头上的参考书几乎都是尾插法的描述，但是倘若尾插法熟络了头插法应该也差不多吧。后期有空会补上头插法的demo
代码部分
1.初始化链表
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int data; //数据域
struct node *next; //指针域
} node;
int main()
{
//初始化链表
int len = 0; //链表长度归零
node *head = (node *)malloc(sizeof(node)); //创建头结点
head->next = NULL; //头结点指针域为NULL
node *p = head; //p指向头结点，其中p为链表操作指针
}此时我们查看链表的结构，大概是这样的
┌──────────┬──────────┐
│ data │ next │
│ 任意值/0 │ NULL │
└──────────┴──────────┘
▲
│
HEAD
│
▼
p2.申请空间
//创建链表，插入节点
node* node1 = (node *)malloc(sizeof(node));
node* node2 = (node *)malloc(sizeof(node));
node* node3 = (node *)malloc(sizeof(node));
node* node4 = (node *)malloc(sizeof(node));
node* node5 = (node *)malloc(sizeof(node));
//申请了五个空间用于储存节点注意 ：此处我们只申请了空间，并为给这几块空间赋值以及串联，所有这五块空间是相互独立毫无联系的！！！
3.赋值以及串联
//下面将为他们分配值
node1->data = 1;
node2->data = 2;
node3->data = 3;
node4->data = 4;
node5->data = 5;
//连接节点
head->next = node1;
node1->next = node2;
node2->next = node3;
node3->next = node4;
node4->next = node5;
node5->next = NULL;此时我们查看链表结构，大概是这样的
完整的链表结构:
┌──────────┬──────────┐ ┌─────┬─────┐ ┌─────┬─────┐ ┌─────┬─────┐ ┌─────┬─────┐ ┌─────┬─────┐
│ data │ next │ │ data│ next│ │ data│ next│ │ data│ next│ │ data│ next│ │ data│ next│
│ 任意值/0 │ ────────┼───▶│ 1 │ ───┼──▶│ 2 │ ───┼──▶│ 3 │ ──┼───▶│ 4 │ ───┼──▶│ 5 │ NULL│
└──────────┴──────────┘ └─────┴─────┘ └─────┴─────┘ └─────┴─────┘ └─────┴─────┘ └─────┴─────┘
▲ ▲ ▲ ▲ ▲ ▲
│ │ │ │ │ │
HEAD node1 node2 node3 node4 node5
│
▼
p- 到现在才发现刚开始初始化时定义的操作变量p似乎目前还没有作用，那就现略过p，后面再写一个demo用p来优雅的操作吧 *
4.遍历链表
//遍历链表
while(p->next != NULL) {
p = p->next;
printf("%dn", p->data);
}输出结果为: 1 2 3 4 5
- 打脸的来了，刚刚还说没用的操作变量p现在用来遍历链表了 *
5.插入节点
//插入节点
node* newNode = (node *)malloc(sizeof(node));
newNode->data = 666;
//现在我们要将newNode插入到node3后面
node* temp = node3;
newNode->next = temp->next;
node3->next = newNode;
len++;
//遍历链表检查
while(p->next != NULL) {
p = p->next;
printf("%dn", p->data);
}此处我们注意到插入前我们将Node3保存到了临时变量temp中，那么此时有一个疑问，既然我们有一个temp变量，难道不用为他申请一个空间吗？
在这里temp 只是一个辅助指针，用来帮助完成插入操作，它不需要单独的内存空间，只需要指向已有节点即可。
6.删除节点
//这里我们假设要删除刚刚加进来的数据域为666的节点，但是我们加点难度，假设不知道删除的节点是哪一个
node* q = head; //获取一个1指针用于遍历
while(q->next != NULL) { //遍历链表
if(q->next->data == 666) { //判断下一个节点的数据域是否为666
node* temp = q->next; //如果遇到了666，那么我们现用临时变量temp保存下一个节点的指针
q->next = temp->next;
free(temp);
len--;
printf("删除成功!n");
break;
} else {
q = q->next; //如果没有遇到，那么q指针继续往下
}
}
//遍历链表检查
while(p->next != NULL) {
p = p->next;
printf("%dn", p->data);
}这里我们假设要删除刚刚加进来的数据域为666的节点，但是我们加点难度，假设不知道删除的节点是哪一个
其实在添加元素时我们可能也不知道目标元素在哪，所以这里加了一个查找目标元素的代码
值得一提的是： 我们删除节点后记得要释放它，养成不用就释放的好习惯
7.释放链表
// 清空链表
node *current = head->next; // 从第一个有效节点开始
while (current != NULL)
{
node *temp = current; // 保存当前节点
current = current->next; // 移动到下一个节点
free(temp); // 释放当前节点内存
}
head->next = NULL; // 头节点指向NULL
len = 0; // 长度归零
printf("链表清空完成!n");综上，就是我们在常规文件中对链表的操作的示例代码片段，完整代码可以在同文件夹下的./Demo1.c中找到,博客会把代码附在评论区
感谢支持！
评论