单链表

---

链表的基本概念

一、什么是链表？
链表是数据结构中线性表的一种，其中的每个元素实际上是一个单独的结构体对象，而所有对象都通过每个元素中的指针链接在一起。

什么是结点：链表中每个结构体对象叫做结点。

什么是首元结点：其中第一个数据结点。

什么是头结点：如果第一个结点不用于存储数据，只用于代表链表的起始点，则这个结点称为链表的头结点。

二、单链表的特点

1、单链表没有固定的长度，可以自由增加节点。

2、单链表能够实现快速的插入删除数据。

3、与数组类似，单链表也是一种线性数据结构。

4、单链表的尾结点的后继必定指向空。

单链表和数组的区别：数组是顺序存储的，而单链表是链式存储的。

链表的结构示意图：

单链表功能的实现

链表的基本操作：增、删、改、查。
单链表节点的插入和删除结构示意图：

单链表的初始化

单链表新结点的创建

单链表头插法

单链表的输出

单链表的查找

单链表修改

单链表的删除

• 单链表删除结点的补充：
  

单链表所有数据结点释放

源代码

#include<stdio.h>
#include<stdlib.h>
#define TYPE int //数据类型通过定义宏的形式来进行灵活运用
#define PRINT(a) printf("%d-->", a)
#define PRINTINDEX(b, c) printf("元素值是%d\t 位置是%d\n\n", b,c)
//结点的类型 声明结点的类型
struct NODE
{int data; //数据域struct NODE*next; //指针域保存下一个结点的地址 struct NODE*//next是一个成员
};//头结点类型 链表结构
struct List
{int len; //保存单链表中的结点个数（不包括头结点）struct NODE*front; //头指针 指向首元结点struct NODE*back; //尾指针 指向尾结点
};//创建单链表结构 从堆区来申请内存 把首地址返回给list
struct List*initList()
{//申请单链表结构内存struct List*temp = (struct List*)malloc(sizeof(struct List));//初始化单链表结构的成员temp->len = 0;temp->front = NULL;temp->back = NULL;return temp;
}//单链表结点的创建
struct NODE*CreateNode(TYPE data)
{struct NODE*temp = (struct NODE*)malloc(sizeof(struct NODE));temp->data = data; //把数据放进新结点temp->next = NULL; //防止野指针的出现return temp;
}//单链表结点的插入 头插法
void insertHead(struct List*head, TYPE data) //list表示要增加数据的单链表
{//1、作为第一个数据结点插入单链表中  头指针与尾指针都需要改变指向if (head->front == NULL) //或者head->len == 0{//1、要生成一个新的结点//2、让头指针和尾指针都指向这个新结点head->front = head->back = CreateNode(data);head->len++;//单链表结点的数量+1}else//不是第一个数据结点 只需改变头指针的指向{//生成一个新的结点struct NODE*S = CreateNode(data);//新结点S指针域保存原来的首元结点的地址S->next = head->front;//更新头指针，指向新结点Shead->front = S;head->len++; //单链表结点的数量+1}
}//输出单链表中所有的数据
void print(struct List*head)
{struct NODE*p = head->front;while (p != NULL){PRINT(p->data); //输出p指向的结点里面的数据p = p->next; //p指向下一个结点//p++;不能使用，单链表的物理内存不连续}printf("\n\n");
}//单链表元素的查找 根据指定值来查找元素，并且输出元素的位置
void find(struct List*head, int val) //head=list val表示要查找的数据
{struct NODE*p = head->front;//p指向首元结点int index = 0; //index表示指定元素的位置while (p != NULL){index++;if (p->data == val){PRINTINDEX(p->data, index);//输出元素值和位置}p = p->next; //p指向下一个结点}
}//单链表元素的修改 根据指定值
void modify(struct List*head, TYPE val, TYPE data)
//val要被修改的数据 data要修改成的数据
{struct NODE*p = head->front; //p指向首元结点while (p != NULL){if (p->data == val){p->data = data;//修改数据}p = p->next; //p指向下一个结点}
}//单链表的删除 根据指定值来删除数据
void delete(struct List*head, TYPE val) //head=list val表示要被删除的数据
{//1、要找到要被删除的数据struct NODE*p1 = head->front; //p指向首元结点struct NODE*p2 = NULL;while (p1 != NULL){if (p1->data == val) //找到了要被删除的数据{//情况一：p1指向是首元结点，需要更新头指针的指向if (p1 == head->front){head->front = p1->next; //让p1的直接后继结点成为新的首元结点free(p1);p1 = head->front; //让p1指向新的首元结点}//情况二：p1指向的是尾结点，需要更新尾指针else if (p1 == head->back){p2->next = p1->next; //给尾指针的结点域置空head->back = p2;free(p1);p1 = NULL;}//情况三：p1指向的结点是中间结点else{//p2的指针域指向p1的后继结点p2->next = p1->next;//释放删除结点free(p1);//更新p1p1 = p2->next;}}else //p2指向p1的前驱节点{p2 = p1;p1 = p1->next;}}
}//假设头结点也是struct node
void delete2(struct NODE*head, TYPE val) //val表示要被删除的数据
{struct NODE*p1 = head;struct NODE*p2 = head->next;while (p2 != NULL){if (p2->data = val){p1->next = p2->next;free(p2);p2->next = p1->next;}else{p1 = p1->next;p2 = p2->next;}}
}//整个单链表结点的释放 释放所有的数据结点 不是释放头节点
void AllClear(struct List*head)
{struct NODE*p = head->front; //p指向首元结点while (p != NULL){head->front = p->next;free(p);p = head->front;}head->front = head->back = NULL;//防止野指针出现
}int main()
{struct List *list = NULL; //list指向单链表 通过list来管理这个单链表list = initList(); //调用创建单链表函数//插入5个数据for (int j = 1; j <= 5; j++){insertHead(list, j);}print(list);//find(list, 4);//modify(list, 5, 9);//print(list);delete(list, 4);print(list);AllClear(list);print(list);return 0;
}