【脚踢数据结构】链表（1）

2023-11-23 15:20
文章标签 链表 数据结构 脚踢

本文主要是介绍【脚踢数据结构】链表（1），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

  • (꒪ꇴ꒪ )，Hello我是祐言QAQ
  • 我的博客主页：C/C++语言,Linux基础,ARM开发板，软件配置等领域博主🌍
  • 快上🚘，一起学习，让我们成为一个强大的攻城狮！
  • 送给自己和读者的一句鸡汤🤔：集中起来的意志可以击穿顽石!
  • 作者水平很有限，如果发现错误，可在评论区指正，感谢🙏

        在计算机科学中，数据结构是一种组织和存储数据的方式，使我们可以有效地访问和修改它。链表是一种常见的数据结构，它是线性表的一种重要实现方式。下面，我们将详细地介绍链表及其操作。

一、线性表

        线性表（Linear List）是由n（n≥0）个相同数据类型的元素a1,a2,……,an 组成的有限序列。线性表中元素的个数n定义为线性表的长度，当n=0 时，称为空表。线性表是数据结构中最基本、最简单、也是最常用的一种数据结构。

        常见的两种实现方式：

  1. 数组实现的线性表：使用连续的内存空间存储数据元素，可以通过索引快速访问元素。数组的优点是随机访问效率高，但插入和删除元素可能涉及元素的移动，时间复杂度较高。

  2. 链表实现的线性表：使用一系列的节点，每个节点存储一个数据元素和指向下一个节点的指针。链表的优点是插入和删除元素效率高，不需要移动其他元素，但访问元素需要从头节点开始遍历，时间复杂度较高。

二、链表

       

        链表是一种具体的数据结构它在逻辑上是一对一的排列的，在存储上是非连续的。

算法包含：        

        新建节点、插入节点、查找节点、删除节点、更新节点、遍历、清空、判断空链表等。

 链表分类：

0

链式存储的优点

        ①不需要一块连续内存；

        ②插入和删除效率极高。

1、单向链表        

        单向链表（Singly linked list）是最简单的一种链表，它的每个节点包含两个域，一个数据域（元素域）和一个指正域（链接域）。头链接指向列表中的下一个节点，而最后一个节点则指向一个空值（NULL）。并且在链式存储结构中：数据元素是随机存储的，通过指针表示（控制）数据之间的逻辑关系。

0

       单链表的节点声明：

typedef [节点数据域类型] DataType;
struct Node
{DataType data;//数据域struct Node *next;//指针域
};
 （1）单链表初始化

        一般定义一个不带数据的节点，用来表示整个链表的头部。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>//数据域
typedef int Database;//链表的节点定义
typedef struct Node
{Database data;		//数据域struct Node *next;	//指针域
}node;//初始化链表
node *init_list()
{node *head = malloc(sizeof(node));if (head != NULL)//头节点不带数据，数据域不用管，但是指针域的指针需要做初始化{head->next = NULL;}return head;
}
（2）新建节点

                在C、C++和一些其他编程语言中，node *表示一个指向节点的指针。节点是一种数据结构，通常包含一个值（可能是任何类型的数据）和一个指向下一个节点的指针。

例如，在链表中，每个节点都有一个指向下一个节点的指针，而最后一个节点的指针通常是NULL，表示链表的结束。

//创建节点
node *create_node(Database data)
{node *new = malloc(sizeof(node));if (new != NULL){new->data = data;new->next = NULL;}return new;
}
（3）尾插法
// 尾插法
void insert_tail(node *head, node *new)
{if (head->next == NULL){head->next = new;}else{//定义一个中间变量，防止头节点的地址发生改变node *p = head;while(p->next != NULL)//循环遍历，找到最后一个节点{p = p->next;}p->next = new;}
}

（4）头插法
//头插法
void insert_head(node *head, node *new)
{new->next = head->next;head->next = new;
}

（5）遍历链表
//遍历打印
void display(node *head)
{node *p = head;while(p->next != NULL){p = p->next;printf("%d ", p->data);}printf("\n");
}

（6）查找节点
//查找节点
node *find_node(node *head,Database data)
{node *p = head;while(p->next !=NULL){if (p->next->data == data){return p->next;}p = p->next;}return NULL;}
（7）删除节点：这里有三种删除节点的方法，具体要因情况而选
//删除节点，链表里的数据唯一的情况，因为这种方法只会删除一个bool delete_node(node *head,Database data)
{node *p = head;while(p->next != NULL){if (p->next->data == data){node *dele = p->next;p->next = dele->next;free(dele);dele = NULL;return true;}p = p->next;}return false;
}//删除节点，链表里面数据不是唯一的情况
void delete_node1(node *head, Database data)
{node *p = head;while(p->next != NULL){if (p->next->data == data){node *dele = p->next;p->next = dele->next;free(dele);dele = NULL;continue;		}p = p->next;}
}//删除节点，以节点的方式删除,每次一个
bool delete_node2(node *head, node *dele)
{if(dele ==NULL){return false;}		node *p = head;while(p->next != NULL){if (p->next->data ==dele->data){p->next =dele->next;free(dele);dele = NULL;return true;}p = p->next;}return false;}

（8）判断空链表
#include <stdbool.h>//判断空链表
bool isempty(node *head)
{return head->next == NULL;
}

（9）清空链表
//清空链表
void clear_list(node *head)
{if (isempty(head)){return ;}while(head->next!=NULL){node *dele = head->next;head->next = dele->next;free(dele);dele = NULL;}
}

（10）更新节点
//更新节点
void update_node(node *head, Database old_data, Database new_data)
{if (isempty(head)){return;}node *p = find_node(head, old_data);if (p!=NULL){p->data = new_data;}else{printf("链表里面没有 %d 这个元素\n", old_data);}
}

（11）取出节点
//取出节点
node *get_node(node *head, Database data)
{if (isempty(head)){return NULL;}node *p = head;while(p->next != NULL){if (p->next->data == data){node *tmp = p->next;p->next = tmp->next;return tmp;}p = p->next;}return NULL;
}

（12）指定位置插入节点

//指定位置插入节点
void insert_node_node(node *n1, node *n2)
{insert_head(n1, n2);
}
//就相当于头插法，node2相当于头节点，node1相当于新节点

           

 （12）移动节点
void move_node(node *head, Database d1, Database d2)
{node *p1 = get_node(head, d1);node *p2 = find_node(head, d2);insert_node_node(p2, p1);
}

        将链表中包含数据d1的节点移动到链表中包含数据d2的节点之前的操作。它通过查找数据为d1和d2的节点，并使用insert_node_node函数将节点d1插入到节点d2之前，实现了节点的移动。

单链表实例

        下面我们来完成一个简单的例子，题目为：

        利用头插法，实现输入一个正整数，就插入对应节点，输入小于等于0的数则把其对应的正数节点删除，输入0则显示链表的所有节点数据（遍历）。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>//数据域
typedef int Database;//链表的节点定义
typedef struct Node
{Database data;		//数据域struct Node *next;	//指针域
}node;//初始化链表
node *init_list()
{node *head = malloc(sizeof(node));if (head != NULL)//头节点不带数据，数据域不用管，但是指针域的指针需要做初始化{head->next = NULL;}return head;
}//创建节点
node *create_node(Database data)
{node *new = malloc(sizeof(node));if (new != NULL){new->data = data;new->next = NULL;}return new;
}void insert_head(node *head, node *new)
{new->next = head->next;head->next = new;
}void insert_sort_tail(node *head, node *new)
{if (head->next == NULL){head->next = new;}else{//定义一个中间变量，防止头节点的地址发生改变node *p = head;while(p->next != NULL){if(p->next->data > new->data){insert_head(p, new);return ;}p = p->next;}p->next = new;}
}//遍历
void display(node *head)
{node *p = head;int i = 0;while(p->next != NULL){p = p->next;printf("%s%d", i>0?"->":"", p->data);i++;}printf("\n");
}//查找节点
node *find_node(node *head, Database data)
{node *p = head;while(p->next != NULL){if (p->next->data == data){return p->next;}p = p->next;}return NULL;
}//删除节点，链表里面数据唯一的情况，只删除一个
bool delete_node(node *head, Database data)
{node *p = head;while(p->next != NULL){if (p->next->data == data)//p->next是不是就是我们要删除的节点{node *dele = p->next;p->next = dele->next;free(dele);dele = NULL;return true;}p = p->next;}return false;
}int main(int argc, char const *argv[])
{node *head = init_list();int n;printf("自定义一个简单链表\n");while(1){	scanf("%d", &n);if (n>0)//插入链表{if (!find_node(head, n)){//插入insert_sort_tail(head, create_node(n));}}else if (n<0)//删除节点{	if(!delete_node(head, -n)){printf("链表里面没有这个节点\n");}}else//遍历链表{	display(head);}}return 0;
}

         我们不难看出，当我们输入自定义的链表并在最后补上0，程序将会输出我们的链表，当我们输入一个正数8的时候，程序会把8放在位于第八位的节点上，输入0再次遍历即可得到结果。最后输入-5 将会删除位于第五位的节点。

        单链表的讲解就到这里啦~

        更多C语言、Linux系统、ARM板实战和数据结构相关文章，关注专栏：

   手撕C语言

            玩转linux

                    脚踢数据结构

                            6818（ARM）开发板实战

📢写在最后

  • 今天的分享就到这啦~
  • 觉得博主写的还不错的烦劳 一键三连喔~
  • 🎉感谢关注🎉

这篇关于【脚踢数据结构】链表（1）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/418850。

相关文章

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
csu1329(双向链表)

csu1329(双向链表)

题意：给n个盒子，编号为1到n，四个操作：1、将x盒子移到y的左边；2、将x盒子移到y的右边；3、交换x和y盒子的位置；4、将所有的盒子反过来放。 思路分析：用双向链表解决。每个操作的时间复杂度为O(1)，用数组来模拟链表，下面的代码是参考刘老师的标程写的。 代码如下： #include<iostream>#include<algorithm>#include<stdio.h>#
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
深入手撕链表

深入手撕链表

链表 分类概念单链表增尾插头插插入 删尾删头删删除 查完整实现带头不带头 双向链表初始化增尾插头插插入 删查完整代码 数组 分类 #mermaid-svg-qKD178fTiiaYeKjl {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-
阅读更多...
建立升序链表

建立升序链表

题目1181：遍历链表 时间限制：1 秒 内存限制：32 兆 特殊判题：否 提交：2744 解决：1186 题目描述： 建立一个升序链表并遍历输出。 输入： 输入的每个案例中第一行包括1个整数：n(1<=n<=1000)，接下来的一行包括n个整数。 输出： 可能有多组测试数据，对于每组数据， 将n个整数建立升序链表，之后遍历链表并输出。 样例输
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...
【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟） 题目描述 给定一个链表，链表中的每个节点代表一个整数。链表中的整数由 0 分隔开，表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点，新节点的值为原区间内所有节点值的和。合并后，需要移除所有的 0，并返回修改后的链表头节点。 思路分析 初始化：创建一个虚拟头节点
阅读更多...
学习记录：js算法（二十八）：删除排序链表中的重复元素、删除排序链表中的重复元素II

学习记录：js算法（二十八）：删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一：循环解法二：递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1：（图一）输入：head = [1,1,2]输出：[1,2]示例 2：（图
阅读更多...
【408数据结构】散列 （哈希）知识点集合复习考点题目

【408数据结构】散列 （哈希）知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独，于是我记下了些许笔记相伴，希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法，它通过散列函数将关键字映射到数组的一个位置，从而实现快速查找。这种方法的时间复杂度平均为(
阅读更多...
浙大数据结构：树的定义与操作

浙大数据结构：树的定义与操作

四种遍历 #include<iostream>#include<queue>using namespace std;typedef struct treenode *BinTree;typedef BinTree position;typedef int ElementType;struct treenode{ElementType data;BinTree left;BinTre
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2