链表

链表是一种物理结构(储存结构)上不一定连续，不一定是顺序的存储结构，数据元素是通过链表中的指针链接次序实现的

链表的分类

链表有很多种类 两两匹配就一共有八种 这里主要介绍一下单链表(单向不带头不循环)

单链表

单链表的存储结构

图示：

链表中的结点一般都是在堆上申请的，从堆上申请的空间，按照一定的规则申请的，两次申请的空间也能相同也可能不相同。用一个指针就能找到下一个结点的空间地址了，从而形成线性关系

typedef int ElemType;
typedef struct SListNode
{ElemType data;struct SListNode* next;
}SLTNode;typedef SLTNode* LinkList;//定义链表

定义一个数据域和指针域。数据域用来存放数据，指针域的指针指向下一个结点的空间地址

单链表主要实现的接口函数

//创建新结点
SLTNode* NewSLTNode(ElemType x);
//尾插
void SLTPushBack(SLTNode** phead, ElemType x);
//头插
void SLTPushFront(SLTNode** phead, ElemType x);
//尾删
void SLTPopBack(SLTNode** phead);
//头删
void SLTPopFront(SLTNode** phead);
//单链表查找
SLTNode* SLTNodeFind(SLTNode* phead, ElemType x);
//在pos之前插入
void SLTInsert(SLTNode** phead, SLTNode* pos, ElemType x);
//在pos之后插入
void SLTInsertAfter(SLTNode* pos, ElemType x);
//删除pos位置
void SLTErase(SLTNode** phead, SLTNode* pos);
//删除pos位置后得
void SLTEraseAfter(SLTNode* pos);
//打印
void SLTNodePrintf(SLTNode* ps);

单链表尾插

单链表插入主要分为两种情况

• 没有结点，单链表是空的情况

• 有一个以上的结点

注意:
这里需要一个头指针(pehad 指向第一个结点的指针)来维护这个链表。否则将无法寻找到这个链表

void SLTPushBack(SLTNode** phead, ElemType x)
{//申请结点SLTNode* newnode = NewSLTNode(x);//空链表if (*phead == NULL){*phead = newnode;}//有一个以上的结点else{SLTNode* tail = *phead;//遍历找最后一个结点while (tail->next != NULL){tail = tail->next;}//连接新结点tail->next = newnode;}
}

链表结点的类型是struct SListNode* (结构体指针)类型，插入一个新元素，需要改变头指针的指向，所以实参需要传其地址，形参需要一个结构体指针的指针才可接受这个地址即二级指针
每次进行插入操作时都要申请结点，封装成函数，方便复用

动态申请新节点

SLTNode* NewSLTNode(ElemType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if(newnode == NULL){perror("malloc fail");eixt(-1);}newnode->data = x;newnode->next = NULL;return newnode;
}

单链表头插

头插可以只看作一种情况
空和非空的处理结果都一样

图解：

代码实现：

void SLTPushFront(SLTNode** phead, ElemType x)
{//申请结点SLTNode* newnode = NewSLTNode(x);//空和非空链表都可处理newnode->next = *phead;*phead = newnode;
}

单链表的尾删

尾删要注意三种情况，分别是

• 空链表
  错误处理
• 只有一个结点
  直接释放该结点即可

• 有两个结点以上的链表
  先找到最后一个结点，记录最后一个结点的前一个 然后释放最后一个结点，再将最后一个的前一个指针域置为NULL
  

代码实现：

void SLTPopBack(SLTNode** phead)
{//空链表assert(*phead);//只有一个结点if ((*phead)->next == NULL){free(*phead);*phead = NULL;}//有两个结点以上的链表else{SLTNode* tail = *phead;SLTNode* tailprev = NULL;//记录最后一个的前一个while (tail->next != NULL){tailprev = tail;tail = tail->next;}free(tail);tail = NULL;tailprev->next = NULL;}
}

单链表的头删

头删时要注意两种情况分别是

• 空链表
  错误处理
• 有一个或多个结点
  先将头指针移动到第二个结点(只有一个结点第二个结点即为NULL也符合逻辑)的位置，在释放该结点
  

代码实现：

void SLTPopFront(SLTNode** phead)
{//空assert(*phead);//一个和多个结点处理逻辑一样SLTNode* newhead = (*phead)->next;free(*phead);*phead = newhead;
}

在指定位置之前插入

位置由自己指定
比如链表元素 1 2 3 4 在2的位置之前插入6 链表变为1 6 2 3 4
插入之前首先要找到该元素结点的位置

单链表查找

SLTNode* SLTNodeFind(SLTNode* phead, ElemType x)
{assert(phead);SLTNode* pos = phead;while (pos){if (pos->data == x){return pos;}pos = pos->next;}//没有该元素return NULL;
}

然后根据查找到元素的结点位置进行插入

插入

在指定位置插入时要考虑以下情况

• 空链表
  不需要做处理 因为空链表找不到指定的位置
• 指定位置不存在
  错误处理
• 指定的位置是第一个结点
  复用头插即可
• 其他情况下插入
  申请新节点 找到pos的前一个结点 将新结点连接接起来
  

void SLTInsert(SLTNode** phead, SLTNode* pos, ElemType x)
{assert(*phead);assert(pos);if (pos == *phead){SLTPushFront(phead, x);}else{//申请结点SLTNode* newnode = NewSLTNode(x);//找pos的前一个SLTNode* cur = *phead;SLTNode* posprev = NULL;while (cur != pos){posprev = cur;cur = cur->next;}posprev->next = newnode;newnode->next = pos;}
}

在指定位置之后插

比如链表元素 1 2 3 4 在2的位置之后插入6 链表变为1 2 6 3 4
和指定位置之前插入一样，首先要找到该元素结点的位置在进行插入
在指定位置后插入要考虑以下情况

• 空链表
  不需要做处理 因为空链表找不到指定的位置
• 指定位置不存在
  错误处理
• 其他情况下插入

这里不用考虑插入的位置是最后一个结点的位置，这样首先要遍历链表进行判断，在复用尾插，代价太大。

代码实现：

void SLTInsertAfter( SLTNode* pos, ElemType x)
{assert(pos);//申请新结点SLTNode* newnode = NewSLTNode(x);newnode->next = pos->next;pos->next = newnode;
}

删除指定位置元素

删除指定位置和插入指定位置一样，需要先查找到该元素结点的位置
比如链表元素 1 2 3 4 删除2的位置链表变为 1 3 4
删除pos位置要考虑以下情况

• 空链表
  不需要做处理 因为空链表找不到指定的位置
• 指定位置不存在
  错误处理
• 指定位置是第一个结点
  复用头删
• 其他情况下删除指定位置

代码实现：

void SLTErase(SLTNode** phead, SLTNode* pos)
{//空链表assert(*phead);// 指定位置不存在assert(pos); //复用头删if (pos == *phead){SLTPopFront(phead);}else{//找pos前一个SLTNode* cur = *phead;SLTNode* prevpos = NULL;while (cur != pos){prevpos = cur;cur = cur->next;}prevpos->next = pos->next;free(pos);}
}

删除指定位置之后的元素

比如链表元素 1 2 3 4 删除2之后位置 链表变为 1 2 4
删除指定位置之后的元素分别要考虑以下情况

• 空链表
  不需要做处理 因为空链表找不到指定的位置
• 指定位置不存在
  错误处理
• 是否是尾结点
  错误处理
• 其他情况下删除指定位置之后

代码实现：

void SLTEraseAfter(SLTNode* pos)
{assert(pos);assert(pos->next);SLTNode* posnesxt = pos->next;pos->next = posnesxt->next;free(posnesxt);posnesxt = NULL;
}

顺序输出链表

void SLTNodePrintf(SLTNode* phead)
{SLTNode* tail = phead;while (tail != NULL){printf("%d " , tail->data);tail = tail->next;}printf("\n");
}

销毁单链表

void SLTNodeDestory(SLTNode** phead)
{assert(*phead);SLTNode* cur = *phead;SLTNode* curnext = NULL;while (cur != NULL){curnext = cur->next;free(cur);cur = curnext;}
}

顺序表和单链表的区别

不同点	顺序表	链表
存储空间上	物理上一定连续	逻辑上连续，物理上不一定连续
随机访问	O(1)	O(n)
任意位置插入或删除	可能需要挪动数据，效率太低O(n)	只需要修改指针指向即可
插入元素	动态顺序表，空间不够时需要扩容	没有容量概念，用多少申请多少
应用场景	元素高效存储+频繁访问	频繁在任意位置插入和删除

关于指针传参

当你传递一个参数给函数的时候，这个参数会不会在函数内被改动决定了函数参数形式

• 如果需要改动，则需要传指向这个参数的指针
  比如单链表的头插，尾插、头删等，都需要改变头指针的指向位置，也就是这个参数需要被改动，那么传这个参数的指针
• 如果不用被改动，可以直接传递这个参数
  比如单链表中的查找和打印，直接传参数就可以了，查找和打印，不用修改里面的内容