企业网站管理系统如何使用说明,品牌网站的愿望清单怎么做,项目经理证书怎么考,网站开发优惠活动方案不同类型的链表 专栏内容#xff1a; postgresql使用入门基础手写数据库toadb并发编程 个人主页#xff1a;我的主页 管理社区#xff1a;开源数据库 座右铭#xff1a;天行健#xff0c;君子以自强不息#xff1b;地势坤#xff0c;君子以厚德载物. 文章目录 不同类型…不同类型的链表 专栏内容 postgresql使用入门基础手写数据库toadb并发编程 个人主页我的主页 管理社区开源数据库 座右铭天行健君子以自强不息地势坤君子以厚德载物. 文章目录 不同类型的链表概述 1. 数据类型识别 1.1 TLV格式介绍 1.2 结构体分层定义 1.3 定义抽象数据类型 2. 链表定义 2.1 数据节点定义 2.2 链表类型定义 节点解析 链表遍历 多级树链表 总结 结尾 概述 在实际使用中会存在不同的数据类型有基本类型有自定义的结构体的复杂类型。
当这么丰富的数据出现时只能记录到动态扩展的链表中同时还能够查找并按正确的类型取出。
本节就来介绍在同一个链表中如何记录如此丰富的数据资源分别从
数据类型识别;链表的定义;节点解析;链表遍历 四个方面来展开介绍。 1. 数据类型识别 要识别出不同的数据类型这里介绍一种数据结构的定义格式TLV。 1.1 TLV格式介绍
TLVtag-length-value是一种用于以结构化方式表示数据的二进制格式。TLV在计算机网络协议、智能卡应用以及其他数据交换场景中经常被使用。TLV由以下三部分组成 标签Tag唯一标识数据的类型。它通常是一个单字节或一小段字节序列, 可以是不同bit代表不同含义也可以是整体表示序列。 长度Length数据字段的字节长度。在某些协议中标签和长度字段的长度也会被包含在内。 值Value实际传输的数据可以是任何类型或格式。 这种格式通过明确区分数据的类型、长度和具体内容使得数据的解析和处理变得更加清晰和高效。 1.2 结构体分层定义
首先定义复合类型一般使用枚举类型进行定义。
在手写数据库toadb的src/sqlcore/node/nodeType.h文件中就有用到这种定义。
这里举例定义如下
typedef enum NodeType
{T_START,/* parser nodes */T_List,T_MANAGER,T_HR,T_EMPLOYEE
}NodeType;然后在各复合类型的结构定中前两个字段采用公共字段。
这里定义经理HR员工三个结构体类型每个人都有一个sno员工号的数据他们的个性化数据有 经理有管理多少个员工HR新入职了多少新员工员工对应的部门经理的工号 typedef struct stManager
{NodeType type;int size;int sno;int employeeNum;
}stManager;typedef struct stHr
{NodeType type;int size;int sno;int newEmployeesNum;
}stHr;typedef struct stEmployee
{NodeType type;int size;int sno;int partMgr;
}stEmployee;1.3 定义抽象数据类型
自定义的数据结构太多了为了在使用中统一和简化这里定义Node数据类型是对上述数据类型的统称。
/* common type, real size is just by type. */
typedef struct Node
{NodeType type;int size;
}Node;Node数据结构中包含两个公共的字段类型和大小。
这样在参数引用链表节点引用时都可以用这个抽象的类型来代表以上众多的数据类型。
当然有这个抽象结构定义之后ListCell中的数据指针类型可以用Node类型代替而不是之前定义的void。 2. 链表定义 既然是链表肯定采用指针的方式串连起来以往都是定义一种明确的数据类型作为链表的节点。
而面对如此多的数据类型链表节点的结构如何定义呢 2.1 数据节点定义
数据节点中存储真实的数据由链表指针将数据节点串连起来。
它的定义如下
/* tree list cell */
typedef struct ListCell
{void* pValue;struct ListCell *next;
}ListCell;数据类型不确定所以定义为void *;单链表的形式next指向下一个节点 2.2 链表类型定义
部门的结构是一个多层级形式每个层级又是多个员工也是一个链表。
因此数据类型中除了实际意义的数据类型如上面定义的经理HR员工外还需要增加链表的数据类型。
/* tree list node */
typedef struct List
{NodeType type;int size;int length; /* number of ListCell struct */ListCell *head;
}List;链表的数据类型中数据有两个
length 链表中的节点个数head链表头 节点解析 数据的多样性增加了链表节点类型解析工作因为之前采用了统一类型定义所以类型的解析变得简单。
采用统一的接口对类型进行解析, 分发到对应的类型进行处理。
static void ShowNode(Node *n)
{if(NULL n){return;}switch(n-type){case T_List:ShowNodList(n);break;case T_MANAGER:ShowNodManager(n);break;case T_HR:ShowNodHR(n);break;case T_EMPLOYEE:ShowNodEmployee(n);break;default:break;}
}这里定义了一个展示各节点信息的接口根据节点类型再调用各自的接口进行展示。 链表遍历 经过上面的抽象类型之后链表的遍历就非常简单这里以链表的节点的显示为例。
void TravelListCell(List *list)
{ListCell *tmpCell NULL;List *l list;if(NULL l){return;}/* list cell node show */for(tmpCell l-head; tmpCell ! NULL; tmpCell tmpCell-next){Node *node (Node *)(tmpCell-pValue);ShowNode(node);}return;
}说明
传入的是一个List的指针这里会包含一个链表从成员head开始遍历直到链表节点的next为空也就是链尾将链表节点的数据成员转为抽象类型Node *, 传入统一的处理接口 多级树链表 将经理的数据成员增加一项除了下属成员数量外还列出下属的员工信息
typedef struct stManager
{NodeType type;int size;int sno;int employeeNum;Node *employeeList;
}stManager;这里有个特别的地方对于T_List类型的数据内部会递归调用TravelListCell这样就是一个多级链表树。 如同一个公司的组织架构一样顶层由HR高级经理列表组成每个高级经理下属由员工中级经理组成
而中级经理下属由多名员工组成整体组成一个公司的树形组织架构图。
对于T_LIst类型的节点它的显示处理函数如下
void ShowNodList(Node *n)
{if(NULL n)return ;TravelListCell((List *) n);
}其实是深度优先的图递归遍历其它数据节点的显示就相对简单打印成员信息即可这里不再列举。
总结 本文介绍了链表节点为不同数据类型时的处理方法定义了抽象类型后使引用的类型统一同时在遍历树形链表时对于成员仍为链表时采用深度优先的递归遍历。
这种链表在数据库内核中应用比较广泛比如在SQL语法解析时将语法的各子句解析成不同的数据类型而像select子句可以写多个列名该子句内部又以链表形成存储列信息。
结尾 非常感谢大家的支持在浏览的同时别忘了留下您宝贵的评论如果觉得值得鼓励请点赞收藏我会更加努力 作者邮箱studysenllang.onaliyun.com 如有错误或者疏漏欢迎指出互相学习。
注未经同意不得转载
