嵌入式学习——数据结构（双向无头有环链表、内核链表、栈）——day48

2024-06-23 07:04
文章标签 环链 链表 day48 嵌入式 数据结构 内核 无头 双向 学习

本文主要是介绍嵌入式学习——数据结构（双向无头有环链表、内核链表、栈）——day48，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 约瑟夫环问题——双向无头回环链表

1.1 问题描述

        给定 ( n ) 个人（编号为 ( 1, 2, \ldots, n )），他们围成一个圈。从第一个人开始报数，每报到第 ( k ) 个人时，杀掉这个人，然后从下一个人重新开始报数。重复这个过程，直到所有人都被杀死。约瑟夫环问题是要确定最后一个幸存者的编号。

1.2 实质

        每次删除循环链表中的一个节点，直到链表中仅剩一个节点结束

2. 双向无头循环链表代码

2.1 makefile

OBJ:=a.out
OBJS+=main.c doublelink.c
CCl=gcc$(OBJ):$(OBJS)$(CC) $^ -o $@
.PHONY:
clean:rm $(OBJ)
test:valgrind --tool=memcheck --leak-check=full ./$(OBJ)

2.2 double.h

#ifndef _DOUBLELINK_H_
#define _DOUBLELINK_H_typedef struct stu
{int id;char name[32];int score;
}DataType;typedef struct node
{DataType data;struct node *ppre;struct node *pnext;
}DouNode;typedef struct list
{DouNode *phead;int clen;
}DouList;extern DouList *create_dou_link();
extern int is_empty_dou_link(DouList *plist);
extern void dou_link_for_each(DouList *plist, int dir);
extern int push_head_dou_link(DouList *plist, DataType data);
extern int  push_tail_dou_link(DouList *plist, DataType data);
extern int pop_head_dou_link(DouList *plist);
extern int pop_tail_dou_link(DouList *plist);
extern void loop_dou_link(DouList *plist);
extern DouNode *Joseph_loop(DouList *plist);
extern void dou_link_for_remain(DouList *plist);#endif

2.3 double.c

#include "doublelink.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>DouList *create_dou_link()//创建标签
{DouList *plist = NULL;plist = (DouList *)malloc(sizeof(DouList));if (NULL == plist){perror("fail to malloc");return NULL;}plist->phead = NULL;plist->clen = 0;return plist;
}int is_empty_dou_link(DouList *plist)//判断空链表
{if (NULL == plist->phead){return 1;}return 0;
}int push_head_dou_link(DouList *plist, DataType data)//头插
{DouNode *pnode = NULL;pnode = malloc(sizeof(DouNode));if (NULL == pnode){perror("fail to malloc");return -1;}pnode->data = data;pnode->ppre = NULL;pnode->pnext = NULL;if (is_empty_dou_link(plist))//空链表直接插{plist->phead = pnode;}else{pnode->pnext = plist->phead;plist->phead->ppre = pnode;plist->phead = pnode;}plist->clen++;return 0;
}int push_tail_dou_link(DouList *plist, DataType data)//头插
{DouNode *p = NULL;DouNode *pnode = NULL;pnode = malloc(sizeof(DouNode));if (NULL == pnode){perror("fail to malloc");return -1;}pnode->data = data;pnode->ppre = NULL;pnode->pnext = NULL;if (is_empty_dou_link(plist))//空链表直接插{plist->phead = pnode;}else{   p = plist->phead;while (p->pnext != NULL){p = p->pnext;}p->pnext = pnode;pnode->ppre = p;}plist->clen++;return 0;
}int pop_head_dou_link(DouList *plist)//头删
{if (is_empty_dou_link(plist))//空链表直接结束程序{return -1;}DouNode *pfree = NULL;pfree = plist->phead;plist->phead = pfree->pnext;//标签指向第二个节点首地址if (plist->phead != NULL)//判断是否空链表{plist->phead->ppre = NULL;//将第二个节点的ppre变为NULL}free(pfree);plist->clen--;return 0;
}int pop_tail_dou_link(DouList *plist)//尾删
{if (is_empty_dou_link(plist))//空链表程序结束{return -1;}DouNode *pfree = NULL;pfree = plist->phead;while (pfree->pnext)//指针指向最后一个节点{pfree = pfree->pnext;}if (pfree->ppre != NULL)//链表有两个以上节点{pfree->ppre->pnext = NULL;}else //链表只有一个节点{plist->phead = NULL;}free(pfree);plist->clen--;return 0;
}void loop_dou_link(DouList *plist)//将非回环链表改为双向回环链表
{DouNode *ptmpnode = NULL;ptmpnode = plist->phead;while (ptmpnode->pnext != NULL)//将指针移动到末尾节点{ptmpnode = ptmpnode->pnext;}ptmpnode->pnext = plist->phead;plist->phead->ppre = ptmpnode;
}void dou_link_for_remain(DouList *plist)//打印约瑟夫回环一次处理后链表中剩下的成员信息
{int i = 0;DouNode *ptmpnode = plist->phead;for (i = 0; i < plist->clen; i++){printf("%d  ", ptmpnode->data.id);printf("%s  ", ptmpnode->data.name);printf("%d\n", ptmpnode->data.score);ptmpnode = ptmpnode->pnext;}printf("=========================\n");
}DouNode *Joseph_loop(DouList *plist)//约瑟夫回环、实质是删除链表节点直到留下最后一个节点为止
{DouNode *pfreenode = NULL;//DouNode *ptmpnode = NULL;//指向回环ptmpnode = plist->phead;while (ptmpnode != ptmpnode->pnext)//判断回环是否只剩下一个节点{pfreenode = ptmpnode;//指向当前所在回环的位置pfreenode = pfreenode->pnext->pnext;//回环向后移动两个单位pfreenode->ppre->pnext = pfreenode->pnext;pfreenode->pnext->ppre = pfreenode->ppre; ptmpnode = pfreenode->pnext;//记录要删除的回环的下一个位置，保证循环的延续if (pfreenode == plist->phead)//判断要删除的节点是否是表头后的第一个节点、若是，给表头接入要删除节点的下一个节点{plist->phead = ptmpnode;}free(pfreenode);plist->clen--;dou_link_for_remain(plist);//打印链表中剩下的节点信息}return ptmpnode;
}

2.4 main.c

#include <stdio.h>
#include <stdlib.h>
#include "doublelink.h"int main(void)
{DataType stus[] = {{1, "doinb", 100},{2, "lwx", 67},{3, "lqs", 99},{4, "tian", 98},{5, "gimgoon", 78},{6, "xinyi", 88},{7, "nuguri", 99},{8, "khan", 77},{9, "bo", 94},{10, "xiaolaohu", 60}};DouNode *ptmpnode = NULL;int i = 0;DouList *plist = create_dou_link();//表头创建if (NULL == plist){return -1;}for (i = 0; i < sizeof(stus) / sizeof(stus[0]); i++)//给链表中插入结构体中的所有内容{push_tail_dou_link(plist, stus[i]);//尾插}dou_link_for_each(plist, 1);dou_link_for_each(plist, 0);loop_dou_link(plist);//创建双向回环链表ptmpnode = Joseph_loop(plist);//约瑟夫回环printf("%s\n", ptmpnode->data.name); return 0;
}

2.5  判断单向链表是否有环

        利用快慢指针，慢指针走一步，快指针走两步

        快指针每走一步，判断是否为空或者是否与慢指针相遇，相遇为有环链表

3. 内核链表（有头、双向循环链表）

3.1 定义

        Linux内核链表是一种双向循环链表，它的实现非常简洁而高效，主要通过一些宏和内联函数来操作链表。链表节点的结构定义在头文件 <linux/list.h> 中。

3.1 offsetof宏

        获取结构体某个成员到结构体开头的偏移量

3.2 container_of宏

        通过offsetof偏移量获取结构体的首地址

3. 栈

3.1 定义

        栈（Stack）是一种抽象的数据结构，它遵循后进先出（LIFO, Last In First Out）的原则。也就是说，最后放入栈中的元素最先被取出。

3.2 栈的基本操作

        1. 入栈、压栈：将一个元素放入栈顶。

        2. 出栈、弹栈：从栈顶移除一个元素。

        3. 取栈顶元素：查看栈顶元素但不移除它。

        4. 判断栈是否为空：检查栈中是否有元素。

3.3 分类

        （1）按实现方式分类：栈分为顺序栈和链式栈

        1. 顺序栈

               使用数组实现的栈，数组中的元素按顺序存储。优点是实现简单，访问效率高；缺点是栈的容量固定，扩展不便。 

        2. 链式栈

        使用链表实现的栈，链表的每个节点存储一个栈元素。优点是栈的容量可以动态扩展；缺点是指针操作复杂，访问效率相对较低。

        （2）按用途来分类

        1. 操作系统栈

        用于管理程序执行时的函数调用，保存函数调用的返回地址、本地变量等信息。操作系统栈通常是顺序栈，采用固定大小。

                1. 局部变量

                2. 函数的形参、返回值

                3. 函数调用关系——保护现场、恢复现场

3.4 数据结构中的栈——链式栈

4. 面试考点

        区分满增栈、满减栈、空增栈、空减栈（前提：仅限于顺序栈，数组方式构成的）

4.1 满栈和空栈——判断栈顶所在位置是否存有数据而非整个栈有没有数据

        1. 满栈：栈顶所在位置有数据

                入栈操作流程：先向上移动栈顶指针，再将数据压入栈中

        2. 空栈：栈顶所在位置没有数据

                入栈操作流程：先将数据压入栈顶，再向上移动栈顶指针


 

4.2 增栈和减栈——判断栈的生长方向

        0x1000与0x2000，内存高地址为0x2000，内存低地址为0x1000

        1. 增栈：数据入栈时栈顶指针向内存高地址移动

        2. 减栈：数据入栈时栈顶指针向内存低地址移动

（1） 满增栈

        1. 出栈时：栈顶指针向内存高地址移动，再向栈顶入栈数据，

        2. 出栈时：出栈数据，栈顶指针向内存低地址移动，

（2） 满减栈

（3） 空增栈

        1. 出栈时：先向栈顶入栈数据，栈顶指针向内存高地址移动

        2. 出栈时：栈顶指针向内存低地址移动，出栈数据

（4） 空减栈

5. 数据结构中的栈——链式栈

5.1 代码

（1）makefile

OBJ:=a.out
OBJS+=main.c stack.c
CCl=gcc$(OBJ):$(OBJS)$(CC) $^ -o $@
.PHONY:
clean:rm $(OBJ)
test:valgrind --tool=memcheck --leak-check=full ./$(OBJ)

注意：在终端输入make test可以测试销毁是否成功以及是否有内存泄漏

（2）stack.h

#ifndef _STACK_H_
#define _STACK_H_typedef int DataType;typedef struct stact_node
{DataType data;struct stact_node *pnext;
}StackNode;typedef struct Stack
{StackNode *ptop;int clen;
}StackList;extern StackList *create_stack();
extern int is_empty_stack(StackList *plist);
extern int push_stack(StackList *plist, DataType data);//入栈头插
extern void stack_for_each(StackList *plist);
extern int pop_stack(StackList *plist, DataType *pdata);//出栈头删
extern void clear_stack(StackList *plist);
extern void destory_stack(StackList *plist);
extern int get_stack_top(StackList *plist, DataType *pdata);#endif

（3）stack.c

#include <stdio.h>
#include <stdlib.h>
#include "stack.h"StackList *create_stack()
{StackList *plist = malloc(sizeof(StackList));if (NULL == plist){perror("fail to malloc");return NULL;}plist->ptop = NULL;plist->clen = 0;return plist;
}int is_empty_stack(StackList *plist)
{if (NULL == plist->ptop){return 1;}return 0;
}int push_stack(StackList *plist, DataType data)//入栈头插
{StackNode *pnode = malloc(sizeof(StackNode));if (NULL == pnode){perror("fail to malloc");return -1;}pnode->data = data;pnode->pnext = NULL;pnode->pnext = plist->ptop;plist->ptop = pnode;plist->clen++;return 0;
}void stack_for_each(StackList *plist)
{StackNode *ptmp = plist->ptop;while (ptmp != NULL){printf("%d ", ptmp->data);ptmp = ptmp->pnext;}printf("\n");
}int pop_stack(StackList *plist, DataType *pdata)//出栈头删
{if (is_empty_stack(plist)){return -1;}StackNode *pfree = plist->ptop;plist->ptop = pfree->pnext;if (pdata != NULL)//传入非空地址，将删除的节点的数据传出{*pdata = pfree->data;}free(pfree);plist->clen--;return 0;
}void clear_stack(StackList *plist)//清空栈区
{while (!is_empty_stack(plist)){pop_stack(plist, NULL);}
}void destory_stack(StackList *plist)
{if (!is_empty_stack(plist)){clear_stack(plist);}free(plist);
}int get_stack_top(StackList *plist, DataType *pdata)//获得栈顶数据
{if (is_empty_stack(plist)){return -1;}*pdata = plist->ptop->data;return 0;
}

（4）main.c

#include <stdio.h>
#include <stdlib.h>
#include "stack.h"int main(void)
{DataType tmpdata = 0;DataType data[] = {1, 2, 3, 4, 5};StackNode *ptmpnode = NULL;int i = 0;int ret = 0;StackList *plist = create_stack();//创建栈表头if (NULL == plist){return -1;}for (i = 0; i < sizeof(data) / sizeof(data[0]); i++)//入栈所有数据{push_stack(plist, data[i]);//入栈头插}stack_for_each(plist);//遍历打印所有数据#if 0for (i = 0; i < sizeof(data)/sizeof(data[0]); i++)//获取栈顶元素并打印，出栈数据，打印栈中的剩下元素{printf("======== %d ========", i);ret = get_stack_top(plist, &tmpdata);if (0 == ret){printf("ptop data:%d   ", tmpdata);}pop_stack(plist, NULL);stack_for_each(plist);//遍历打印所有数据}
#endif#if 0clear_stack(plist);//清理栈中所有节点if (is_empty_stack(plist)){printf("clear_stack success!\n");}
#endif#if 1destory_stack(plist);
#endifreturn 0;
}

5.2  应用

                1. 撤回操作

                2. 浏览器返回上一层操作

                3. 计算器

6.

中缀表达式

        前缀表达式

        后缀表达式

        

        

这篇关于嵌入式学习——数据结构（双向无头有环链表、内核链表、栈）——day48的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


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

相关文章

51单片机学习记录———定时器

51单片机学习记录———定时器

文章目录 前言一、定时器介绍二、STC89C52定时器资源三、定时器框图四、定时器模式五、定时器相关寄存器六、定时器练习 前言 一个学习嵌入式的小白~ 有问题评论区或私信指出~ 提示：以下是本篇文章正文内容，下面案例可供参考 一、定时器介绍 定时器介绍：51单片机的定时器属于单片机的内部资源，其电路的连接和运转均在单片机内部完成。 定时器作用： 1.用于计数系统，可
阅读更多...
问题：第一次世界大战的起止时间是 #其他#学习方法#微信

问题：第一次世界大战的起止时间是 #其他#学习方法#微信

问题：第一次世界大战的起止时间是 A.1913 ~1918 年 B.1913 ~1918 年 C.1914 ~1918 年 D.1914 ~1919 年 参考答案如图所示
阅读更多...
[word] word设置上标快捷键 #学习方法#其他#媒体

[word] word设置上标快捷键 #学习方法#其他#媒体

word设置上标快捷键 办公中，少不了使用word，这个是大家必备的软件，今天给大家分享word设置上标快捷键，希望在办公中能帮到您！ 1、添加上标 在录入一些公式，或者是化学产品时，需要添加上标内容，按下快捷键Ctrl+shift++就能将需要的内容设置为上标符号。 word设置上标快捷键的方法就是以上内容了，需要的小伙伴都可以试一试呢！
阅读更多...
AssetBundle学习笔记

AssetBundle学习笔记

AssetBundle是unity自定义的资源格式，通过调用引擎的资源打包接口对资源进行打包成.assetbundle格式的资源包。本文介绍了AssetBundle的生成，使用，加载，卸载以及Unity资源更新的一个基本步骤。 目录 1.定义： 2.AssetBundle的生成： 1）设置AssetBundle包的属性——通过编辑器界面 补充：分组策略 2）调用引擎接口API
阅读更多...
Javascript高级程序设计(第四版)--学习记录之变量、内存

Javascript高级程序设计(第四版)--学习记录之变量、内存

原始值与引用值 原始值：简单的数据即基础数据类型，按值访问。 引用值：由多个值构成的对象即复杂数据类型，按引用访问。 动态属性 对于引用值而言，可以随时添加、修改和删除其属性和方法。 let person = new Object();person.name = 'Jason';person.age = 42;console.log(person.name,person.age);//'J
阅读更多...
【Linux进阶】UNIX体系结构分解——操作系统，内核，shell

【Linux进阶】UNIX体系结构分解——操作系统，内核，shell

1.什么是操作系统？ 从严格意义上说，可将操作系统定义为一种软件，它控制计算机硬件资源，提供程序运行环境。我们通常将这种软件称为内核（kerel)，因为它相对较小，而且位于环境的核心。  从广义上说，操作系统包括了内核和一些其他软件，这些软件使得计算机能够发挥作用，并使计算机具有自己的特生。这里所说的其他软件包括系统实用程序（system utility）、应用程序、shell以及公用函数库等
阅读更多...
大学湖北中医药大学法医学试题及答案，分享几个实用搜题和学习工具 #微信#学习方法#职场发展

大学湖北中医药大学法医学试题及答案，分享几个实用搜题和学习工具 #微信#学习方法#职场发展

今天分享拥有拍照搜题、文字搜题、语音搜题、多重搜题等搜题模式，可以快速查找问题解析，加深对题目答案的理解。 1.快练题 这是一个网站 找题的网站海量题库,在线搜题,快速刷题~为您提供百万优质题库,直接搜索题库名称,支持多种刷题模式:顺序练习、语音听题、本地搜题、顺序阅读、模拟考试、组卷考试、赶快下载吧! 2.彩虹搜题 这是个老公众号了 支持手写输入，截图搜题，详细步骤，解题必备
阅读更多...
《offer来了》第二章学习笔记

《offer来了》第二章学习笔记

1.集合 Java四种集合：List、Queue、Set和Map 1.1.List：可重复 有序的Collection ArrayList： 基于数组实现，增删慢，查询快，线程不安全 Vector： 基于数组实现，增删慢，查询快，线程安全 LinkedList： 基于双向链实现，增删快，查询慢，线程不安全 1.2.Queue：队列 ArrayBlockingQueue：
阅读更多...
硬件基础知识——自学习梳理

硬件基础知识——自学习梳理

计算机存储分为闪存和永久性存储。 硬盘（永久存储）主要分为机械磁盘和固态硬盘。 机械磁盘主要靠磁颗粒的正负极方向来存储0或1，且机械磁盘没有使用寿命。 固态硬盘就有使用寿命了，大概支持30w次的读写操作。 闪存使用的是电容进行存储，断电数据就没了。 器件之间传输bit数据在总线上是一个一个传输的，因为通过电压传输（电流不稳定），但是电压属于电势能，所以可以叠加互相干扰，这也就是硬盘，U盘
阅读更多...
人工智能机器学习算法总结神经网络算法(前向及反向传播)

人工智能机器学习算法总结神经网络算法(前向及反向传播)

1.定义，意义和优缺点 定义: 神经网络算法是一种模仿人类大脑神经元之间连接方式的机器学习算法。通过多层神经元的组合和激活函数的非线性转换，神经网络能够学习数据的特征和模式，实现对复杂数据的建模和预测。(我们可以借助人类的神经元模型来更好的帮助我们理解该算法的本质，不过这里需要说明的是，虽然名字是神经网络，并且结构等等也是借鉴了神经网络，但其原型以及算法本质上还和生物层面的神经网络运行原理存在
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2