手把手教你实现链表—单链表（数据结构C语言实现3）-阿里云开发者社区

手把手教你实现链表—单链表（数据结构C语言实现3）

2022-08-14 175

版权

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

简介： 手把手教你实现链表—单链表（数据结构C语言实现3）

本节目标

1.链表表示和实现（单链表+双向链表）

2.链表的常见OJ题

3.顺序表和链表的区别和联系

链表表示和实现（单链表+双向链表）

顺序表的问题及思考问题：

中间/头部的插入删除，时间复杂度为O(N)

增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗

增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

思考：如何解决以上问题呢？下面给出了链表的结构来看看。

链表的概念

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的

逻辑结构

想必大家看的都是链表的逻辑结构，其实真实并不存在连接两个链表的箭头，为了更好理解罢了。箭头代表前面的节点存了，后面节点的指针。

物理结构

物理结构就是真正的结构，便于初学者学习!

是不是突然对链表有了更深刻的理解！

单链表的实现

// 1、无头+单向+非循环链表增删查改实现
// 动态申请一个节点
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
void SListInsert(SListNode** pplist, SListNode* pos, SLTDateType x);
// 单链表删除pos位置的值
void SListErase(SListNode** pplist, SListNode* pos);

链表节点创建

链表的创建也是用结构体创建。

//类型创建
  typedef int SLDataType;
  typedef struct SListNode
  {
      SLDataType date;   //存值
      struct SListNode* next; //存下一节点的指针
  }SLNode;

// 动态申请一个节点
SLTNode* BuySListNode(SLTDataType x)
{
   SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
   newnode->date = x;
   newnode->next = NULL;
   return newnode;
}

// 打印
void SListPrint(SLTNode* phead)
{
   while (phead != NULL)
   {
    printf("%d ", phead->date);
    phead = phead->next;
   }
   printf("NULL\n");
}

//尾插
void SListPushBack(SLTNode** pphead, SLTDataType x)
{
   if (*pphead == NULL)
   {
    *pphead = BuySListNode(x);
   }
   else
   {
    SLTNode* tail = *pphead;
    while (tail->next)
    {
      tail = tail->next;
    }
    tail->next = BuySListNode(x);
   }
}

//头插接口测试
void TestSList2()
{
   SLTNode* plist = NULL;
   SListPushFront(&plist, 1);
   SListPushFront(&plist, 2);
   SListPushFront(&plist, 3);
   SListPushFront(&plist, 4);
   SListPushFront(&plist, 5);
   SListPushFront(&plist, 6);
   SListPrint(plist);
}

//头插
void SListPushFront(SLTNode** pphead, SLTDataType x)
{
   if (!*pphead)
   {
    *pphead= BuySListNode(x);
   }
   else
   {
    SLTNode* first = BuySListNode(x);
    first->next = *pphead;
    *pphead = first;
   }
}

//头插接口测试
void TestSList2()
{
  SLTNode* plist = NULL;
  SListPushFront(&plist, 1);
  SListPushFront(&plist, 2);
  SListPushFront(&plist, 3);
  SListPushFront(&plist, 4);
  SListPushFront(&plist, 5);
  SListPushFront(&plist, 6);
  SListPrint(plist);
}

//头删
void SListPopFront(SLTNode** pphead)
{
  if (!*pphead)
  {
  return;
  } 
  else
  {
  *pphead = (*pphead)->next;
  }
}

//头删接口测试
void TestSList3()
{
  SLTNode* plist = NULL;
  SListPushFront(&plist, 1);
  SListPushFront(&plist, 2);
  SListPushFront(&plist, 3);
  SListPushFront(&plist, 4);
  SListPushFront(&plist, 5);
  SListPushFront(&plist, 6);
  SListPrint(plist);
  SListPopFront(&plist);
  SListPopFront(&plist);
  SListPopFront(&plist);
  SListPopFront(&plist);
  SListPrint(plist);
}

//尾删
void SListPopBack(SLTNode** pphead)
{
  //1头结点为空
  //2只有一个节点
  //3多个节点
  if (*pphead == NULL)
  {
  return;
  }
  else if ((*pphead)->next ==NULL)
  {
  *pphead = NULL;
  free(*pphead);
  }
  else
  {
  SLTNode* tail = *pphead;
  SLTNode* ret = *pphead;
  while (tail->next)
  {
    ret = tail;
    tail = tail->next;
  }
  tail = NULL;
  ret->next = NULL;
  free(tail);
  }
}

//尾删接口测试
void TestSList4()
{
  SLTNode* plist = NULL;
  SListPushFront(&plist, 1);
  SListPushFront(&plist, 2);
  SListPushFront(&plist, 3);
  SListPushFront(&plist, 4);
  SListPushFront(&plist, 5);
  SListPushFront(&plist, 6);
  SListPrint(plist);
  SListPopBack(&plist);
  SListPopBack(&plist);
  SListPopBack(&plist);
  SListPopBack(&plist);
  SListPrint(plist);
}

//查找节点x位置并返回节点位置
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
  if (phead == NULL)  //节点为空
  {
  return NULL;
  }
  else
  {
  SLTNode *ret= phead;
  while (ret) 
  {
    if (ret->date == x)    //找到了
    {
    return ret;
    }
    ret = ret->next;
  }
  return NULL;           //找不到
  }
}

// 在pos的前面插入x
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
  SLTNode* newnode = BuySListNode(x);
  if (*pphead == NULL)
  {
  return;
  }
  else if(*pphead==pos)
  {
  *pphead = newnode;
  newnode->next = pos;
  }
  else
  {
  SLTNode* ret = *pphead;
  while (ret->next != pos)
  {
    ret = ret->next;
  }
  ret->next = newnode;
  newnode->next = pos;
  }
}

//任意位置查找插入测试
void TestSList5()
{
  SLTNode* plist = NULL;
  SListPushFront(&plist, 1);
  SListPushFront(&plist, 2);
  SListPushFront(&plist, 3);
  SListPushFront(&plist, 4);
  SListPushFront(&plist, 5);
  SListPushFront(&plist, 6);
  SListPrint(plist);
  SLTNode* pos = SListFind(plist,3);
  if (pos)
  {
  SListInsert(&plist,pos,0);
  }
  SListPrint(plist);
}

//删除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos)
{
  if (*pphead==NULL)
  {
  return;
  }
  else if (*pphead == pos)
  {
  *pphead = NULL;
  }
  else
  {
  SLTNode* ret = *pphead;
  while (ret->next != pos)
  {
    ret = ret->next;
  }
  ret->next = pos->next;
  pos = NULL;
  free(pos);
  }
}

//任意位置修改接口测试
void TestList6()
{
  SLTNode* plist = NULL;
  SListPushBack(&plist, 1);
  SListPushBack(&plist, 2);
  SListPushBack(&plist, 3);
  SListPushBack(&plist, 4);
  SListPushBack(&plist, 5);
  SListPushBack(&plist, 6);
  SListPrint(plist);
  SLTNode* pos = SListFind(plist, 3);
  if (pos)
  {
  SListErase(&plist, pos);
  }
  SListPrint(plist);
}

手把手教你实现链表—单链表（数据结构C语言实现3）

本节目标

链表表示和实现（单链表+双向链表）

单链表的实现

热门文章

最新文章

相关课程

相关电子书