[数据结构与算法]数据结构 II 深入理解单链表的实现

数据结构就是定义出某种结构：像数组结构、链表结构、树形结构等，实现数据结构就是我们主动去管理增删查改的实现函数

链表的概念理解

概念：链表就是一个一个的节点，按需去堆上申请内存，要一个申请一个，先理解 “无头单向非循环链表” 之后，再去理解其他链表结构就会很容易，单链表的价值也便于我们学习哈希桶

在编程实现之前，我们要先知道链表在内存中的真实存储过程，本质上可以指向下一个节点是因为我们前一个存着下一个的地址

下面我们仍然在vs环境下编程实现动态顺序表，这里我们分文件编写，在头文件 SList.h 进行声明，在 SList.c 当中进行具体的函数定义，在 test.c 当中的做具体的测试实现

先来了解一下头文件 SeqList.h 当中接口

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//typedef 使用typedef想换类型时可以将int改成double、char等
typedef int SLTDateType;

typedef struct SListNode
{
  SLTDateType data;//定义date存数据
  //每个数据中有一个指针指向下一个，否则找不到
  struct SListNode* next;
} SListNode;

//链表有一个指针 指向第一个节点 第一个又存下一个 一直到最后一个指针指向空 

SListNode* BuyListNode(SListNode* phead);//增加新节点函数

void SListPrint(SListNode* phead);//打印函数，一开始传一个指针，指向第一个

void SListPushBack(SListNode** pphead,SLTDateType x);//尾部插入

void SListPopBack(SListNode** pphead);//尾部删除

void SListPushFront(SListNode** pphead, SLTDateType x);//头部插入

void SListPopFront(SListNode** pphead);//头部删除

void SListDestroy(SListNode** pphead);//置空函数，释放开辟空间

SListNode* SListFind(SListNode* phead, SLTDateType x);//查找某个节点位置

void SListInsert(SListNode** pphead, SListNode* pos, SLTDateType x);
//指定位置之前插入

void SListInsertAfter(SListNode* pos, SLTDateType x);//指定位置之后插入

void SListErase(SListNode** pphead, SListNode* pos);//删除指定位置

void SListEraseAfter(SListNode* pos);//删除指定位置后面数据

我们知道，函数的定义方法是非常重要的，也是我们需要深入理解的，下面我们详细学习在 SList.c 当中具体的函数实现

增加新节点函数定义

SListNode* BuyListNode(SLTDateType x)//增加新节点函数
{
  //考虑当链表为空时，所以先开辟一个新的节点
  SListNode* newnode = 
   (SListNode*)malloc(sizeof(SListNode));
  if (newnode == NULL)
  {
    printf("malloc fail\n");
    exit(-1);
  }
  newnode->data = x;
  newnode->next = NULL;

  return newnode;//返回新节点
}

打印函数定义

每一个节点当中都会有一个next存储下一个节点的地址

void SListPrint(SListNode* phead)//打印链表函数
{
  SListNode* cur = phead;
   //此时cur是等于传过来指向头节点的指针
   //里面有一个数据存着第一个节点的地址
  while (cur != NULL)
  {
   printf("%d->", cur->data);//使用指针获取头节点数据
   cur = cur->next;
  //每一个节点当中都会有一个next存储下一个节点的地址
  //通过地址就可以找到下一个节点
  }
  printf("NULL\n");
}

尾部插入函数定义

尾节点标志 next 是指向空的

void SListPushBack(SListNode** pphead, SLTDateType x)//尾部插入节点
{
  assert(pphead);
  //考虑当链表为空时，所以先开辟一个新的节点
  SListNode* newnode = BuyListNode(x);
  //调用上面开辟新节点函数
  if (*pphead == NULL)//如果为空，就不找尾
  {
    //让第一个指针指向新节点，存新节点的地址
    *pphead = newnode;
  }
  else// //不为空走下面
  {
    SListNode* tail = *pphead;//定义尾指针，先指向头，从头开始往后找
    while (tail->next != NULL)//不为空一直找
    {
      tail = tail->next;
    }
    //到这找到尾，下面将新节点的地址给刚才的尾节点
    tail->next = newnode;//只要尾节点tail的next指向新节点就可以
  }
}

尾部删除函数定义

//尾删除也要传二级指针，最后要修改头指针
void SListPopBack(SListNode** pphead)//尾部删除
{
 assert(*pphead != NULL);//判断不为空

 if ((*pphead)->next == NULL)
 {
	free(*pphead);
	*pphead = NULL;
 }
 else
 {
  SListNode* prev = NULL;//在多定义一个指针保存尾指针
  //此时* pphead第一个指针地址
  SListNode* tail = *pphead;
  while (tail->next != NULL)//我们找尾
  {
 	prev = tail;//每次走之前先把我给前面一个prev
 	tail = tail->next;
  }

  //到这里找到尾
  // 注意删除之前我们要先将尾的前一个指向空，否则就成野指针了
  free(tail);
  tail = NULL;
  prev->next = NULL;
  }
}

头部插入函数定义

先定义一个新节点 把第一个节点的地址给新节点?

void SListPushFront(SListNode** pphead, SLTDateType x)
{
 assert(pphead);
 SListNode* newnode = BuyListNode(x);//调用上面开辟新节点函数
 newnode->next = *pphead;//把第一个节点的地址给新节点
 *pphead = newnode;//然后成为新的头
}

头部删除函数定义

void SListPopFront(SListNode** pphead)//头部删除
{
 assert(*pphead != NULL);
 SListNode* next = (*pphead)->next;//要先取phead的下一个
 free(*pphead);
 *pphead = next;
}

置空函数定义

置空函数一般会放在我们进行插入或删除的函数最后，释放我们在堆上申请的空间，将其还给操作系统，另外也会相应的进行检查越界等问题

void SListDestroy(SListNode** pphead)//置空函数，释放开辟空间
{
  assert(pphead);
  //空间不连续，都要释放，不然内存泄漏
  SListNode* cur = *pphead;//从头开始置空
  while (cur)//不为空一直走
  {
   //先找到下一个节点位置在删除
   SListNode* next = cur->next;
   free(cur);
   cur = next;
  }
  *pphead = NULL;
}

我们先用上面接口实现一个在 test.c 当中的第一个测试案例TestSList 1?

void TestSList1()
{
//将开始链表给空
SListNode* plist = NULL;
SListPushBack(&plist, 1);//尾插 1 2 3 4 5 6
SListPushBack(&plist, 2);
SListPushBack(&plist, 3);
SListPushBack(&plist, 4);
SListPushBack(&plist, 5);
SListPushBack(&plist, 6);
SListPrint(plist);//打印1->2->3->4->5->6->NULL
	
SListPopBack(&plist);//尾删2次
SListPopBack(&plist);

SListPrint(plist);//打印1->2->3->4->NULL

SListPushFront(&plist, 1);//头插数据1 2 3 4
SListPushFront(&plist, 2);
SListPushFront(&plist, 3);
SListPushFront(&plist, 4);
SListPrint(plist);//打印4->3->2->1->1->2->3->4->NULL

SListPopFront(&plist);//头删2次
SListPopFront(&plist);

SListPrint(plist);//打印2->1->1->2->3->4->NULL

SListDestroy(&plist);//置空函数，放在最后释放开辟空间
}
int main()
{
TestSList1();
return 0;
}

注意：这里plist（实参）和phead（形参) 都指向第一个节点的地址

下面我们我们接着详细学习剩下函数接口在 SList.c 当中具体的函数实现

查找某个节点位置

SListNode* SListFind(SListNode* pphead, SLTDateType x)//查找某个节点
{
//遍历链表，差找值为x节点
SListNode* cur = pphead;
while (cur)
{
 if (cur->data == x)
 {
 return cur;//找到了就返回
 }
 else 
 {
 cur = cur->next;//没找到一直找
 }
}
 return NULL;//最后未找到返回空
}

这里我们是用使用返回节点的指针（SListNode* pphead）的find进行查找，先用上面查找接口实现一个在 test.c 当中的第2个测试案例TestSList 2

void TestSList2()
{
//将开始链表给空
SListNode* plist = NULL;
SListPushFront(&plist, 1);//头插数据1 2 3 4 2
SListPushFront(&plist, 2);
SListPushFront(&plist, 3);
SListPushFront(&plist, 4);
SListPushFront(&plist, 2);
SListPrint(plist);//打印2->4->3->2->1->NULL
	
//查找多个数据时
SListNode* pos = SListFind(plist, 2);
int i = 1;
while (pos)
{
printf("第%d个pos节点:%p->%d\n",i++,pos,pos->data);
//打印第1个pos节点:0000020C088EF120->2
//打印第2个pos节点:0000020C088EF580->2
pos = SListFind(pos->next, 2);
//这里从第一个2后面继续往后找
}
	 
//注意：
//使用返回节点的指针的find除了查找还可以修改pos位置数据
pos = SListFind(plist, 3);//修改3—>30
if (pos)
{
 pos->data = 30;
}
SListPrint(plist);//打印2->4->30->2->1->NULL

SListDestroy(&plist);//置空函数，放在最后释放开辟空间
}
int main()
{
 TestSList2();
 return 0;
}

指定位置之前插入

//指定位置之前插入
void SListInsert(SListNode** pphead, SListNode* pos, SLTDateType x)
{
 assert(pphead);
 assert(pos);
 //光有pos位置还不行
 //我们还要有pos前一个位置，让前一个位置指向新的数据节点，新的节点位置在指向pos
  
 //第一步,先准备一个新节点出来
 SListNode* newnode = BuyListNode(x);//调用上面开辟新节点函数
 if (*pphead == pos)//判断头插的情况
 {
  newnode->next = *pphead;
  *pphead = newnode;
 }
 else
 {
  //找pos的前一个位置
  SListNode* posprev = *pphead;//定义posorev从头找
  while (posprev->next != pos)
  {
  posprev = posprev->next;
  }
  posprev->next = newnode;//让前一个位置指向新的数据节点
  newnode->next = pos;//新的节点位置在指向pos
 }

}

指定位置之后插入

void SListInsertAfter(SListNode* pos, SLTDateType x)//指定位置之后插入
{
 assert(pos);
 //此时注意 必须先让newnode指向pos的下一个 
 //第一步//先准备一个新节点出来
 SListNode* newnode = BuyListNode(x);//调用上面开辟新节点函数
 newnode->next = pos->next;
 pos->next = newnode;
}

删除指定位置

void SListErase(SListNode** pphead, SListNode* pos)//删除指定位置
{
 assert(pphead);
 assert(pos);
 //pos是任意位置
 //删除之前先让前一个指向pos位置的下一个
 if (pos == *pphead)//先考虑删除头
 {
  SListPopFront(pphead);//调用上方头删函数
 }
 else
 {
  //找pos的前一个位置
  SListNode* posprev = *pphead;//定义posorev从头找
  while (posprev->next != pos)
  {
   posprev = posprev->next;
  }
  //
  posprev->next = pos->next;//让前一个位置先指向pos的后一个位置
  free(pos);//然后再删除pos
 }
}

删除指定位置后面数据

void SListEraseAfter(SListNode* pos)//删除指定位置pos后面数据
{
 //先让pos指向pos的下一个位置
 assert(pos->next);
 SListNode* next = pos->next;//定义next为要删除的数据
 pos->next = next->next;
 //先让pos的下一个位置指向要删除数据（next）的下一个位置
 free(next);//然后再删除next
}

这时我们用上面接口实现一个在 test.c 当中的第3个测试案例TestSList 3

void TestSList3()
{
//开始将链表给空
SListNode* plist = NULL;
SListPushBack(&plist, 1);//尾插 1 2 3 4 
SListPushBack(&plist, 2);
SListPushBack(&plist, 3);
SListPushBack(&plist, 4);

SListNode* pos = SListFind(plist, 4);//指定数字4位置前插入
if (pos)
{
 SListInsert(&plist, pos, 60);//在4位置的前面插入60
}
SListPrint(plist);//打印1->2->3->60->4->NULL

pos = SListFind(plist, 4);//指定数字4位置后插入
if (pos)
{
 SListInsertAfter(pos, 5);//在4位置的后面插入5
}
SListPrint(plist);//打印1->2->3->60->4->5->NULL

pos = SListFind(plist, 4);//查找4
if (pos)
{
 SListErase(&plist, pos);//删除当前位置4
}
	
SListPrint(plist);//打印1->2->3->60->5->NULL

pos = SListFind(plist, 60);//查找60
if (pos)
{
 SListEraseAfter(pos);//删除60的后一个
}
SListPrint(plist);//打印1->2->3->60->NULL
	
SListDestroy(&plist);//置空函数，放在最后释放开辟空间
}
int main()
{
 TestSList3();
 return 0;
}

在Java和C++的学习当中，前期学习数据结构当中的顺序表、链表、二叉树等便于我们后面更好的学习容器，后面会继续分享二叉树和算法的实现

希望这篇文章大家有所收获，我们下篇见