嵌入式学习第二十七天--线性表的链式存储

线性表的链式存储
解决顺序存储的缺点，插入和删除，动态存储问题。
特点：
，线性表链式存储结构的特点是一组任意的存储单位存储线性表的数据元素，存储单元可以是连续的，也可以不连续。可以被存储在任意内存未被占用的位置上。

所以前面的顺序表只需要存储数据元素信息就可以了。在链式结构中还需要一个元素存储下一个元素的地址。

为了表示每个数据元素，ai与其直接后继数据元素ai+1之间的逻辑关系，对ai来说，除了存储其本身的信息外，还需要存一个指示器直接后续的信息。把存储元素信息的域叫数据域，把存储直接后继位置的域叫指针域。这两部分信息组成数据元素ai的存储映像，叫结点(Node);



单链表中，c语言的描述
typedef struct person {
char name[32];
char sex;
int age;
int score;
}DATATYPE;

typedef struct node {
DATATYPE data;
struct node *next,*prev;
}LinkNode;

typedef struct list {
LinkNode *head;
int tlen;
int clen;
}LinkList;

LinkList *CreateLinkList(int len);
int InsertHeadLinkList(LinkList *list, DATATYPE data);
int ShowLinkList(LinkList *list);
LinkNode *FindLinkList(LinkList *list, char *name);
int DeleteLinkList(LinkList *list, char *name);
int ReviseLinkList(LinkList *list, char *name, DATATYPE data);
int DestroyLinkList(LinkList *list);
int InsertTailLinkList(LinkList *list, DATATYPE data);



顺序表和链表 优缺点
存储方式：
顺序表是一段连续的存储单元
链表是逻辑结构连续物理结构（在内存中的表现形式）不连续
时间性能，
查找 顺序表O(1)
 链表  O(n)
插入和删除
顺序表 O(n)
链表   O(1)

空间性能
顺序表 需要预先分配空间，大小固定
链表， 不需要预先分配，大小可变，动态分配


循环链表
简单的来说，就是将原来单链表中最有一个元素的next指针指向第一个元素或头结点，链表就成了一个环，头尾相连，就成了循环链表。circultlar linker list.

注意非空表，和空表。多数会加入头结点。
原来结束的条件是
p->next != NULL ------->>>>> p-next != Head 

linklist.h

#ifndef __LINK_LIST_H__
#define __LINK_LIST_H__
typedef struct person {char name[32];char sex;int age;int score;
}DATATYPE;typedef struct node {DATATYPE data;struct node *next;
}LinkNode;typedef struct list {LinkNode *head;int clen;
}LinkList;LinkList*CreateLinkList();
int InsertHeadLinkList(LinkList*ll,DATATYPE*data);
int ShowLinkList(LinkList*ll);
int IsEmptyLinkList(LinkList*ll);
int GetSizeLinkList(LinkList*ll);
int InserTailLinkList(LinkList*ll,DATATYPE*data);
LinkNode* FindLinkList(LinkList*ll,char* name);
int InsertLinkListPos(LinkList*ll,DATATYPE*data,int pos);
int DelLinkList(LinkList*ll,char * name);
int ModifyLinkList(LinkList*ll,char* name,DATATYPE*newdata);
int DestroyLinkList(LinkList*ll);
int ReversLinkList (LinkList *ll);
DATATYPE* FindMidLinkList(LinkList *ll);
DATATYPE* FindLastKLinkList(LinkList *ll,int k);
int InsertSortLinkList(LinkList *ll);
#endif

linklist.c


#include "./linklist.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>LinkList *CreateLinkList ()
{LinkList *ll = malloc (sizeof (LinkList));if (NULL == ll) {perror ("CreateLinkList malloc error\n");return NULL;}ll->head = NULL;ll->clen = 0;return ll;
}
/*** @brief** @param ll* @param data* @return int*/
int InsertHeadLinkList (LinkList *ll, DATATYPE *data)
{if (NULL == ll || NULL == data) {fprintf (stderr, "InsertHeadLinkList parmter error\n");return 1;}LinkNode *newnode = malloc (sizeof (LinkNode));if (NULL == newnode) {perror ("InsertHeadLinkList malloc error\n");return 1;}memcpy (&newnode->data, data, sizeof (DATATYPE));newnode->next = NULL;if (IsEmptyLinkList (ll)) {ll->head = newnode;} else {newnode->next = ll->head;ll->head = newnode;}ll->clen++;return 0;
}int IsEmptyLinkList (LinkList *ll)
{if (NULL == ll) {fprintf (stderr, "IsEmptyLinkList parmter error\n");return 1;}return 0 == ll->clen;
}
int ShowLinkList (LinkList *ll)
{if (NULL == ll) {fprintf (stderr, "ShowLinkList parmter error\n");return 1;}LinkNode *tmp = ll->head;while (tmp) {printf ("name:%s age:%d\n", tmp->data.name, tmp->data.age);tmp = tmp->next; // i++}return 0;
}
/*** @brief 获得单向链表的节点个数** @param ll  链表的头信息指针* @return int 0表示成功 1表示失败 1*/
int GetSizeLinkList (LinkList *ll)
{if (NULL == ll) {fprintf (stderr, "GetSizeLinkList parmter error\n");return 1;}return ll->clen;
}int InserTailLinkList (LinkList *ll, DATATYPE *data)
{LinkNode *newnode = malloc (sizeof (LinkNode));if (NULL == newnode) {perror ("InserTailLinkList malloc error\n");return 1;}// newnode initmemcpy (&newnode->data, data, sizeof (DATATYPE));newnode->next = NULL;if (IsEmptyLinkList (ll)) {ll->head = newnode;} else // not empty{LinkNode *tmp = ll->head;while (tmp->next) {tmp = tmp->next; // i++}tmp->next = newnode;}ll->clen++;return 0;
}LinkNode *FindLinkList (LinkList *ll, char *name)
{if (NULL == ll || NULL == name || IsEmptyLinkList (ll)) {return NULL;}LinkNode *tmp = ll->head;int len = GetSizeLinkList (ll);for (int i = 0; i < len; i++) {if (0 == strcmp (tmp->data.name, name)) {return tmp;}tmp = tmp->next;}return NULL;
}int InsertLinkListPos (LinkList *ll, DATATYPE *data, int pos)
{if (NULL == ll || NULL == data) {return 1;}int len = GetSizeLinkList (ll);if (pos < 0 || pos > len) {fprintf (stderr, " InsertLinkListPos paramter error\n");return 1;}if (0 == pos) {return InsertHeadLinkList (ll, data);} else //中间插入或尾插{LinkNode *newnode = malloc (sizeof (LinkNode));if (NULL == newnode) {perror ("InsertLinkListPos malloc error\n");return 1;}memcpy (&newnode->data, data, sizeof (DATATYPE));newnode->next = NULL;LinkNode *tmp = ll->head;for (int i = 0; i < pos - 1; i++) {tmp = tmp->next;}newnode->next = tmp->next;tmp->next = newnode;}ll->clen++;return 0;
}int DelLinkList (LinkList *ll, char *name)
{LinkNode *tmp = ll->head;if (0 == strcmp (tmp->data.name, name)) // head del{ll->head = ll->head->next;free (tmp);} else {while (strcmp (tmp->next->data.name, name)) {tmp = tmp->next;if (NULL == tmp->next) {return 1;}}LinkNode *free_node = tmp->next;tmp->next = tmp->next->next;free (free_node);}ll->clen--;return 0;
}int ModifyLinkList (LinkList *ll, char *name, DATATYPE *newdata)
{LinkNode *ret = FindLinkList (ll, name);if (NULL == ret) {fprintf (stderr, "ModifyLinkList error\n");return 1;}memcpy (&ret->data, newdata, sizeof (DATATYPE));return 0;
}int DestroyLinkList (LinkList *ll)
{LinkNode *tmp = ll->head;while (1) {ll->head = ll->head->next;free (tmp);tmp = ll->head;if (NULL == tmp) {break;}}free (ll);return 0;
}int ReversLinkList (LinkList *ll)
{if (NULL == ll) {return 1;}int len = GetSizeLinkList (ll);if (len < 2) {return 1;}LinkNode *prev = NULL;LinkNode *tmp = ll->head;LinkNode *next = tmp->next;while (1) {tmp->next = prev; //逆序prev = tmp;tmp = next;if (NULL == tmp) {break;}next = next->next;}ll->head = prev;return 0;
}DATATYPE *FindMidLinkList (LinkList *ll)
{LinkNode *fast = ll->head;LinkNode *slow = ll->head;while (fast) {fast = fast->next;if (NULL == fast) {break;}slow = slow->next;fast = fast->next;}return &slow->data;
}DATATYPE *FindLastKLinkList (LinkList *ll, int k)
{if (NULL == ll) {return NULL;}int len = GetSizeLinkList (ll);if (k < 1 || k > len) {return NULL;}LinkNode *slow = ll->head;LinkNode *fast = ll->head;for (int i = 0; i < k; i++) {fast = fast->next;}while (fast) {fast = fast->next;slow = slow->next;}return &slow->data;
}int InsertSortLinkList (LinkList *ll)
{LinkNode *phead = ll->head;LinkNode *pinsert = phead->next;LinkNode *pnext = pinsert->next;phead->next = NULL;while (1){phead = ll->head;while (phead->next != NULL && pinsert->data.age > phead->data.age&& pinsert->data.age > phead->next->data.age) {phead = phead->next;}if (pinsert->data.age < phead->data.age){pinsert->next = phead;ll->head = pinsert;}else{pinsert->next = phead->next;phead->next = pinsert;}pinsert = pnext;if (NULL == pinsert) { break; }pnext = pnext->next;}return 0;
}

main.c

#include "./linklist.h"
#include <stdio.h>int main (int argc, char **argv)
{LinkList *ll = CreateLinkList ();DATATYPE data[] = {{ "zhangsan", 'm', 20, 80 }, { "lisi", 'f', 22, 86 },{ "wangmazi", 'f', 22, 67 }, { "guanerge", 'm', 40, 88 },{ "liubei", 'm', 42, 90 },};InsertHeadLinkList(ll, &data[3]);InsertHeadLinkList(ll, &data[1]);InsertHeadLinkList(ll, &data[0]);InserTailLinkList(ll,&data[4]);InserTailLinkList(ll,&data[2]);// InserTailLinkList (ll, &data[0]);// InserTailLinkList (ll, &data[1]);// InserTailLinkList (ll, &data[2]);// ShowLinkList (ll);// char want_name[50] = "li1si";// LinkNode *ret = FindLinkList (ll, want_name);// if (NULL == ret) {//   printf ("can't find per %s\n", want_name);// } else {//   printf ("find per,name:%s score:%d\n", ret->data.name, ret->data.score);// }// printf ("---------pos---------\n");// InsertLinkListPos (ll, &data[3], 2);// ShowLinkList (ll);// printf ("---------del---------\n");// DelLinkList (ll, "guanerge");// ShowLinkList (ll);// printf ("---------modify---------\n");// ModifyLinkList (ll, "lis1i", &data[4]);// ShowLinkList (ll);// printf ("---------rev---------\n");// ReversLinkList(ll);// ShowLinkList (ll);// printf ("---------last 1---------\n");// DATATYPE* tmp = FindLastKLinkList(ll,3);// if(NULL == tmp)// {//   fprintf(stderr,"can't find\n");// }// printf("name:%s\n",tmp->name);printf ("---------sort---------\n");InsertSortLinkList(ll);ShowLinkList (ll);DestroyLinkList(ll);// system("pause");return 0;
}


双向链表
double link list。

typedef struct DulNode
{

ElemType date;
struct DulNode *pri;
sturct DulNode *next；
}DulNode,*DuLinkList;
 

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/38237.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

ubuntu 解挂载时提示 “umount: /home/xx/Applications/yy: target is busy.”

ubuntu 解挂载时提示 “umount: /home/xx/Applications/yy: target is busy.”

问题如题所示&#xff0c;我挂载一个squanfs文件系统到指定目录&#xff0c;当我使用完后&#xff0c;准备解挂载时&#xff0c;提示umount: /home/xx/Applications/yy: target is busy.&#xff0c;具体的如图所示&#xff0c; 这种提示通常是表明这个路径的内容正在被某些进…
阅读更多...
跟着StatQuest学知识06-CNN进行图像分类

跟着StatQuest学知识06-CNN进行图像分类

目录 一、CNN特点 二、CNN应用于图像分类 &#xff08;一&#xff09;使用过滤器 &#xff08;二&#xff09;通过ReLU激活函数 &#xff08;三&#xff09;应用新的滤波器&#xff08;池化&#xff09; &#xff08;四&#xff09;输入 &#xff08;五&#xff09;输出…
阅读更多...
MATLAB 控制系统设计与仿真 - 27

MATLAB 控制系统设计与仿真 - 27

状态空间的标准型 传递函数和状态空间可以相互转换&#xff0c;接下来会举例如何有传递函数转成状态空间标准型。 对角标准型 当 G(s)可以写成&#xff1a; 即&#xff1a; 根据上图可知&#xff1a; 约当标准型 当 G(s)可以写成&#xff1a; 即&#xff1a; 根据上图…
阅读更多...
Python网络编程入门

Python网络编程入门

一.Socket 简称套接字&#xff0c;是进程之间通信的一个工具&#xff0c;好比现实生活中的插座&#xff0c;所有的家用电器要想工作都是基于插座进行&#xff0c;进程之间要想进行网络通信需要Socket&#xff0c;Socket好比数据的搬运工~ 2个进程之间通过Socket进行相互通讯&a…
阅读更多...
C++ --- 多态

C++ --- 多态

1 多态的概念 多态(polymorphism)的概念&#xff1a;通俗来说&#xff0c;就是多种形态。多态分为编译时多态(静态多态)和运⾏时多 态(动态多态)&#xff0c;这⾥我们重点讲运⾏时多态&#xff0c;编译时多态(静态多态)和运⾏时多态(动态多态)。编译时 多态(静态多态)主要就是我…
阅读更多...
MQTT的安装和使用

MQTT的安装和使用

MQTT的安装和使用 在物联网开发中&#xff0c;mqtt几乎已经成为了广大程序猿必须掌握的技术&#xff0c;这里小编和大家一起学习并记录一下~~ 一、安装 方式1、docker安装 官网地址 https://www.emqx.com/zh/downloads-and-install/broker获取 Docker 镜像 docker pull e…
阅读更多...
ROS多机通信功能包——Multibotnet

ROS多机通信功能包——Multibotnet

引言 这是之前看到一位大佬做的集群通信中间件&#xff0c;突发奇想&#xff0c;自己也来做一个&#xff0c;实现更多的功能、更清楚的架构和性能更加高效的ROS多机通信的功能包 链接&#xff1a;https://blog.csdn.net/benchuspx/article/details/128576723 Multibotnet Mu…
阅读更多...
pfsense部署四（静态路由的配置）

pfsense部署四（静态路由的配置）

目录 一 . 介绍 二 . 配置过程 一 . 介绍 pfsense开源防火墙经常在进行组网时&#xff0c;通常会用于连接不同的网络&#xff0c;在这个时候进需要给pfsense配置路由&#xff0c;而这篇文章介绍的是静态路由的配置 二 . 配置过程 拓扑图&#xff1a; 本次实验使用ensp模拟器…
阅读更多...
干货！三步搞定 DeepSeek 接入 Siri

干货！三步搞定 DeepSeek 接入 Siri

Siri高频用户福音&#xff0c;接下来仅需3步教你如何将 DeepSeek 接入 Siri&#xff01;虽然苹果公司并没有给国行产品提供 ai 功能&#xff0c;但是我们可以让自己的 iPhone 更智能一点。虽然有消息称苹果和阿里巴巴将合作为中国iPhone用户开发AI功能&#xff0c;但我们可以先…
阅读更多...
自动学习和优化过程，实现更加精准的预测和决策的智慧交通开源了

自动学习和优化过程，实现更加精准的预测和决策的智慧交通开源了

智慧交通视觉监控平台是一款功能强大且简单易用的实时算法视频监控系统。它的愿景是最底层打通各大芯片厂商相互间的壁垒&#xff0c;省去繁琐重复的适配流程&#xff0c;实现芯片、算法、应用的全流程组合&#xff0c;从而大大减少企业级应用约95%的开发成本。通过高效的实时视…
阅读更多...
DeepSeek R1 本地部署指南 (3) - 更换本地部署模型 Windows/macOS 通用

DeepSeek R1 本地部署指南 (3) - 更换本地部署模型 Windows/macOS 通用

0.准备 完成 Windows 或 macOS 安装&#xff1a; DeepSeek R1 本地部署指南 (1) - Windows 本地部署-CSDN博客 DeepSeek R1 本地部署指南 (2) - macOS 本地部署-CSDN博客 以下内容 Windows 和 macOS 命令执行相同&#xff1a; Windows 管理员启动&#xff1a;命令提示符 CMD ma…
阅读更多...
使用 Node.js 读取 Excel 文件并处理合并单元格

使用 Node.js 读取 Excel 文件并处理合并单元格

使用 Node.js 读取 Excel 文件并处理合并单元格 在现代的数据处理任务中&#xff0c;Excel 文件是一种非常常见的数据存储格式。无论是数据分析、报表生成&#xff0c;还是数据迁移&#xff0c;Excel 文件都扮演着重要的角色。然而&#xff0c;处理 Excel 文件时&#xff0c;尤…
阅读更多...
汇川EASY系列之以太网通讯（MODBUS_TCP做从站）

汇川EASY系列之以太网通讯（MODBUS_TCP做从站）

汇川easy系列PLC做MODBUS_TCP从站，不需要任何操作，但是有一些需要知道的东西。具体如下： 1、汇川easy系列PLC做MODBUS_TCP从站，，ModbusTCP服务器默认开启，无需设置通信协议（即不需要配置），端口号为“502”。ModbusTCP从站最多支持31个ModbusTCP客户端（ModbusTCP主站…
阅读更多...
1996-2023年各省公路里程数据（无缺失）

1996-2023年各省公路里程数据（无缺失）

1996-2023年各省公路里程数据&#xff08;无缺失&#xff09; 1、时间&#xff1a;1996-2023年 2、来源&#xff1a;国家统计局、统计年鉴 3、指标&#xff1a;公路里程&#xff08;万公里&#xff09; 4、范围&#xff1a;31省 5、指标解释&#xff1a;公路里程指报告期末…
阅读更多...
虚拟机访问主机的plc仿真

虚拟机访问主机的plc仿真

主机 虚拟机 默认&#xff0c;连接物理地址
阅读更多...
从“不敢买大”到“按墙选屏”，海信电视如何凭百吋重构客厅？

从“不敢买大”到“按墙选屏”，海信电视如何凭百吋重构客厅？

电视买小了&#xff0c;成为茜茜新房入住后最大的遗憾。 新房装修的时候&#xff0c;茜茜担心电视买大了眼睛看着累&#xff0c;因此把尺寸选在了65吋。结果入住后&#xff0c;孩子看动画片嚷着“画面太小”&#xff0c;老公看球赛吐槽“看不清球员号码”&#xff0c;全家追剧…
阅读更多...
Swift 经典链表面试题：如何在不访问头节点的情况下删除指定节点？

Swift 经典链表面试题：如何在不访问头节点的情况下删除指定节点？

摘要 在日常开发中&#xff0c;链表虽然不像数组、字典那么常用&#xff0c;但在某些场景下还是挺重要的。尤其是面试的时候&#xff0c;链表题目可是经典考点之一。今天我们要聊的就是一个看似简单&#xff0c;但很多人第一次做都会卡住的问题——删除单链表中的指定节点。 …
阅读更多...
楼宇自控系统的结构密码：总线与分布式结构方式的差异与应用

楼宇自控系统的结构密码：总线与分布式结构方式的差异与应用

在现代建筑中&#xff0c;为了实现高效、智能的管理&#xff0c;楼宇自控系统变得越来越重要。它就像建筑的 智能管家&#xff0c;可自动控制照明、空调、通风等各种机电设备&#xff0c;让建筑运行更顺畅&#xff0c;还能节省能源成本。而在楼宇自控系统里&#xff0c;有两种关…
阅读更多...
git | 回退版本 并保存当前修改到stash，在进行整合。[git checkout | git stash 等方法 ]

git | 回退版本 并保存当前修改到stash，在进行整合。[git checkout | git stash 等方法 ]

目录 一些常见命令&#xff1a; git 回退版本 一、临时回退&#xff08;不会修改历史&#xff0c;可随时回到当前版本&#xff09; 方法1&#xff1a;git checkout HEAD~1 问题&#xff1a;处于 detached HEAD 状态下提交的&#xff0c;无法直接 git push ✅ 选项 1&…
阅读更多...
Linux系统之美：环境变量的概念以及基本操作

Linux系统之美：环境变量的概念以及基本操作

本节重点 理解环境变量的基本概念学会在指令和代码操作上查询更改环境变量环境变量表的基本概念父子进程间环境变量的继承与隔离 一、引入 1.1 自定义命令&#xff08;我们的exe&#xff09; 我们以往的Linux编程经验告诉我们&#xff0c;我们在对一段代码编译形成可执行文件后…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023