AI 助理
备案控制台
开发者社区 云计算 文章 正文

数据结构之链表详解（二）

2023-06-10 51
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 即顺序表之后，今天给大家带来另外一个线性结构——链表。

2.7 单链表的头插

1.void SListPushFront(SListNode** pplist, SLTDateType x)
{   
  assert(pplist);
  SListNode* newnode = BuySListNode(x);
  newnode->next = *pplist;
  *pplist = newnode;
}

对于头插这里我们进行的操作就比较简单了，首先向内存创建一个节点，然后新节点的next指向头节点，然后把头指针指向新节点，具体如下：

第一步：

第二步：

测试如下：

void text2()
{
  SListNode* s = NULL;
  SListPushFront(&s, 1);
  SListPushFront(&s, 2);
  SListPushFront(&s, 3);
  SListPushFront(&s, 4);
  SListPrint(s);
}
int main()
{
  text2();
  return 0;
}

结果如下：

2.8 单链表头删

void SListPopFront(SListNode** pplist)
{
  assert(pplist);
  assert(*pplist);
  SListNode* first = *pplist;
  *pplist = first->next;
  free(first);
  first = NULL;
}

对于头删，这里我们需要用一个指针记录头节点位置，然后把头指针指向头节点的下一个节点，然后把头节点释放了即可，具体如下：

这样我们就完成了头删。

测试如下：

void text2()
{
  SListNode* s = NULL;
  SListPushFront(&s, 1);
  SListPushFront(&s, 2);
  SListPushFront(&s, 3);
  SListPushFront(&s, 4);
  SListPrint(s);
  SListPopFront(&s);
  SListPrint(s);
  SListPopFront(&s);
  SListPrint(s);
}
int main()
{
  text2();
  return 0;
}

结果如下：

2.9  单链表查找

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

这里我们还是以内容查找，思路很简单，就是遍历，找到后返回找到的那个节点，没找到返回空指针即可。由于这里我们不好测试，我们配合下面的在某个位置插入给大家演示。


2.10  单链表在pos位置之后插入x

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

这里我们需要配合查找找到需要插入的元素，这里的逻辑也比较简单，我给大家用演示一下

测试如下：

1.void text1()
{
  SListNode* s = NULL;
  SListPushBack(&s, 1);
  SListPushBack(&s, 2);
  SListPushBack(&s, 3);
  SListPushBack(&s, 4);
  SListPrint(s);
  SLTDateType x = 0;
  scanf("%d", &x);
  SListNode* pos = SListFind(s, x);
  SListInsertAfter(pos, 6);
  SListPrint(s);
}
int main()
{
  text1();
  return 0;
}

结果如下：

2.11 单链表删除pos位置之后的值

void SListEraseAfter(SListNode* pos)
{
  if (pos == NULL&&pos->next)
  {
    return;
  }
  else
  {
    SListNode* find;
    find = pos->next;
    pos->next = pos->next->next;
    free(find);
    find = NULL;
  }
}

首先判断该位置和下一个位置是不是空，为空直接退出程序，这里我们用指针find记录pos下一个节点，然后将pos的next指向下下个节点即可。

具体如下：

测试如下：

1.void text1()
{
  SListNode* s = NULL;
  SListPushBack(&s, 1);
  SListPushBack(&s, 2);
  SListPushBack(&s, 3);
  SListPushBack(&s, 4);
  SListPrint(s);
  SLTDateType x = 0;
  scanf("%d", &x);
  SListNode* pos = SListFind(s, x);
  SListInsertAfter(pos, 6);
  SListPrint(s);
  SListNode*pos1= SListFind(s, x);
  SListEraseAfter(pos1);
  SListPrint(s);
}
int main()
{
  text1();
  return 0;
}

结果如下：

2.12  单链表的销毁

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

对于销毁操作，我们需要使用双指针，用q记录要销毁节点的下一个，p用来销毁指针，然后不断对链表进行遍历。


总代码

Slist.c
#include"slist.h"
SListNode* BuySListNode(SLTDateType x)
{
  SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
  if (newnode == NULL)
  {
  perror("malloc fail");
  return NULL;
  }
  newnode->data = x;
  newnode->next = NULL;
  return newnode;
}
void SListPrint(SListNode* plist)
{
  SListNode* cur = plist;
  while (cur)
  {
  printf("%d-> ", cur->data);
  cur = cur->next;
  }
  printf("NULL\n");
}
void SListPushBack(SListNode** pplist, SLTDateType x)
{
  assert(pplist);
  SListNode*newnode= BuySListNode(x);
  if (*pplist == NULL)
  {
  *pplist = newnode;
  }
  else
  {
  SListNode* tail=*pplist;
  while (tail->next)
  {
    tail = tail->next;
  }
  tail->next = newnode;
  }
}
void SListPushFront(SListNode** pplist, SLTDateType x)
{   
  assert(pplist);
  SListNode* newnode = BuySListNode(x);
  newnode->next = *pplist;
  *pplist = newnode;
}
void SListPopBack(SListNode** pplist)
{
  assert(pplist);
  assert(*pplist);
  if ((*pplist)->next==NULL)
  {
  free(*pplist);
  *pplist = NULL;
  }
  else
  {
  SListNode* tail = *pplist;
  while (tail->next->next)
  {
    tail = tail->next;
  }
  free(tail->next);
  tail->next = NULL;
  }
}
void SListPopFront(SListNode** pplist)
{
  assert(pplist);
  assert(*pplist);
  SListNode* first = *pplist;
  *pplist = first->next;
  free(first);
  first = NULL;
}
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
  if (plist == NULL)
  {
  return NULL;
  }
  SListNode* dest=plist;
  while (dest)
  {
  if (dest->data == x)
  {
    return dest;
  }
  dest = dest->next;
  }
  return NULL;
}
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
  SListNode* newnode=BuySListNode(x);
  assert(pos);
  newnode->next = pos->next;  
  pos->next = newnode;
}
void SListEraseAfter(SListNode* pos)
{
  if (pos == NULL&&pos->next)
  {
  return;
  }
  else
  {
  SListNode* find;
  find = pos->next;
  pos->next = pos->next->next;
  free(find);
  find = NULL;
  }
}
void SListDestroy(SListNode* plist)
{
  SListNode* p = plist;
  SListNode* q;
  while (p)
  {
  q = p->next;
  free(p);
  p = q;
  }
  plist = NULL;
}
Slist.h
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDateType;
typedef struct SListNode
{
  SLTDateType data;
  struct SListNode* next;
}SListNode;
// 动态申请一个节点
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 SListInsertAfter(SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos);
// 单链表的销毁
void SListDestroy(SListNode* plist);
Text.c
#include"slist.h"
void text3()
{
  SListNode* s = NULL;
  SListPushBack(&s, 1);
  SListPushBack(&s, 2);
  SListPushBack(&s, 3);
  SListPushBack(&s, 4);
  SListPrint(s);
  SListPopBack(&s);
  SListPopBack(&s);
  SListPrint(s);
}
void text2()
{
  SListNode* s = NULL;
  SListPushFront(&s, 1);
  SListPushFront(&s, 2);
  SListPushFront(&s, 3);
  SListPushFront(&s, 4);
  SListPrint(s);
  SListPopFront(&s);
  SListPrint(s);
  SListPopFront(&s);
  SListPrint(s);
}
void text1()
{
  SListNode* s = NULL;
  SListPushBack(&s, 1);
  SListPushBack(&s, 2);
  SListPushBack(&s, 3);
  SListPushBack(&s, 4);
  SListPrint(s);
  SLTDateType x = 0;
  scanf("%d", &x);
  SListNode* pos = SListFind(s, x);
  SListInsertAfter(pos, 6);
  SListPrint(s);
  SListNode*pos1= SListFind(s, x);
  SListEraseAfter(pos1);
  SListPrint(s);
}
int main()
{
  text1();
  return 0;
}


关键词：
数据结构链表
链表数据结构
半只牛马
目录
相关文章
2的n次方_
|
6天前
|
存储 Java 索引
【数据结构】链表从实现到应用，保姆级攻略
本文详细介绍了链表这一重要数据结构。链表与数组不同，其元素在内存中非连续分布，通过指针连接。Java中链表常用于需动态添加或删除元素的场景。文章首先解释了单向链表的基本概念，包括节点定义及各种操作如插入、删除等的实现方法。随后介绍了双向链表，说明了其拥有前后两个指针的特点，并展示了相关操作的代码实现。最后，对比了ArrayList与LinkedList的不同之处，包括它们底层实现、时间复杂度以及适用场景等方面。
2的n次方_
28 10
【数据结构】链表从实现到应用，保姆级攻略
百色彭于晏
|
28天前
|
存储 C语言
【数据结构】c语言链表的创建插入、删除、查询、元素翻倍
【数据结构】c语言链表的创建插入、删除、查询、元素翻倍
百色彭于晏
32 0
【数据结构】c语言链表的创建插入、删除、查询、元素翻倍
是基德吖
|
2月前
【数据结构OJ题】环形链表
力扣题目——环形链表
是基德吖
30 3
【数据结构OJ题】环形链表
chian-ocean
|
1月前
【数据结构】双向带头（哨兵位）循环链表 —详细讲解（赋源码）
【数据结构】双向带头（哨兵位）循环链表 —详细讲解（赋源码）
chian-ocean
29 4
是基德吖
|
2月前
【数据结构OJ题】复制带随机指针的链表
力扣题目——复制带随机指针的链表
是基德吖
42 1
【数据结构OJ题】复制带随机指针的链表
是基德吖
|
2月前
【数据结构OJ题】环形链表II
力扣题目——环形链表II
是基德吖
19 1
【数据结构OJ题】环形链表II
是基德吖
|
2月前
【数据结构OJ题】相交链表
力扣题目——相交链表
是基德吖
23 1
【数据结构OJ题】相交链表
东方睿赢
|
22天前
|
存储 Java 程序员
"揭秘HashMap底层实现：从数组到链表，再到红黑树，掌握高效数据结构的秘密武器！"
【8月更文挑战第21天】HashMap是Java中重要的数据结构，采用数组+链表/红黑树实现，确保高效查询与更新。构造方法初始化数组，默认容量16，负载因子0.75触发扩容。`put`操作通过计算`hashCode`定位元素，利用链表或红黑树处理冲突。`get`和`remove`操作类似地定位并返回或移除元素。JDK 1.8优化了链表转红黑树机制，提升性能。理解这些原理能帮助我们更高效地应用HashMap。
东方睿赢
29 0
aliyun6365824167
|
24天前
|
存储 算法
【初阶数据结构篇】顺序表和链表算法题
此题可以先找到中间节点，然后把后半部分逆置，最近前后两部分一一比对，如果节点的值全部相同，则即为回文。
aliyun6365824167
13 0
aliyun6365824167
|
24天前
|
存储 测试技术
【初阶数据结构篇】双向链表的实现（赋源码）
因为头结点的存在，plist指针始终指向头结点，不会改变。
aliyun6365824167
17 0