当前位置:   article > 正文

[数据结构与算法] 线性表之单链表初始化详解

链表初始化

活动地址:CSDN21天学习挑战赛

一、什么是链表

1.1 定义

根据数据的存储结构,数据结构可分为数组和链表。

数组:连续的内存空间。

链表:离散的内存空间。

链表通过指针将一组离散的内存块串联在一起。每个内存块称为链表的 节点,每个节点包含数据域和指针域。

链表相关知识点如下:

在这里插入图片描述

1.2 特点

  1. 动态分配存储空间,无需预先估计存储空间,使用灵活。
  2. 消耗内存空间大,除存储数据外,还需存储地址。
  3. 插入和删除效率高,由于使用指针连接各节点,插入和删除时只需改变指针指向即可,无需移动其他元素,时间复杂度O(1)。
  4. 随机访问效率低,由于内存空间不连续,访问节点时需要从第一个节点遍历链表,时间复杂度O(n)。

1.3 节点分类

头节点:数据域为空,或存放链表大小,指针域存储首元节点的地址,对于一个链表,头节点不是必须的。(为了统一操作,无头空链表使用尾插法,首元结点的处理与其他不同)

首元节点:链表存储第一个数据元素的节点。

尾节点:链表存储最后一个数据元素的节点。

头指针:指向链表的第一个节点,有头节点指向头节点,没有头节点则指向首元节点。

二、单链表

2.1 定义

单链表通过任意的存储单元存储线性表中的数据元素,每个节点由数据域指针域两部分组成,如下图,其中data为数据域,存放数据元素,next为指针域,存放其直接后继节点的地址。

在这里插入图片描述

2.2 特点

  1. 单链表只能单向遍历
  2. 为了统一所有节点的处理方法,可增加头节点,对于一个链表来说,头节点可有可无。

带头结点的单链表如下:

在这里插入图片描述

不带头结点的单链表如下:

在这里插入图片描述

2.3 基本操作原理与实现

序号基本操作描述
1initial()构造/初始化链表
2insert()插入元素
3delete()删除元素
4find()按值查找,如存在返回地址,不存在返回null
5size()获取链表大小,即链表中元素的个数
6getValue()取值,链表不支持下标访问(当然可以实现,但也是通过指针实现的),所以用指针取出指向的节点的值
7empty()判空
8reverse()反转
2.3.1 初始化链表
2.3.1.1 配置选项

就像买电脑手机一样,链表也有不同配置,没有哪个更好,只有哪个适合当前的需求。

  1. 是否为空
  2. 头节点
  3. 尾指针
  4. 表长

链表初始化配置如下:

头指针头节点成员节点尾指针大小
0. 不带头节点的空链表
1. 带头节点的空链表
2. 带头节点的非空链表(头插法)
3. 带头节点的非空链表(尾插法)
4. 功能最全的链表
2.3.1.2 各种链表初始化

首先定义一下节点类型,数据域为int类型,指针域为struct Node类型:

typedef struct Node
{
    int data;
    struct Node* next;
} node;
  • 1
  • 2
  • 3
  • 4
  • 5
0.不带头节点的空链表
node *initLinkList()
{
    node *head = NULL;
    return head;
}
  • 1
  • 2
  • 3
  • 4
  • 5
1.带头节点的空链表
node *initLinkList()
{
    node *head = (node *)malloc(sizeof(node));
    head->next = NULL;
    return head;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
2.带头节点的非空链表(头插法)
node *initLinkList()
{
    node *head = (node *)malloc(sizeof(node)); //头指针与头节点
    head->next = NULL;
    //头插法建立链表
    for (int i = 0; i < 5; i++)
    {
        node *a = (node *)malloc(sizeof(node));
        a->data = i;
        a->next = head->next;
        head->next = a;
    }
    return head;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
3.带头节点的非空链表(尾插法)
node *initLinkList()
{
    node *head = (node *)malloc(sizeof(node)); //头指针与头节点
    node *tail = head;                         //尾指针
    //尾插法建立链表
    for (int i = 0; i < 5; i++)
    {
        node *a = (node *)malloc(sizeof(node));
        a->data = i;
        tail->next = a;
        tail = a;
    }
    tail->next = NULL;
    return head;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

总结

  1. 链表,一定要保证尾节点的指针置空。
  2. 每一个节点要至少被一个指针指向。
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/喵喵爱编程/article/detail/767409
推荐阅读
相关标签
  

闽ICP备14008679号