前言

本文主要介绍了链表，如何创建一个链表节点，以及如何创建链表。对链表的操作：增删查改等

一、链表

1.概念

        链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针链接次序实现的。

        链表结构多种多样，主要实现无头单项非循环链表以及带头双向循环链表

2.链表的实现

链表的节点中分为两个部分，一部分存储数据，一部分存储下一个节点的地址，故使用结构体来定义一个节点：

//链表的定义
typedef int SLTDataType;
typedef struct SListNode{SLTDataType data;struct SListNode * next;   //指向下一个节点的指针 所以类型为struct SListNode * 
}SLTNode; // 重命名为SLTNode

3.动态申请一个节点

SLTNode * BuySLTNode(SLTDataType x)  //形参为节点中的数据，返回值为链表类型的指针
{SLTNode * newnode = (SLTNode *)malloc(sizeof(SLTNode)); if(newnode == NULL){perror("malloc fail");exit(-1);}newnode ->data = x;newnode ->next = NULL;return newnode;   // 返回节点
}// 为什么不直接定义一个结构体类型的节点 SLTnode n1 ?
// SLTnode n1 为一个局部变量，这个变量是存储在栈上的，当函数结束，其中的变量会被销毁
// 要实现增删查改需要再使用，所以出了函数要还存在（全局变量或静态变量)
//malloc的是在堆上开辟的 出了函数不会被销毁 

4.创建一个链表

SLTNode * CreateList(int n) // 创建一个N个节点的链表
{//先动态申请一个节点SLTNode * newnode = BuySLTNode();//定义一个头，一个尾SLTNode * phead = NULL;SLTNode * ptail = NULL;//注意这里申请尾的作用是，不让头去迭代，否则等会找不到头for(int i=0;i<n;i++){if(phead == NULL){phead =ptail = newnode;}else{//插入ptail-next = newnode;//ptail变成新的尾巴ptail = newnode;}}return phead;
}

二、链表的增删查改

1.单链表的打印

实现的思想：找到链表的头部，并给一个临时的变量cur指针，循环打印，每打印一个，cur++，直到cur为尾节点,提示打印完成

void SListPrint(SLTNode * plist)
{SLTNode * cur = plist;while(cur!=NULL){printf("%d->%p",cur->data,cur->next);cur = cur->next;}printf("NULL");
}

2.单链表的尾插

实现思路：先创建一个新节点，找到原链表的尾，修改尾的指针指向新节点

2.1.经典错误:while(tail)

//经典错误
void SListPushBack(SLTNode * plist,SLTDataType x)
{//尾插 先创建一个新的节点SLTNode * newnode = BuySLTNode(x);struct SLTNode * tail = plist;//此时tail为一个局部指针变量，指向最后一个节点//现在修改tail指向newnode,，出了作用域tail销毁，newnode销毁//并没有将最后一个节点的指针的地址域修改为新节点的地址//尾插一定是最后一个节点链接新节点//链接新节点一定是将节点(结构体)的next指向下一个//  while(tail){tail = tail->next;}tail = newnode;//修改方法:找指针中的地址 当tail->next不为空，说明不是最后一个指针,循环，直到找到最后一个 //此时将新节点的地址赋值给tail的指针域,实现了尾插   while(tail->next){tail = tail->next;}tail->next = newnode;}

 2.2经典错误2:当链表为空的时候，没有尾指针，此时对null无法修改

void SListPushBack(SLTNode* pphead, SLTDateType x)
{//先创建一个要插入的节点SLTNode* newnode = BuySLTNode(x);SLTNode* tail = pphead;//判断是否为空链表if (pphead == NULL){pphead = newnode;}else{ tail = newnode;while (tail->next){tail = tail->next;}tail->next = newnode;} }

 2.3经典错误3：主函数中传入链表，如：SLTNode* plist ;使用上述方法传参给phead，phead与plist都为SLTNode * 的指针，此时形参为实参的临时拷贝，插入之后并没有返回到新的链表中

具体地，首先，看如下的交换函数Swap1,此时形参为实参的一份临时拷贝

int Swap1(int a, int b)
{int tmp = a;a = b;b = tmp;
}int main()
{int a = 1;int b = 2;Swap1(a,b);return 0;
} 

Swap2中形参为指针类型，分别指向a,b,实现指针指向内容的交换；Swap3中传入的是一个指针

使用二级指针去修改,二级指针解引用为一级指针，修改一级指针的指向，实现函数的交换

int Swap1(int* p1, int * p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}int main()
{int a = 1;int b = 2;Swap1(&a,&b);return 0;
} 

//传过来实参为一级指针类型，我使用二级指针接收,pp1指向p1,pp2指向p2void Swap3(int pp1, int pp2)
{int* tmp = *pp1;*pp1 = *pp2;   // p1指向原来p2指向的b*pp2 = tmp;
}int main()
{int a = 1;int b = 2;int * p1 = &a;int * p2 = &b;Swap3(*p1,*p2);return 0;
}

从栈帧的角度上理解，pushback之后，newnode传给了phead,函数结束后phead被释放，plist在另外的栈帧中,plist没有指向phead，要改变plist,需要把plist的地址传给phead，即使用SLTNode pphead为形参，&plist为实参,所以完整的尾插代码如下：

void SLTPushBack(SLTNode  pphead,SLTDataType x)
{SLTNode * newnode = BuySLTNode(x);SLTNode * tail = *pphead;if(*pphead == NULL){*pphead = newnode;}else{while(tail->next){tail = tail->next;}tail-next = newnode;}
}void Test()
{SLTNode * plist =CreateList(5);SLTPushBack(&plist,6);
} 

3.单链表的头插

实现思路：创建一个新节点，把新节点的指针域指向原来的头节点，修改链表的头节点为新节点。

void SListPushFront(SLTNode pplist, SLTDateType x)
{SLTNode* newnode = BuySLTNode(x);//先改变newnode的指针域，让newnode链接进来newnode->next = *pplist;//再改变新的链表头*pplist = newnode;
}

4.单链表的尾删

实现思路：找到链表的尾，释放此节点(是一种经典错误）

//经典错误
void SLTPopBack(SLTNode * phead)
{SLTNode * tail = phead;while(tail->next){tail = tail->next);}//释放的只是tail局部变量，没有改变链表的链接，要让前一个指针域置空//要改变链表，即需要改变结构体，需要结构体的指针才能改变free(tail);tail=NULL;

正确的实现方法：要看这个链表是否为空(使用assert断言），不为空：①使用双指针，找到倒数第二个，将倒数第二个的指针域置为空，释放倒数第一个；②使用while(tail->next->next)作为判断,不满足循环的时候，Tail为倒数第二个

当只有一个节点的时候，找不到倒数第二个，需要单独判断

void SListPopBack(SLTNode pplist)
{//先判断是否为空assert(*pplist);//判断是否为一个节点if((*pplist)->next = NULL){free(*pplist);*pplist=NULL;}else{//方法1，保存前一个/*  SLTNode * pre = *pplist;while(tail->next){pre->next = tail->next;tail = tail->next;}free(tail);pre->next = NULL;*///方法二，用倒数第二个判断while(tail->next->next){tail = tail->next;}free(tail->next);tail->next = NULL;
}

5.单链表的头删

实现思路：先判断这个链表是否为空，空了无法删除；如果不是空，找到链表的头节点，将头节点的指针域修改为下一个节点，将下一个节点变为新的头节点；当只有一个节点和多个节点的删除情况相同，指针域直接置空。

void SListPopFront(SLTNode pplist)
{//先判断是否为空assert(*pplist);//头删的步骤：找到头，找到头下一个，删除头节点，让下一个变为新的头//free(*pplist);//删除之前，要先保存下一个，不然删除之后找不到新的头SLTNode* next = (*pplist)->next;free(*pplist);*pplist = (*pplist)->next;
}

总结

        本文主要介绍了链表，以及对链表的操作：增删查改等，如有错误，敬请指正。