数据结构之单向不循环链表

时间：2023-03-02 18:32:21

链表是一种物理存储结构上非连续、非顺序的线性存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表中的元素（节点）中记录了与其他元素的连接关系，链表的存储方式相比于顺序表更加灵活。

链表结构多样，分带头/不带头、单向/双向和循环/不循环，相互组合可以有8种结构。本文实现不带头单向不循环链表。


逻辑结构

链表的逻辑结构是线性和连续的，各个节点通过指针进行连接。

数据结构之单向不循环链表


物理结构

链表的物理结构是离散的，存储链表的内存空间是非连续的。

数据结构之单向不循环链表


链表的定义

链表的每个节点包含两部分信息：有效数据(Value)和指向下一节点的指针(Next)。其中尾节点的​​Next​​​指针为​​NULL​​。

typedef int SListDataType;

typedef struct SListNode
{
SListDataType data; //有效数据
struct SListNode* next; //Next指针
}SListNode;

void SLPrint(SListNode* phead); //链表打印
void SLPushBack(SListNode** phead, SListDataType x); //尾插数据
void SLPopBack(SListNode** pphead); //尾删数据
void SLPushFront(SListNode** pphead, SListDataType x); //头插数据
void SLPopFront(SListNode** pphead); //头删数据
SListNode* SListFind(SListNode* plist, SListDataType x); //查找数据
void SListInsertAfter(SListNode* pos, SListDataType x); //(后方)插入数据
void SListEraseAfter(SListNode* pos); //(后方)删除数据
void SListDestroy(SListNode* plist); //链表销毁


链表的初始化

通常用指针维护一个链表，这个指针通常指向一个链表的头结点，即phead->list。事实上，我们通常将头结点作为一个链表的代称，例如头结点head和链表head实际上是同义的。

建立一个链表通常分为两步，第一步是初始化各个节点，第二是在各个节点之间建立连接关系。完成后，即可从头结点出发，访问其余所有节点。

SListNode* plist = NULL; //用plist维护链表


接口实现和注意事项

创建节点

在下面的接口中往往需要申请一个新节点，此处将创建节点的功能单独封装成一个函数，返回新节点的地址。

SListNode* BuySLNode(const int x)
{
SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));
if (newNode == NULL)
  {
perror("BuySLNode::malloc");
return NULL;
  }
else
  {
newNode->data = x;
newNode->next = NULL;
return newNode;
  }
}


链表打印

打印链表便于调试和直观显示数据。从头结点开始向后遍历链表以实现链表数据的打印。

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


尾部插入数据

在尾部插入数据时，首先要创建一个新节点，再寻找尾节点并将尾节点的Next修改为新节点的地址以实现链表和新节点的链接。

另外，需要额外考虑空表情况。当链表为空时，需要将新节点的地址赋值给plist，所以在传参时需要传plist的地址以顺利修改链表的头结点。另外，为了检查使用者的传参错误，需要对​​pphead​​进行断言。

void SLPushBack(SListNode** pphead, SListDataType x)
{
assert(pphead);
SListNode* newNode = BuySLNode(x);
if (*pphead == NULL)
  {
*pphead = newNode;
  }
else
  {
SListNode* cur = *pphead;
while (cur->next)
    {
cur = cur->next;
    }
cur->next = newNode;
  }
}

一种常见的错误实现如下：

void SLPushBack(SListNode** pphead, SListDataType x)
{
assert(pphead);
SListNode* newNode = BuySLNode(x);
if (*pphead == NULL) {
*pphead = newNode;
  }
else
  {
SListNode* cur = *pphead;
while (cur)
    {
cur = cur->next;
    }
cur = newNode;
  }
}

出现上面错误的原因是对链表的物理结构理解不透彻，当循环停止时，​​tail​​​的值为​​NULL​​​，当赋值新节点的指针给​​tail​​​时，尾节点的​​Next​​并未被改变，即这个操作不能将新节点链接起来。

注意深刻理解链表的物理结构：临时指针变量的地址不变，临时指针变量存储的地址在变。


尾部删除数据

空表情况和只有一个节点的情况需要额外考虑。

数据结构之单向不循环链表

void SLPopBack(SListNode** pphead)
{
assert(pphead);
assert(*pphead);
SListNode* cur = *pphead;
if (cur->next == NULL)
  {
free(cur);
*pphead = NULL;
  }
else
  {
while (cur->next->next)
    {
cur = cur->next;
    }
free(cur->next);
cur->next = NULL;
  }
}


头部插入数据

数据结构之单向不循环链表

void SLPushFront(SListNode** pphead, SListDataType x)
{
assert(pphead);
SListNode* newNode = BuySLNode(x);
newNode->next = *pphead;
*pphead = newNode;
}


头部删除数据

数据结构之单向不循环链表

void SLPopFront(SListNode** pphead)
{
assert(pphead);
assert(*pphead);
SListNode* nextNode = (*pphead)->next;
free(*pphead);
*pphead = nextNode;
}


查找数据

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


在指定位置后方插入数据

数据结构之单向不循环链表

void SListEraseAfter(SListNode* pos)
{
assert(pos);
SListNode* DelNode = pos->next;
assert(DelNode);//最后一个节点后面没有节点
SListNode* nextNode = DelNode->next;
free(DelNode);
DelNode = NULL;
pos->next = nextNode;
}


删除指定位置后方的一个数据

数据结构之单向不循环链表

void SListEraseAfter(SListNode* pos)
{
assert(pos);
SListNode* DelNode = pos->next;
assert(DelNode);//最后一个节点后面没有节点
SListNode* nextNode = DelNode->next;
free(DelNode);
DelNode = NULL;
pos->next = nextNode;
}


链表销毁

void SListDestroy(SListNode* plist)
{
while (plist->next != NULL)
  {
SListEraseAfter(plist);
  }
free(plist);
}

无头单向不循环链表的缺点

可以注意到，上述实现中间插入和删除数据都是在指定位置的后方进行操作，这是因为由于在单向不循环链表中，无法直接找到一个节点的前驱节点和后继节点，若要实现删除指定位置和在指定位置的前面插入一个节点，需要从头遍历链表找到​​pos​​位置的前驱节点，效率较低。STL库中对单向链表这种接口的实现的原因也是如此。

STL中单向链表中的部分接口:数据结构之单向不循环链表

链表具有以下缺点：

  1. 链表的随机访问效率较低。当需要寻找一个节点时，要从链表的头结点开始遍历寻找。
  2. 链表占用的内存较多。因为每个链表节点不仅要存储有效数据，还要额外存储指针。不过这些额外的内存在如今已经不值一提，所以这个缺点几乎可以忽略不计。
标签：

相关文章