嵌入式学习的第二十三天-数据结构-树+哈希表+内核链表

一、树（一对多）

1.树的定义

树：n（n>=0）个结点的有限集合。n = 0 ,空树。

2.在任意一个非空树中，

(1)，有且仅有一个特定的根结点

(2)，当n>1 时，其余结点可分为m个互不相交的有限集合T1,T2,T3.。。。。Tm，其中每一个

集合又是一个树，并且称谓子树。

3.度

结点拥有子树的个数称谓结点的度。度为0的结点称谓叶结点。度不为0，称谓分支结点。

树的度数是指，这棵树中，最大的结点的度数，称谓树的度数。

树的深度或高度，从根开始，根为第一层，根的孩子为第二层。

4.树的存储，顺序结构，链式结构。

二、二叉树 binary tree

1.定义

n个结点的有限集合，集合要么为空树，要么由一个根结点和两棵互不相交，分别称谓根结点的左

子树和右子树的二叉树组成。

相交：D-E  

2.特点

(1)，每个结点最多两个子树。

(2)，左子树和右子树是有顺序的，次序不能颠倒。

(3)，如果某个结点只有一个子树，也要区分左，右子树。

3.特殊的二叉树

(1)，斜树，所有的结点都只有左子树，左斜树，所有结点都只有右子树，右树。

(2)，满二叉树，所有的分支结点都存在左右子树，并且叶子都在同一层上。

(3)，完全二叉树，对于一颗有n个结点的二叉树按层序编号，如果编号i（1<=i<=n）的结点于同样

深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这可树为完全二叉树。

4.特性（选填）
(1)，在二叉树的第i层上最多有2^(i-1)个结点 i>=1

(2),深度为k的二叉树至多有2^k  -1 个结点 k>=1

(3）,任意一个二叉树T，如果其叶子结点的个数是n0,度数为2的结点数为n2， n0 = n2 +1;

(4),有n个结点的完全二叉树深度为(logn/log 2) +1;

        注：向下取整

5.树的遍历

（1）广度遍历：层序

（2）深度遍历

        前序，根左右，先访问根，然访问左，访问右。

        中序，左根右，先从根开始（不是先访问根），从左开始访问，在访问根，在访问右结点。

        后序，左右根，先从根开始（不是先访问根），先访问左，在访问右。在访问根。

三、树的链式存储的一般操作 

1.创建

void CreateTree(TreeNode **root)
{char c = data[ind++];if('#'==c){*root=NULL;return;}else{*root = malloc(sizeof(TreeNode));if(NULL == *root){fprintf(stderr, "CreateTree malloc error");return ;}(*root)->data=c;CreateTree(&(*root)->left);CreateTree(&(*root)->rigjt);}
}

2.前序

void PreOrderTraverse(TreeNode*root)
{if(NULL == root){return;}printf("%c",root->data);PreOrderTraverse(root->left);PreOrderTraverse(root->rigjt);
}

3.中序

void InOrderTraverse(TreeNode*root)
{if(NULL == root){return;}InOrderTraverse(root->left);printf("%c",root->data);InOrderTraverse(root->rigjt);
}

4.后序

void PostOrderTraverse(TreeNode*root)
{if(NULL == root){return;}PostOrderTraverse(root->left);PostOrderTraverse(root->rigjt);printf("%c",root->data);
}

5.销毁

void DestoryTree(TreeNode *root)
{if(NULL == root){return;}DestoryTree(root->left);DestoryTree(root->rigjt);free(root);
}

四、哈希表

1.创建

HSTable*CreateHsTable(int len)
{HSTable*hs = malloc(sizeof(HSTable));if(NULL == hs){fprintf(stderr, "CreateHsTable malloc error");return NULL;}hs->head = malloc(sizeof(DATATYPE)*len);if(NULL == hs->head){fprintf(stderr, "CreateHsTable malloc2 error");return NULL;}    hs->tlen =len;int i=0;for(i =0;i<len;i++){hs->head[i]=-1;}return hs;
}

2.HSFun

int HSFun(HSTable*hs,DATATYPE*data)
{return *data % hs->tlen;
}

3.插入

int HSInsert(HSTable*hs,DATATYPE*data)
{int ind=HSFun(hs, data);while(hs->head[ind]!=-1){printf("pos %d,num :%d\n",ind,*data);ind =(ind+1)%hs->tlen;}hs->head[ind]=*data;return 0;}

4.查找

int HsSearch(HSTable*hs,DATATYPE*data)
{int ind=HSFun(hs, data);int old_ind=ind;while(hs->head[ind]!=*data){ind =(ind+1)%hs->tlen;if(old_ind==ind){return -1;}}return ind;
}

5.main.c

int main(int argc, char **argv)
{HSTable*hs=CreateHsTable(15);int array[]={12,67,56,16,25,37,22,29,15,47,48,34};int i = 0;for (i = 0; i < 12; i++){HSInsert(hs, &array[i]);}int want_num = 37;int ret = HsSearch(hs, &want_num);if (-1 == ret){printf("not find \n");}else{printf("find ,%d\n", hs->head[ret]);}return 0;
}

五、内核链表（双向链表）

 思想：将数据摘出来,没有耦合，需自己定义结构体，结构体内部包括节点和数据，可按照自己的

            需求设计

Linux第一宏：offset(地址偏移量) 和 contrainof（求地址）

相关操作：

1.klist.c

#include "./klist.h"void klist_init(KLIST* head)
{head->prev = head;head->next = head;
}void klist_add(KLIST* newnode,KLIST*prev,KLIST* next)
{newnode->next =next;newnode->prev = prev;prev->next = newnode;next->prev = newnode;}void klist_add_head(KLIST* head,KLIST* newnode)
{klist_add(newnode,head,head->next);
}
void klist_add_tail(KLIST* head,KLIST* newnode)
{klist_add(newnode,head->prev,head);
}void klist_del(KLIST*prev,KLIST*next)
{prev->next = next;next->prev = prev;
}

2.klist.h

#ifndef __KLIST_H__
#define __KLIST_H__typedef struct __klist
{struct __klist *next;struct __klist* prev;
}KLIST;#define offset(type,mem) ((size_t)  &((type*)0)->mem)
/*** @brief ptr 结构体node的指针type 结构体 per *       mem  node在结构中的变量名*/
#define containerof(ptr,type,mem) ({ const typeof(((type*)0)->mem) * _mptr = (ptr);\(type*) ((char*)_mptr- offset(type,mem)); })#define klist_for_entry(ptr,type,mem)  containerof(ptr,type,mem)
/*** @brief p , 指向结构体的指针*        n, 指向当前结构体的下一个指针head， 链表的头节点指针mem， node在结构体中变量的名字*/
//for(p=klist_for_entry(&(head)->next,typeof(*p),mem),n=klist_for_entry((p)->mem.next,typeof(*p),mem);
#define klist_for_each(p,n,head,mem) \
for(p=klist_for_entry(head->next,typeof(*p),mem),n=klist_for_entry((p)->mem.next,typeof(*p),mem);\
&p->mem != (head); p=n,n=klist_for_entry((n)->mem.next,typeof(*n),mem))// #define offset(type,mem) ((size_t) &((type*)0)->mem)
// #define containerof(p,type,mem) ({\
// const typeof(  ((type*)0)->mem ) * _mptr = (p);\
// (type*)((char*)_mptr - offset(type,mem));})
// #define klist_entry(p,type,mem) containerof(p,type,mem)// #define klist_for_each(p,n,head,node)\
// for(p=klist_entry((head)->next,typeof(*p),node),\
//     n=klist_entry(p->node.next,typeof(*p),node);        \
//     &p->node != (head);p=n,n=klist_entry(n->node.next,typeof(*n),node))void klist_init(KLIST* head);
void klist_add_head(KLIST* head,KLIST* newnode);
void klist_add_tail(KLIST* head,KLIST* newnode);
void klist_del(KLIST*prev,KLIST*next);#endif

3.per.c

#include "./per.h"
#include "klist.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>int add_per(int id,char *name,KLIST* head)
{PER* per = malloc(sizeof(PER));if(NULL == per){perror("add_per malloc\n");return 1;}strcpy(per->name,name);per->id = id;klist_add_tail(head,&per->node);return 0;
}int show_per(KLIST* head)
{PER *p ,*n;klist_for_each(p,n,head,node){printf("%d %s\n",p->id,p->name);}return 0;
}int del_per(KLIST* head,int id)
{PER *p ,*n;klist_for_each(p,n,head,node){//printf("%d %s\n",p->id,p->name);if(p->id == id){klist_del(p->node.prev, p->node.next);free(p);}}return 0;}

4.per.h

#ifndef __PER_H__
#define __PER_H__
#include "./klist.h"
typedef struct 
{int id;char name[40];KLIST node;
} PER;int add_per(int id,char *name,KLIST* head);
int show_per(KLIST* head);
int del_per(KLIST* head,int id);
#endif

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【C++】map和multimap的常用接口详解

【C++】map和multimap的常用接口详解

map和multimap的文档&#xff1a;<map> - C Reference 1.map类的介绍 map 有两个模板参数&#xff0c;是 key/value的场景。 这里的Key就是key&#xff0c;T就是value&#xff0c;命名不同而已。map默认要求Key⽀持⼩于⽐较&#xff08;升序&#xff09;&#xff0c;如…
阅读更多...
sqli-labs第九关—‘时间盲注

sqli-labs第九关—‘时间盲注

一&#xff1a;判断闭合类型 先按照之前的判断方式判断&#xff0c;发现无论输入什么都显示You are in.......... 可以考虑使用时间盲注&#xff1a; 二&#xff1a;时间盲注Time-based Blind&#xff1a; 1.解释&#xff1a; 通过时间延迟判断结果 2.核心原理&#xff1a…
阅读更多...
先说爱的人为什么先离开

先说爱的人为什么先离开

2025年5月19日&#xff0c;15~23℃&#xff0c;贼好的一天&#xff0c;无事发生 待办&#xff1a; 2024年税务申报 《高等数学2》取消考试资格学生名单 《物理[2]》取消考试资格名单 5月24日、25日监考报名 《高等数学2》备课 《物理[2]》备课 职称申报材料 教学技能大赛PPT 遇…
阅读更多...
（10）python开发经验

（10）python开发经验

文章目录 1 cp35 cp36什么意思2 找不到pip3 subprocess编码错误4 导出依赖文件包含路径5 使用自己编译的python并且pyinstall打包程序 更多精彩内容&#x1f449;内容导航 &#x1f448;&#x1f449;Qt开发 &#x1f448;&#x1f449;python开发 &#x1f448; 1 cp35 cp36什…
阅读更多...
Ubuntu搭建TFTP服务器的方法

Ubuntu搭建TFTP服务器的方法

0 工具 Ubuntu 18.041 Ubuntu搭建TFTP服务器的方法 在Ubuntu下搭建TFTP服务器可以让我们下载文件到开发板更加方便&#xff0c;同时也可以实现TFTP加载Linux镜像&#xff0c;方便调试。 1.1 安装tftp-hpa&#xff08;TFTP客户端&#xff09;、tftpd-hpa&#xff08;TFTP服务…
阅读更多...
深入了解linux系统—— 基础IO（上）

深入了解linux系统—— 基础IO（上）

文件 在之前学习C语言文件操作时&#xff0c;我们了解过什么是文件&#xff0c;这里简单回顾一下&#xff1a; 文件存在磁盘中&#xff0c;文件有分为程序文件、数据文件&#xff1b;二进制文件和文本文件等。 详细描述见文章&#xff1a;文件操作——C语言 文件在磁盘里&a…
阅读更多...
代码随想录算法训练营第六十六天| 图论11—卡码网97. 小明逛公园，127. 骑士的攻击

代码随想录算法训练营第六十六天| 图论11—卡码网97. 小明逛公园，127. 骑士的攻击

继续补&#xff0c;又是两个新算法&#xff0c;继续进行勉强理解&#xff0c;也是训练营最后一天了&#xff0c;六十多天的刷题告一段落了&#xff01; 97. 小明逛公园 97. 小明逛公园 感觉还是有点难理解原理 Floyd 算法对边的权值正负没有要求&#xff0c;都可以处理。核心…
阅读更多...
【深度学习基础】从感知机到多层神经网络：模型原理、结构与计算过程全解析

【深度学习基础】从感知机到多层神经网络：模型原理、结构与计算过程全解析

【深度学习基础】从感知机到多层神经网络&#xff1a;模型原理、结构与计算过程全解析 1. 引言 神经网络的重要性&#xff1a; 作为人工智能的核心技术之一&#xff0c;神经网络通过模拟人脑神经元的工作机制&#xff0c;成为解决复杂模式识别、预测和决策任务的利器。从图像分…
阅读更多...
第8讲、Multi-Head Attention 的核心机制与实现细节

第8讲、Multi-Head Attention 的核心机制与实现细节

&#x1f914; 为什么要有 Multi-Head Attention&#xff1f; 单个 Attention 机制虽然可以捕捉句子中不同词之间的关系&#xff0c;但它只能关注一种角度或模式。 Multi-Head 的作用是&#xff1a; 多个头 多个视角同时观察序列的不同关系。 例如&#xff1a; 一个头可能专…
阅读更多...
2025年PMP 学习十八 第11章 项目风险管理 （11.5~11.7）

2025年PMP 学习十八 第11章 项目风险管理 （11.5~11.7）

2025年PMP 学习十八 第11章 项目风险管理 &#xff08;11.5~11.7&#xff09; 第11章 项目风险管理 序号过程过程组1规划风险管理规划2识别风险规划3实施定性风险分析规划4实施定量风险分析规划5规划风险应对执行6实施风险应对执行7监控风险监控 文章目录 2025年PMP 学习十八…
阅读更多...
怎么在excel单元格1-5行中在原来内容前面加上固定一个字？

怎么在excel单元格1-5行中在原来内容前面加上固定一个字？

环境&#xff1a; WPS 2024 问题描述&#xff1a; 怎么在excel单元格1-5行中在原来内容前面加上固定一个字&#xff1f; 解决方案&#xff1a; 1.在Excel中&#xff0c;如果您想在单元格的内容前面添加一个固定的字&#xff0c;可以通过以下几种方法实现&#xff1a; 方法…
阅读更多...
浅论3DGS溅射模型在VR眼镜上的应用

浅论3DGS溅射模型在VR眼镜上的应用

摆烂仙君小课堂开课了&#xff0c;本期将介绍如何手搓VR眼镜&#xff0c;并将随手拍的电影变成3D视频。 一、3DGS模型介绍 3D 高斯模型是基于高斯函数构建的用于描述三维空间中数据分布概率的模型&#xff0c;高斯函数在数学和物理领域有着广泛应用&#xff0c;其在 3D 情境下…
阅读更多...
最新文章

Copyright @ 2022~2023