数据结构预算法------链表

目录

数据结构预算法------链表

01、链表的定义

02、链表的优缺点

03、单链表的基本操作（代码实现）

04、理论知识参考文献

01、链表的定义

链表（Linked List）：一种线性表数据结构。它使用一组任意的存储单元（可以是连续的，也可以是不连续的），来存储一组具有相同类型的数据。

简单来说，链表就是实现线性表链式存储结构的基础。

链表是由链节点通过 next 指针链接而构成的，我们可以先定义一个简单的「链节点类」，再来定义完整的「链表类」。

  • 链节点类（即 Node 类）：使用成员变量 data 表示数据元素的值，使用指针变量 next表示后继指针。

  • 链表类（即 LinkedList 类）：使用一个链节点变量 head 来表示链表的头节点。

我们在创建空链表时，只需要把相应的链表头节点变量设置为空链接即可。

图解：

链表通过将一组任意的存储单元串联在一起。其中，每个数据元素占用若干存储单元的组合称为一个「链节点」。为了将所有的节点串起来，每个链节点不仅要存放一个数据元素的值，还要存放一个指出这个数据元素在逻辑关系上的直接后继元素所在链节点的地址，该地址被称为「后继指针 nextnext」。

02、链表的优缺点

  • 优点：存储空间不必事先分配，在需要存储空间的时候可以临时申请，不会造成空间的浪费；一些操作的时间效率远比数组高（插入、移动、删除元素等）。

  • 缺点：不仅数据元素本身的数据信息要占用存储空间，指针也需要占用存储空间，链表结构比数组结构的空间开销大。

03、单链表的基本操作（代码实现）

定义链节点类

#include <cstdlib>
struct NODE {
	int data; // 数据
	NODE *next; // 后继
};

定义单链表的抽象数据结构

struct LinkList {
	NODE *head; //头[链表的第0个元素]
	bool IsEmpty(); //判断链表是否为空
	void Init(); // 初始化链表
	void HeadCreate(int c); // 插入：头插法
	void TailCreate(int c); // 插入：尾插法
	void Traverse(); // 链表迭代器
	void Insert(int i, int data); // 在i的位置插入一个node节点,数据为data
	bool Delete(int i, int &e); // 删除链表中第i个位置的节点，并将数据赋值给e

	void Modify(int x, int y); // 将单链表中值为x的数据改为 y
	void Replace(int i, int x); // 将i位置上的数据替换为 x
	int Seek(int x); // 查找单链表是否有值为x的节点，若有则返回值为x的位置，若没有则返回 -1
	int Count(int x);// 统计单链表节点值为x的数据的个数
	int Length(); // 求单链表的长度
	void Sort(); //链表排序

	NODE *Unsortfind(int x); // 无序查找
	bool GetElem(int i, int &e); // 取第i位置上的数据并保存在e中
	void Destroy(); // 销毁单链表
};

头插法图解

链表头部插入元素：在链表第 1个链节点之前插入值为 valval 的链节点。

  1. 先创建一个值为 value 的链节点 newNode。
  2. 然后将 newNode的 next 指针指向链表的头节点 head -> next。
  3. 再将链表的头节点head -> next指向 newNode。

中间位置插入节点图解

链表中间插入元素：在链表第 i个链节点之前插入值为 data的链节点。

  1. 使用指针变量 cur (代码实现中使用p) 和一个节点变量node来申请新节点的空间，并存放数据。令 cur 指向链表的头节点。
  2. 沿着链节点的 next 指针遍历链表，指针变量 cur每指向一个链节点，计数器就做一次计数。
  3. 当遍历到第（i-1）个链节点时停止遍历。
  4. 创建一个值为 data 的链节点 node。
  5. 将 node ->next 指向 cur ->next。
  6. 然后令cur ->next 指向 node。

具体算法实现

/**
 * @brief  统计单链表节点值为x的数据的个数
 *
 * @param x 需要对比的数据
 *
 * @return 值为X的数量
 */
int LinkList::Count(int x) {
	NODE *p;
	int count = 0;
	p = head ->next;
	for (int i = 0; i < Length(); i++) {
		if (x == p ->data) {
			count++;
		}
		p = p ->next;
	}
	return count;
}
/**
 * @brief 将i位置上的数据替换为 x
 *
 * @param i 链表的节点位置
 * @param y 给该节点替换的数据
 */
void LinkList::Replace(int i, int y) {
	if (i < 0 || IsEmpty() || i > Length()) return;
	NODE *p;
	p = head ->next;
	for (int j = 0; j < i - 1; j++) {
		p = p ->next;
	}
	p ->data = y;
}
/**
 * @brief 查找单链表是否有值为x的节点，
 *
 * @param x 需要对比的数据
 *
 * @return 若有则返回值为x的位置，若没有则返回 -1
 */
int LinkList::Seek(int x) {
	NODE *p;
	p = head ->next;
	for (int i = 0; i <= Length() - 1; i++) {
		if (x == p ->data) {
			return i;
		}
		p = p ->next;
	}
	return -1;
}
/**
 * @brief 将单链表中值为x的数据改为 y
 *
 * @param x 需要查找的数据
 * @param y 用于替换的数据
 */
void LinkList::Modify(int x, int y) {
	NODE *p;
	p = head ->next;
	int j = Seek(x);
	if (j == -1) return;
	for (int i = 0; i < j; i++) {
		p = p ->next;
	}
	p ->data = y;
	Modify(x, y);
}
/**
 * @brief 求单链表的长度
 *
 * @return 链表的长度
 */
int LinkList::Length() {
	NODE *p;
	int length = 0;
	p = head ->next;
	while (p) {
		p = p ->next;
		length++;
	}
	return length;
}

/**
 * @brief 删除链表中第i个位置的节点，并将数据赋值给
 *
 * @param e 被删除节点的数据
 * @param i 被删除节点的位置
 *
 * @return 删除成功返回true，否则返回false
 */
bool LinkList::Delete(int i, int &e) {
	if (i < 0 || IsEmpty()) return false;
	NODE *p,*q;
	p = head ->next;
	for (int j = 0; (j < i - 1 ) && (p ->next != NULL); j++) {
		p = p ->next;
	}
	e = p ->next ->data;
	q = p ->next ->next;
	p ->next = q;
	if (p ->next == NULL) {
		return false;
	}
	return true;
}
/**
 * @brief 在i的位置插入一个node节点,数据为data
 *
 * @param data 插入节点的数据
 * @param i 插入节点的位置
 */
void LinkList::Insert(int i, int data) {
	NODE *p,*node;
	p = head ->next;
	node = (NODE *) malloc(sizeof(NODE));
	node ->data = data;
	node ->next = NULL;
	if (i <= 0) {
		node ->next = head -> next;
		head ->next = node;
		return;
	}
	for (int j = 0; j < i - 1 && p ->next != NULL; j++) {
		p = p ->next;
	}
	node ->next = p ->next;
	p ->next = node;

	if (p ->next == NULL) {
		p ->next = node;
		return;
	}
}
/**
 * @brief 链表的迭代器，返回每个链表中每个NODE的值
 */
void LinkList::Traverse() {
	NODE *p;
	p = head ->next;
//	int countSize = sizeof(NODE);
//	printf("每个NODE的大小：%d", countSize);
	while (p) {
		printf("%5d", p->data);
		p = p ->next;
	}
	printf("\n");
}
/**
 * 尾插法
 * @param c(count) 插入数据的数量
 */
void LinkList::TailCreate(int c) {
	if (c <= 0) return;
	NODE *q,*node;
	q = head;
	int x = 1;
	for (int i = 0; i < c; i++) {
		node = (NODE *)malloc(sizeof(NODE));
//		x = rand() % 300;
		node ->data = x++;
		node ->next = NULL;
		// 连接
		q ->next = node;
		q = node;
	}
}
/**
 * 头插法
 * @param c(count) 插入数据的数量
 */
void LinkList::HeadCreate(int c) {
	if (c <= 0) return;
	NODE *p;
	int x = 1;
	for (int i = 0; i < c; i++) {
		p = (NODE *)malloc(sizeof(NODE));
		p ->data = x++;
		p ->next = NULL;
		// 连接
		p ->next =  head ->next;
		head ->next = p;
	}
}
/**
 * 初始化链表
 */
void LinkList::Init() {
	head = (NODE *)malloc(sizeof(NODE));
	head ->next = NULL;
}
/**
 * 判断链表是否为空
 */
bool LinkList::IsEmpty() {
	if (head ->next == NULL) {
		return true;
	}
	return false;
}

最后三个实现（无序查找、查找某一个并保存在变量e中、销毁线程表）

/**
 * @brief 销毁单链表（将每个节点动态分配的空间释放）
 */
void LinkList::Destroy() {
	if (IsEmpty()) return;
	NODE *p,*p_next;
	p = head ->next;
	p_next = p;
	int i = 1;
	while (p_next) {
		p_next = p_next ->next;
		printf("\n销毁前的值：%d", p ->data);
		if (p != NULL) {
			free(p);
			printf("\n销毁%d个节点！", i++);
		}
		printf("\n销毁后的值：%d", p ->data);
		p = p_next;
	}
	head ->next = NULL;
	printf("\n销毁成功！");
}
/**
 * @brief 取第i位置上的数据并保存在e中
 *
 * @param e 获取到的数据
 * @param i 获取的链表位置
 *
 * @return true / false
 */
bool LinkList::GetElem(int i, int &e) {
	if (i < 0 || IsEmpty() || i >= Length()) return false;
	NODE *p;
	p = head ->next;
	for (int j = 0; j < i - 1; j++) {
		p = p ->next;
	}
	e = p ->data;
	return true;
}
/**
 * @brief 返回节点的值为x的第一个节点的地址，无值为X节点时，返回NULL
 *
 * @param x
 *
 * @return *x / NULL
 */
NODE *LinkList::Unsortfind(int x) {
	NODE *p;
	p = head ->next;
	for (int i = 0; i < Length(); i++) {
		if (p ->data == x) {
			return p;
		}
		p = p->next;
	}
	return NULL;
}

04、理论知识参考文献

算法通关手册（LeetCode） | 算法通关手册（LeetCode） (itcharge.cn)

本次内容到此结束，没有任何商业行为，主要用于学习，如有不正确的地方，麻烦给位大佬多多提点，鄙人必当认真改正！！！谢谢大家，祝诸位天天开心，学习进步！

# 链表 # c++
Logo
开放原子开发者工作坊

开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！

更多推荐

开源成为金融领域创新发展的新动力引擎

开源成为金融领域创新发展的新动力引擎

avatar 开放原子开发者工作坊

开源成为推动城市数字化转型的核心动力

城市，不仅是人们工作与生活的基本载体，更是承载着亿万人民的希望与梦想。近年来，我国智慧城市建设如火如荼，开源技术的深度融合为其发展注入了新的活力。在民生、环保、公共安全、城市服务等多个领域，开源技术的应用不仅为民众带来了切实的便捷，而且促进了政府决策的科学化，显著提升了城市综合治理能力。

avatar 开放原子开发者工作坊

OpenLoong项目通过技术监督委员会（TOC）评审

OpenLoong项目通过技术监督委员会（TOC）评审

avatar 开放原子开发者工作坊