数据结构（三）——链表

embedded/2025/3/15 19:16:29/

​ 一、线性表的链式表示——链表
线性表链式存储结构的特点是：用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）
为了表示每个数据元素ai与其后继数据元素ai+1之间的逻辑关系，对数据元素ai来说，除了其本身的信息之外，还需要存储一个指示其直接后继的信息（直接后继的存储位置）。这两部分信息组成数据元素ai的存储映像，称为节点。
节点包括两个域，其中存储数据元素信息的称为数据域，存储直接后继存储位置有域称为指针域。指针域中存储的信息称为指针或链。
n个节点[ai(1<=i<=n)的存储映像]链接成一个链表，即为线性表(a1,a2,a3,...,an)

链表存储结构：
​

二、单链表
​

1.单链表——初始化

2.单链表(单个方向)——头插法

每一次把数据都插在头节点的后面

#include<stdio.h>
#include <string.h>
#include<stdlib.h>
#define MAXSIZE 100typedef int ElemType;//链表存储结构
typedef struct node{ElemType data;struct node *next;
}Node;//单链表初始化
Node* initList()
{Node *head = (Node*)malloc(sizeof(Node));head->data = 0;head->next = NULL;return head;
}//单链表头插法
int insertHead(Node* L,ElemType e)
{Node *p = (Node*)malloc(sizeof(Node));p->data = e;p->next = L->next;L->next = p;return 0;
}int main()
{Node *list = initList(); //初始化链表free(list); //释放内存insertHead(list,10);insertHead(list,20);return 1;
}

原理：

①

②

③

3.单链表——遍历

#include<stdio.h>
#include <string.h>
#include<stdlib.h>
#define MAXSIZE 100typedef int ElemType;//链表存储结构
typedef struct node{ElemType data;struct node *next;
}Node;//单链表初始化
Node* initList()
{Node *head = (Node*)malloc(sizeof(Node));head->data = 0;head->next = NULL;return head;
}//单链表头插法
int insertHead(Node* L,ElemType e)
{Node *p = (Node*)malloc(sizeof(Node));p->data = e;p->next = L->next;L->next = p;return 1;
}//单链表遍历
void listNode(Node* L)
{Node *p = L->next; //第一个节点赋值给p指针while(p != NULL) //p不为空，即链表有数据{printf("%d ",p->data); //输出数据p = p->next; //指向下一个节点}printf("\n");
}int main(int argc,char const *argv[])
{Node *list = initList(); //初始化链表insertHead(list,10);insertHead(list,20);insertHead(list,30);listNode(list);return 0;
}

运行：

头插法的顺序和排列的顺序是相反的

4.单链表——尾插法

#include<stdio.h>
#include <string.h>
#include<stdlib.h>
#define MAXSIZE 100typedef int ElemType;//链表存储结构
typedef struct node{ElemType data;struct node *next;
}Node;//单链表初始化
Node* initList()
{Node *head = (Node*)malloc(sizeof(Node));head->data = 0;head->next = NULL;return head;
}//单链表头插法
int insertHead(Node* L,ElemType e)
{Node *p = (Node*)malloc(sizeof(Node));p->data = e;p->next = L->next;L->next = p;return 1;
}//单链表遍历
void listNode(Node* L)
{Node *p = L->next; //第一个节点赋值给p指针while(p != NULL) //p不为空，即链表有数据{printf("%d ",p->data); //输出数据p = p->next; //指向下一个节点}printf("\n");
}//获取尾节点的地址
Node* get_tail(Node *L)
{Node *p = L; //把L链表赋值给p指针while(p->next != NULL){p = p->next;}return p;
}//单链表尾插法
Node* insertTail(Node *tail,ElemType e)
{Node *p = (Node*)malloc(sizeof(Node)); //创建一块空间并赋值给指针p->data = e; //数据域tail->next = p;p->next = NULL; //使新创建的p节点成为新的尾节点 return p;
}int main(int argc,char const *argv[])
{Node *list = initList(); //初始化链表Node *tail = get_tail(list);tail = insertTail(tail,10);tail = insertTail(tail,20);tail = insertTail(tail,30);listNode(list);return 0;
}

运行：

原理：

①当前尾节点指向新创建的一个节点

②新创建的节点指向NULL

5. 在指定位置插入数据

#include<stdio.h>
#include <string.h>
#include<stdlib.h>
#define MAXSIZE 100typedef int ElemType;//链表存储结构
typedef struct node{ElemType data;struct node *next;
}Node;//单链表初始化
Node* initList()
{Node *head = (Node*)malloc(sizeof(Node));head->data = 0;head->next = NULL;return head;
}//单链表头插法
int insertHead(Node* L,ElemType e)
{Node *p = (Node*)malloc(sizeof(Node));p->data = e;p->next = L->next;L->next = p;return 1;
}//单链表遍历
void listNode(Node* L)
{Node *p = L->next; //第一个节点赋值给p指针while(p != NULL) //p不为空，即链表有数据{printf("%d ",p->data); //输出数据p = p->next; //指向下一个节点}printf("\n");
}//获取尾节点的地址
Node* get_tail(Node *L)
{Node *p = L; //把L链表赋值给p指针while(p->next != NULL){p = p->next;}return p;
}//单链表尾插法
Node* insertTail(Node *tail,ElemType e)
{Node *p = (Node*)malloc(sizeof(Node)); //创建一块空间并赋值给指针p->data = e; //数据域tail->next = p;p->next = NULL; //使新创建的p节点成为新的尾节点 return p;
}//在指定位置插入数据
int insertNode(Node *L,int pos,ElemType e)
{//用来保存插入位置的前驱节点Node *p = L;int i = 0;//遍历这个链表找到插入位置的前驱节点while(i < pos - 1)  {p = p->next;i++;if(p == NULL){return 0;}}Node *q = (Node*)malloc(sizeof(Node)); //要插入的新节点q->data = e;q->next = p->next; //插入位置前一个节点的下一个位置赋值给新节点的下一个位置p->next = q; //把新节点赋值给前一个位置的nextreturn 1;
}int main(int argc,char const *argv[])
{Node *list = initList(); //初始化链表Node *tail = get_tail(list);tail = insertTail(tail,10);tail = insertTail(tail,20);tail = insertTail(tail,30);listNode(list);insertNode(list,2,15);listNode(list); sreturn 0;
}

运行：

原理：

①

②先找到插入位置之前的那个位置，然后指向那个位置所指向的下一个位置

（先找到70，再指向80）

③70指向新的节点

6.删除节点

#include<stdio.h>
#include <string.h>
#include<stdlib.h>
#define MAXSIZE 100typedef int ElemType;//链表存储结构
typedef struct node{ElemType data;struct node *next;
}Node;//单链表初始化
Node* initList()
{Node *head = (Node*)malloc(sizeof(Node));head->data = 0;head->next = NULL;return head;
}//单链表头插法
int insertHead(Node* L,ElemType e)
{Node *p = (Node*)malloc(sizeof(Node));p->data = e;p->next = L->next;L->next = p;return 1;
}//单链表遍历
void listNode(Node* L)
{Node *p = L->next; //第一个节点赋值给p指针while(p != NULL) //p不为空，即链表有数据{printf("%d ",p->data); //输出数据p = p->next; //指向下一个节点}printf("\n");
}//获取尾节点的地址
Node* get_tail(Node *L)
{Node *p = L; //把L链表赋值给p指针while(p->next != NULL){p = p->next;}return p;
}//单链表尾插法
Node* insertTail(Node *tail,ElemType e)
{Node *p = (Node*)malloc(sizeof(Node)); //创建一块空间并赋值给指针p->data = e; //数据域tail->next = p;p->next = NULL; //使新创建的p节点成为新的尾节点 return p;
}//在指定位置插入数据
int insertNode(Node *L,int pos,ElemType e)
{//用来保存插入位置的前驱节点Node *p = L;int i = 0;//遍历这个链表找到插入位置的前驱节点while(i < pos - 1)  {p = p->next;i++;if(p == NULL){return 0;}}Node *q = (Node*)malloc(sizeof(Node)); //要插入的新节点q->data = e;q->next = p->next; //插入位置前一个节点的下一个位置赋值给新节点的下一个位置p->next = q; //把新节点赋值给前一个位置的nextreturn 1;
}//删除指定位置的节点
int deleteNode(Node *L,int pos)
{Node *p = L; //要删除节点的前驱int i = 0;//遍历链表，找到要删除节点的前驱while(i < pos - 1){p = p->next;i++;if(p == NULL){return 0;}}if(p->next == NULL){printf("要删除的位置错误\n");return 0;}Node *q = p->next; //q指向要删除的节点p->next = q->next; //让要删除节点的前驱指向要删除节点的后继free(q); //释放要删除节点的内存空间return 1;
}int main(int argc,char const *argv[])
{Node *list = initList(); //初始化链表Node *tail = get_tail(list);tail = insertTail(tail,10);tail = insertTail(tail,20);tail = insertTail(tail,30);listNode(list);insertNode(list,2,15);listNode(list); deleteNode(list,2);listNode(list);return 0;
}

运行：

原理：

①删除70这个节点

②找到要删除节点的前置节点p

③用指针q记录要删除的节点

④通过改变p的后继节点实现删除

（原本p指向的是70，现在使70直接指向80即可）

⑤释放删除节点的空间

free(q);

7.获取链表长度

#include<stdio.h>
#include <string.h>
#include<stdlib.h>
#define MAXSIZE 100typedef int ElemType;//链表存储结构
typedef struct node{ElemType data;struct node *next;
}Node;//单链表初始化
Node* initList()
{Node *head = (Node*)malloc(sizeof(Node));head->data = 0;head->next = NULL;return head;
}//单链表头插法
int insertHead(Node* L,ElemType e)
{Node *p = (Node*)malloc(sizeof(Node));p->data = e;p->next = L->next;L->next = p;return 1;
}//单链表遍历
void listNode(Node* L)
{Node *p = L->next; //第一个节点赋值给p指针while(p != NULL) //p不为空，即链表有数据{printf("%d ",p->data); //输出数据p = p->next; //指向下一个节点}printf("\n");
}//获取尾节点的地址
Node* get_tail(Node *L)
{Node *p = L; //把L链表赋值给p指针while(p->next != NULL){p = p->next;}return p;
}//单链表尾插法
Node* insertTail(Node *tail,ElemType e)
{Node *p = (Node*)malloc(sizeof(Node)); //创建一块空间并赋值给指针p->data = e; //数据域tail->next = p;p->next = NULL; //使新创建的p节点成为新的尾节点 return p;
}//在指定位置插入数据
int insertNode(Node *L,int pos,ElemType e)
{//用来保存插入位置的前驱节点Node *p = L;int i = 0;//遍历这个链表找到插入位置的前驱节点while(i < pos - 1)  {p = p->next;i++;if(p == NULL){return 0;}}Node *q = (Node*)malloc(sizeof(Node)); //要插入的新节点q->data = e;q->next = p->next; //插入位置前一个节点的下一个位置赋值给新节点的下一个位置p->next = q; //把新节点赋值给前一个位置的nextreturn 1;
}//删除指定位置的节点
int deleteNode(Node *L,int pos)
{Node *p = L; //要删除节点的前驱int i = 0;//遍历链表，找到要删除节点的前驱while(i < pos - 1){p = p->next;i++;if(p == NULL){return 0;}}if(p->next == NULL){printf("要删除的位置错误\n");return 0;}Node *q = p->next; //q指向要删除的节点p->next = q->next; //让要删除节点的前驱指向要删除节点的后继free(q); //释放要删除节点的内存空间return 1;
}//获取链表长度
int listLength(Node *L)
{Node *p = L;int len = 0;//从头节点循环到尾节点while(p != NULL){p = p->next;len++;}return len;
}int main(int argc,char const *argv[])
{Node *list = initList(); //初始化链表Node *tail = get_tail(list);tail = insertTail(tail,10);tail = insertTail(tail,20);tail = insertTail(tail,30);listNode(list);insertNode(list,2,15);listNode(list); deleteNode(list,2);listNode(list);printf("%d\n",listLength(list));return 0;
}

运行：

8.释放链表（除头节点之外的所有内容全都释放）

#include<stdio.h>
#include <string.h>
#include<stdlib.h>
#define MAXSIZE 100typedef int ElemType;//链表存储结构
typedef struct node{ElemType data;struct node *next;
}Node;//单链表初始化
Node* initList()
{Node *head = (Node*)malloc(sizeof(Node));head->data = 0;head->next = NULL;return head;
}//单链表头插法
int insertHead(Node* L,ElemType e)
{Node *p = (Node*)malloc(sizeof(Node));p->data = e;p->next = L->next;L->next = p;return 1;
}//单链表遍历
void listNode(Node* L)
{Node *p = L->next; //第一个节点赋值给p指针while(p != NULL) //p不为空，即链表有数据{printf("%d ",p->data); //输出数据p = p->next; //指向下一个节点}printf("\n");
}//获取尾节点的地址
Node* get_tail(Node *L)
{Node *p = L; //把L链表赋值给p指针while(p->next != NULL){p = p->next;}return p;
}//单链表尾插法
Node* insertTail(Node *tail,ElemType e)
{Node *p = (Node*)malloc(sizeof(Node)); //创建一块空间并赋值给指针p->data = e; //数据域tail->next = p;p->next = NULL; //使新创建的p节点成为新的尾节点 return p;
}//在指定位置插入数据
int insertNode(Node *L,int pos,ElemType e)
{//用来保存插入位置的前驱节点Node *p = L;int i = 0;//遍历这个链表找到插入位置的前驱节点while(i < pos - 1)  {p = p->next;i++;if(p == NULL){return 0;}}Node *q = (Node*)malloc(sizeof(Node)); //要插入的新节点q->data = e;q->next = p->next; //插入位置前一个节点的下一个位置赋值给新节点的下一个位置p->next = q; //把新节点赋值给前一个位置的nextreturn 1;
}//删除指定位置的节点
int deleteNode(Node *L,int pos)
{Node *p = L; //要删除节点的前驱int i = 0;//遍历链表，找到要删除节点的前驱while(i < pos - 1){p = p->next;i++;if(p == NULL){return 0;}}if(p->next == NULL){printf("要删除的位置错误\n");return 0;}Node *q = p->next; //q指向要删除的节点p->next = q->next; //让要删除节点的前驱指向要删除节点的后继free(q); //释放要删除节点的内存空间return 1;
}//获取链表长度
int listLength(Node *L)
{//头节点赋值给pNode *p = L;int len = 0;//从头节点循环到尾节点while(p != NULL){p = p->next;len++;}return len;
}//释放链表
void freeList(Node *L)
{Node *p = L->next; //头节点的next赋值给p指针Node *q; //声明一个新节点while(p != NULL){q = p->next;free(p);p = q;}L->next = NULL;
}int main(int argc,char const *argv[])
{Node *list = initList(); //初始化链表Node *tail = get_tail(list);tail = insertTail(tail,10);tail = insertTail(tail,20);tail = insertTail(tail,30);listNode(list);insertNode(list,2,15);listNode(list); deleteNode(list,2);listNode(list);printf("%d\n",listLength(list));freeList(list);printf("%d\n",listLength(list));return 0;
}

运行：

原理：

①指针p指向头节点后的第一个节点

②判断指针p是否指向空节点

③如果p不为空，用指针q记录指针p的后继节点

④释放指针p指向的节点

⑤指针p和指针q指向同一个节点，循环上面的操作


http://www.ppmy.cn/embedded/172843.html

相关文章

前端面试：如何减少项目里面 if-else？

前端面试：如何减少项目里面 if-else？

在前端开发中&#xff0c;大量使用 if-else 结构可能导致代码调试困难、可读性降低和冗长的逻辑。不妨考虑以下多种策略来减少项目中的 if-else 语句&#xff0c;提高代码的可维护性和可读性&#xff1a; 1. 使用对象字面量替代 用对象字面量来替代 if-else 语句&#xff0c;…
阅读更多...
RabbitMQ入门：从安装到高级消息模式

RabbitMQ入门：从安装到高级消息模式

文章目录 一. RabbitMQ概述1.1 同步/异步1.1.1 同步调用1.1.2 异步调用 1.2 消息中间件1.2.1 概念1.2.2 作用1.2.3 常见的消息中间件1.2.4 其他中间件 1.3 RabbitMQ1.3.1 简介1.3.2 特点1.3.3 方式1.3.4 架构1.3.5 运行流程 二. 安装2.1 Docker 安装 RabbitMQ 三. 简单队列&…
阅读更多...
Vue 中如何使用 slot 和 scoped slot？

Vue 中如何使用 slot 和 scoped slot？

在 Vue.js 中&#xff0c;slot 和 scoped slot 是实现组件内容分发和灵活布局的重要特性。它们允许开发者在子组件中插入父组件的内容&#xff0c;从而提高组件的复用性和灵活性。本文将详细探讨 slot 和 scoped slot 的使用方法、应用场景及其最佳实践。 1. Slot 的基本概念 …
阅读更多...
ubuntu20.04装nv驱动的一些坑

ubuntu20.04装nv驱动的一些坑

**1.一定要去bios里面关闭secure boot&#xff0c;否则驱动程序需要签名&#xff0c;安装了的驱动无法被识别加载 2.假如没有关闭secure boot然后装了驱动&#xff0c;然后再去关闭secure boot&#xff0c;可能会导致进入不了ubuntu的情况 此时&#xff0c;先恢复secure boot&…
阅读更多...
Flask实现分页的三种方法

Flask实现分页的三种方法

在 Flask 中实现分页的方式有多种&#xff0c;最常用的是使用 Flask-SQLAlchemy 自带的分页功能&#xff0c;或者手动实现分页逻辑。下面介绍几种方法&#xff1a; 方法 1&#xff1a;使用 Flask-SQLAlchemy 的 paginate() Flask-SQLAlchemy 提供了 paginate() 方法&#xff0…
阅读更多...
2025-3-12 leetcode刷题情况（贪心算法--区间问题）

2025-3-12 leetcode刷题情况（贪心算法--区间问题）

一、452.用最少数量的箭引爆气球 1.题目描述 2.代码 3.思路 使用 Arrays.sort 方法对 points 数组按照气球的起始坐标进行排序。这里使用 Integer.compare(a[0], b[0]) 作为比较器&#xff0c;确保气球按起始坐标从小到大排列。将箭的数量 count 初始化为 1&#xff0c;因为至…
阅读更多...
MCU的工作原理：嵌入式系统的控制核心

MCU的工作原理：嵌入式系统的控制核心

MCU的工作原理可以概括为以下几个步骤&#xff1a; 1. 初始化 上电后&#xff0c;MCU从Flash存储器中加载程序代码&#xff0c;并初始化外设和寄存器。 2. 任务执行 根据程序逻辑&#xff0c;MCU执行数据处理、外设控制和通信等任务。通过中断系统实时响应外部事件。 3. 低…
阅读更多...
postgresql源码安装

postgresql源码安装

步骤 1: 安装依赖 在开始之前&#xff0c;请确保您的系统上安装了编译 PostgreSQL 所需的依赖包。使用以下命令安装必要的软件包&#xff1a; 对于 Debian/Ubuntu 系统&#xff1a; sudo apt update sudo apt install build-essential libreadline-dev zlib1g-dev flex biso…
阅读更多...
最新文章

Copyright @ 2022~2023