IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓ 		图片批量下载器
↓批量下载图片,美女图库↓ 		图片自动播放器
↓图片自动播放器↓ 		一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 数据结构与算法-链表 -> 正文阅读

[数据结构与算法]数据结构与算法-链表

数据结构与算法【C语言】

一、数据结构与算法-单向链表

??优点：删除和插入方便。
??缺点：查找某元素时需遍历链表中的所有结点。

1.1 简单单向链表

?? 1.1.1 简单链表的存储结构

???? 简单单向链表的存储结构如下图所示，
在这里插入图片描述

?? 1.1.2 在链表指定位置处插入元素

???? 具体步骤如下所示：
???? ?? 1) 创建指向头结点的辅助结点(LinkNode *pCurrent)
???? ?? 2) 将辅助结点移动至指定位置处
???? ?? 3) 插入元素；注意：插入元素时需要新开辟结点(LinkNode *newNode)存放需要插入的数据。
???? 插入步骤如下图所示，

在这里插入图片描述
???? 实现代码如下所示：

// 在给定位置处插入元素
void Insert_LinkList(LinkList* list, void* data, int pos) {
	// 判断链表和数据是否为空
	if (list == NULL || data == NULL) return;
	// 判断插入位置是否正常
	if (pos < 0 || pos>list->size) pos = list->size; // 若插入位置异常，则在链表尾部插入元素
	// 创建辅助结点，定位到pos指向的结点
	LinkNode* pCurrentLinkNode = list->head;
	for (int i = 0; i < pos; i++) {
		pCurrentLinkNode = pCurrentLinkNode->next;
	}
	// 插入数据
	//   1) 开辟新结点(newNode)，保存数据
	LinkNode* newNode = (LinkNode*)malloc(sizeof(LinkNode));
	newNode->data = data;
	//  2) 更改结点的next指针，插入数据
	newNode->next = pCurrentLinkNode->next;
	pCurrentLinkNode->next = newNode;
	// 元素个数加1
	list->size++;
}

?? 1.1.3 在指定位置删除元素

???? 具体步骤如下所示：
???? ?? 1) 创建指向头结点的辅助结点(LinkNode pCurrent)
???? ?? 2) 将辅助结点移动至指定位置处
???? ?? 3) 删除结点中的元素；注意：删除元素时需要创建一个指向被删除结点的临时指针(tempNode)，结点中元素删除完毕后，需要释放该结点所占用的内存，否则会造成内存泄漏。
???? 删除步骤如下图所示，在这里插入图片描述

// 删除指定位置的元素
void RemoveValueByPos_LinkList(LinkList* list, int pos) {
	// 判断链表和数据是否为空
	if (list == NULL) return;
	if (pos < 0 || pos>list->size) return;
	
	// 创建辅助结点，查找pos位置处的结点
	LinkNode* pCurrentLinkNode = list->head;
	for (int i = 0; i < pos; i++) {
		pCurrentLinkNode = pCurrentLinkNode->next;
	}
	// 缓存当前结点，否则会造成内存泄露
	LinkNode* newNode = pCurrentLinkNode->next;
	pCurrentLinkNode->next = newNode->next;
	// 释放缓存结点
	free(newNode);
	list->size--;
}

?? 1.1.4 完整代码

// 头文件 LinkList.h
#ifndef LINKLIST_H
#define LINKLIST_H
#include<stdlib.h>
#include<stdio.h>
#include<string.h>

// 打印函数
typedef void (*PRINT)(void*);
// 比较函数
typedef int (*COMPARE)(void*, void*);

// 定义链表结点
typedef struct LINKNODE {
	// 数据域
	void* data;
	// 指针域
	struct LINKNODE* next;
}LinkNode;

// 链表
typedef struct LINKLIST {
	// 头结点
	LinkNode* head;
	// 元素的个数
	int size;
}LinkList;

// 链表初始化
LinkList* Init_LinkList();

// 在给定位置处插入元素,插入成功返回1，插入失败返回-1
void Insert_LinkList(LinkList* list, void* data, int pos);

// 删除指定位置的元素
void RemoveValueByPos_LinkList(LinkList* list, int pos);

// 删除特定值的元素
void RemoveValueByValue_LinkList(LinkList* list, void* data, COMPARE compare);

// 查找，根据传入的值查找，并返回第一个为data的位置pos
int Find_LinkList(LinkList* list, void* data, COMPARE compare);

// 第一个元素的结点
void* Front_LinkLsit(LinkList* list);

// 返回链表中元素的个数
int Size_LinkList(LinkList* list);

// 打印链表
void Print_LinkList(LinkList* list, PRINT print);
// 释放链表空间
void FreeSpace_LinkList(LinkList* list);

#endif // !LINKLIST_H

// LinkList.c
#include"LinkList.h"
// 链表初始化
LinkList* Init_LinkList() {
	LinkList* list = (LinkList*)malloc(sizeof(LinkList));
	if (list != NULL) {
		list->size = 0;
		list->head = (LinkNode*)malloc(sizeof(LinkNode));
		if (list->head != NULL) {
			list->head->data = NULL;
			list->head->next = NULL;
		}
	}
	else {
		printf("内存分配失败!");
		return NULL;
	}
	return list;
}


// 在给定位置处插入元素,插入成功返回1，插入失败返回-1
void Insert_LinkList(LinkList* list, void* data, int pos) {
	// 判断链表和数据是否为空
	if (list == NULL || data == NULL) return;
	// 判断插入位置是否正常
	if (pos < 0 || pos>list->size) pos = list->size; // 若插入位置异常，则在链表尾部插入元素
	// 创建辅助结点，定位到pos指向的结点
	LinkNode* pCurrentLinkNode = list->head;
	for (int i = 0; i < pos; i++) {
		pCurrentLinkNode = pCurrentLinkNode->next;
	}
	// 插入数据
	//     开辟新结点，保存数据
	LinkNode* newNode = (LinkNode*)malloc(sizeof(LinkNode));
	newNode->data = data;
	newNode->next = pCurrentLinkNode->next;
	pCurrentLinkNode->next = newNode;
	// 元素个数加1
	list->size++;
}

// 删除指定位置的元素
void RemoveValueByPos_LinkList(LinkList* list, int pos) {
	// 判断链表和数据是否为空
	if (list == NULL) return;
	if (pos < 0 || pos>list->size) return;
	
	// 创建辅助结点，查找pos位置处的结点
	LinkNode* pCurrentLinkNode = list->head;
	for (int i = 0; i < pos; i++) {
		pCurrentLinkNode = pCurrentLinkNode->next;
	}
	// 缓存当前结点，否则会造成内存泄露
	LinkNode* newNode = pCurrentLinkNode->next;
	pCurrentLinkNode->next = newNode->next;
	// 释放缓存结点
	free(newNode);
	list->size--;
}

// 删除特定值的元素
void RemoveValueByValue_LinkList(LinkList* list, void* data, COMPARE compare) {
	if (list == NULL || data == NULL) return;
	// 创建辅助结点，遍历整个链表，删除第一个与data相等的元素
	LinkNode* pCurrent = list->head;
	while (pCurrent) {
		if (compare(pCurrent->next->data, data) == 1) {
			// 删除pCurrent->next结点
			// 简历缓存结点
			LinkNode* newNode = pCurrent->next;
			pCurrent->next = newNode->next;
			// 释放缓存结点
			free(newNode);
			list->size--;
			return;
		}
		// 结点指针指向下一个结点
		pCurrent = pCurrent->next;
	}
}

// 查找，根据传入的值查找，并返回第一个为data的位置pos
int Find_LinkList(LinkList* list, void* data, COMPARE compare) {
	if (list == NULL || data == NULL) return -1;
	// 创建辅助结点,跳过头结点
	LinkNode* pCurrent = list->head->next;
	int pos = 0, flag = -1;
	while (pCurrent) {
		if (compare(pCurrent->data, data) == 1) {
			return flag = pos;
		}
		// 移动位置
		pos++;
		// 将指向当前结点的指针移向下一个结点
		pCurrent = pCurrent->next;
	}
	return flag;
}
// 第一个元素的结点
void* Front_LinkLsit(LinkList* list) {
	if (list == NULL) return NULL;
	return list->head->next->data;
}

// 返回链表中元素的个数
int Size_LinkList(LinkList* list) {
	if (list == NULL) return -1;
	return list->size;
}

// 打印链表
void Print_LinkList(LinkList* list, PRINT print) {
	if (list == NULL) return;
	// 创建辅助结点
	LinkNode* pCurrent = list->head->next;
	while (pCurrent) {
		// 打印结点中的数据
		print(pCurrent->data);
		// 移动辅助当前结点指向的位置
		pCurrent = pCurrent->next;
	}
}

// 释放链表空间
void FreeSpace_LinkList(LinkList* list) {
	if (list == NULL) return;
	// 先释放链表中每个结点的空间
	LinkNode* pCurrent = list->head;
	while (pCurrent) {
		// 缓存下一个结点
		LinkNode* pNext = pCurrent->next;
		// 释放当前结点
		free(pCurrent);
		pCurrent = pNext->next;
	}
	free(list);
}

// main.c
#include"LinkList.h"
#include<string.h>

#define MAX_NUM 10

typedef struct PERSON {
	char name[64];
	int age;
}Person;


// 打印函数
void myPrint(void* data) {
	Person* p = (Person*)data;
	printf("姓名：%s，年龄：%d\n", p->name, p->age);
}

// 比较函数, data1为动态数组中的元素，data2为用户传入的数据
int compare(void* data1, void* data2) {
	Person* p1 = (Person*)data1;
	Person* p2 = (Person*)data2;
	// 如果姓名和年龄均相等，则判定data1与data2相等
	if (!strcmp(p1->name, p2->name) && p1->age == p2->age) return 1;
	return -1;
}

int main() {
	// 初始化结构体
	Person p1 = { "aaa", 20 }, p2 = { "bbb", 30 }, p3 = { "ccc", 40 }, p4 = { "ddd", 50 }, p5 = {"eee", 60};

	// 初始化数组
	LinkList* list = Init_LinkList();

	// 插入结构体数据
	Insert_LinkList(list, &p1, 0);
	Insert_LinkList(list, &p2, 0);
	Insert_LinkList(list, &p3, 0);
	Insert_LinkList(list, &p4, 0);
	Insert_LinkList(list, &p5, 0);
	// 删除前的数组
	printf("删除结点前的链表：\n");
	Print_LinkList(list, myPrint);

	// 根据位置删除元素
	RemoveValueByPos_LinkList(list, 0);
	// 删除后的数组
	printf("删除0号结点后的链表：\n");
	Print_LinkList(list, myPrint);

	// 根据值删除数组
	Person p6 = { "aaa", 20 };
	RemoveValueByValue_LinkList(list, &p6, compare);
	printf("删除数据为{name：aaa, age: 20}的结点后的链表：\n");
	Print_LinkList(list, myPrint);
	
	// 根据值查找位置
	printf("{name：ccc, age: 40}所在位置：%d\n", Find_LinkList(list, &p3, compare));
	//RemoveValueByPos_LinkList(list, Find_LinkList(list, &p3, compare));
	//Print_LinkList(list, myPrint);

	printf("\n=====================\n");
	// 数组大小
	printf("链表中元素个数：%d\n", Size_LinkList(list));

	//返回第一个结点
	Person* ret = (Person*)Front_LinkLsit(list);
	printf("姓名：%s, 年龄：%d", ret->name, ret->age);
	
	// 释放链表空间
	FreeSpace_LinkList(list);
	
	return 0;
}

?? 1.1.5 运行结果

???? 运行结果如下所示，
在这里插入图片描述

1.2 改进后的链表

?? 1.2.1 改进链表的存储结构

??改进后的链表结点(LinkNode)仅包含指针域(LinkNode *next)，无数据域。用链表维(LinkList)护链表结点(LinkNode)和元素数量(size)。链表结构如下所示，
在这里插入图片描述
??值得注意的是，放入链表中的数据必须包含一个链表结点，通过链表结点将数据串联串联，具体如下所示。
在这里插入图片描述
??相较于1.1小节的链表，改进后的链表在插入元素无需开辟新结点存储数据，仅需改变结点的next指针即可。

?? 1.2.2 向改进后的链表插入元素

??向改进后的链表插入元素如下图所示，
在这里插入图片描述

// 向链表中指定位置插入元素
void Insert_LinkList(LinkList* list, LinkNode* node, int pos) {
	// 判断边界情况
	if (list == NULL || node == NULL) return;
	if (pos < 0 || pos >list->size) pos = list->size; // 插入到链表末尾
	// 找到pos位置处对应的结点
	//    1) 创建辅助结点
	LinkNode* pCurrent = &list->head;
	for (int i = 0; i < pos; i++) {
		pCurrent = pCurrent->next;
	}
	//    2) 将传入的node,插入到链表中
	node->next = pCurrent->next;
	pCurrent->next = node;
	// 与包含指针与和数据域的结点相比，更加节省空间，不用新开辟结点保存数据
	//    3) 将链表中的元素数量+1
	list->size++;
}

二、参考链接

???1、数据结构与算法知识点总结
???2、C++教程
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用：海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题＜有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-10-08 21:07:03  更:2022-10-08 21:09:17 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/25 19:43:17-

图片自动播放器
↓图片自动播放器↓ 		TxT小说阅读器
↓语音阅读,小说下载,古典文学↓ 		一键清除垃圾
↓轻轻一点,清除系统垃圾↓ 		图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码