AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

C++链表常用的函数编写（增查删改）内附完整程序

2024-04-01 108
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： C++链表常用的函数编写（增查删改）内附完整程序

一、链表主体

// 链表结构体
typedef struct node
{
    int date;
    struct node *next; // 还未定义别名只能使用struct node定义next指针
} Node;
/***
typedef struct 结构名
{
  类型 变量名;
  类型 变量名;
} 结构别名1, 结构别名2; 
这里如果没有typedef定义别名在定义结构体的时候则需要添加 struct node n1;
 ***/

链表由结构体构成，结构体包含节点数据以及指向下一个节点的指针

二、创建链表

// 创建链表
Node *NodeInit(int n)
{
    // 创建链表
    Node *head = new Node; // 头节点 这里也可以使用malloc方式
    // Node *head = (Node *)malloc(sizeof(Node));
    // 头节点一般不存储数据
    Node *per = head;
    for (int i = 0; i < n; i++)
    {
        // 申请新的空间存储相应数据然后放入per指针
        Node *p = new Node;   //申请新的空间
        p->date = i * 10 + 1; //给新的空间写入数据
        p->next = NULL;       //新的空间指向空
        per->next = p;        //原来的节点指向这个新的空间
        per = p;              //获取新空间的数据
    }
    return head;
}

Node *MainHead = NodeInit(5);

三、链表的应用

1.打印链表

// 打印链表数据
void NodeDisplay(Node *head)
{
    Node *p = head->next;
    while (p != NULL)
    {
        // 遍历节点
        std::cout << p->date << " -> ";
        p = p->next;
    }
    std::cout << "NULL" << std::endl;
}

2.求链表长度

// 链表长度
int NodeLenth(Node *head)
{
    Node *p = head->next;
    int count = 0;
    while (p != NULL)
    {
        // 遍历节点
        count++;
        p = p->next;
    }
    return count;
}

3.插入数据（按照指定位置）

// 指定位置插入链表数据 (头节点、插入位置、插入数据)
void NodeInsert(Node *head, int index, int date)
{
    if (index < 0 || index > NodeLenth(head))
        throw "index error"; //如果插入位置超出链表长度抛出异常
    Node *per = head;
    for (int i = 0; i < index; i++)
    {
        // 循环next到index位置
        per = per->next;
    }
    Node *NewNode = new Node;
    NewNode->date = date;
    NewNode->next = per->next;
    per->next = NewNode;
}

4.插入数据（头插）

// 头插
void NodePushFront(Node *head, int date)
{
    Node *per = head;
    Node *NewNode = new Node;
    NewNode->date = date;
    NewNode->next = per->next;
    per->next = NewNode;
}

5.插入数据（尾插）

// 尾插
void NodePushBack(Node *head, int date)
{
    Node *per = head;
    for (int i = 0; i < NodeLenth(head); i++)
    {
        // 让节点指向最后一个节点
        per = per->next;
    }
    Node *NewNode = new Node;
    NewNode->date = date;
    NewNode->next = NULL;
    per->next = NewNode;
}

6.查找元素是否存在

// 查找元素：如果元素存在返回true，不存在返回false
bool NodeFind(Node *head, int date)
{
    Node *p = head->next;
    for (int i = 0; i < NodeLenth(head); i++)
    {
        if (p->date == date)
            return true;
        else
            p = p->next;
    }
    return false;
}

7.删除指定位置数据

// 删除指定位置数据
void NodeDeleteDate(Node *head, int index)
{
    if (index < 0 || index > NodeLenth(head))
        throw "index error"; //如果删除位置超出链表长度抛出异常
    Node *per = head;
    for (int i = 0; i < index; i++)
    {
        per = per->next;
    }
    Node *p = per->next;
    per->next = per->next->next;
    delete p;
}

8.删除最后一个节点

// 删除最后一个节点
void NodePopback(Node *head)
{
    Node *per = head;
    for (int i = 0; i < NodeLenth(head) - 1; i++)
    {
        per = per->next;
    }
    Node *p = per->next;
    per->next = NULL;
    delete p;
}

9.删除第一个节点

// 删除第一个节点
void NodePopFront(Node *head)
{
    Node *per = head;
    Node *p = per->next;
    per->next = per->next->next;
    delete p;
}

10.修改节点数据

// 修改元素
void NodeChange(Node *head, int index, int date)
{
    if (index < 0 || index > NodeLenth(head))
        throw "index error"; //如果修改位置超出链表长度抛出异常
    Node *per = head;
    for (int i = 0; i < index; i++)
    {
        // 让节点指向index位置
        per = per->next;
    }
    per->date = date;
}

11.清空链表节点

// 清空链表
void NodeClear(Node *head)
{
    while (head->next != NULL)
    {
        Node *p = head->next;
        head->next = head->next->next;
        delete p;
    }
}

四、完整程序

/*
 * @Author: Stylle
 * @Date: 2020-08-25 18:08:28
 * @LastEditors: Stylle
 * @LastEditTime: 2020-08-25 21:43:50
 * @FilePath: \learing-master\链表.cpp
 */
#include <iostream>
// 链表结构体
typedef struct node
{
    int date;
    struct node *next; // 还未定义别名只能使用struct node定义next指针
} Node;
/***
typedef struct 结构名
{
  类型 变量名;
  类型 变量名;
} 结构别名1, 结构别名2; 
这里如果没有typedef定义别名在定义结构体的时候则需要添加 struct node n1;
 ***/
// 创建链表
Node *NodeInit(int n)
{
    // 创建链表
    Node *head = new Node; // 头节点 这里也可以使用malloc方式
    // Node *head = (Node *)malloc(sizeof(Node));
    // 头节点一般不存储数据
    Node *per = head;
    for (int i = 0; i < n; i++)
    {
        // 申请新的空间存储相应数据然后放入per指针
        Node *p = new Node;   //申请新的空间
        p->date = i * 10 + 1; //给新的空间写入数据
        p->next = NULL;       //新的空间指向空
        per->next = p;        //原来的节点指向这个新的空间
        per = p;              //获取新空间的数据
    }
    return head;
}
// 链表长度
int NodeLenth(Node *head)
{
    Node *p = head->next;
    int count = 0;
    while (p != NULL)
    {
        // 遍历节点
        count++;
        p = p->next;
    }
    return count;
}
// 指定位置插入链表数据 (头节点、插入位置、插入数据)
void NodeInsert(Node *head, int index, int date)
{
    if (index < 0 || index > NodeLenth(head))
        throw "index error"; //如果插入位置超出链表长度抛出异常
    Node *per = head;
    for (int i = 0; i < index; i++)
    {
        // 循环next到index位置
        per = per->next;
    }
    Node *NewNode = new Node;
    NewNode->date = date;
    NewNode->next = per->next;
    per->next = NewNode;
}
// 头插
void NodePushFront(Node *head, int date)
{
    Node *per = head;
    Node *NewNode = new Node;
    NewNode->date = date;
    NewNode->next = per->next;
    per->next = NewNode;
}
// 尾插
void NodePushBack(Node *head, int date)
{
    Node *per = head;
    for (int i = 0; i < NodeLenth(head); i++)
    {
        // 让节点指向最后一个节点
        per = per->next;
    }
    Node *NewNode = new Node;
    NewNode->date = date;
    NewNode->next = NULL;
    per->next = NewNode;
}
// 打印链表数据
void NodeDisplay(Node *head)
{
    Node *p = head->next;
    while (p != NULL)
    {
        // 遍历节点
        std::cout << p->date << " -> ";
        p = p->next;
    }
    std::cout << "NULL" << std::endl;
}
// 查找元素：如果元素存在返回true，不存在返回false
bool NodeFind(Node *head, int date)
{
    Node *p = head->next;
    for (int i = 0; i < NodeLenth(head); i++)
    {
        if (p->date == date)
            return true;
        else
            p = p->next;
    }
    return false;
}
// 清空链表
void NodeClear(Node *head)
{
    while (head->next != NULL)
    {
        Node *p = head->next;
        head->next = head->next->next;
        delete p;
    }
}
// 删除指定位置数据
void NodeDeleteDate(Node *head, int index)
{
    if (index < 0 || index > NodeLenth(head))
        throw "index error"; //如果删除位置超出链表长度抛出异常
    Node *per = head;
    for (int i = 0; i < index; i++)
    {
        per = per->next;
    }
    Node *p = per->next;
    per->next = per->next->next;
    delete p;
}
// 删除最后一个节点
void NodePopback(Node *head)
{
    Node *per = head;
    for (int i = 0; i < NodeLenth(head) - 1; i++)
    {
        per = per->next;
    }
    Node *p = per->next;
    per->next = NULL;
    delete p;
}
// 删除第一个节点
void NodePopFront(Node *head)
{
    Node *per = head;
    Node *p = per->next;
    per->next = per->next->next;
    delete p;
}
// 修改元素
void NodeChange(Node *head, int index, int date)
{
    if (index < 0 || index > NodeLenth(head))
        throw "index error"; //如果修改位置超出链表长度抛出异常
    Node *per = head;
    for (int i = 0; i < index; i++)
    {
        // 让节点指向index位置
        per = per->next;
    }
    per->date = date;
}
int main(int argc, char **argv)
{
    Node *MainHead = NodeInit(5);
    NodeDisplay(MainHead);
    std::cout << "链表长度：" << NodeLenth(MainHead) << std::endl;
    // 按位置插入数据
    NodeInsert(MainHead, 2, 12);
    NodeDisplay(MainHead);
    std::cout << "链表长度：" << NodeLenth(MainHead) << std::endl;
    // 尾插
    NodePushBack(MainHead, 42);
    NodeDisplay(MainHead);
    std::cout << "链表长度：" << NodeLenth(MainHead) << std::endl;
    // 头插
    NodePushFront(MainHead, 0);
    NodeDisplay(MainHead);
    std::cout << "链表长度：" << NodeLenth(MainHead) << std::endl;
    // 修改数据
    NodeChange(MainHead, 1, 99);
    NodeDisplay(MainHead);
    // 查找数据
    if (NodeFind(MainHead, 12))
    {
        std::cout << "已查询到元素12" << std::endl;
    }
    // 删除指定节点
    NodeDeleteDate(MainHead, 7);
    NodeDisplay(MainHead);
    std::cout << "链表长度：" << NodeLenth(MainHead) << std::endl;
    // 删除最后一个节点
    NodePopback(MainHead);
    NodeDisplay(MainHead);
    std::cout << "链表长度：" << NodeLenth(MainHead) << std::endl;
    // 删除第一个节点
    NodePopFront(MainHead);
    NodeDisplay(MainHead);
    std::cout << "链表长度：" << NodeLenth(MainHead) << std::endl;
    // 清空节点
    NodeClear(MainHead);
    NodeDisplay(MainHead);
    std::cout << "链表长度：" << NodeLenth(MainHead) << std::endl;
    return 0;
}

五、运行结果

六、总结

程序的说明在注释里已经说明的比较清楚了，最后说一下链表的一般使用场景，和其他的几种链表（本文编写的链表为单链表）

1、链表包含两个部分：数据域、节点指针

2、链表一般使用在需要快速插入和删除而不需要随机访问的情况下使用

3、链表和数组的区别：链表数据随机地址存储，访问需要需要从节点遍历，而数组存储在连续的内存空间，可以使用下标访问（随机访问）

4、单向链表：

5、双向链表（不常使用）：

和单向链表相比多一个指针域，一个指向前面的数据节点，一个指向后面的数据节点

6、循环链表：

首尾节点相互链接，特点是”无头无尾“，比较利于数据存储缓存。

虽然本文只编写了单向链表，但是我相信看懂了上面的代码，写出双向链表和循环链表并不是多难。


文章标签：
C++
存储
缓存
关键词：
C++函数
C++程序
链表函数
C++链表
链表c++
凉开水白菜
目录
相关文章
hylreg
|
3月前
|
C++
C++ 根据程序运行的时间和cpu频率来计算在另外的cpu上运行所花的时间
C++ 根据程序运行的时间和cpu频率来计算在另外的cpu上运行所花的时间
hylreg
43 0
c的前世今生
|
1月前
|
存储 程序员 编译器
简述 C、C++程序编译的内存分配情况
在C和C++程序编译过程中，内存被划分为几个区域进行分配：代码区存储常量和执行指令；全局/静态变量区存放全局变量及静态变量；栈区管理函数参数、局部变量等；堆区则用于动态分配内存，由程序员控制释放，共同支撑着程序运行时的数据存储与处理需求。
c的前世今生
92 21
c的前世今生
|
21天前
|
程序员 C++ 容器
在 C++中，realloc 函数返回 NULL 时，需要手动释放原来的内存吗？
在 C++ 中，当 realloc 函数返回 NULL 时，表示内存重新分配失败，但原内存块仍然有效，因此需要手动释放原来的内存，以避免内存泄漏。
c的前世今生
64 4
石小浪♪
|
1月前
|
存储 前端开发 C++
C++ 多线程之带返回值的线程处理函数
这篇文章介绍了在C++中使用`async`函数、`packaged_task`和`promise`三种方法来创建带返回值的线程处理函数。
石小浪♪
44 6
石小浪♪
|
1月前
|
C++
C++ 多线程之线程管理函数
这篇文章介绍了C++中多线程编程的几个关键函数，包括获取线程ID的`get_id()`，延时函数`sleep_for()`，线程让步函数`yield()`，以及阻塞线程直到指定时间的`sleep_until()`。
石小浪♪
21 0
C++ 多线程之线程管理函数
徐霞客320
|
1月前
|
编译器 C语言 C++
C++入门3——类与对象2-2（类的6个默认成员函数）
C++入门3——类与对象2-2（类的6个默认成员函数）
徐霞客320
23 3
徐霞客320
|
1月前
|
编译器 C语言 C++
详解C/C++动态内存函数（malloc、free、calloc、realloc）
详解C/C++动态内存函数（malloc、free、calloc、realloc）
徐霞客320
137 1
徐霞客320
|
1月前
|
存储 编译器 C++
C++入门3——类与对象2-1（类的6个默认成员函数）
C++入门3——类与对象2-1（类的6个默认成员函数）
徐霞客320
26 1
徐霞客320
|
1月前
|
编译器 C语言 C++
C++入门6——模板（泛型编程、函数模板、类模板）
C++入门6——模板（泛型编程、函数模板、类模板）
徐霞客320
38 0
C++入门6——模板（泛型编程、函数模板、类模板）
数据知道
|
2月前
|
编译器 C++
【C++核心】函数的应用和提高详解
这篇文章详细讲解了C++函数的定义、调用、值传递、常见样式、声明、分文件编写以及函数提高的内容，包括函数默认参数、占位参数、重载等高级用法。
数据知道
22 3