数据结构和算法学习记录——线性表之单链表(上)-初始单链表及其尾插函数(顺序表缺陷、单链表优点、链表打印)

简介: 数据结构和算法学习记录——线性表之单链表(上)-初始单链表及其尾插函数(顺序表缺陷、单链表优点、链表打印)

单链表的概念

单链表是一种链式存取的数据结构,链表中的数据是以结点来表示的。

每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置)。

元素就是存储数据的存储单元,指针就是连接每个结点的地址数据。

以“结点的序列”表示的线性表称作线性链表(单链表),单链表是链式存取的结构。


复习一下之前学过的顺序表:

顺序表的缺陷

1.当空间不够时需要增容,而增容需要付出代价,浪费一些空间。

2.为了避免频繁增容,一般地,增容时都增至原本容量的2倍;这样就会可能存在一部分空间没有被使用的情况。

3.顺序表的数据是从开始的位置连续存储的,当需要从头部或者中间插入或删除数据时,就需要挪动数据,效率不高。


顺序表的优势

1.支持随机访问。

(有些算法需要结构支持随机访问,比如:二分查找、优化的快速排序等等)

而链表呢

链表的优势.1.按需申请空间,不用了就释放空间(更合理地使用空间)。 2.在头部或中间插入或删除数据时,不需要挪动数据,效率较高。


链表的缺陷

1.每一个数据,都要存一个指针去链接后面的数据结点。

2.不支持随机访问。

单链表的结构

逻辑结构

想象出来的、便于理解的

物理结构

内存中实际如何存储的

代码呈现

//单链表的基本结构
#define SLTDataType int
typedef struct SListNode
{
    SLTDataType data;
    struct SListNode * next;
}SLTNode;

单链表的打印

//单链表的打印
void SListPrint(SLTNode* phead)
{  //创建一个临时结点,将phead赋给cur
  SLTNode* cur = phead;
  
  //判断cur是否等于空
   while(cur != NULL)
   {
     //打印链表数据
     printf("%d->",cur->data);
     
     //找下一块的数据,就要找下一个结点
     //而下一个结点存放于cur中,通过cur找到下一个结点
     //一直循环,直到next指针指向NULL时,链表打印完成
     cur = cur->next;
   }
}

单链表的尾插函数

要实现单链表尾插,首先判断传入的链表是否为空,如果为空,则直接给其赋值。

如果不为空,则需要找到最后一个结点,即尾结点。尾结点的特征是:next指针指向NULL。

通过这一特征找到尾结点,再将新结点赋给尾结点。同时新结点的next指针指向NULL。

//单链表尾插函数
void SListPushBack(SLTNode ** pphead,SLTDataType x)
{  //创建一个新结点
   SLTNode * newnode = (SLTNode *)malloc(sizeof(SLTNode));
   newnode->data = x;
   newnode->next = NULL;
  //当传入的链表为空时,要先给其赋值,才能进行后面的操作
  //二级指针pphead存储着一级指针变量phead的地址,解引用一次得到phead的地址
   if(*pphead == NULL)
   {
       *pphead = newnode; //将新结点赋给头结点
   }
   else
   {
       //要进行尾插,就要先找到尾结点
       //尾结点的特征:next指针为空指针
       //建立一个新结点,命名为尾结点
       SLTNode * tail = *pphead;
       while(tail->next != NULL)//遍历找到尾结点
       {
           tail = tail->next;
       }
       tail->next = newnode;
   }
}


线性表之单链表(下)

目录
相关文章
|
9天前
|
存储 C语言
【数据结构】顺序表
数据结构中的动态顺序表
17 3
【数据结构】顺序表
|
6天前
|
机器学习/深度学习 数据采集 算法
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机回归模型(SVR算法)项目实战
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机回归模型(SVR算法)项目实战
|
6天前
|
机器学习/深度学习 数据采集 算法
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机分类模型(SVC算法)项目实战
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机分类模型(SVC算法)项目实战
|
6天前
|
机器学习/深度学习 数据采集 监控
算法金 | DL 骚操作扫盲,神经网络设计与选择、参数初始化与优化、学习率调整与正则化、Loss Function、Bad Gradient
**神经网络与AI学习概览** - 探讨神经网络设计,包括MLP、RNN、CNN,激活函数如ReLU,以及隐藏层设计,强调网络结构与任务匹配。 - 参数初始化与优化涉及Xavier/He初始化,权重和偏置初始化,优化算法如SGD、Adam,针对不同场景选择。 - 学习率调整与正则化,如动态学习率、L1/L2正则化、早停法和Dropout,以改善训练和泛化。
6 0
算法金 | DL 骚操作扫盲,神经网络设计与选择、参数初始化与优化、学习率调整与正则化、Loss Function、Bad Gradient
|
9天前
|
存储 DataX C语言
【数据结构】单链表
数据结构中的单链表
11 0
【数据结构】单链表
|
11天前
|
Dart 算法 JavaScript
C#数据结构与算法入门教程,值得收藏学习!
C#数据结构与算法入门教程,值得收藏学习!
|
19天前
|
算法 Java
《JVM由浅入深学习【八】 2024-01-12》JVM由简入深学习提升分(JVM的垃圾回收算法)
《JVM由浅入深学习【八】 2024-01-12》JVM由简入深学习提升分(JVM的垃圾回收算法)
11 0
|
22天前
|
算法 C语言
【数据结构与算法 经典例题】使用栈实现队列(图文详解)
【数据结构与算法 经典例题】使用栈实现队列(图文详解)
|
16天前
|
存储 缓存 算法
堆和栈的区别及应用场景
堆和栈的区别及应用场景
|
22天前
|
算法 C语言
【数据结构与算法 经典例题】使用队列实现栈(图文详解)
【数据结构与算法 经典例题】使用队列实现栈(图文详解)