嵌入式学习——数据结构（双向无头有环链表、内核链表、栈）——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。

相关文章

Linux内核的调试（TODO）

Linux内核的调试（TODO）

（TODO）
阅读更多...
HarmonyOS学习(七)——UI（五）常用布局总结

HarmonyOS学习(七)——UI（五）常用布局总结

自适应布局 1.1、线性布局（LinearLayout） 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列，Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距，达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式，且在各类尺寸屏幕上表现一致，其中交叉轴为垂直时，取值为Vert
阅读更多...
Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya（不是本人，claude AI）在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容： 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用
阅读更多...
【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画（下）

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画（下）

【课程链接】 AntV G6：深入图形与图形分组、自定义节点、节点动画（下）_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中，应该怎样去计算和绘制图形，如何给一个图形制作不间断的动画，以及在鼠标事件之后产生动画。（有点难，需要好好理解） <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06
阅读更多...
学习hash总结

学习hash总结

2014/1/29/   最近刚开始学hash，名字很陌生，但是hash的思想却很熟悉，以前早就做过此类的题，但是不知道这就是hash思想而已，说白了hash就是一个映射，往往灵活利用数组的下标来实现算法，hash的作用：1、判重；2、统计次数；
阅读更多...
嵌入式QT开发：构建高效智能的嵌入式系统

嵌入式QT开发：构建高效智能的嵌入式系统

摘要： 本文深入探讨了嵌入式 QT 相关的各个方面。从 QT 框架的基础架构和核心概念出发，详细阐述了其在嵌入式环境中的优势与特点。文中分析了嵌入式 QT 的开发环境搭建过程，包括交叉编译工具链的配置等关键步骤。进一步探讨了嵌入式 QT 的界面设计与开发，涵盖了从基本控件的使用到复杂界面布局的构建。同时也深入研究了信号与槽机制在嵌入式系统中的应用，以及嵌入式 QT 与硬件设备的交互，包括输入输出设
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

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

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 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>#
阅读更多...
内核启动时减少log的方式

内核启动时减少log的方式

内核引导选项 内核引导选项大体上可以分为两类：一类与设备无关、另一类与设备有关。与设备有关的引导选项多如牛毛，需要你自己阅读内核中的相应驱动程序源码以获取其能够接受的引导选项。比如，如果你想知道可以向 AHA1542 SCSI 驱动程序传递哪些引导选项，那么就查看 drivers/scsi/aha1542.c 文件，一般在前面 100 行注释里就可以找到所接受的引导选项说明。大多数选项是通过"_
阅读更多...
零基础学习Redis(10) -- zset类型命令使用

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合，内部除了存储元素外，还会存储一个score，存储在zset中的元素会按照score的大小升序排列，不同元素的score可以重复，score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2