【023】C/C++数据结构之链表及其实战应用

article/2025/8/25 14:14:45

C++ 链表及其实战应用

  • 引言
  • 一、链表的概述
  • 二、利用链表设计一个学生管理系统
    • 2.1、设计主函数main()
    • 2.2、实现插入节点
    • 2.3、实现链表的遍历
    • 2.4、实现链表的查找
    • 2.5、实现删除某个节点
    • 2.6、实现释放链表
    • 2.7、完整代码
  • 总结

引言

💡 作者简介：专注于C/C++高性能程序设计和开发，理论与代码实践结合，让世界没有难学的技术。包括C/C++、Linux、MySQL、Redis、TCP/IP、协程、网络编程等。
👉
🎖️ CSDN实力新星，社区专家博主
👉
🔔 专栏介绍：从零到c++精通的学习之路。内容包括C++基础编程、中级编程、高级编程；掌握各个知识点。
👉
🔔 专栏地址：C++从零开始到精通
👉
🔔 博客主页：https://blog.csdn.net/Long_xu

🔔 上一篇：【022】C++的结构体、共用体以及枚举详解（最全讲解）

一、链表的概述

链表（Linked List）是一种常见的数据结构，它由若干个节点（Node）组成，每个节点包含一个数据元素和指向下一个节点的指针。相邻两个节点之间通过指针连接起来，形成了链式结构。

链表可以分为单向链表、双向链表和循环链表三种类型。其中单向链表每个节点只有一个指向下一个节点的指针；双向链表每个节点除了有指向下一个节点的指针外，还有指向前一个节点的指针；循环链表则是将最后一个节点的指针指向头结点，使得整个链条形成了一个闭环。

单向链表是由一个一个节点组成，节点没有名字，每个节点从堆区动态申请，节点间物理上是非连续的，但是每个节点通过指针保存下一个节点的位置达到逻辑上的连续。
在这里插入图片描述

数组和链表的优缺点：

  • 静态数组：缺点是必须事先知道数组元素个数，设置过多了浪费内存空间，设置过少容易溢出，插入、删除数据效率低；优点是遍历元素效率高，支持随机访问。
  • 动态数组：不需要实现知道元素的个数，在使用中动态申请，插入、删除数据效率低；优点是遍历元素效率高，支持随机访问。
  • 链表：优点是不需要实现知道元素的个数，在使用中动态申请，插入、删除数据不需要移动数据；缺点是遍历效率低。

二、利用链表设计一个学生管理系统

通过实战的方式掌握链表的使用。

2.1、设计主函数main()

首先是一个帮助函数和main()函数的实现：

void help()
{cout << "*************************************" << endl;cout << "1) help:" << endl;cout << "2) insert:" << endl;cout << "3) print:" << endl;cout << "4) search:" << endl;cout << "5) delete:" << endl;cout << "6) free:" << endl;cout << "7) quit:" << endl;cout << "*************************************" << endl;
}int main() {help();struct Student *head=NULL;while (1){char cmd[64] = { 0 };cout << "请输入指令：";cin >> cmd;if (strcmp(cmd, "help")==0){help();}else if (strcmp(cmd, "insert")==0){cout << "请输入节点信息（id, name）：";struct Student *tmp=new struct Student;cin >> tmp->id >> tmp->name;head=insert_link(head,tmp);}else if (strcmp(cmd, "print")==0){print_link(head);}else if (strcmp(cmd, "search") == 0){char name[32] = { 0 };cout << "请输入查询的姓名：";cin >> name;struct Student *res=search_link(head, name);if (res != NULL){cout << "查询结果："<<res->id << " " << res->name << endl;}else{cout << name << "不存在" << endl;}}else if (strcmp(cmd, "delete") == 0){cout << "请输入要删除的节点学号：";int num;cin >> num;head = delete_link(head, num);}else if (strcmp(cmd, "free") == 0){head=free_link(head);if (head == NULL)cout << "已完成释放" << endl;}else if (strcmp(cmd, "quit") == 0){head = free_link(head);if (head == NULL)cout << "已完成释放" << endl;cout << "已退出系统" << endl;return 0;}else{cout << "不识别的指令，请正确输入指令。" << endl;help();}}return 0;
}

2.2、实现插入节点

插入节点的方式有三种：

  • 头部插入。
  • 尾部插入。
  • 有序插入（双指针法）。
// 插入链表
struct Student * insert_link(struct Student *head, struct Student *node)
{
#if 0//头插法// 链表不存在时；if (head == NULL){head = node;head->next = NULL;}else{// 链表串联起来。头插法node->next = head;head = node;}return head;
#elif 0// 尾插法if (head == NULL){head = node;head->next = NULL;return head;}// 查找末尾struct Student *cur = head;while (cur->next != NULL){cur = cur->next;}// 尾部插入cur->next = node;node->next = NULL;return head;
#else// 有序插入if (head == NULL){head = node;head->next = NULL;return head;}// 双指针法struct Student *cur = head;struct Student *pre = head;while (cur->id < node->id && cur->next != NULL){// 保存cur记录pre = cur;// cur移动到下一个cur = cur->next;}// 判断插入点的位置if (cur->id > node->id){if (cur == head)//头部插入{node->next = head;head = node;}else//中部插入{pre->next = node;node->next = cur;}}else{// 尾部插入cur->next = node;node->next = NULL;}
#endif
}

2.3、实现链表的遍历

// 遍历链表
void print_link(struct Student *head)
{if (head == NULL){cout << "link is empty." << endl;return;}// 循环遍历链表struct Student *cur;cur = head;while (cur != NULL){cout << cur->id << " " << cur->name << endl;cur = cur->next;}
}

2.4、实现链表的查找

struct Student *search_link(struct Student *head,const char *name)
{if (head == NULL)return NULL;struct Student *cur = head;while (cur->next != NULL && strcmp(cur->name, name) != 0)cur = cur->next;if (strcmp(cur->name, name) == 0)return cur;return NULL;
}

2.5、实现删除某个节点

struct Student *delete_link(struct Student *head,int num)
{if (head == NULL){cout << "链表不存在" << endl;return NULL;}struct Student *cur = head;struct Student *pre = head;// 查找节点while (cur->next != NULL && cur->id != num){pre = cur;cur = cur->next;}if (cur->id == num){cout << "找到节点，并删除了。" << endl;if (cur == head)//头部删除{head = cur->next;}else//中尾部删除pre->next = cur->next;delete cur;}else{cout << "节点不存在" << endl;}return head;
}

2.6、实现释放链表

struct Student *free_link(struct Student *head)
{if (head == NULL){cout << "链表不存在" << endl;return NULL;}struct Student *cur = head;while (cur != NULL){head = head->next;delete cur;cur = head;}return head;
}

2.7、完整代码

#include <stdio.h>#include <iostream>
#include <string.h>
using namespace std;void help()
{cout << "*************************************" << endl;cout << "1) help:" << endl;cout << "2) insert:" << endl;cout << "3) print:" << endl;cout << "4) search:" << endl;cout << "5) delete:" << endl;cout << "6) free:" << endl;cout << "7) quit:" << endl;cout << "*************************************" << endl;
}struct Student {int id;char name[16];struct Student *next;
};// 插入链表
struct Student * insert_link(struct Student *head, struct Student *node)
{
#if 0//头插法// 链表不存在时；if (head == NULL){head = node;head->next = NULL;}else{// 链表串联起来。头插法node->next = head;head = node;}return head;
#elif 0// 尾插法if (head == NULL){head = node;head->next = NULL;return head;}// 查找末尾struct Student *cur = head;while (cur->next != NULL){cur = cur->next;}// 尾部插入cur->next = node;node->next = NULL;return head;
#else// 有序插入if (head == NULL){head = node;head->next = NULL;return head;}// 双指针法struct Student *cur = head;struct Student *pre = head;while (cur->id < node->id && cur->next != NULL){// 保存cur记录pre = cur;// cur移动到下一个cur = cur->next;}// 判断插入点的位置if (cur->id > node->id){if (cur == head)//头部插入{node->next = head;head = node;}else//中部插入{pre->next = node;node->next = cur;}}else{// 尾部插入cur->next = node;node->next = NULL;}
#endif
}// 遍历链表
void print_link(struct Student *head)
{if (head == NULL){cout << "link is empty." << endl;return;}// 循环遍历链表struct Student *cur;cur = head;while (cur != NULL){cout << cur->id << " " << cur->name << endl;cur = cur->next;}
}struct Student *search_link(struct Student *head,const char *name)
{if (head == NULL)return NULL;struct Student *cur = head;while (cur->next != NULL && strcmp(cur->name, name) != 0)cur = cur->next;if (strcmp(cur->name, name) == 0)return cur;return NULL;
}struct Student *delete_link(struct Student *head,int num)
{if (head == NULL){cout << "链表不存在" << endl;return NULL;}struct Student *cur = head;struct Student *pre = head;// 查找节点while (cur->next != NULL && cur->id != num){pre = cur;cur = cur->next;}if (cur->id == num){cout << "找到节点，并删除了。" << endl;if (cur == head)//头部删除{head = cur->next;}else//中尾部删除pre->next = cur->next;delete cur;}else{cout << "节点不存在" << endl;}return head;
}struct Student *free_link(struct Student *head)
{if (head == NULL){cout << "链表不存在" << endl;return NULL;}struct Student *cur = head;while (cur != NULL){head = head->next;delete cur;cur = head;}return head;
}int main() {help();struct Student *head=NULL;while (1){char cmd[64] = { 0 };cout << "请输入指令：";cin >> cmd;if (strcmp(cmd, "help")==0){help();}else if (strcmp(cmd, "insert")==0){cout << "请输入节点信息（id, name）：";struct Student *tmp=new struct Student;cin >> tmp->id >> tmp->name;head=insert_link(head,tmp);}else if (strcmp(cmd, "print")==0){print_link(head);}else if (strcmp(cmd, "search") == 0){char name[32] = { 0 };cout << "请输入查询的姓名：";cin >> name;struct Student *res=search_link(head, name);if (res != NULL){cout << "查询结果："<<res->id << " " << res->name << endl;}else{cout << name << "不存在" << endl;}}else if (strcmp(cmd, "delete") == 0){cout << "请输入要删除的节点学号：";int num;cin >> num;head = delete_link(head, num);}else if (strcmp(cmd, "free") == 0){head=free_link(head);if (head == NULL)cout << "已完成释放" << endl;}else if (strcmp(cmd, "quit") == 0){head = free_link(head);if (head == NULL)cout << "已完成释放" << endl;cout << "已退出系统" << endl;return 0;}else{cout << "不识别的指令，请正确输入指令。" << endl;help();}}return 0;
}

总结

链表（Linked List）是一种常见的数据结构，它由若干个节点（Node）组成，每个节点包含一个数据元素和指向下一个节点的指针。相邻两个节点之间通过指针连接起来，形成了链式结构。

链表可以分为单向链表、双向链表和循环链表三种类型。其中单向链表每个节点只有一个指向下一个节点的指针；双向链表每个节点除了有指向下一个节点的指针外，还有指向前一个节点的指针；循环链表则是将最后一个节点的指针指向头结点，使得整个链条形成了一个闭环。

相比于数组等线性存储结构，链表具有以下优点：

  1. 链表可以动态扩展，不需要预先定义大小。

  2. 插入和删除操作非常高效，只需要修改相邻两个节点之间的指针即可。

  3. 对于大规模数据存储时空效率更高。

但是也存在一些缺点：

  1. 随机访问元素比较困难，需要遍历整个链条才能找到对应位置的元素。

  2. 存储多余的地址信息会占用额外空间。

在这里插入图片描述


http://chatgpt.dhexx.cn/article/QFdZ8d80.shtml

相关文章

KNN分类算法详解

KNN分类算法详解

参考&#xff1a;https://www.cnblogs.com/listenfwind/p/10311496.html https://www.cnblogs.com/listenfwind/p/10685192.html 1. 概述 KNN 可以说是最简单的分类算法之一&#xff0c;同时&#xff0c;它也是最常用的分类算法之一。注意&#xff1a;KNN 算法是有监督学习中的…
阅读更多...
【python代码实现】朴素贝叶斯分类算法

【python代码实现】朴素贝叶斯分类算法

目录 前置知识1、概念2、算法原理2.1、条件概率2.2、全概率2.3、先验概率2.4、后验概率 朴素贝叶斯分类算法1、构建数据集2、分类概率3、条件概率4、先验概率 前置知识 1、概念 上一篇我们讲到的决策树算法&#xff0c;是反映了一种非常明确、固定的判断选择过程&#xff0c;…
阅读更多...
分类算法-KNN(原理+代码+结果)

分类算法-KNN(原理+代码+结果)

KNN&#xff0c;即K最邻近算法&#xff0c;是数据挖掘分类技术中比较简单的方法之一&#xff0c;简单来说&#xff0c;就是根据“最邻近”这一特征对样本进行分类。 1、K-means和KNN区别 K-means是一种比较经典的聚类算法&#xff0c;本质上是无监督学习&#xff0c;而KNN是分…
阅读更多...
伯努利贝叶斯分类算法

伯努利贝叶斯分类算法

贝叶斯分类的核心概念&#xff1a; 我们对某件事情的判断首先有一个概率&#xff0c;这个概率称为先验概率。先验概率时根据经验总结出来的概率值&#xff0c;如果首先没有经验&#xff0c;那么可以将先验概率设置为50%&#xff0c;随着后面事情的发展&#xff0c;再调整先验概…
阅读更多...
【机器学习原理】KNN分类算法

【机器学习原理】KNN分类算法

上一篇&#xff1a;Logistic回归分类算法 文章目录 一、KNN分类算法&#xff1a;用多数表决进行分类1. 用“同类相吸”的办法解决分类问题可视化下的分类问题 2. KNN分类算法的基本方法&#xff1a;多数表决3. 表决权问题4. KNN的具体含义 KNN分类算法原理1. KNN分类算法的基本…
阅读更多...
Python实现分类算法

Python实现分类算法

前言&#xff1a;出自于学校课程数据挖掘与分析布置的实验小作业&#xff0c;案例经典&#xff0c;代码注释较全&#xff0c;供大家参考。 题目&#xff1a; 现有西瓜挑选数据文件&#xff1a;dataset.txt&#xff0c;编程实现朴素贝叶斯算法&#xff0c;并判断有如下特征的瓜…
阅读更多...
贝叶斯分类算法

贝叶斯分类算法

贝叶斯分类是一类分类算法的总称&#xff0c;这类算法均以贝叶斯定理为基础&#xff0c;故统称为贝叶斯分类。而朴素朴素贝叶斯分类是贝叶斯分类中最简单&#xff0c;也是常见的一种分类方法。这篇文章我尽可能用直白的话语总结一下我们学习会上讲到的朴素贝叶斯分类算法&#…
阅读更多...
基于Python实现五大常用分类算法(原理+代码)

基于Python实现五大常用分类算法(原理+代码)

读&#xff1a; 在机器学习和统计中&#xff0c;分类算法通过对已知类别训练集的计算和分析&#xff0c;从中发现类别规则并预测新数据的类别。分类被认为是监督学习的一个实例&#xff0c;即学习可以获得正确识别的观察的训练集的情况。 实现分类的算法&#xff0c;特别是在具…
阅读更多...
EIGRP综合实验解析

EIGRP综合实验解析

实验要求 1.R1为ISP,只能配置IP地址 2.R1与R2之间为PPP封装&#xff0c;使用CHAP认证&#xff0c;R1为主认证方 3.R2-R8地址为172.16.0.0/16 4.R4的S1/1口带宽为800K。R4到R2环回为非等开销负载均衡 5.保证更新安全&#xff0c;减少路由条目数量 6.R6到达R8环回通过R7进行 7.R2…
阅读更多...
EIGRP协议

EIGRP协议

EIGRP是距离矢量路由协议&#xff0c;但又非距离矢量那样路由完全是别人告诉&#xff0c;而是通过维护3张表自己对比计算后放入路由表。同样会受水平分割影响。 EIGRP建邻居过程 第一步&#xff1a;路由器R1和R2接口配置EIGRP后&#xff0c;在相应接口上向外组播发送Hello包…
阅读更多...
EIGRP总结

EIGRP总结

EIGRP 增强内部网关路由协议 无类别距离矢量IGP协议&#xff1b; 增量更新—仅触发更新&#xff0c;无周期更新----更新量小&#xff08;DV&#xff09;&#xff0c;可靠性高&#xff08;RTP&#xff09;&#xff0c;保活机制&#xff08;hello&#xff09; 复合度量—多个参数…
阅读更多...
EIGRP

EIGRP

EIGRP增强型网关路由协议 基本内容&#xff1a; Cisco私有&#xff1b;无类别距离矢量协议&#xff1b;跨层封装协议&#xff0c;封装于网络层–协议号88&#xff1b;组播更新&#xff1a;224.0.0.10 &#xff1b;支持非等开销负载均衡&#xff1b;增量更新&#xff08;部分更…
阅读更多...
思科EIGRP配置及基本讲解

思科EIGRP配置及基本讲解

思科EIGRP配置及基本讲解 什么是EIGRP EIGRP全称 [增强型内部网关路由选择协议] 是思科自主研发的动态路由选择协议&#xff0c;按类型划分是一款IGP协议&#xff0c;距离矢量协议&#xff0c;是一款基于传闻的协议。 EIGRP是思科的私有协议&#xff0c;直到13年&#xff0c;此…
阅读更多...
EIGRP协议的配置

EIGRP协议的配置

EIGRP(Enhanced Interior Gateway Routing Protocol&#xff0c;增强型内部网关路由协议)是Cisco公司开发的一个平衡混合型路由协议&#xff0c;它融合了距离向量和链路状态两种路由协议的优点&#xff0c;支持IP&#xff0c;IPX和ApplleTalk等多种网络层协议。由于TCP/IP是当今…
阅读更多...
网络篇 EIGRP协议-27

网络篇 EIGRP协议-27

目录 一、EIGRP的基本概述 二、EIGRP的特点 三、EIGRP的四种重要技术 四、EIGRP的相关术语 五、EIGRP的三张表 1.路由表 2.邻居表 3.拓扑表 六、EIGRP的五个分组 1.Hello分组&#xff1a; 2.Update更新分组&#xff1a; 3.Query查询分组&#xff1a; 4.Reply应答分…
阅读更多...
EIGRP（Enhanced Interior Gateway Routing Protocol，增加型内部网关路由协议）

EIGRP（Enhanced Interior Gateway Routing Protocol，增加型内部网关路由协议）

EIGRP是Cisco公司于1992年开发的一个无类别距离矢量路由协议&#xff0c;它融合了距离矢量和链路状态两种路由协议的优点。EIGRP是Cisco的专有路由协议&#xff0c; 是Cisco的IGRP协议的增加版。IGRP是一种有类距离矢量协议&#xff0c;Cisco IOS 12.3版以后不再支持该协议。 E…
阅读更多...
EIGRP理论详解及基础实验

EIGRP理论详解及基础实验

EIGRP:( Enhanced Interior Gateway Routing Protocol )增强型内部网关路由协议 EIGRP 是一种Cisco专用协议,同时具备链路状态和距离矢量路由协议的优点.只发送变化后的信息(这类似于链路状态协议),同时只将这些信息发送给邻接路由器(这类似于距离矢量协议). 距离矢量路由协议…
阅读更多...
CSMA协议

CSMA协议

介质访问控制 CSMA协议 1-坚持CSMA 非坚持CSMA p-坚持CSMA 三种CSMA对比总结
阅读更多...
3.4.2 CSMA/CD协议

3.4.2 CSMA/CD协议

为了解决各站点争用总线的问题&#xff0c;共享总线使用了一种专用协议CSMA/CD&#xff0c;它是载波监听多址接入/碰撞检测&#xff08;Carrier Sence Multiple Access Collision Detection&#xff09;的英文缩写。 假设站点C要发送帧&#xff0c;它首先进行载波监听&#xff…
阅读更多...
关于CSMA/CA和CSMA/CD的区别

关于CSMA/CA和CSMA/CD的区别

转载自&#xff1a;https://www.cnblogs.com/aixin0813/p/3289183.html 1.1 载波侦听多路访问 根据具体的监听/发送策略&#xff0c;可将CSMA分为&#xff1a; 非持续CSMA&#xff08;英语&#xff1a;non-persistent CSMA&#xff09; 当要发送帧的设备侦听到线路忙或发生冲…
阅读更多...
推荐文章

Copyright @ 2022~2023