数据结构(单链表)

简介: 数据结构(单链表)

前言

 这是我学习数据结构的第三份笔记,有关单链表的知识。后期我会继续将数据结构知识的笔记补全。


 上一期笔记有关顺序表,没看过的同学可以去看看:


有关顺序表的笔记

https://blog.csdn.net/hsy1603914691/article/details/142280812?spm=1001.2014.3001.5501


链表

链表的概念

1. 链表是⼀种物理存储结构上非连续、非顺序的存储结构。

2. 链表是顺序表的一种,所以它一定在逻辑结构上是线性的。

3. 数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

4. 链表实际上由一个个节点组成。

结点的概念

1. 结点的组成主要有两个部分:当前结点要保存的数据和下⼀个结点的地址(指针变量)。


2. 链表中每个结点都是独立申请的,即需要插⼊数据时才去申请⼀块结点的空间。


3. 我们需要通过指针变量来保存下⼀个结点位置才能从当前结点找到下⼀个结点。


4. 两个节点之间的地址不一定是连续的。  

单链表

定义单链表

typedef int LTDataType
typedef struct SListNode
{
 LTDataType data; //节点数据
 struct SListNode* next; //指针变量⽤保存下⼀个节点的地址
}SLTN;
//SListNode==Single List Node 单链表节点

创建新的节点

SLTN* Add_STLNode(SLTDataType x)
{
  SLTN* node=(SLTN*)malloc(sizeof(SLTN));
  node->data = x;
  node->next = NULL;
  return node;
}

打印单链表

void Print_SLTNode(SLTN* phead)//不需要对原来的链表进行修改,所以只要传值。
{
    assert(phead);
  SLTN* purc = phead;
  while (purc != NULL)
  {
    printf("%d\n", purc->data);
    purc = purc->next;
  }
  printf("NULL\n");
}

尾插单链表

void Back_Push_STLNode(SLTN** pphead, SLTDataType x)//要对原来的链表进行操作,所以传地址。
{
  SLTN* newnode = Add_STLNode(x);
  SLTN* purc = *pphead;
  if (*pphead == NULL)
  {
    *pphead = newnode;
  }
  else
  {
    while (purc->next != NULL)
    {
      purc = purc->next;
    }
    purc->next = newnode;
  }
}

头插单链表

void Front_Push_STLNode(SLTN** pphead, SLTDataType x)
{
  SLTN* newnode = Add_STLNode(x);
  newnode->next = *pphead;
  *pphead = newnode;
}

指定插入单链表

void Insert_STLNode(SLTN** pphead, SLTN* pos, SLTDataType x)
{
  assert(*pphead);
  assert(pos);
  SLTN* newnode=Add_STLNode(x);
  SLTN* prev = *pphead;
  while (prev->next != pos)
  {
    prev = prev->next;
  }
  newnode->next = pos;
  prev->next = newnode;
}

尾删单链表

void Back_Pop_STLNode(SLTN** pphead)
{
  assert(*pphead);
  SLTN* ptail = *pphead;
  SLTN* prev = NULL;
  if (ptail->next == NULL)
  {
    free(ptail);
    ptail = NULL;
  }
  else
  {
    while (ptail->next != NULL)
    {
      prev = ptail;
      ptail = ptail->next;
    }
    prev->next = NULL;
    free(ptail);
    ptail = NULL;
  }
}

头删单链表

void Front_Pop_STLNode(SLTN** pphead)
{
  assert(*pphead);
  if ((*pphead)->next == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  else
  {
    SLTN* second = (*pphead)->next;
    free(*pphead);
    *pphead = second;
  }
}

指定删除单链表

void Delete_STLNode(SLTN** pphead, SLTN* pos)
{
  assert(*pphead);
  assert(pos);
  SLTN* prev = *pphead;
    if ((*pphead)->next == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
    else
    {
      while (prev->next != pos)
      {
        prev = prev->next;
      }
      prev->next = pos->next;
      free(pos);
      pos = NULL;
    }
}

销毁单链表

void Destroy_STLNode(SLTN** pphead)
{
  assert(*pphead);
  SLTN* pcur = *pphead;
  while (pcur)
  {
    if (pcur!=NULL)
    {
      SLTN* next = pcur;
      free(pcur);
      pcur = next->next;
    }
  }
  *pphead = NULL;
}

单链表实现代码

<test.h>文件

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDataType;
typedef struct SListNode
{
  SLTDataType data;
  struct SLTNode* next;
}SLTN;
void PrintSLTNode(SLTN* phead);
void Back_Push_STLNode(SLTN** pphead, SLTDataType x);
SLTN* Add_STLNode(SLTDataType x);
void Front_Push_STLNode(SLTN** pphead, SLTDataType x);
void Back_Pop_STLNode(SLTN** pphead);
void Front_Pop_STLNode(SLTN** pphead);
SLTN* Search_STLNode(SLTN* phead, SLTDataType x);
void Insert_STLNode(SLTN** pphead, SLTN* pos, SLTDataType x);
void STLNode_Insert(SLTN** pphead, SLTN* pos, SLTDataType x);
void Delete_STLNode(SLTN** pphead, SLTN* pos);
void Destroy_STLNode(SLTN** pphead);

<test.c>文件

#include "test.h"
void Print_SLTNode(SLTN* phead)
{
  SLTN* purc = phead;
  while (purc)
  {
    printf("%d\n", purc->data);
    purc = purc->next;
  }
  printf("NULL");
}
SLTN* Add_STLNode(SLTDataType x)
{
  SLTN* node=(SLTN*)malloc(sizeof(SLTN));
  node->data = x;
  node->next = NULL;
  return node;
}
void Back_Push_STLNode(SLTN** pphead, SLTDataType x)
{
  SLTN* newnode = Add_STLNode(x);
  SLTN* purc = *pphead;
  if (*pphead == NULL)
  {
    *pphead = newnode;
  }
  else
  {
    while (purc->next != NULL)
    {
      purc = purc->next;
    }
    purc->next = newnode;
  }
}
void Front_Push_STLNode(SLTN** pphead, SLTDataType x)
{
  SLTN* newnode = Add_STLNode(x);
  newnode->next = *pphead;
  *pphead = newnode;
}
void Back_Pop_STLNode(SLTN** pphead)
{
  assert(*pphead);
  SLTN* ptail = *pphead;
  SLTN* prev = NULL;
  if (ptail->next == NULL)
  {
    free(ptail);
    ptail = NULL;
  }
  else
  {
    while (ptail->next != NULL)
    {
      prev = ptail;
      ptail = ptail->next;
    }
    prev->next = NULL;
    free(ptail);
    ptail = NULL;
  }
}
void Front_Pop_STLNode(SLTN** pphead)
{
  assert(*pphead);
  if ((*pphead)->next == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  else
  {
    SLTN* second = (*pphead)->next;
    free(*pphead);
    *pphead = second;
  }
}
SLTN* Search_STLNode(SLTN* phead, SLTDataType x)
{
  assert(phead);
  SLTN* pcur = phead;
  while (pcur)
  {
    if (pcur->data == x)
    {
      printf("找到了。\n");
      return pcur;
    }
    else
    {
      pcur = pcur->next;
    }
  }
  printf("没找到。\n");
}
void Insert_STLNode(SLTN** pphead, SLTN* pos, SLTDataType x)
{
  assert(*pphead);
  assert(pos);
  SLTN* newnode=Add_STLNode(x);
  SLTN* prev = *pphead;
  while (prev->next != pos)
  {
    prev = prev->next;
  }
  newnode->next = pos;
  prev->next = newnode;
}
void STLNode_Insert( SLTN* pos, SLTDataType x)
{
  assert(pos);
  SLTN* newnode = Add_STLNode(x);
  newnode->next = pos->next;
  pos->next = newnode;
}
void Delete_STLNode(SLTN** pphead, SLTN* pos)
{
  assert(*pphead);
  assert(pos);
  SLTN* prev = *pphead;
  while (prev->next != pos)
  {
    prev = prev->next;
  }
  prev->next = pos->next;
  free(pos);
  pos = NULL;
}
void Destroy_STLNode(SLTN** pphead)
{
  assert(*pphead);
  SLTN* pcur = *pphead;
  while (pcur)
  {
    if (pcur!=NULL)
    {
      SLTN* next = pcur;
      free(pcur);
      pcur = next->next;
    }
  }
  *pphead = NULL;
}
int main()
{
  SLTN* plist = NULL;
  Back_Push_STLNode(&plist,2);
  Back_Push_STLNode(&plist,3);
  Back_Push_STLNode(&plist,4);
  Front_Push_STLNode(&plist, 1);
  //Back_Pop_STLNode(&plist);
  //Front_Pop_STLNode(&plist);
  SLTN* pos1=Search_STLNode(plist,3);
  Insert_STLNode(&plist, pos1, 9);
  STLNode_Insert(pos1, 8);
  Delete_STLNode(&plist, pos1);
  //Destroy_STLNode(&plist);
  Print_SLTNode(plist);
  return 0;
}

致谢

 感谢您花时间阅读这篇文章!如果您对本文有任何疑问、建议或是想要分享您的看法,请不要犹豫,在评论区留下您的宝贵意见。每一次互动都是我前进的动力,您的支持是我最大的鼓励。期待与您的交流,让我们共同成长,探索技术世界的无限可能!

相关文章
|
4月前
【数据结构】单链表(长期维护)(1)
【数据结构】单链表(长期维护)(1)
|
2月前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
37 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
2月前
|
存储
[数据结构] -- 单链表
[数据结构] -- 单链表
26 1
|
3月前
|
存储 Java
java数据结构,线性表链式存储(单链表)的实现
文章讲解了单链表的基本概念和Java实现,包括头指针、尾节点和节点结构。提供了实现代码,包括数据结构、接口定义和具体实现类。通过测试代码演示了单链表的基本操作,如添加、删除、更新和查找元素,并总结了操作的时间复杂度。
java数据结构,线性表链式存储(单链表)的实现
|
2月前
|
存储
【数据结构】——单链表实现
【数据结构】——单链表实现
|
2月前
|
存储
数据结构2——单链表
数据结构2——单链表
34 1
|
2月前
|
存储
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)(一)
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)
|
2月前
|
存储
数据结构--单链表
数据结构--单链表
|
2月前
|
存储 缓存
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)(二)
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)
|
3月前
|
存储 算法 C语言
数据结构基础详解(C语言):单链表_定义_初始化_插入_删除_查找_建立操作_纯c语言代码注释讲解
本文详细介绍了单链表的理论知识,涵盖单链表的定义、优点与缺点,并通过示例代码讲解了单链表的初始化、插入、删除、查找等核心操作。文中还具体分析了按位序插入、指定节点前后插入、按位序删除及按值查找等算法实现,并提供了尾插法和头插法建立单链表的方法,帮助读者深入理解单链表的基本原理与应用技巧。
609 6