【单链表】数据结构单链表的实现

简介: 【单链表】数据结构单链表的实现


1.概念及结构

概念:

链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。它包括两个域,其中存储数据元素信息的称为数据域,存储直接后继存储位置的域称为指针域。

结构如下:

然而在我们实际的运用中,它的结构却是以下类型:

因此这里有我们需要注意的地方:

1.链式结构逻辑上是连续的,但物理上并不一定是连续的;

2.现实中的节点一般是从堆上申请来的;

3.从堆上申请的空间,是按照一定的策略的,在次申请可能是连续的也可能是不连续的。

2. 链表的分类

根据链表结点所含指针个数、指针指向和指针连接方式,可将链表分为单链表、循环链表、双向链表、二叉链表、十字链表、邻接表、邻接多重表等。其中单链表、循环链表和 向链表用于实现线性表的链式存储结构,其他形式多用于实现树和图等非线性结构。

实际中链表的结构非常多样,以下情况组合起来就有8种链表结构:

  1. 单向或者双向

  2. 带头或者不带头

  3. 循环或者非循环

    注意:虽然有这么多的链表的结构,但是我们实际中最常用还是两种结构:

  1. 无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
  2. 带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单了,后面我们代码实现了就知道了。

3.接口实现

// 动态申请一个结点
SLTNode* BuySLTNode(SLTDataType x);
SLTNode* CreateSList(int n);
// 单链表打印
void SLTPrint(SLTNode* phead);
// 单链表尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
// 单链表的尾删
void SLTPopBack(SLTNode** pphead);
// 单链表的头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);
// 单链表头删
void SLTPopFront(SLTNode** pphead);
// 单链表查找
SLTNode* SListFind(SLTNode* plist, SLTDataType x);
// 单链表在pos位置之后插入x
void SListInsertAfter(SLTNode* pos, SLTDataType x);
// 单链表删除pos位置之后的值
void SListEraseAfter(SLTNode* pos);
// 在pos之前插入x
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
// 删除pos位置
void SListErase(SLTNode** pphead, SLTNode* pos);

接下来我们便一一进行实现!

3.1动态申请一个结点

代码如下:

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;
}

思路:

开始时我们从堆上动态申请一个结点,生成的新结点作为头结点,用头指针指向该结点,在把头结点的指针域置空。

3.2创建单链表

SLTNode* CreateSList(int n)
{
  SLTNode* phead = NULL, *ptail = NULL;
  int x = 0;
  for (int i = 0; i < n; ++i)
  {
    SLTNode* newnode = BuySLTNode(i);
    if (phead == NULL)
    {
      ptail = phead = newnode;
    }
    else
    {
      ptail->next = newnode;
      ptail = newnode;
    }
  }
  return phead;
}

3.3遍历单链表

void SLTPrint(SLTNode* phead)
{
  SLTNode* cur = phead;
  while (cur != NULL)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("NULL\n");//便于调试
}

思路:

我们对单链表进行遍历操作,整体思路还是从开头挨着遍历,直到我们的指针指向空的时候就完成相应的操作。

3.4尾插

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
  SLTNode* newnode = BuySLTNode(x);
  if (*pphead == NULL)
  {
    *pphead = newnode;
  }
  else
  {
    SLTNode* tail = *pphead;
    // 找尾
    while (tail->next)
    {
      tail = tail->next;
    }
    tail->next = newnode;
  }
}

思路:

每次都将新的结点链接到链表的最后一个结点的后面,从而达到创建单链表的过程,我们这里用到二级指针来接收实参,因为在函数传参时如果想改变实参,则需要我们传递实参的地址,那么同样想要改变首地址,则需要传递首地址的地址。

3.5尾删

void SLTPopBack(SLTNode** pphead)
{
  // 暴力的检查
  assert(*pphead);
  // 温柔的检查
  //if (*pphead == NULL)
  //  return;
  if ((*pphead)->next == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  else
  {
    SLTNode* tail = *pphead;
    while (tail->next->next)
    {
      tail = tail->next;
    }
    free(tail->next);
    tail->next = NULL;
  }
}

思路:

当进行尾删操作时我们有两种情况需要进行考虑:

如果是正常情况下的删除操作,我们就需要找到该链表最后一个节点的前一个节点,然后将这个节点的 next指针指向由最后一个节点改变为null;

如果链表最后只剩下一个结点,则直接释放到即可,然后还是数据域置空。

3.6头插

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
  SLTNode* newnode = BuySLTNode(x);
  newnode->next = *pphead;
  *pphead = newnode;
}

思路:

首先初始化一个单链表,其头结点为空,然后循环插入新结点:将新节点的next指向头结点的下一个结点,然后将头结点的next指向我们的新节点。(思路同尾插类似)

3.7头删

void SLTPopFront(SLTNode** pphead)
{
  assert(*pphead);
  
  SLTNode* next = (*pphead)->next;
  free(*pphead);
  *pphead = next;
}

思路:

删除第一个结点依然需要修改我们的头部指针,所以还是需要用到二级指针。

3.8查找

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
  SLTNode* cur = phead;
  while (cur)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}

思路:

查找值x在单链表L中的结点指针,从单链表的第一个结点开始,依次比较表中各个结点的数据域的值,若某结点数据域的值等于x,则返回该结点的指针;若整个单链表中没有这样的结点,则返回空。

3.9在pos后插入

void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
  assert(pos);
  SLTNode* newnode = BuySLTNode(x);
  newnode->next = pos->next;
  pos->next = newnode;
}

思路:

这里注意的是指针链接的顺序问题,如果改变链接的顺序则会出现自己指向自己的情况!

3.10在pos之前插入

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
  assert(pos);
  if (*pphead == pos)
  {
    SLTPushFront(pphead, x);
  }
  else
  {
    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    SLTNode* newnode = BuySLTNode(x);
    prev->next = newnode;
    newnode->next = pos;
  }
}

思路:

这种操作的情况还是有两种:

第一种就是当我们以头结点为pos位置,那么就演变为头插操作;

第二种就是正常的插入,我们就需要从头开始去查找pos位置的前一个位置,接着就是结点的链接的顺序一定要注意。

3.11删除pos之后的值

void SLTEraseAfter(SLTNode* pos)
{
  assert(pos);
  if (pos->next == NULL)
  {
    return;
  }
  else
  {
    SLTNode* nextNode = pos->next;
    pos->next = nextNode->next;
    free(nextNode);
  }
}

思路:

最后一个位置我们需要特别注意,开始时先判断。不能写成pos->next=pos->next->next,使用这种我们需要开始时先保存pos->next。

3.12删除pos位置

void SLTErase(SLTNode** pphead, SLTNode* pos)
{
  assert(pos);
  assert(*pphead);
  if (pos == *pphead)
  {
    SLTPopFront(pphead);
  }
  else
  {
    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    prev->next = pos->next;
    free(pos);
    //pos = NULL;
  }
}

思路:

这里还是两种情况:

第一种当删除的pos位置为最后一个结点时,相当于尾删操作此时;

第二种就是正常的删除操作,跟之前的有类似

总结:以上就是关于单链表的所有的内容知识,希望大家多多指教!

相关文章
|
2天前
|
存储
数据结构第二课 -----线性表之单向链表
数据结构第二课 -----线性表之单向链表
|
1天前
|
存储
数据结构链表详解(不仅顺序表可以,我链表也可以)
数据结构链表详解(不仅顺序表可以,我链表也可以)
10 0
|
2天前
特殊链表(循环单链表,循环双链表,静态链表)
特殊链表(循环单链表,循环双链表,静态链表)
13 3
|
2天前
|
存储 算法 Java
数据结构与算法 数组和链表
数据结构与算法 数组和链表
11 0
|
2天前
|
存储 Java
深入浅出数据结构之链表
深入浅出数据结构之链表
|
2天前
|
C++
数据结构(循环单链表
数据结构(循环单链表
12 2
|
2天前
|
C++
数据结构(双链表
数据结构(双链表
11 1
|
2天前
|
C++
数据结构(单链表
数据结构(单链表
9 0
|
2天前
|
存储 缓存
[数据结构]~双向+循环链表从(0~1)
[数据结构]~双向+循环链表从(0~1)
|
2天前
|
存储
[数据结构]单链表(从0->1)
[数据结构]单链表(从0->1)