[数据结构与算法]数据结构与算法（4）不带头单链表

在今天的学习中，将会介绍链表的概念，以及单链表的增删查改功能的实现，以及和顺序表的对比

不带头单向单链表

• • 前言
  • 链表的实现：
  • 0.购买节点
  • 1.链表头插
  • 2.链表尾插
  • 3.链表头删
  • 4.链表尾删
  • 5.任意位置之后插入
  • 6.链表查找
  • 7.链表打印
  • 8.链表销毁
  • 总结
  • 源码

前言

链表也是线性表的一种，但是在物理结构上链表并非是连续的，也没有什么顺序可言，那他的线性体现在哪里呢？体现在逻辑顺序，在逻辑链表中的节点是连续的，一个接一个的，这种连续是通过指针实现的。

逻辑上链表是这样连在一起的，（地址都是瞎编的）但是可以注意到，地址并不是连续的，所以在内存中并不是连续的，有可能这样的：

画的有点简陋，但就是这么个意思，在内存里，节点可能隔了很多很多字节，并不是连续的。

链表的分类：
链表有带头的不带头的，双向的单向的，循环的不循环的，那就是有八种，这里我们先介绍其中的不带头的单链表，这种链表结构上比较简单，但是实现上并不是很简单（带头双向循环最简单），同时不带头单向的单链表在其他的数据结构中也有应用，我们先介绍它。

链表的实现：

看了上面的图解以后，我们知道，链表的节点由两部分构成：数据区和指针区，指针区存储的是下一个节点的地址信息，所以节点的结构体就可以定义为：

typedef int SLTDateType;    
typedef struct SListNode    
{    
  SLTDateType data;    
  struct SListNode* next;    
}SListNode; 

下面就是对单链表功能的实现

0. 购买节点

1. 链表头插

2. 链表尾插

3. 链表头删

4. 链表尾删

5. 链表任意位置之后插入

6. 链表查找

7. 链表打印

8. 链表销毁

0.购买节点

SListNode* BuySListNode(SLTDateType x)    
{          
  SListNode* ret = (SListNode * )malloc(sizeof(SListNode));    
  if(ret == NULL)    
  {                                                                               
    return NULL;    
  }                               
  ret->data = x;    
  ret->next =NULL;                                        
  return ret;    
}

1.链表头插

void SListPushFront(SListNode** pplist, SLTDateType x)
{
  SListNode* newnode = BuySListNode(x);
  if(*pplist == NULL)
  {
    *pplist = newnode;
  }
  else 
  {
    newnode->next = *pplist;
    *pplist = newnode;
  }
}

注意看啊，我们这里传的是一个二级指针进去，不是一级指针，这是为什么呢？因为我们的链表是不带头节点的链表啊，所以无论是哪一种都要考虑一种情况，那就是第一个节点的值为空的情况，这时候整个链表还没有创建，例如SListNode * plist = NULL,这时候如果我们的插入函数的参数是一级指针的话：void SListPushFront(SListNode* pplist, SLTDateType x)，我们相当于是把NULL传给了里面的pplist，就像这样：

注意看plist 和pplist的地址并不一样，pplist只是一个和plist值一样的复制品而已，这时候我们给pplist后面链接上再多的节点也没有用，因为函数一结束，pplist就会被销毁了，他的使命就结束了。所以我们不能传一级指针进去，那如果我们传二级指针进去呢？也就是&plist，那这时候在链表没有节点的时候，我们就可以 *pplist，这和我们外面的plist是一样的：

这时候你想链接就可以了，聊到这我们在说说带头节点的单链表，如果是带头结点的单链表我们就可以不用传二级指针了，为什么？因为你开始已经有一个头节点了。

我们看，这时候函数里的指针地址是多少已经不重要了，最重要的是phead的值和复制是一样的，那么我在函数里对0x11223344进行操作自然和在外面一样。
这也是带头的和不带头的区别之一。

2.链表尾插

void SListPushBack(SListNode** pplist, SLTDateType x)
{
  SListNode* newnode = BuySListNode(x);
  if(*pplist==NULL)
  {
    *pplist = newnode;
  }
  else 
  {
    SListNode*tail = *pplist;
    while(tail->next!=NULL)
    {
      tail = tail->next;
    }
    tail->next = newnode;
  }
}     

在尾插中，如果链表本身不为空，我们就要遍历链表，找到链表的结尾，在这里注意 while中的条件是tail->next不为空而不是tail不为空如果是tail不为空，你退出循环的时候tail就和我们原本的链表没有关系了，只是一个空指针而已。

3.链表头删

void SListPopFront(SListNode** pplist)
{
  SListNode * first = *pplist;
  if(first == NULL)
  {
    return ;
  }
  else if(first->next == NULL)
  {
    free(first);
    *pplist = NULL;
  }
  else 
  {
    SListNode *next = first->next;
    free(first);
    *pplist = next;
  }
}

在这里进行删除之前链表有三种情况，一种是链表本身为空，另一是链表只有一个节点，最后是有多个节点的链表，不同的情况我们有不同的解决方式，有多个链表时要注意，在头删之前我们要先把头部之后的链表储存起来，要不然头删之后我们的链表就找不到了。

4.链表尾删

// 单链表的尾删    
void SListPopBack(SListNode** pplist)
{
  SListNode * tail = *pplist;
  SListNode * prev = NULL;
  if(tail == NULL)
    return;
  else if(tail->next == NULL)
  {
    free(tail);
    *pplist = NULL;
  }
  else 
  {
    while(tail->next)
    {
      prev = tail;
      tail = tail->next;
    }
    free(tail);
    tail = NULL;
  }                                                                               
}

尾删也要分成三种情况，同时要储存前一个节点的地址，我们把最后一个节点free了，这时候节点是一个野指针了，你前一个节点还链接着，会出现错误，所以我们要保留前一个节点的地址，然后让他为空。

5.任意位置之后插入

void SListInsertAfter(SListNode* pos, SLTDateType x)
{
  assert(pos);
  SListNode* next = pos->next;
  SListNode * newnode = BuySListNode(x);
  pos->next = newnode;
  newnode->next = next;
}

没啥说的，跟头插也差不多，值得注意的是为什么我们是在任意位置之后插入，而不是之前呢？这是因为，单向链表只储存后一个节点的值，不储存前一个节点的值，所以我们链接在后面，还有一点
如果这个任意位置之后插入的函数是这样的：

void SListInsertAfter(SListNode* pos, SLTDateType x)
{
  assert(pos);
  SListNode * newnode = BuySListNode(x);
  newnode->next = pos->next;//1
  pos->next = newnode;//2
}

标号1和2的语句顺序可以变吗？为什么？
当然是不可以变的，因为是在任意位置处的节点(不是头尾)，它都有前一个节点和后一个节点，你如果让pos->next = newnode;先执行，那你就和后面的节点没联系了，你就找不到后面的节点了：

原先是这样链接一块的，现在我在2和3中间插入一个值为0的节点，先执行pos->next = newnode;

你想给0节点赋3节点的地址也不行，因为原本存储3节点的2-》next的值已经被你覆盖了，找不到了。

6.链表查找

SListNode* SListFind(SListNode* plist, SLTDateType x)
{
  SListNode * cur = plist;
  while(cur)
  {
    if(cur->data == x)
      return cur;
    cur = cur->next;
  }
  return NULL;
}

7.链表打印

void SListPrint(SListNode* plist)
{
  SListNode * cur = plist;
  while(cur)
  {
    printf("%d->",cur->data);
    cur = cur->next;
  }
  printf("NULL\n");
}

8.链表销毁

void SListDestroy(SListNode* plist)
{
  assert(plist);
  SListNode * cur = plist;
  while(plist)
  {
    cur = plist->next;
    free(plist);                                                                  
    plist = cur;
  }
}

总结

链表和顺序表相比，内存浪费的更少，用几个我们就有几个，缺点就是不能用下标的方式访问，是链式访问的每回都要遍历，希望大家在学习的时候多多画图，真的可以加深理解！

源码

Slist.h

// slist.h
#include<stdio.h>
#include<assert.h>            
#include<stdlib.h>                      
typedef int SLTDateType;
typedef struct SListNode
{
  SLTDateType data;               
  struct SListNode* next;             
}SListNode;                         
 
// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插                                                                                                                                                                           
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删                 
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入？
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置？
void SListEraseAfter(SListNode* pos);
// 单链表的销毁
void SListDestroy(SListNode* plist);

Slist.c

#include"Slist.h"

SListNode* BuySListNode(SLTDateType x)
{
  SListNode* ret = (SListNode * )malloc(sizeof(SListNode));
  if(ret == NULL)
  {
    return NULL;
  }
  ret->data = x;
  ret->next =NULL;
  return ret;
}
// 单链表打印    
void SListPrint(SListNode* plist)
{
  SListNode * cur = plist;
  while(cur)
  {
    printf("%d->",cur->data);
    cur = cur->next;
  }
  printf("NULL\n");
}
// 单链表尾插    
void SListPushBack(SListNode** pplist, SLTDateType x)
{
  SListNode* newnode = BuySListNode(x);
  if(*pplist==NULL)
  {
    *pplist = newnode;
  }
  else  
  {
    SListNode*tail = *pplist;
    while(tail->next!=NULL)                                                                                                                                                               
    {
      tail = tail->next;
    }
    tail->next = newnode;
  }
}
// 单链表的头插   
//为什么要用二级指针呢，就像这个链表中的头插，如果没有传二级指针，你正在进行的操作就是对一个plist的
//复制品进行操作复制品和plist都指向一个地方，但是复制品链接的不是plist链接的，我们最后用的是plist（复制品和plist的值一样，地址不一样）
//正是因为这样，所以我们才有了带头结点的单链表和不带头的单链表，如果开始我们给的值就是另一个的指针的地址，那就没问题了
void SListPushFront(SListNode** pplist, SLTDateType x)
{
  SListNode* newnode = BuySListNode(x);
  if(*pplist == NULL)
  {
    *pplist = newnode;
  }
  else 
  {
    newnode->next = *pplist;
    *pplist = newnode;
  }
}
// 单链表的尾删    
void SListPopBack(SListNode** pplist)
{
  SListNode * tail = *pplist;
  SListNode * prev = NULL;
  if(tail == NULL)
    return;
else if(tail->next == NULL)
  {
    free(tail);                                                                                                                                                                           
    *pplist = NULL;
  }
  else 
  {
    while(tail->next)
    {
      prev = tail;
      tail = tail->next;
    }
    free(tail);
    tail = NULL;
  }
}
// 单链表头删    
void SListPopFront(SListNode** pplist)
{
  SListNode * first = *pplist;
  if(first == NULL)
  {
    return ;
  }
  else if(first->next == NULL)
  {
    free(first);
    *pplist = NULL;
  }
  else 
  {
    SListNode *next = first->next;
    free(first);
    *pplist = next;
  }
}                                                                                                                                                                                         
// 单链表查找    
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
  SListNode * cur = plist;
  while(cur)
  {
    if(cur->data == x)
      return cur;
    cur = cur->next;
  }
  return NULL;
}
// 单链表在pos位置之后插入x      
// 分析思考为什么不在pos位置之前插入？      
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
  assert(pos);
  SListNode* next = pos->next;
  SListNode * newnode = BuySListNode(x);
  pos->next = newnode;
  newnode->next = next;
}
// 单链表删除pos位置之后的值      
// 分析思考为什么不删除pos位置？      
void SListEraseAfter(SListNode* pos)
{
  assert(pos);
  SListNode* next = pos->next;

  if(next != NULL)
  {
    SListNode * nextnext = next->next->next;
    free(next);
    pos->next = nextnext;
  }
}
// 单链表的销毁               
void SListDestroy(SListNode* plist)
{
  assert(plist);
  SListNode * cur = plist;
  while(plist)
  {
    cur = plist->next;
    free(plist);
    plist = cur;
  }
}