数据结构——单链表-阿里云开发者社区

数据结构——单链表

2024-05-20 24

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 数据结构——单链表

单链表描述

链表在物理储存结构上是非连续的，它主要是通过指针指向下一个数据的。

节点都是动态开辟出来的。

我们把数据和指向下一个节点地址的指针叫做一个节点。

代码实现

创建节点

typedef int SLTypeDate;
typedef struct SListNode
{
  SLTypeDate date;
  struct SListNode* next;
}SListNode;

增加节点

SListNode* BuySListNode(SLTypeDate x)
{
  SListNode* NewNode = (SListNode*)malloc(sizeof(SListNode));
  if (NewNode == NULL)
    exit(-1);
  NewNode->date = x;
  NewNode->next = NULL;
  return NewNode;
}

链表数据的打印

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

单链表的销毁

从头节点一个一个进行销毁

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

头插

void SListPushFront(SListNode** pphead, SLTypeDate x)
{
  assert(pphead);
  SListNode* NewNode=BuySListNode(x);
  SListNode* NewNode = (SListNode*)malloc(sizeof(SListNode));
  if (NewNode == NULL)
    exit(-1);
  NewNode->date = x;
  NewNode->next = *pphead;
  *pphead = NewNode;
}

尾插

尾插的时候也要注意没有节点的情况。

void SListPushBack(SListNode** pphead, SLTypeDate x)
{
  assert(pphead);
  SListNode* NewNode = BuySListNode(x);
  if (*pphead == NULL)
  {
    *pphead = NewNode;
  }
  else
  {
    SListNode* tail = *pphead;
    while (tail->next)
    {
      tail = tail->next;
    }
    tail->next = NewNode;
  }
}

尾删

需要判断节点为1，还有多个的情况

void SListPopBack(SListNode** pphead)
{
  assert(*pphead);

  if ((*pphead)->next==NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  else
  {
    SListNode* tail = *pphead;
    while (tail->next->next != NULL)
    {
      tail = tail->next;
    }
    free(tail->next);
    tail->next = NULL;
  }
}

头删

先用临时变量储存起来头节点后面的节点

void SListPopFront(SListNode** pphead)
{
  assert(*pphead);
  SListNode* cur = (*pphead)->next;
  free(*pphead);
  *pphead = cur;
}

查找数据的位置

查找到返回改节点的地址，查找不到返回空指针

SListNode* SListFind(SListNode* phead, SLTypeDate x)
{
  assert(phead);
  while (phead->date!=x)
  {
    phead = phead->next;
    if (phead == NULL)
      return NULL;
  }
  return phead;
}

在查找位置之前插入

1.pos不能为空指针

2.注意在第一个节点前插的情况

void SListInsertPre(SListNode** pphead, SListNode* pos, SLTypeDate x)
{
  assert(pphead);
  assert(pos);
  SListNode* NewNode = BuySListNode(x);
  
  if (pos==*pphead)
  {
    //NewNode->next = *pphead;
    //*pphead = NewNode;
    SListPushFront(pphead,x);
  }
  else
  {
    SListNode* cur = *pphead;
    while (cur->next != pos)
    {
      cur = cur->next;
    }
    NewNode->next = pos;
    cur->next = NewNode;
  }
  
}

在查找位置之后插入

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

删除查找位置的节点

void SListErase(SListNode** pphead, SListNode* pos)
{
  assert(pphead);
  assert(pos);
  if (pos == *pphead)
  {
    //*pphead = (*pphead)->next;
    //free(pos);
    //pos = NULL;
    SListPopFront(pphead);
  }
  else
  {
    SListNode* cur = *pphead;
    while (cur->next != pos)
    {
      cur = cur->next;
    }
    cur->next = pos->next;
    free(pos);
    pos = NULL;
  }
  
}

删除查找位置之后的节点

注意为最后一个节点的时候，不能进行删除

void SListEraseAfter(SListNode* pos)
{
  assert(pos);
  if (pos->next == NULL)
  {
    return;
  }
  SListNode* cur = pos->next->next;
  free(pos->next);
  pos->next = cur;
  
}