1. Toy模板网首页
  2. > Toy博客

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

10月前 作者：Lion Long 分类：Toy博客 阅读(55) 违法举报

这篇具有很好参考价值的文章主要介绍了【023】C/C++数据结构之链表及其实战应用。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

引言

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

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

一、链表的概述

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

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

单向链表是由一个一个节点组成，节点没有名字，每个节点从堆区动态申请，节点间物理上是非连续的，但是每个节点通过指针保存下一个节点的位置达到逻辑上的连续。
【023】C/C++数据结构之链表及其实战应用

数组和链表的优缺点：

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

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

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

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. 存储多余的地址信息会占用额外空间。

【023】C/C++数据结构之链表及其实战应用文章来源地址https://www.toymoban.com/news/detail-477029.html

到了这里，关于【023】C/C++数据结构之链表及其实战应用的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • C语言数据结构之链表

    C语言数据结构之链表

    在上一篇博客中我们提到，线性表包括顺序表和链表，顺序表在上篇博客中已经介绍，本篇博客介绍一下另一种线性表—— 链表 。 概念：链表是⼀种 物理存储结构上⾮连续、⾮顺序 的存储结构，数据元素的 逻辑顺序是通过链表中的指针链接次序实现的 。 链表的结构跟⽕

    2024年04月22日
    浏览(44)
  • C++数据结构之链表（详解）

    C++数据结构之链表（详解）

    主要参考文章地址 01.链表基础知识 | 算法通关手册 (itcharge.cn)） 本次内容是对链表的总结，可以看了上面的文章之后。 在看我下面的内容，做一个简短的复习，且本内容的代码均用C++实现，而参考资料的代码则为python。 每一个标题都有一个完整的链接，也可以点击下面的链

    2024年02月15日
    浏览(75)
  • C语言进阶——数据结构之链表（续）

    C语言进阶——数据结构之链表（续）

    hello，大家好呀，我是Humble，本篇博客承接之前的 C语言进阶——数据结构之链表 的内容 （没看过的小伙伴可以从我创建的专栏C语言进阶之数据结构 找到那篇文章并阅读后在回来哦~） ，上次我们重点说了链表中的 单链表 ，即 不带头单向不循环链表 还说到了链表的分类虽

    2024年01月25日
    浏览(59)
  • 数据结构之链表练习与习题详细解析

    数据结构之链表练习与习题详细解析

    个人主页：点我进入主页 专栏分类：C语言初阶      C语言程序设计————KTV       C语言小游戏     C语言进阶 C语言刷题       数据结构初阶 欢迎大家点赞，评论，收藏。 一起努力，一起奔赴大厂。 目录 1.前言 2.习题解析 2.1习题一 2.2习题二 2.3习题三 2.4习题四 2.

    2024年02月05日
    浏览(44)
  • C/C++数据结构之链表题目答案与解析

    C/C++数据结构之链表题目答案与解析

    个人主页：点我进入主页 专栏分类：C语言初阶      C语言程序设计————KTV       C语言小游戏     C语言进阶 C语言刷题       数据结构初阶 欢迎大家点赞，评论，收藏。 一起努力，一起奔赴大厂。 目录 1.前言  2.题目解析 2.1 移除链表元素 2.2反转链表 2.3链表的中

    2024年02月05日
    浏览(60)
  • 数据结构之链表 - 超详细的教程，手把手教你认识并运用链表

    数据结构之链表 - 超详细的教程，手把手教你认识并运用链表

    顺序表只适合静态的查找和更新，不适合插入和删除元素， 因为在ArrayList中插入和删除元素时，由于需要将后序元素往前后者往后移动，所以时间复杂度会相当高，能达到O(N)。 为了解决这一问题，java 引入了 LinkedList(链表)。 链表是一种 逻辑上连续，物理上不连续 的存储结

    2024年02月09日
    浏览(63)

  • 数据结构例题代码及其讲解-链表

    单链表的结构体定义及其初始化。 ①强调结点 LNode *p; ②强调链表 LinkList p; 01 遍历打印 02 按位查找（有一个带头结点的单链表 L，请设计一个算法查找其第 i 个结点位置，若存在则返回指向该结点的指针，若不存在则返回 NULL。） 03 按值查找（有一个带头结点的单链表 L，请

    2024年02月10日
    浏览(55)
  • 【数据结构与算法】之双向链表及其实现！

    【数据结构与算法】之双向链表及其实现！

    ​                                                                                 个人主页：秋风起，再归来~                                                                                             数据结构与

    2024年04月23日
    浏览(42)
  • c语言数据结构——链表的实现及其基本操作

    c语言数据结构——链表的实现及其基本操作

    顺序表的问题及思考 问题： 中间/头部的插入删除，时间复杂度为O(N) 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到 200，我们再继续插入了5个数据，后面没有数据插

    2023年04月09日
    浏览(85)
  • 第14章_集合与数据结构拓展练习(前序、中序、后序遍历,线性结构,单向链表构建,单向链表及其反转,字符串压缩)

    第14章_集合与数据结构拓展练习(前序、中序、后序遍历,线性结构,单向链表构建,单向链表及其反转,字符串压缩)

    1、前序、中序、后序遍历 分析： 完全二叉树： 叶结点只能出现在最底层的两层，且最底层叶结点均处于次底层叶结点的左侧 2、线性结构 3、其它 4、单向链表构建 （1）定义一个单向链表SingleLinked类 包含私有的静态内部类Node 包含Object类型的data属性和Node类型的next属性 包含

    2024年01月23日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包