单链表
单链表
链表的基本概念
链表别名链式存储结构、单链表，用于存储结构关系为一对一的数据。与顺序表不一样的地方在于，链表并不限制存储数据的物理状态，使用链表存储数据是随机存放位置的。
数据元素随机存储数据，并通过指针表示数据之间逻辑关系的存储结构就是链式存储结构。
链表的节点
从上面的图片可以看出，链表中每个数据的组成分为两个部分：
- 数据元素本身，其所在区域称为
数据域。 - 指向直接后继元素的指针所在区域称为指针域。
和顺序表一样都要使用到结构体来定义每个存储节点：
typedef struct Link{
char elem;//代表数据域
struct Link * next;//代表指针域，指向直接后继元素
}link;//link为节点名，每个节点都是一个link结构体
由于指针域指向的也是一个节点，所以用struct Link *来声明。
头节点，头指针和首元节点
实际上上面的图并不能表示出完整的链表
- 头指针：一个普通的指针，它的特点是永远指向链表中的第一个元素节点的位置，也就是说头指针用于指明链表的位置，便于后期找到链表并使用链表中的数据。
- 节点：
- 头节点：其实就是一个不存储任何数据的空节点，通常作为链表的第一个节点，对于链表来说，头节点并不是必须的，它的出现只是为了解决一些实际问题。
- 首元节点：由于头节点（也就是空节点）的缘故，链表中存储数据的第一个节点就被称为首元节点，首元节点这个名词只是对第一个存数据的节点的一个称呼，没有实际意义。
- 其他节点：链表中其他的节点。
需要注意的是，如果有头节点，头指针指向头节点，如果没有头指针指向首元节点。
链表的创建
创建一个链表需要做如下工作：
- 声明一个头指针（如果有必要，可以声明一个头节点）
- 创建多个存储数据的节点，在创建的过程中，要随时与其前驱节点建立逻辑关系。
link * initLink(){
link * p = NULL;//创建头指针
link * temp = (link *)malloc(sizeof(link));//创建首元节点
//首元节点初始化
temp->elem = 1;
temp->next = NULL;
p = temp;//头指针指向首元节点
// 第二个节点开始创建
for(int i=2;i<5;i++){
//创建一个新节点并初始化
link * a = (link *)malloc(sizeof(link));
a->elem = i;
a->exit = NULL;
//将temp节点指向新建立的a的节点建立逻辑关系
temp->next = a;
//指针temp指针一直指向新链表中的最后一个节点，在这里写temp=a也对
temp=temp->next;
}
//返回建立的节点，只返回头指针p即可，我们需要通过头指针来找到这个链表。
return p;
}
如果想要创建一个含有头节点的链表：
link * initLink(){
link * p = (link *)malloc(sizeof(link));
link * temp = p;//声明一个指针指向头节点
//生成链表
for(int i;i<5;i++){
link * a = (linnk *)malloc(sizeof(link));
a->elem = i;
a->next = NULL;
temp->next = a;
temp = temp->next;
}
return p;
}
和顺序表差不多，我们只需要调用函数就可以创建链表：
#include <stdio.h>
#include <stdlib.h>
//链表中节点的结构
typedef struct Link{
char elem;
struct Link * next;
}link;
//初始化链表的函数
link * initLink(){
link * p = NULL;
link * temp = (link *)malloc(sizeof(link));
temp->elem = 1;
temp->next = NULL;
p = temp;
for(int i=2;i<5;i++){
link * a = (link *)malloc(sizeof(link));
a->elem = i;
a->next = NULL;
temp->next = a;
temp = temp->next;
}
return p;
}
void display(link *p){
link * temp = p;//将temp指针重新指向头节点
//只要temp指针指向的节点的next不是NULL，就执行输出语句。
while(temp){
printf("%d",temp->elem);
temp=temp->next;
}
printf("\n");
}
int main(){
//初始化链表（1.2.3.4）
printf("初始化链表为：\n");
link * p=initLink();
display(p);
return 0;
}
程序运行结果：
初始化链表为：
1234
但是我们要是使用具有头节点的方式创建新链表，则我们的输出有些变化就是display函数做出相应的修改：
void display (link *p){
link * temp = p//这个不变，还是将temp指针重新指向头节点。
//只要temp指针指向的节点的next不是NULL，就执行输出语句。
while(temp->next){
temp=temp->next;
printf("%d",temp->elem);
}
printf("\n");
}
单链表还有一些其他的基本操作，而这些基本操作都建立在我们已经建立好一个链表的基础上进行操作。
链表插入元素
同顺序表一样，向链表中增添元素，根据添加的位置不同，分为三种情况：
- 插入到链表头部（头节点之后），作为首元节点；
- 插入到链表中间某个位置
- 插入到链表的最末端，作为链表中最后一个数据元素。
虽然插入元素的位置不是固定的，但是链表插入元素的思想是固定的：
- 将新节点的next指向插入位置后的节点；
- 将插入位置之前的节点的next指向插入节点；
需要注意的是链表中插入元素必须先执行步骤1，再执行步骤2；若反之执行，先执行步骤2那么就会导致，新插入的元素找不到再插入点之后的元素，除非再添加一个指针，作为插入点之后元素的头指针。如果不这样做，我们将失去插入点之后的所有元素，也就是无法再执行步骤1。
//p为原始链表，elem为新插入元素，add为新插入位置
link * insertLink(link * p, int elem,int add){
link * temp = p;//创建临时节点temp
//首先要找到插入位置的上一个节点
for(int i=1;i<add;i++){
temp = temp->next;
if(temp == NULL){
printf("插入位置无效\n");
return p;
}
}
//创建插入节点
link * c = (link *)malloc(sizeof(link));
c->elem=elem;
//像链表中插入节点
c->next = temp->next;
temp->next = c;
return p;
}
链表中删除元素
从链表中删除指定元素时，实则就是将存有该数据元素的节点从链表中摘除，但作为一名合格的程序员，要对存储空间负责，对不再使用的空间要及时进行释放：
- 将节点从链表中摘下来；
- 手动释放掉节点，回收被节点占用的存储空间
实际上把节点从链表中摘除出来非常简单只需要找到这个节点的下一个节点，然后将本节点的上一个节点next指向这个节点的下一个节点就ok了。
temp->next = temp->next->next;
//p为原始链表,add为要删除元素的值
link * delElem(link * p, int add){
link * temp = p;
//遍历到被删除数据的上一个节点
for(int i=0;i<add;i++){
temp = temp->next;
if(text->next == NULL){
printf("没有该节点\n");
return p;
}
link * del = temp->next;//单独设置一个指针指向被删除节点，以防丢失。
temp->next = temp->next->next;//删除某个节点的方法就是更改前一个结点的指针域。
free(del);//手动释放该节点，防止内存泄漏。
return p；
}
}
链表查找元素
在链表中查找指定数据结构，我们常用的查找方法一般是从头遍历到我们要查找的节点，如果没有找到我们要查找的元素，则执行到表的最末端，也就是执行到NULL，也就是没有找到我们要查找的元素，然后结束循环，要么返回我们要查找的东西，要么返回执行错误。
//p为原链表，elem表示被查找元素
int selectElem(link * p , int elem){
//新建一个节点t，初始化头指针p
link * t = p;
int i = 1;
//由于头结点的存在，因为while中的判断t->next
while(t->next){
t=t->next;
if(t->elem==elem){
return i;
}
i++;
}
//程序要是执行到这里表示执行失败
return -1;
}
在遍历具有头节点的链表时，要避免头节点对程序的影响，我们尽量在具有头节点的链表中使用上述程序编写。
链表更新元素
和顺序表差不多，都是查找到要更新的元素，然后替换它，我们可以调用上面的查找程序，然后更改元素。
//更新函数，其中 add 表示更改节点在链表中的位置，newElem为新的数据域的值
link * amendElem(link * p , int add , int newElem){
link * temp = p;
temp = temp->next;//在遍历之前，temp指向首元节点
//遍历到待更新的节点
for(int i = 1 ; i<add ; i++){
temp = temp ->next;
}
temp->elem = newElem;
return p;
}
结合所有的代码，我把所有的代码写在一个程序中：
#include <stdio.h>
#include <stdlib.h>
typedef struct Link{
int elem;
struct Link * next;
}link;
link * initLink(){
link * p = (link *)malloc(sizeof(link));//创建一个头节点
link * temp = p;//声明一个指针指向头节点，用于遍历链表
//生成链表
for(int i = 1; i < 5;i++){
link *a = (link *)malloc(sizeof(link));
a->elem = i;
a->next = NULL;
temp->next = a;
temp = temp->next;
}
return p;
}
link * insertElem(link * p,int elem , int add){
link * temp = p;//建立临时节点temp
//首先找到要插入位置的上一个节点
for(int i = 1; i < add ; i++){
temp = temp->next;
if(temp == NULL){
printf("插入位置无效\n");
return p;
}
}
//创建插入节点C
link * c = (link *)malloc(sizeof(link));
c->elem = elem;
//向链表中插入节点
c->next = temp->next;
temp->next = c;
return p;
}
link * delElem(link * p,int add){
link * temp = p;
//遍历到要删除的节点上一个节点
for(int i = 0 ; i<add ; i++){
temp = temp->next;
if(temp->next == NULL){
printf("没有该指针\n");
return p;
}
}
link * del = temp->next;//单独设置一个节点指向要删除的节点
temp->next = temp->next->next;//删除某个节点的方法就是更改前一个结点的指针域
free(del);//手动释放掉节点
return p;
}
int selectElem(link * p ,int elem){
link * t = p;
int i = 1;
while(t->next){
t = t->next;
if(t->elem == elem){
return i;
}
i++;
}
return -1;
}
link * amendElem(link * p, int add, int newElem){
link * temp = p;
temp = temp -> next;//temp指向首元节点
//temp指向被删除节点
for(int i=1; i<add; i++){
temp = temp->next;
}
temp->elem = newElem;
return p;
}
void display(link *p){
link * temp = p;//将temp指向头节点
//只要temp指针指向的不是NULL就执行printf
while(temp->next){
temp = temp->next;
printf("%d",temp->elem);
}
printf("\n");
}
int main(){
printf("初始化链表为：\n");
link * p = initLink();
display(p);
printf("在第四的位置插入元素5：\n");
p = insertElem(p,5,4);
display(p);
printf("删除元素3：\n");
p = delElem(p,3);
display(p);
printf("查找元素2的位置为：\n");
int address = selectElem(p,2);
if(address == -1){
printf("没有这个元素：\n");
}
else {
printf("元素二的位置为：%d\n", address);
}
printf("更改第三的位置上的数据为7：\n");
p = amendElem(p,3,7);
display(p);
return 0;
}
程序运行结果：
初始化链表为：
1234
在第四的位置插入元素5：
12354
删除元素3：
1234
查找元素2的位置为：
元素二的位置为：2
更改第三的位置上的数据为7：
1274