文章目录
前言
之前做的项目需要用到多级菜单，我由于使用的是128*64的OLED，像是LVGL等UI软件不能使用。而且，由于项目的特殊性，市面上的UI不符合需求，我需要自己动手使用一些专业的绘图软件来构建自己的UI和自己的风格，因此需要一个多级菜单的功能。
网上的普遍采用的多级菜单的方案是基于索引或者树的结构，索引居多。网上构建索引这种方案经过我自己的使用经验和分析，不利于扩展，阅读性也是差的不要不要的，而且也容易造成内存越界访问的缺点。基于这些缺点，我就自己开发了一个简单的多级菜单的功能。这个多级菜单实际上是树的模式，但是我使用了一个比较巧妙地方法来把树结构的数据直接转换成哈希表的方式，使用哈希表的方式构建的一个多级菜单。
1、理解多级菜单的基础
其实，这个多级菜单也是基于索引的，但是它可阅读性好，拓展性也不错，查找的性能差不多是最优，就是有点占用内存空间。
1.1哈希表
这个多级菜单用到的就是一个很少单片机开发人员会学习的点，也就是数据结构。这里使用比较简单的数据结构的一种来构建多级菜单。这个数据结构就是哈希表或者说是散列表。
这里就用哈希表来说明，哈希表，也可以说是Python中的字典，也就是哈希表中有一个关键字，程序可以通过关键字来找到数据存在哪里。
我们用一个图就大概可以理解关键字（Key）和哈希表的关系。下图，程序可以通过哈希函数生成一个Key，这里的Key等于存储的地址，我们得到Key，也就是得到存储的地址，那就可以直接访问地址来获取数据。
注意，这里的Key是自己通过一个哈希函数生成的，我们可以通过这个Key来找到存放的数据。
1.11哈希函数
哈希函数也就是生成一个关键字的函数，该关键字是唯一的，这样我们才能通过地址找到想要的内容。哈希函数有很多，这里简单举个例子，看代码：
/*最简单的哈希函数*/
#define MAXARRY 50
int HASH_TABLE[MAXARRY];
int create_hashkey(int num)
{
return (num*2+3%MAXARRY);
}
/*找到相关数据*/
int Find_data(int num)
{
int key=create_hashkey(num);
return HASH_TABLE[key];
}
从这里就可以看出，哈希表实际上建立的是一个地址与关键字之间的联系，通过关键字就可以找到相关的地址，从而找到相关的内容。
1.12哈希冲突
哈希冲突，就是生成的通过哈希函数生成的关键字一样，也就是映射地址是一样的，这样我们就没法通过地址来查找到需要的数据，我们不同的数据不可能都存放到同一个区域。
这就叫做哈希冲突，哈希冲突也是有办法解决的，比如简单的开放地址法，也就是如果冲突，就重新计算哈希值找到下一块空的地址，然后进行存放。
1.13适合场景
哈希表最适合求解问题是查找与给定值相等的记录。这里的重点是给定值很特殊，不重复，也就是计算哈希值的关键字要特殊。每一个都是挺特殊的，都挺唯一，那对于查找的问题就非常棒了。外插一句，查找的时间复杂度是O(1)。
2、哈希表与多级菜单
说了这么多，那哈希表与多级菜单有什么联系捏？我们认真观察，多级菜单需要高频率的查询，而且多级菜单的每一个选项的绝对位置都是唯一的。回顾哈希表的应用场景，
适用于查找与给定值相等数据，我们的每一个选项都是唯一的绝对位置，也就是非常符合哈希表的使用场景，完美。
2.1多级菜单的选项映射
如果我们能够将每一个选项的特殊性标识出来，那么是不是就可以进行映射，就可以查询到我们设置的菜单。那它的图示应该是这个样子的。
我们可以假设，子选项1.1是选项1的下一级。基于这个假设，我们访问的哈希表时候，是不是可以直接输入类似字符串“1.1”就可以知道它的实际内容了。
2.2参考代码
经过上面的简单分析，我们可以通过使用哈希表来构建多级菜单，只不过菜单的上一级和下一级的指向对象我们不关心，我们只需要输入相关选项的位置就一直通过哈希函数得到它指向的内容。如果我们需要改变选项的情况，那么改变输入的位置就可以知道。
这里提供一个关于哈希表的增删改查的基础函数，并基于这四个基础函数进行一个多级菜单的构建和使用的例子。
2.3实际位置定义
我将在下面使用字符串来获得哈希表的唯一Key，这个的字符串格式是个人自定义的，如果想使用这个和理解这个代码，可以先理解下图。
从图中可以看出这个多级目录实际是一个树的结构，如果想要遍历树，一般的思路是使用指针来指向其子节点和父节点，可以知道树是以指针的形式保存了其每一个成员的相对位置。而我使用了一个比较巧妙的方法，直接使用字符串的形式将每个位置的绝对位置表示出来，这其实有点类似文件存放的形式，只不过实际的位置存放在哈希表当中。
2.4 哈希表参考代码
实现基于面向对象的思想，代码略复杂，如果懂函数指针，static和const，结构体也不会特别难懂！
代码中将GUI更新和数据更新写成了两个函数指针，方便分开来使用。
代码使用纯C的方式书写，想要使用在单片机上面，直接复制叭！
2.4.1核心逻辑代码
/*************************************************
Copyright:None
Author: Silent Knight
Date:2021/7/18
Description:基于哈希表的多级菜单
**************************************************/
#include "stdio.h"
#include "string.h"
#define MAX_EXPLAIN 10 /*最大说明缓冲*/
#define HASH_SKEY_LEN 15 /*哈希关键字最大长度*/
#define HASH_SIZE 50
#define HASH_NULLKEY '\0'
#define HASH_OK 1
#define HASH_ERROR (HASH_SIZE+2)
typedef unsigned long long uint64_t;
typedef unsigned int uint16_t;
typedef unsigned char uint8_t;
typedef unsigned char Status;
/*初始化函数*/
static void * my_memset(void *s,int c,int n)/*初始化*/
{
char *c_s=(char *)s;
while(n--) *c_s++=c;
return s;
}
/*复制函数*/
static void * my_memcpy(void *dest,void *src,unsigned int size)
{
char *b_dest=(char *)dest,*b_src=(char *)src;
unsigned int len;
for(len=size;len>0;len--)
{
*b_dest++=*b_src++;
}
return dest;
}
/*函数行为表*/
struct hashmenu_vtbl;
/*
选项位置使用说明：pos赋值为相应的格式的内容即可访问相应节点的内容
1 表示一级选项的第一个
2.2，二级选的下一级子选项的第二个
1.1.1表示一级选的下一级子选项的第一个，
*/
typedef struct
{
char pos[HASH_SKEY_LEN]; /*选项位置也是关键字*/
char explain[MAX_EXPLAIN]; /*选项说明*/
void (*gui)(void *parameter);/*选项GUI更新函数*/
void (*act)(void *parameter);/*选项动作函数*/
void (*default_act)(void *parameter);/*选项默认动作，执行上下左右切换界面后默认执行*/
}hashmenu_member; /*每个成员的属性*/
/*哈希表构成菜单*/
typedef struct
{
hashmenu_member hashtable[HASH_SIZE]; /*哈希表*/
struct hashmenu_vtbl *c_vptr;/*哈希表行为函数指针*/
int hash_table_size; //哈希表关键字的数量
}hashmenu;/*表头*/
/*函数行为表*/
struct hashmenu_vtbl
{
Status (*insert)(hashmenu * const Me,hashmenu_member *const member); /*添加选项*/
Status (*remove)(hashmenu * const Me,hashmenu_member * const member); /*删除选项*/
Status (*modify)(hashmenu * const Me,hashmenu_member * const member); /*设置选项*/
Status (*search)(hashmenu * const Me,hashmenu_member * const member); /*查找选项*/
/*找到上下左右选项*/
Status (*searchleft)(hashmenu * const Me,hashmenu_member * const member); /*查找当前节点左选项*/
Status (*searchright)(hashmenu * const Me,hashmenu_member * const member); /*查找当前节点右选项*/
Status (*searchup)(hashmenu * const Me,hashmenu_member * const member); /*查找当前节点上一个选项*/
Status (*searchdown)(hashmenu * const Me,hashmenu_member * const member); /*查找当前节点下一个选项*/
};
/*仅留创建和删除接口留给其他文件进行访问*/
void HashMenuCreate(hashmenu * const Me);
void HashMenuDelete(hashmenu * const Me);
/*增删改查接口*/
static Status HashOpenInser(hashmenu * const Me,hashmenu_member *const member);
static Status HashOpenRemove(hashmenu * const Me,hashmenu_member * const member);
static Status HashOpenSearch(hashmenu * const Me,hashmenu_member * const member);
static Status HashOpenModify(hashmenu * const Me,hashmenu_member * const member);
/*菜单切换接口*/
static Status HashMenuPeerLeft(hashmenu * const Me,hashmenu_member * const member);/*找到当前节点同级的选项*/
static Status HashMenuPeerRight(hashmenu * const Me,hashmenu_member * const member);/*找到当前节点下一级的选项*/
static Status HashMenuDepthUp(hashmenu * const Me,hashmenu_member * const member);/*找到当前节点下一级的选项*/
static Status HashMenuDepthDown(hashmenu * const Me,hashmenu_member * const member);/*找到当前节点下一级的选项*/
/*去符号化哈希表*/
static uint16_t HashOpenKey(const char* skey)
{
char *p = (char*)skey;
uint16_t hasy_key = 0;
if(*p)
{
for(;*p != '\0'; ++p)
hasy_key = (hasy_key << 5) - hasy_key + *p;
}
return hasy_key%(HASH_SIZE-1);
}
/*找到唯一的哈希值*/
static uint16_t HashOpenFindUniqueKey(hashmenu * const Me,hashmenu_member *const member)
{
uint16_t unique_addr;
int cout=HASH_SIZE;
uint16_t clen;
if(Me->hash_table_size<=0) return HASH_ERROR;
unique_addr=HashOpenKey(member->pos);
/*根据内容查看哈希值是不是指向需要的地址*/
clen=strlen(member->pos);
clen = (clen >HASH_SKEY_LEN) ?HASH_SKEY_LEN:clen;
while((strncmp(Me->hashtable[unique_addr].pos,member->pos,clen)!=0)&&cout--)
{
unique_addr=(unique_addr+1)%HASH_SIZE; /*开放地址法则线性探测*/
}
if(cout<0) return HASH_ERROR;/*遍历完这个哈希表都没有找到*/
return unique_addr;
}
/*创建哈希表*/
void HashMenuCreate(hashmenu * const Me)
{
int i;
static struct hashmenu_vtbl vtable;
Me->hash_table_size=0;
my_memset(Me, 0, sizeof(hashmenu));
vtable.insert=&HashOpenInser;
vtable.remove=&HashOpenRemove;
vtable.modify=&HashOpenModify;
vtable.search=&HashOpenSearch;
vtable.searchleft=&HashMenuPeerLeft;
vtable.searchright=&HashMenuPeerRight;
vtable.searchup=&HashMenuDepthUp;
vtable.searchdown=&HashMenuDepthDown;
Me->c_vptr=&vtable;
}
/*删除哈希表*/
void HashMenuDelete(hashmenu * const Me)
{
int i;
my_memset(Me, 0, sizeof(hashmenu));
}
/*增*/
Status HashOpenInser(hashmenu * const Me,hashmenu_member *const member)
{
uint16_t addr;
if(Me->hash_table_size>=HASH_SIZE) return HASH_ERROR;
addr=HashOpenKey(member->pos);
/*开放地址法则线性探测解决冲突*/
while(Me->hashtable[addr].explain[0]!=HASH_NULLKEY)
addr=(addr+1)%HASH_SIZE;
/*插入数据*/
my_memcpy(&(Me->hashtable[addr]),member,sizeof(hashmenu_member));
Me->hash_table_size++;
return HASH_OK;
}
/*删*/
Status HashOpenRemove(hashmenu * const Me,hashmenu_member * const member)
{
uint16_t addr;
addr=HashOpenFindUniqueKey(Me,member);
if(addr)
{
my_memset(&(Me->hashtable[addr]),0,sizeof(hashmenu_member));
Me->hash_table_size--;
return HASH_OK;
}
else return HASH_ERROR;
return HASH_OK;
}
/*查*/
Status HashOpenSearch(hashmenu * const Me,hashmenu_member * const member)
{
uint16_t addr;
addr=HashOpenFindUniqueKey(Me,member);
if(addr!=HASH_ERROR)
{
my_memcpy(member,&(Me->hashtable[addr]),sizeof(hashmenu_member));
return HASH_OK;
}
else return HASH_ERROR;
return HASH_OK;
}
/*改*/
Status HashOpenModify(hashmenu * const Me,hashmenu_member * const member)
{
uint16_t addr;
addr=HashOpenFindUniqueKey(Me,member);
if(addr)
{
my_memcpy(&(Me->hashtable[addr]),member,sizeof(hashmenu_member));
return HASH_OK;
}
else return HASH_ERROR;
return HASH_OK;
}
/*找到当前节点同级的左选项*/
/*例如：当前pos="1.1.2"，左选项节点就是pos="1.1.1"*/
static Status HashMenuPeerLeft(hashmenu * const Me,hashmenu_member * const member)
{
uint8_t *c_pos=(uint8_t *)member->pos;
uint8_t t_chang;
Status flag;
if(Me->hash_table_size<=0) return HASH_ERROR;
while(*++c_pos!='\0');/*找到位置最后的位置*/
t_chang=*(--c_pos)-1;/*将最后位置的上一个字符值-1*/
*c_pos=t_chang;
flag=Me->c_vptr->search(Me,member);
if(flag!=HASH_ERROR) return HASH_OK;
else
{
/*重新指向先前内容*/
t_chang=(*c_pos)+1;
*c_pos=t_chang;
Me->c_vptr->search(Me,member);
}
/*执行默认函数*/
member->default_act(NULL);
return HASH_OK;
}
/*找到当前节点同级的右选项*/
/*例如：当前pos="1.1.2"，右选项节点就是pos="1.1.3"*/
static Status HashMenuPeerRight(hashmenu * const Me,hashmenu_member * const member)
{
uint8_t *c_pos=(uint8_t *)member->pos;
uint8_t t_chang;
Status flag;
if(Me->hash_table_size<=0) return HASH_ERROR;
while(*++c_pos!='\0');/*找到位置最后的位置*/
t_chang=*(--c_pos)+1;/*将最后位置的上一个字符值-1*/
*c_pos=t_chang;
flag=Me->c_vptr->search(Me,member);
if(flag!=HASH_ERROR) return HASH_OK;
else
{
/*重新指向先前内容*/
t_chang=(*c_pos)-1;
*c_pos=t_chang;
Me->c_vptr->search(Me,member);
}
/*执行默认函数*/
member->default_act(NULL);
return HASH_OK;
}
/*找到当前节点下一级的选项*/
/*例如：当前pos="1.1"，下一级的选项节点就是pos="1.1.1"*/
static Status HashMenuDepthDown(hashmenu * const Me,hashmenu_member * const member)
{
uint8_t *c_pos=(uint8_t *)member->pos;
Status flag;
uint16_t clen;
if(Me->hash_table_size<=0) return HASH_ERROR;
clen=strlen(member->pos);
if(clen>=HASH_SKEY_LEN-3) return HASH_ERROR; /*避免内存越界*/
while(*++c_pos!='\0');/*找到位置最后的位置*/
*c_pos='.';
*(c_pos+1)='1';
*(c_pos+2)='\0';
flag=Me->c_vptr->search(Me,member);
if(flag!=HASH_ERROR) return HASH_OK;
else
{
/*重新指向先前内容*/
*c_pos='\0';
*(c_pos+1)='\0';
*(c_pos+2)='\0';
Me->c_vptr->search(Me,member);
}
/*执行默认函数*/
member->default_act(NULL);
return HASH_OK;
}
/*找到当前节点上一级的选项*/
/*例如：当前pos="1.1"，上一级的选项节点就是pos="1"*/
static Status HashMenuDepthUp(hashmenu * const Me,hashmenu_member * const member)
{
uint8_t *c_pos=(uint8_t *)member->pos;
uint8_t last_pos;/*保存上次数字*/
Status flag;
uint16_t clen;
if(Me->hash_table_size<=0) return HASH_ERROR;
clen=strlen(member->pos);
if(clen<=1) /*避免内存越界*/
{
Me->c_vptr->search(Me,member);
return HASH_OK;
}
while(*++c_pos!='\0');/*找到位置最后的位置*/
last_pos=*(c_pos-1);/*保存数字*/
*(c_pos-1)='\0';/*.1，删除数字*/
*(c_pos-2)='\0';/*.，删除点*/
flag=Me->c_vptr->search(Me,member);
if(flag!=HASH_ERROR) return HASH_OK;
else
{
/*重新指向先前内容*/
*(c_pos-1)=last_pos;
*(c_pos-2)='.';
Me->c_vptr->search(Me,member);
}
/*执行默认函数*/
member->default_act(NULL);
return HASH_OK;
}
/*打印成员信息*/
void PrintMember(hashmenu_member member)
{
printf("pos=%s\r\n",member.pos);
}
/*打印哈希表所有内容*/
void HashOpenPrint(hashmenu const * const Me)
{
for(int i=0;i<HASH_SIZE;i++)
{
if(Me->hashtable[i].explain[0]!=HASH_NULLKEY)
{
printf("key is %s explain = %s\n",Me->hashtable[i].pos,Me->hashtable[i].explain);
}
}
}
2.4.2测试参考代码
使用参考代码，主要可以看我创建数据的格式就行，逻辑都是一样的，就是略长。
/*测试GUI*/
void GUI_1(void *parameter)
{
printf("--------------- -GUI 123--------------\r\n");
printf("---------------->OPTION 1<-------------\r\n");
printf("-----------------OPTION 2-------------\r\n");
printf("-----------------OPTION 3-------------\r\n");
}
void GUI_2(void *parameter)
{
printf("--------------- -GUI 123--------------\r\n");
printf("-----------------OPTION 1-------------\r\n");
printf("---------------->OPTION 2<------------\r\n");
printf("-----------------OPTION 3-------------\r\n");
}
void GUI_3(void *parameter)
{
printf("--------------- -GUI 123--------------\r\n");
printf("-----------------OPTION 1-------------\r\n");
printf("-----------------OPTION 2-------------\r\n");
printf("---------------->OPTION 3<------------\r\n");
}
void GUI_1_1(void *parameter)
{
printf("------------------GUI 1_1-------------\r\n");
printf("---------------->OPTION 1.1<------------\r\n");
printf("-----------------OPTION 1.2-------------\r\n");
printf("-----------------OPTION 1.3------------\r\n");
}
void GUI_1_2(void *parameter)
{
printf("------------------GUI 1_1-------------\r\n");
printf("-----------------OPTION 1.1-------------\r\n");
printf("---------------->OPTION 1.2<------------\r\n");
printf("-----------------OPTION 1.3------------\r\n");
}
void GUI_1_3(void *parameter)
{
printf("------------------GUI 1_1-------------\r\n");
printf("-----------------OPTION 1.1-------------\r\n");
printf("-----------------OPTION 1.2-------------\r\n");
printf("---------------->OPTION 1.3<------------\r\n");
}
/*测试功能函数*/
void func1(void *num)
{
hashmenu_member *mem=(hashmenu_member *)num;
printf("mem->explain =%s\r\n",mem->explain);
}
#define UP 'w'
#define DOWM 's'
#define LEFT 'a'
#define RIGHT 'd'
#define ENTER 'e'
#define QUIT 'q'
hashmenu tmenu;
void test()
{
hashmenu_member t_member;
hashmenu_member d_member;
int x=1;
char choice;
/*创建哈希表*/
HashMenuCreate(&tmenu);
/*输入内容，插入哈希表*/
t_member.act=func1;
t_member.gui=GUI_1;
strcpy(t_member.pos,"1");
strcpy(t_member.explain,"1 EXPLAIN\r\n");
tmenu.c_vptr->insert(&tmenu,&t_member);
PrintMember(t_member);
t_member.act=func1;
t_member.gui=GUI_2;
strcpy(t_member.pos,"2");
strcpy(t_member.explain,"2 EXPLAIN\r\n");
tmenu.c_vptr->insert(&tmenu,&t_member);
PrintMember(t_member);
strcpy(t_member.pos,"3");
t_member.gui=GUI_3;
t_member.act=func1;
strcpy(t_member.explain,"3 EXPLAIN\r\n");
tmenu.c_vptr->insert(&tmenu,&t_member);
PrintMember(t_member);
t_member.act=func1;
t_member.gui=GUI_1_1;
strcpy(t_member.pos,"1.1");
strcpy(t_member.explain,"1.1 EXPLAIN\r\n");
tmenu.c_vptr->insert(&tmenu,&t_member);
PrintMember(t_member);
t_member.gui=GUI_1_2;
t_member.act=func1;
strcpy(t_member.pos,"1.2");
strcpy(t_member.explain,"1.2 EXPLAIN\r\n");
tmenu.c_vptr->insert(&tmenu,&t_member);
PrintMember(t_member);
t_member.gui=GUI_1_3;
t_member.act=func1;
strcpy(t_member.pos,"1.3");
strcpy(t_member.explain,"1.3 EXPLAIN\r\n");
tmenu.c_vptr->insert(&tmenu,&t_member);
PrintMember(t_member);
strcpy(t_member.pos,"2.1");
strcpy(t_member.explain,"2.1 EXPLAIN\r\n");
tmenu.c_vptr->insert(&tmenu,&t_member);
t_member.act=func1;
PrintMember(t_member);
strcpy(t_member.pos,"2.2");
strcpy(t_member.explain,"2.2 EXPLAIN\r\n");
tmenu.c_vptr->insert(&tmenu,&t_member);
t_member.act=func1;
PrintMember(t_member);
strcpy(t_member.pos,"3.1");
strcpy(t_member.explain,"2.1 EXPLAIN\r\n");
tmenu.c_vptr->insert(&tmenu,&t_member);
t_member.act=func1;
PrintMember(t_member);
strcpy(t_member.pos,"3.2");
strcpy(t_member.explain,"2.2 EXPLAIN\r\n");
tmenu.c_vptr->insert(&tmenu,&t_member);
t_member.act=func1;
PrintMember(t_member);
strcpy(t_member.pos,"1.1.1");
strcpy(t_member.explain,"1.1.1 EXPLAIN\r\n");
tmenu.c_vptr->insert(&tmenu,&t_member);
PrintMember(t_member);
t_member.act=func1;
strcpy(t_member.pos,"1.1.2");
strcpy(t_member.explain,"1.1.2 EXPLAIN\r\n");
tmenu.c_vptr->insert(&tmenu,&t_member);
PrintMember(t_member);
t_member.act=func1;
strcpy(t_member.pos,"1.1.3");
strcpy(t_member.explain,"1.1.3 EXPLAIN\r\n");
tmenu.c_vptr->insert(&tmenu,&t_member);
PrintMember(t_member);
strcpy(t_member.pos,"2.1.1");
strcpy(t_member.explain,"2.1.1 EXPLAIN\r\n");
tmenu.c_vptr->insert(&tmenu,&t_member);
t_member.act=func1;
PrintMember(t_member);
strcpy(t_member.pos,"2.2.1");
strcpy(t_member.explain,"2.2.1 EXPLAIN\r\n");
tmenu.c_vptr->insert(&tmenu,&t_member);
t_member.act=func1;
PrintMember(t_member);
strcpy(t_member.pos,"3.1.1");
strcpy(t_member.explain,"3.1.1 EXPLAIN\r\n");
tmenu.c_vptr->insert(&tmenu,&t_member);
PrintMember(t_member);
t_member.act=func1;
strcpy(t_member.pos,"3.1.2");
strcpy(t_member.explain,"3.1.2 EXPLAIN\r\n");
tmenu.c_vptr->insert(&tmenu,&t_member);
PrintMember(t_member);
t_member.act=func1;
strcpy(t_member.pos,"3.1.3");
strcpy(t_member.explain,"3.1.3 EXPLAIN\r\n");
tmenu.c_vptr->insert(&tmenu,&t_member);
PrintMember(t_member);
HashOpenPrint(&tmenu);
printf("--------------------------------------\r\n");
strcpy(d_member.pos,"1");
tmenu.c_vptr->search(&tmenu,&d_member);
PrintMember(d_member);
while(choice!=QUIT)
{
/*模拟按键或者串口输入*/
scanf("%c",&choice);
/*根据输入执行动作*/
switch (choice)
{
case UP:
if(tmenu.c_vptr->searchup(&tmenu,&d_member)!=HASH_ERROR) d_member.act(&d_member);;
break;
case DOWM:
if(tmenu.c_vptr->searchdown(&tmenu,&d_member)!=HASH_ERROR) d_member.act(&d_member);
break;
case LEFT:
if(tmenu.c_vptr->searchleft(&tmenu,&d_member)!=HASH_ERROR) d_member.act(&d_member);
break;
case RIGHT:
if(tmenu.c_vptr->searchright(&tmenu,&d_member)!=HASH_ERROR) d_member.act(&d_member);
break;
case ENTER:
d_member.act(&d_member);
break;
default:
break;
}
/*根据查询内容更新GUI*/
if(choice!='\n') d_member.gui(NULL);
}
}
int main()
{
test();
return 0;
}
2.4.3执行结果
pos=1
context=1
pos=2
context=2
pos=3
context=3
pos=1.1
context=11
pos=1.2
context=12
pos=1.3
context=13
-------------all content-------------
key is 1 explain = 1 EXPLAIN
key is 2 explain = 2 EXPLAIN
key is 3 explain = 3 EXPLAIN
key is 1.1 explain = 1.1 EXPLAIN
key is 1.2 explain = 1.2 EXPLAIN
key is 1.3 explain = 1.3 EXPLAIN
--------------------------------------
pos=1
context=1
d
mem->explain =2 EXPLAIN
,content=2
--------------- -GUI 123--------------
-----------------OPTION 1-------------
---------------->OPTION 2<------------
-----------------OPTION 3-------------
d
mem->explain =3 EXPLAIN
,content=3
--------------- -GUI 123--------------
-----------------OPTION 1-------------
-----------------OPTION 2-------------
---------------->OPTION 3<------------
a
mem->explain =2 EXPLAIN
,content=2
--------------- -GUI 123--------------
-----------------OPTION 1-------------
---------------->OPTION 2<------------
-----------------OPTION 3-------------
a
mem->explain =1 EXPLAIN
,content=1
--------------- -GUI 123--------------
---------------->OPTION 1<-------------
-----------------OPTION 2-------------
-----------------OPTION 3-------------
s
mem->explain =1.1 EXPLAIN
,content=11
------------------GUI 1_1-------------
---------------->OPTION 1.1<------------
-----------------OPTION 1.2-------------
-----------------OPTION 1.3------------
d
mem->explain =1.2 EXPLAIN
,content=12
------------------GUI 1_1-------------
-----------------OPTION 1.1-------------
---------------->OPTION 1.2<------------
-----------------OPTION 1.3------------
d
mem->explain =1.3 EXPLAIN
,content=13
------------------GUI 1_1-------------
-----------------OPTION 1.1-------------
-----------------OPTION 1.2-------------
---------------->OPTION 1.3<------------
a
mem->explain =1.2 EXPLAIN
,content=12
------------------GUI 1_1-------------
-----------------OPTION 1.1-------------
---------------->OPTION 1.2<------------
-----------------OPTION 1.3------------
a
mem->explain =1.1 EXPLAIN
,content=11
------------------GUI 1_1-------------
---------------->OPTION 1.1<------------
-----------------OPTION 1.2-------------
-----------------OPTION 1.3------------
3.碎碎念
其实这个菜单是挺适合调试的时候或者硬件实在非常简陋的环境下使用。比较简陋的环境下比如，只有按键和很简陋的显示屏(例如128*64的OLED这种)，或者连一个显示屏都没有。实际上还是建议大家学一些常用的嵌入式 GUI 图形库，比如LVGL，QT等。如果不是像我这样，需要自主绘制合适的GUI，还是不建议在非调试的时候或者硬件实在常简陋的环境下使用。
分享就到这里啦，这个思路也是思考挺久的，从有一个合适的想法到边写文章边写代码，其中推翻之前的思路两次，也整了一整天了，希望对大家有帮助！！！
4.完整参考代码
完整参考代码包括测试与核心的代码就贴在这里啦。
/*************************************************
Copyright:None
Author: Silent Knight
Date:2021/7/18
Description:基于哈希表的多级菜单
**************************************************/
#include "stdio.h"
#include "string.h"
#define MAX_EXPLAIN 10 /*最大说明缓冲*/
#define HASH_SKEY_LEN 15 /*哈希关键字最大长度*/
#define HASH_SIZE 50
#define HASH_NULLKEY '\0'
#define HASH_OK 1
#define HASH_ERROR (HASH_SIZE+2)
typedef unsigned long long uint64_t;
typedef unsigned int uint16_t;
typedef unsigned char uint8_t;
typedef unsigned char Status;
/*初始化函数*/
static void * my_memset(void *s,int c,int n)/*初始化*/
{
char *c_s=(char *)s;
while(n--) *c_s++=c;
return s;
}
/*复制函数*/
static void * my_memcpy(void *dest,void *src,unsigned int size)
{
char *b_dest=(char *)dest,*b_src=(char *)src;
unsigned int len;
for(len=size;len>0;len--)
{
*b_dest++=*b_src++;
}
return dest;
}
/*函数行为表*/
struct hashmenu_vtbl;
/*
选项位置使用说明：pos赋值为相应的格式的内容即可访问相应节点的内容
1 表示一级选项的第一个
2.2，二级选的下一级子选项的第二个
1.1.1表示一级选的下一级子选项的第一个，
*/
typedef struct
{
char pos[HASH_SKEY_LEN]; /*选项位置也是关键字*/
char explain[MAX_EXPLAIN]; /*选项说明*/
void (*gui)(void *parameter);/*选项GUI更新函数*/
void (*act)(void *parameter);/*选项动作函数*/
void (*default_act)(void *parameter);/*选项默认动作，执行上下左右切换界面后默认执行*/
}hashmenu_member; /*每个成员的属性*/
/*哈希表构成菜单*/
typedef struct
{
hashmenu_member hashtable[HASH_SIZE]; /*哈希表*/
struct hashmenu_vtbl *c_vptr;/*哈希表行为函数指针*/
int hash_table_size; //哈希表关键字的数量
}hashmenu;/*表头*/
/*函数行为表*/
struct hashmenu_vtbl
{
Status (*insert)(hashmenu * const Me,hashmenu_member *const member); /*添加选项*/
Status (*remove)(hashmenu * const Me,hashmenu_member * const member); /*删除选项*/
Status (*modify)(hashmenu * const Me,hashmenu_member * const member); /*设置选项*/
Status (*search)(hashmenu * const Me,hashmenu_member * const member); /*查找选项*/
/*找到上下左右选项*/
Status (*searchleft)(hashmenu * const Me,hashmenu_member * const member); /*查找当前节点左选项*/
Status (*searchright)(hashmenu * const Me,hashmenu_member * const member); /*查找当前节点右选项*/
Status (*searchup)(hashmenu * const Me,hashmenu_member * const member); /*查找当前节点上一个选项*/
Status (*searchdown)(hashmenu * const Me,hashmenu_member * const member); /*查找当前节点下一个选项*/
};
/*仅留创建和删除接口留给其他文件进行访问*/
void HashMenuCreate(hashmenu * const Me);
void HashMenuDelete(hashmenu * const Me);
/*增删改查接口*/
static Status HashOpenInser(hashmenu * const Me,hashmenu_member *const member);
static Status HashOpenRemove(hashmenu * const Me,hashmenu_member * const member);
static Status HashOpenSearch(hashmenu * const Me,hashmenu_member * const member);
static Status HashOpenModify(hashmenu * const Me,hashmenu_member * const member);
/*菜单切换接口*/
static Status HashMenuPeerLeft(hashmenu * const Me,hashmenu_member * const member);/*找到当前节点同级的选项*/
static Status HashMenuPeerRight(hashmenu * const Me,hashmenu_member * const member);/*找到当前节点下一级的选项*/
static Status HashMenuDepthUp(hashmenu * const Me,hashmenu_member * const member);/*找到当前节点下一级的选项*/
static Status HashMenuDepthDown(hashmenu * const Me,hashmenu_member * const member);/*找到当前节点下一级的选项*/
/*去符号化哈希表*/
static uint16_t HashOpenKey(const char* skey)
{
char *p = (char*)skey;
uint16_t hasy_key = 0;
if(*p)
{
for(;*p != '\0'; ++p)
hasy_key = (hasy_key << 5) - hasy_key + *p;
}
return hasy_key%(HASH_SIZE-1);
}
/*找到唯一的哈希值*/
static uint16_t HashOpenFindUniqueKey(hashmenu * const Me,hashmenu_member *const member)
{
uint16_t unique_addr;
int cout=HASH_SIZE;
uint16_t clen;
if(Me->hash_table_size<=0) return HASH_ERROR;
unique_addr=HashOpenKey(member->pos);
/*根据内容查看哈希值是不是指向需要的地址*/
clen=strlen(member->pos);
clen = (clen >HASH_SKEY_LEN) ?HASH_SKEY_LEN:clen;
while((strncmp(Me->hashtable[unique_addr].pos,member->pos,clen)!=0)&&cout--)
{
unique_addr=(unique_addr+1)%HASH_SIZE; /*开放地址法则线性探测*/
}
if(cout<0) return HASH_ERROR;/*遍历完这个哈希表都没有找到*/
return unique_addr;
}
/*创建哈希表*/
void HashMenuCreate(hashmenu * const Me)
{
int i;
static struct hashmenu_vtbl vtable;
Me->hash_table_size=0;
my_memset(Me, 0, sizeof(hashmenu));
vtable.insert=&HashOpenInser;
vtable.remove=&HashOpenRemove;
vtable.modify=&HashOpenModify;
vtable.search=&HashOpenSearch;
vtable.searchleft=&HashMenuPeerLeft;
vtable.searchright=&HashMenuPeerRight;
vtable.searchup=&HashMenuDepthUp;
vtable.searchdown=&HashMenuDepthDown;
Me->c_vptr=&vtable;
}
/*删除哈希表*/
void HashMenuDelete(hashmenu * const Me)
{
int i;
my_memset(Me, 0, sizeof(hashmenu));
}
/*增*/
Status HashOpenInser(hashmenu * const Me,hashmenu_member *const member)
{
uint16_t addr;
if(Me->hash_table_size>=HASH_SIZE) return HASH_ERROR;
addr=HashOpenKey(member->pos);
/*开放地址法则线性探测解决冲突*/
while(Me->hashtable[addr].explain[0]!=HASH_NULLKEY)
addr=(addr+1)%HASH_SIZE;
/*插入数据*/
my_memcpy(&(Me->hashtable[addr]),member,sizeof(hashmenu_member));
Me->hash_table_size++;
return HASH_OK;
}
/*删*/
Status HashOpenRemove(hashmenu * const Me,hashmenu_member * const member)
{
uint16_t addr;
addr=HashOpenFindUniqueKey(Me,member);
if(addr)
{
my_memset(&(Me->hashtable[addr]),0,sizeof(hashmenu_member));
Me->hash_table_size--;
return HASH_OK;
}
else return HASH_ERROR;
return HASH_OK;
}
/*查*/
Status HashOpenSearch(hashmenu * const Me,hashmenu_member * const member)
{
uint16_t addr;
addr=HashOpenFindUniqueKey(Me,member);
if(addr!=HASH_ERROR)
{
my_memcpy(member,&(Me->hashtable[addr]),sizeof(hashmenu_member));
return HASH_OK;
}
else return HASH_ERROR;
return HASH_OK;
}
/*改*/
Status HashOpenModify(hashmenu * const Me,hashmenu_member * const member)
{
uint16_t addr;
addr=HashOpenFindUniqueKey(Me,member);
if(addr)
{
my_memcpy(&(Me->hashtable[addr]),member,sizeof(hashmenu_member));
return HASH_OK;
}
else return HASH_ERROR;
return HASH_OK;
}
/*找到当前节点同级的左选项*/
/*例如：当前pos="1.1.2"，左选项节点就是pos="1.1.1"*/
static Status HashMenuPeerLeft(hashmenu * const Me,hashmenu_member * const member)
{
uint8_t *c_pos=(uint8_t *)member->pos;
uint8_t t_chang;
Status flag;
if(Me->hash_table_size<=0) return HASH_ERROR;
while(*++c_pos!='\0');/*找到位置最后的位置*/
t_chang=*(--c_pos)-1;/*将最后位置的上一个字符值-1*/
*c_pos=t_chang;
flag=Me->c_vptr->search(Me,member);
if(flag!=HASH_ERROR) return HASH_OK;
else
{
/*重新指向先前内容*/
t_chang=(*c_pos)+1;
*c_pos=t_chang;
Me->c_vptr->search(Me,member);
}
/*执行默认函数*/
member->default_act(NULL);
return HASH_OK;
}
/*找到当前节点同级的右选项*/
/*例如：当前pos="1.1.2"，右选项节点就是pos="1.1.3"*/
static Status HashMenuPeerRight(hashmenu * const Me,hashmenu_member * const member)
{
uint8_t *c_pos=(uint8_t *)member->pos;
uint8_t t_chang;
Status flag;
if(Me->hash_table_size<=0) return HASH_ERROR;
while(*++c_pos!='\0');/*找到位置最后的位置*/
t_chang=*(--c_pos)+1;/*将最后位置的上一个字符值-1*/
*c_pos=t_chang;
flag=Me->c_vptr->search(Me,member);
if(flag!=HASH_ERROR) return HASH_OK;
else
{
/*重新指向先前内容*/
t_chang=(*c_pos)-1;
*c_pos=t_chang;
Me->c_vptr->search(Me,member);
}
/*执行默认函数*/
member->default_act(NULL);
return HASH_OK;
}
/*找到当前节点下一级的选项*/
/*例如：当前pos="1.1"，下一级的选项节点就是pos="1.1.1"*/
static Status HashMenuDepthDown(hashmenu * const Me,hashmenu_member * const member)
{
uint8_t *c_pos=(uint8_t *)member->pos;
Status flag;
uint16_t clen;
if(Me->hash_table_size<=0) return HASH_ERROR;
clen=strlen(member->pos);
if(clen>=HASH_SKEY_LEN-3) return HASH_ERROR; /*避免内存越界*/
while(*++c_pos!='\0');/*找到位置最后的位置*/
*c_pos='.';
*(c_pos+1)='1';
*(c_pos+2)='\0';
flag=Me->c_vptr->search(Me,member);
if(flag!=HASH_ERROR) return HASH_OK;
else
{
/*重新指向先前内容*/
*c_pos='\0';
*(c_pos+1)='\0';
*(c_pos+2)='\0';
Me->c_vptr->search(Me,member);
}
/*执行默认函数*/
member->default_act(NULL);
return HASH_OK;
}
/*找到当前节点上一级的选项*/
/*例如：当前pos="1.1"，上一级的选项节点就是pos="1"*/
static Status HashMenuDepthUp(hashmenu * const Me,hashmenu_member * const member)
{
uint8_t *c_pos=(uint8_t *)member->pos;
uint8_t last_pos;/*保存上次数字*/
Status flag;
uint16_t clen;
if(Me->hash_table_size<=0) return HASH_ERROR;
clen=strlen(member->pos);
if(clen<=1) /*避免内存越界*/
{
Me->c_vptr->search(Me,member);
return HASH_OK;
}
while(*++c_pos!='\0');/*找到位置最后的位置*/
last_pos=*(c_pos-1);/*保存数字*/
*(c_pos-1)='\0';/*.1，删除数字*/
*(c_pos-2)='\0';/*.，删除点*/
flag=Me->c_vptr->search(Me,member);
if(flag!=HASH_ERROR) return HASH_OK;
else
{
/*重新指向先前内容*/
*(c_pos-1)=last_pos;
*(c_pos-2)='.';
Me->c_vptr->search(Me,member);
}
/*执行默认函数*/
member->default_act(NULL);
return HASH_OK;
}
/*打印成员信息*/
void PrintMember(hashmenu_member member)
{
printf("pos=%s\r\n",member.pos);
}
/*打印哈希表所有内容*/
void HashOpenPrint(hashmenu const * const Me)
{
for(int i=0;i<HASH_SIZE;i++)
{
if(Me->hashtable[i].explain[0]!=HASH_NULLKEY)
{
printf("key is %s explain = %s\n",Me->hashtable[i].pos,Me->hashtable[i].explain);
}
}
}
/*测试GUI*/
void GUI_1(void *parameter)
{
printf("--------------- -GUI 123--------------\r\n");
printf("---------------->OPTION 1<-------------\r\n");
printf("-----------------OPTION 2-------------\r\n");
printf("-----------------OPTION 3-------------\r\n");
}
void GUI_2(void *parameter)
{
printf("--------------- -GUI 123--------------\r\n");
printf("-----------------OPTION 1-------------\r\n");
printf("---------------->OPTION 2<------------\r\n");
printf("-----------------OPTION 3-------------\r\n");
}
void GUI_3(void *parameter)
{
printf("--------------- -GUI 123--------------\r\n");
printf("-----------------OPTION 1-------------\r\n");
printf("-----------------OPTION 2-------------\r\n");
printf("---------------->OPTION 3<------------\r\n");
}
void GUI_1_1(void *parameter)
{
printf("------------------GUI 1_1-------------\r\n");
printf("---------------->OPTION 1.1<------------\r\n");
printf("-----------------OPTION 1.2-------------\r\n");
printf("-----------------OPTION 1.3------------\r\n");
}
void GUI_1_2(void *parameter)
{
printf("------------------GUI 1_1-------------\r\n");
printf("-----------------OPTION 1.1-------------\r\n");
printf("---------------->OPTION 1.2<------------\r\n");
printf("-----------------OPTION 1.3------------\r\n");
}
void GUI_1_3(void *parameter)
{
printf("------------------GUI 1_1-------------\r\n");
printf("-----------------OPTION 1.1-------------\r\n");
printf("-----------------OPTION 1.2-------------\r\n");
printf("---------------->OPTION 1.3<------------\r\n");
}
/*测试功能函数*/
void func1(void *num)
{
hashmenu_member *mem=(hashmenu_member *)num;
printf("mem->explain =%s\r\n",mem->explain);
}
#define UP 'w'
#define DOWM 's'
#define LEFT 'a'
#define RIGHT 'd'
#define ENTER 'e'
#define QUIT 'q'
hashmenu tmenu;
void test()
{
hashmenu_member t_member;
hashmenu_member d_member;
int x=1;
char choice;
/*创建哈希表*/
HashMenuCreate(&tmenu);
/*输入内容，插入哈希表*/
t_member.act=func1;
t_member.gui=GUI_1;
strcpy(t_member.pos,"1");
strcpy(t_member.explain,"1 EXPLAIN\r\n");
tmenu.c_vptr->insert(&tmenu,&t_member);
PrintMember(t_member);
t_member.act=func1;
t_member.gui=GUI_2;
strcpy(t_member.pos,"2");
strcpy(t_member.explain,"2 EXPLAIN\r\n");
tmenu.c_vptr->insert(&tmenu,&t_member);
PrintMember(t_member);
strcpy(t_member.pos,"3");
t_member.gui=GUI_3;
t_member.act=func1;
strcpy(t_member.explain,"3 EXPLAIN\r\n");
tmenu.c_vptr->insert(&tmenu,&t_member);
PrintMember(t_member);
t_member.act=func1;
t_member.gui=GUI_1_1;
strcpy(t_member.pos,"1.1");
strcpy(t_member.explain,"1.1 EXPLAIN\r\n");
tmenu.c_vptr->insert(&tmenu,&t_member);
PrintMember(t_member);
t_member.gui=GUI_1_2;
t_member.act=func1;
strcpy(t_member.pos,"1.2");
strcpy(t_member.explain,"1.2 EXPLAIN\r\n");
tmenu.c_vptr->insert(&tmenu,&t_member);
PrintMember(t_member);
t_member.gui=GUI_1_3;
t_member.act=func1;
strcpy(t_member.pos,"1.3");
strcpy(t_member.explain,"1.3 EXPLAIN\r\n");
tmenu.c_vptr->insert(&tmenu,&t_member);
PrintMember(t_member);
strcpy(t_member.pos,"2.1");
strcpy(t_member.explain,"2.1 EXPLAIN\r\n");
tmenu.c_vptr->insert(&tmenu,&t_member);
t_member.act=func1;
PrintMember(t_member);
strcpy(t_member.pos,"2.2");
strcpy(t_member.explain,"2.2 EXPLAIN\r\n");
tmenu.c_vptr->insert(&tmenu,&t_member);
t_member.act=func1;
PrintMember(t_member);
strcpy(t_member.pos,"3.1");
strcpy(t_member.explain,"2.1 EXPLAIN\r\n");
tmenu.c_vptr->insert(&tmenu,&t_member);
t_member.act=func1;
PrintMember(t_member);
strcpy(t_member.pos,"3.2");
strcpy(t_member.explain,"2.2 EXPLAIN\r\n");
tmenu.c_vptr->insert(&tmenu,&t_member);
t_member.act=func1;
PrintMember(t_member);
strcpy(t_member.pos,"1.1.1");
strcpy(t_member.explain,"1.1.1 EXPLAIN\r\n");
tmenu.c_vptr->insert(&tmenu,&t_member);
PrintMember(t_member);
t_member.act=func1;
strcpy(t_member.pos,"1.1.2");
strcpy(t_member.explain,"1.1.2 EXPLAIN\r\n");
tmenu.c_vptr->insert(&tmenu,&t_member);
PrintMember(t_member);
t_member.act=func1;
strcpy(t_member.pos,"1.1.3");
strcpy(t_member.explain,"1.1.3 EXPLAIN\r\n");
tmenu.c_vptr->insert(&tmenu,&t_member);
PrintMember(t_member);
strcpy(t_member.pos,"2.1.1");
strcpy(t_member.explain,"2.1.1 EXPLAIN\r\n");
tmenu.c_vptr->insert(&tmenu,&t_member);
t_member.act=func1;
PrintMember(t_member);
strcpy(t_member.pos,"2.2.1");
strcpy(t_member.explain,"2.2.1 EXPLAIN\r\n");
tmenu.c_vptr->insert(&tmenu,&t_member);
t_member.act=func1;
PrintMember(t_member);
strcpy(t_member.pos,"3.1.1");
strcpy(t_member.explain,"3.1.1 EXPLAIN\r\n");
tmenu.c_vptr->insert(&tmenu,&t_member);
PrintMember(t_member);
t_member.act=func1;
strcpy(t_member.pos,"3.1.2");
strcpy(t_member.explain,"3.1.2 EXPLAIN\r\n");
tmenu.c_vptr->insert(&tmenu,&t_member);
PrintMember(t_member);
t_member.act=func1;
strcpy(t_member.pos,"3.1.3");
strcpy(t_member.explain,"3.1.3 EXPLAIN\r\n");
tmenu.c_vptr->insert(&tmenu,&t_member);
PrintMember(t_member);
HashOpenPrint(&tmenu);
printf("--------------------------------------\r\n");
strcpy(d_member.pos,"1");
tmenu.c_vptr->search(&tmenu,&d_member);
PrintMember(d_member);
while(choice!=QUIT)
{
/*模拟按键或者串口输入*/
scanf("%c",&choice);
/*根据输入执行动作*/
switch (choice)
{
case UP:
if(tmenu.c_vptr->searchup(&tmenu,&d_member)!=HASH_ERROR) d_member.act(&d_member);;
break;
case DOWM:
if(tmenu.c_vptr->searchdown(&tmenu,&d_member)!=HASH_ERROR) d_member.act(&d_member);
break;
case LEFT:
if(tmenu.c_vptr->searchleft(&tmenu,&d_member)!=HASH_ERROR) d_member.act(&d_member);
break;
case RIGHT:
if(tmenu.c_vptr->searchright(&tmenu,&d_member)!=HASH_ERROR) d_member.act(&d_member);
break;
case ENTER:
d_member.act(&d_member);
break;
default:
break;
}
/*根据查询内容更新GUI*/
if(choice!='\n') d_member.gui(NULL);
}
}
int main()
{
test();
return 0;
}
5.PS
其实文章的结构和我写的代码定义的位置是差不多一样的，可以翻上去看看。