数据结构入门(C语言版)线性表中链表介绍及无头单向非循环链表接口实现

简介: 概念: 线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素。因此,为了表示每个数据元素与其直接后继数据元素之间的逻辑关系,对数据元素来说,除了存储其本身的信息之外,还需存储一个指示其直接后继的信息(即直接后继的存储位置)。

a0751b77c1cf4978862aface7c5f2068.png


导航


1、链表的概念和结构


概念: 线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素。因此,为了表示每个数据元素与其直接后继数据元素之间的逻辑关系,对数据元素来说,除了存储其本身的信息之外,还需存储一个指示其直接后继的信息(即直接后继的存储位置)。这两部分信息组成数据元素的存储映像,称为节点,它包括两个域,其中存储数据单元信息的域被称为数据域,存储直接后继存储位置的域被称为指针域,指针域中的存储信息乘坐指针或链。

结构:


4521c33e37cb4869a676ce6321be3713.jpg


从上图可以看出,链式存储结构在逻辑上是连续的,但是在物理上不一定连续;

现实中的结点一般都是从堆上申请出来的;

从堆上申请的空间,是按照一定的策略来分配的,两次申请的空间可能连续,也可能不连续(一般都不是连续,这里大家可以用vscode跑一边看看内存监视,这里就不演示了)。


2、链表的分类


实际中链表的结构非常多样,主要总结为以下6种特征组成的8种链表结构:

①单向或双向


052209b84c4b45e59c0edc7c8dc9eb48.jpg


②带头或不带头


d7742ff2cffd464585a01d6d1ac8a561.jpg


③循环或者非循环


381cb17b64204bd8982a85d088144c8a.jpg


常用的两种组合结构:


343990123d754004b65ee1e720c5a827.jpg


无头单向非循环链表:

结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。

带头双向循环链表:

结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单了。


3、链表的实现


这篇文章先实现第一种常用的链表——无头单向非循环链表

因为学校的教材可能都是带头的,那样更容易理解,但在现实运用中,带头的并不常用,没有学过不带头的UU也不用担心,其实实现起来是类似的,而且学会不带头的,再去看带头的就简单很多了。特点:随机存储,顺序存取


3.1 结构体定义


首先我们先看看无头单向非循环链表的结构体如何实现

代码如下:


typedef int SLTDateType;
typedef struct SListNode
{
  SLTDateType data;//存放数据
  struct SListNode* next;//指向下一结点的指针
}SLTNode;


3.2 接口函数定义


代码如下:


SLTNode* BuyListNode(SLTDateType x);//动态申请结点
void SListPushBack(SLTNode** pphead, SLTDateType x);//尾插
void SListPushFront(SLTNode** pphead, SLTDateType x);//头插
void SListPopBack(SLTNode** pphead);//尾删
void SListPopFront(SLTNode** pphead);//头删
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x);//插入(之后)
void SListErase(SLTNode** pphead, SLTNode* pos);//删除(之后)
void SListInsertAfter(SLTNode* pos, SLTDateType x);//插入(之前)
void SListEraseAfter(SLTNode* pos);//删除(之前)
SLTNode* SListFind(SLTNode* phead, SLTDateType x);//查找
void SListPrint(SLTNode* phead);//打印
void SListDestory(SLTNode** pphead);//销毁链表


3.3 接口函数的实现


这里提一句,接口函数的命名并不是固定的,但是要有由头,不能瞎取

一个优秀程序员要有良好的代码素养

毕竟在公司里,代码不仅是写给你自己看的

动态申请结点函数(BuyListNode)

你可以理解为新增结点初始化操作

代码如下:


SLTNode* BuyListNode(SLTDateType x)
{
  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  if (newnode == NULL)
  {
    printf("malloc fail\n");
    exit(-1);
  }
  newnode->data = x;
  newnode->next = NULL;
  return newnode;
}


这里首先使用了一个malloc函数实现动态内存分配,令第一个元素为x,并让指向下一个节点为NULL,这里我们可以看到,和之前的顺序表对比,我们会发现,在内存分配上,链表所分配空间更合理,不会造成大量浪费内存的现象,这是链表的一个优点。

尾部插入函数(SListPushBack)

显而易见,就是在链表尾部插入新元素

代码如下:


void SListPushBack(SLTNode** pphead, SLTDateType x)
{
  assert(pphead);
  SLTNode* newnode = BuyListNode(x);
  if (*pphead == NULL)
  {
    *pphead = newnode;
  }
  else
  {
    SLTNode* tail = *pphead;
    while (tail->next != NULL)
    {
      tail = tail->next;
    }
    tail->next = newnode;
  } 
}


在上面的代码中我们可以看到,在链表中插入元素,需要申请新的结点空间,这里我们考虑两种情况:

一种是链表为空的情况,那我们直接进行赋值插入即可;

第二种是链表中有元素的情况,我们借用另外一段临时链表空间tail进行插入(注意,这里要使用*进行赋值,否则形参无法改变实参的结果,不理解的小伙伴可以再去复习一下C语言中指针的知识)

头部插入函数(SListPushFront)

代码如下:


void SListPushFront(SLTNode** pphead, SLTDateType x)
{
  assert(pphead);
  SLTNode* newnode = BuyListNode(x);
  newnode->next = *pphead;
  *pphead = newnode;
}


头插的实现我们只需要借助临时链表newnode存储要插入的值x,再将x指向要插入的链表pphead,再将临时链表newnode赋回给pphead,即可完成头插操作

尾部删除函数(SListPopBack)

代码如下:


void SListPopBack(SLTNode** pphead)
{
  assert(pphead);
  assert(*pphead != NULL);//断言链表为空
  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指向的就是空,那么就直接释放内存,再置空;

第二种是链表还有元素的情况,在这里我们复制原链表利用while循环进行遍历,再释放掉尾元素空间,令尾元素前一个元素指向空。

头部删除函数(SListPopBack)

代码如下:


void SListPopFront(SLTNode** pphead)
{
  assert(pphead);
  assert(*pphead != NULL);//断言链表为空
  SLTNode* next = (*pphead)->next;
  free(*pphead);
  *pphead = next;
}


在这里同样考虑链表为空的情况,加一个断言,避免越界访问,头删需要先把指针指向第二个元素再进行释放内存,二者顺序不可颠倒。

插入函数——之后(SListInsertAfter)

在单链表中,一般的插入都是再某元素之后,这里涉及到单链表的一个缺点,他不能像顺序表一样通过下标直接访问某个元素,单链表查找元素都是通过遍历查找的,因为在内存中可能是不连续的,单链表仅仅是通过指针来访问下一个结点,而无法访问上一个结点,所以这里正常的插入是在某元素之后,在某个元素之前插入也可以实现,不过更复杂,对于初学者来说,这个更简单也更适合。

代码如下:


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


这里的第二个断言是防止找不到上一个元素pos,导致无法插入,这个在pos元素后插入是先把要插入元素x封装成一个节点指向pos的初始下一元素,再将pos指向要插入的元素结点,完成插入操作。

要注意的是,顺序不可以颠倒哦,如果先将pos指向x,那么x将无法找到下一个元素结点

删除函数——之后1(SListErase)

在这里删除函数不管是某函数之前还是之后相对都没那么复杂了,我们先看删除某个元素之后的写法。

代码如下:


void SListErase(SLTNode** pphead, SLTNode* pos)
{
  assert(pphead);
  assert(pos);
  if (*pphead == pos)
  {
    SListPopFront(pphead);
  }
  else
  {
    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    prev->next = pos->next;
    free(pos);
  }
}


这种写法首先我们分两种情况:

第一种是只剩一个元素结点,这个我们直接调用头删就可以了;

第二种是还有多个元素结点,使用while循环遍历链表找到pos元素,将pos上一个元素结点指向pos元素的下一个元素结点,再将pos的内存释放。

插入函数——之前(SListInsertBefore)

代码如下:


void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
  assert(pphead);
  assert(pos);
  SLTNode* newnode = BuyListNode(x);
  if (*pphead == pos)
  {
    newnode->next = *pphead;
    *pphead = newnode;
  }
  else
  {
    SLTNode* posPrev = *pphead;
    while (posPrev->next != pos)
    {
      posPrev = posPrev->next;
    }
    posPrev->next = newnode;
    newnode->next = pos;
  }
}


和前面一样分两种情况讨论:

第一种情况是只有一个元素,那么我们就直接将x元素结点指向原链表pphead,再重新赋值即可;

第二种是链表中有多个元素,使用while循环遍历链表找到pos上一元素结点,使其指向要插入的元素结点x,再将x指向pos元素结点,完成插入操作。

删除函数——之后2(SListEraseAfter)

代码如下:


void SListEraseAfter(SLTNode* pos)
{
  assert(pos);
  assert(pos->next);
  SLTNode* next = pos->next;
  pos->next = next->next;
  free(next);
}


这个写法看起来比前面的删除更为简洁,你觉得哪个更好,更符合实际应用,就用哪个;


查找函数(SListFind)

代码如下:


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


简单来说就是利用循环来进行遍历查找,没啥好讲的。

打印函数(SListPrint)

代码如下:


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


同样的通过遍历链表来进行逐个打印元素,用->连接更为直观。

销毁链表函数(SListDestory)

代码如下:


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


这里也是通过遍历链表逐个元素节点释放内存空间。


4、结语


这就是无头单向非循环链表的接口函数实现,对比一下我们会发现单链表和顺序表各自的优缺点,他们两个都不完美,因此在实际应用中,这两种线性表都是有需求的,我们都需要掌握好,才能打好基础,下一章节我们来讲讲带头双向循环链表的实现。


制作不易,如有不正之处敬请指出,感谢大家的来访,UU们的观看是我坚持下去的动力,在时间的催化剂下,让我们彼此都成为更优秀的人吧!!!

b9c0ee6149724c4095d693241a47f178.png

相关文章
|
4天前
|
存储 C语言
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
26 4
|
5天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
4天前
|
C语言
【数据结构】双向带头循环链表(c语言)(附源码)
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点:双向、带头和循环。与单链表相比,它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1),提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现,包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
17 0
|
2天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
44 9
|
1天前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息?
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息,操作系统能够实现用户模式和内核模式之间的无缝切换,为用户程序提供稳定、可靠的系统服务。
20 4
|
25天前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
25 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
5天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
24天前
初步认识栈和队列
初步认识栈和队列
53 10
|
19天前
数据结构(栈与列队)
数据结构(栈与列队)
15 1
|
25天前
|
算法
数据结构与算法二:栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式
这篇文章讲解了栈的基本概念及其应用,并详细介绍了中缀表达式转换为后缀表达式的算法和实现步骤。
39 3