C++实现线性表 - 02 单向链表

简介: 今天我们来动手实现一下链表结构,链表在我们后续的数据结构中用的十分频繁,可以说就是实现后续很多数据结构一个的基本工具,也是最容易的数据结构之一,我们先从最基础的单向链表讲起,小白刚开始学习肯定会被折磨的头疼,我也是这样的,但只要啃下这块硬骨头就已经前进一大步了!
写在前面:
今天我们来动手实现一下链表结构,链表在我们后续的数据结构中用的十分频繁,可以说就是实现后续很多数据结构一个的基本工具,也是最容易的数据结构之一,我们先从最基础的单向链表讲起,小白刚开始学习肯定会被折磨的头疼,我也是这样的,但只要啃下这块硬骨头就已经前进一大步了!

何为链表

我们先看下面这张图来理解一下什么是链表,直接讲代码可能会比较头晕,我们先从图入手。

1.jpg

上面就是一个最基本的单向链表,链表的作用有很多,它可以存储数据也可以连接不同的结点信息,解决很多问题。

链表首先一个很重要的性质就是需要一个头结点,但是头结点的实现也有两种,一种是像上面一样直接将存有数据的结点当成头结点,但是每次插入结点的时候可能都需要将头结点指向新的结点;另一种可能会更好理解一些,head指针单独指向一个空结点,这个结点不存任何东西(如下图所示),所有新创建的结点都接到头结点之后,我更喜欢这种方式,因为实现起来也更容易理解一些,所以接下来的代码都以这种方式实现。

2.jpg

链表的创建

我们先以单向链表的实现为例,结点结构体也以最简单的形式创建。

struct node
{
    int data;        //数据
    node* next;      //指向下一个结点的指针
};

接下来就是对于链表的初始化操作了,其实很多人包括我自己,刚开始之所以对链表很抗拒,是因为不知道如何进行结点的创建,只要知道如何创建,后面就顺风顺水啦~

node* head = NULL;    //将头指针设为全局变量,方便使用

//结点的初始化
void init_node()
{
    node* new_node = new node;
    new_node->data = -1;    //将数据初始化一个不可能插入的数据
    new_node->next = NULL;  //初始化指针为空
    head = new_node;        //将头指针指向这一个新创建的结点,这样就有了一个空结点啦~
}

头插法

实现起来非常简单,只需要三步即可,直接看下面图解。

3.jpg

4.jpg

5.jpg

void head_insert(int key)
{
    node* new_node = new node;
    new_node->data = key;
    new_node->next = head->next;    //将新结点的next指向head的ne
    head->next = new_node;          //将head的next指向新结点
}

尾插法

其实尾插法可以和头插法一样,也创建一个尾指针,只不过不是让它指向空结点,而是指向最后一个结点,每次插入新结点都将尾指针指向它,这样每次采用尾插法时可以直接找到链表的最后一个结点,进行插入操作。

但是,为了方便初学者理解,我们暂时不引入上述操作,而是在只有头指针的基础上进行插入,大家后续可以尝试自己去创建一个尾指针,我们这里就用一个临时指针去寻找链表的最后一个结点。

void end_insert(int key)
{
    node* new_node = new node;
    node* temp = head;                //创建一个临时指针
    while (temp->next != NULL)        //将临时指针指向最后一个结点
        temp = temp->next;
    new_node->data = key;            //给新结点赋值
    new_node->next = temp->next;    //将新结点的next指向temp的next
    temp->next = new_node;            //将temp的next指向新结点
}

删除结点

删除结点的操作其实和插入操作比较类似,需要用到两个临时指针,一个去找到要删除的结点,一个去找到要删除结点的前一个结点。

6.jpg
7.jpg

8.jpg

void delete_node(int key)
{
    node* temp = head->next;     //创建一个临时指针寻找删除结点
    node* prev = head;           //同样创建一个指针寻找删除结点的前一个结点
    while (temp->data != key && temp != NULL)
    {
        prev = temp;
        temp = temp->next;
    }
    if (temp == NULL)
    {
        cout << "没有此结点" << endl;
        return;
    }
    prev->next = temp->next;     //让前一个结点指向删除结点的next
    temp->next = NULL;           //让删除结点的next指向空
    delete[]temp;
    temp = NULL;
}

遍历链表

相信经过上面的学习,对你来说链表的遍历就已经是小儿科啦,话不多说直接上代码!

void show()
{
    node* temp = head->next;  //创建一个临时指针
    if (temp == NULL)
    {
        cout << "当前还没有创建结点" << endl;
        return;
    }
    while (temp != NULL)      //遍历整个链表
    {
        cout << temp->data << " ";
        temp = temp->next;
    }
    cout << endl;
}

全部代码

#include<bits/stdc++.h>
using namespace std;

struct node
{
    int data;        //数据
    node* next;        //指向下一个结点的指针
};

node* head = NULL;    //将头指针设为全局变量,方便使用
void init_node();         //初始化结点
void head_insert(int);    //头插法
void end_insert(int);     //尾插法
void delete_node(int);    //删除结点
void show();              //遍历链表

int main()
{
    init_node();
    head_insert(4);
    head_insert(9);
    end_insert(7);
    show();
    delete_node(4);
    show();
}

void show()
{
    node* temp = head->next;
    if (temp == NULL)
    {
        cout << "当前还没有创建结点" << endl;
        return;
    }
    while (temp != NULL)
    {
        cout << temp->data << " ";
        temp = temp->next;
    }
    cout << endl;
}

void init_node()
{
    node* new_node = new node;
    new_node->data = -1;
    new_node->next = NULL;
    head = new_node;
}

void head_insert(int key)
{
    node* new_node = new node;
    new_node->data = key;
    new_node->next = head->next;    //将新结点的next指向head的ne
    head->next = new_node;          //将head的next指向新结点
}

void end_insert(int key)
{
    node* new_node = new node;
    node* temp = head;                //创建一个临时指针
    while (temp->next != NULL)        //将临时指针指向最后一个结点
        temp = temp->next;
    new_node->data = key;            //给新结点赋值
    new_node->next = temp->next;    //将新结点的next指向temp的next
    temp->next = new_node;            //将temp的next指向新结点
}

void delete_node(int key)
{
    node* temp = head->next;
    node* prev = head;
    while (temp->data != key && temp != NULL)
    {
        prev = temp;
        temp = temp->next;
    }
    if (temp == NULL)
    {
        cout << "没有此结点" << endl;
        return;
    }
    prev->next = temp->next;
    temp->next = NULL;
    delete[]temp;
    temp = NULL;
}

如果大家有什么问题的话,欢迎在下方评论区进行讨论哦~

目录
相关文章
|
22天前
|
C++
【链表】还不会用C++实现链表?一文教会你各种链表的实现
【链表】还不会用C++实现链表?一文教会你各种链表的实现
|
1月前
【数据结构】单链表之--无头单向非循环链表
【数据结构】单链表之--无头单向非循环链表
|
21天前
|
存储 算法 C语言
线性表,双向链表,静态链表,循环链表(约瑟夫环)(上)
线性表,双向链表,静态链表,循环链表(约瑟夫环)
39 5
|
18天前
|
存储 缓存 C++
C++链表常用的函数编写(增查删改)内附完整程序
C++链表常用的函数编写(增查删改)内附完整程序
|
24天前
|
存储 设计模式 算法
【C/C++ 数据结构 线性表】深入理解与实现栈:从基础到应用的全面探索
【C/C++ 数据结构 线性表】深入理解与实现栈:从基础到应用的全面探索
52 0
|
24天前
|
存储 算法 C语言
【C/C++ 链表结构】探索链表迭代器:C++实现的深入分析与优化策略
【C/C++ 链表结构】探索链表迭代器:C++实现的深入分析与优化策略
36 0
|
存储 算法 程序员
【C/C++ 线性表 简介】C/C++中的线性表探索:从标准库到自定义实现
【C/C++ 线性表 简介】C/C++中的线性表探索:从标准库到自定义实现
24 0
|
1月前
|
存储 缓存 算法
C++链表解析:从基础原理到高级应用,全面掌握链表的使用
C++链表解析:从基础原理到高级应用,全面掌握链表的使用
49 0
|
2月前
|
C语言 C++
【c++】用c++实现带头双向循环链表
【c++】用c++实现带头双向循环链表
|
2月前
|
Java C++ Python
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-456 求链表各节点的平均值(C++解法)
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-456 求链表各节点的平均值(C++解法)
29 0

热门文章

最新文章