我们清楚:数据库设计中,表结构设计的好坏,直接影响程序的复杂度。所以,本文就无限级分类(目录)树与链表的复合在表设计中的应用进行探讨。当然,什么是树,什么是链表,这里不作介绍。有兴趣可以去看相关的教材。
需求简介:
经常遇到这样的需求,我们希望能将保存在数据库中的树结构能够按确定的顺序读出来。比如,多级菜单、组织结构、商品分类。更具体的,我们希望某个二级菜单在这一级别中就是第一个。虽然它是最后插入的。或者,我们希望这个商品小类在其父类下也是第一个,以使可以网上促销……
实现方式:
关于在数据库中保存树型结构并不复杂,一般,我们只要保存当前记录在谁下面,所以,给定一个parent_id(父节点ID)字段就可以了。
以mysql为例,我们只要使用inner join,就能一次性查出无限级的树的数据。
一般而言,我们在设计中会增加以下一些字段,以增强数据的可操作性:
path:以逗号分隔的ID字串,标明了从顶级到本节点的path,
比如:3,34,257 :那说明,本节点的parent_id是257,257的parent_id是34,34的parent_id是3。
使用path的好处:可以使用在sql语句中使用like直接查出某节点下的所有子孙节点。
level:层级,表明此节点是第几层节点。当然,我们完全可以从path中的逗号看出此节点是第几层,但有了层级这个数据,将会给程序操作树偍供很大的方便。
is_leaf:是否叶节点,这也是为程序渲染界面,以及程序中控制所用的。
sort_no: 排序编号。这是我们经常需要的,并且也是最难维护的。它的目的是维护树中每一节点的正常顺序。有多种方案。一般有,直接使用整数的方案,以及对树进行编码的方案。
直接使用整数,好处是排序速度快。问题在于,维护连续整数的sort_no较为复杂。
比如,当我们插入一个节点,我们要将其节点后的所有节点的sort_no全部加1。
当我们移动一个节点,我们则要判断是前移,还是后移。
如果前移,则要将新位置到当前位置的节点的sort_no全部加1,如果是后移,则要将新位置到当前位置的节点的sort_no全部减1。
对树进行编码的方案,好处是,每次只对局部操作。编码可以不连续。比如一个节点从父节点3移动父节点7下面,则只要操作父节点7下面的记录。如果在新的父节点下只是追加,则不需要变更所有sort_no。但是,基于编码的解决方案虽有这些优点,也有明显的缺点。那就是,我们有时无法预知树的层级数量,以及每一层的节点数。
比如,如果我们预估每一层是100个节点,那最多是两位编码足够了,但一旦节点数超标,则编码方案就得调整。
链表算法:
针对这一问题,最完美的解决方案是引入链表算法。即sort_no仍使用整数。同时为每一个节点增加链表的before指针,或next指针,或者before、next指针二者均加上。
理论上,单向链表即可以支持插入操作了。所以,本例中,我们只增加before指针,指明,它的前一个节点是谁。
但是,我们无法能够根据before指针更新其排序码。所以,我们需要根据排序码来更新before和next。所以,我们要对排序码算法作进一步优化。
遥遥相对取的方式是:使用奇数序列或偶数序列作为排序码。那么,我们即可以在任一两节点间插入。插入后再作更新。
总结下来,我们的表结构如下:
id: 记录的id(可使用mysql自增字段)
parent_id: 父节点ID
path: 基于逗号分隔的ID完整路径
level: 层级,标明节点是第几层
is_leaf: 是否叶节点 (默认为1, 即叶节点)
sort_no: 排序编号
before_id 前一节点的id
假如此表是一个商品分类表,那么,表名称是prd_catagory
我们增加一个业务数据字段:cat_name 分类名称。
接下来,就看我们sql算法是不是非常简单了。
无论插入,更新(移动或不移动)还是删除,我们可用以下SQL重新更新排序码:
SET @var =0;
UPDATE t1 a,
(
SELECT t1.id,tq.sort_no,@var:=@var+2 AS new_sort_no
FROM t1
ORDER BY t1.sort_no
) b
SET a.sort_no=b.new_sort_no
WHERE a.id = b.id;
由此,我们通过链表结构维护了树结构中的基于公差为2的整数序列的排序码。
有一点比较好的是:我们根据其排序码,可以相当方便地维护before和next.
只要再加一两条SQL语句即可。
所以,当我们要完整示树结构时,我们的SQL查询只要是
select id, parent_id, path, level, is_leaf, sort_no, before_id from prd_catagory orderby sort_no
即可,非常简单吧。你的程序中只要用单层for循环顺序读取记录集即可。
查出某个节点下的所有子孙节点
select id, parent_id, path, level, is_leaf from prd_catagory where path like :path orderby sort_no.
查出某个节点下的所有叶节点或非叶点
select id, parent_id, path, level, is_leaf from prd_catagory where parent_id = :parent_id and is_leaf=:is_leaf orderby sort_no.
查出所有同一级别的叶节点或非叶点
select id, parent_id, path, level, is_leaf from prd_catagory where level = :level and is_leaf=:is_leaf orderby sort_no.
好了。这个基于链表算法的无限级分类树的设计已经完成了。不知你还有什么改进意见。
相关推荐
本资源“数据结构——使用C语言”提供了一套经典的学习材料,帮助读者深入理解数据结构并掌握其在C语言中的实现。 首先,我们要了解数据结构的基本类型,包括数组、链表、栈、队列、树和图。数组是最基本的数据结构...
3.5.4 字符数据在内存中的存储形式及使用方法 41 3.5.5 字符串常量 41 3.5.6 符号常量 42 3.6 变量赋初值 42 3.7 各类数值型数据之间的混合运算 43 3.8 算术运算符和算术表达式 44 3.8.1 C运算符简介 44 3.8.2 算术...
而"数据结构与算法中的‘递归’——用回溯法求解8皇后问题.wps"则可能是通过8皇后问题的实例来探讨递归和回溯法的实际运用。 总的来说,学好C语言和数据结构需要理论与实践相结合,不断练习编程,理解并熟练运用...
例如,使用文件操作功能来保存和加载学生数据,或者利用链表、树等数据结构来动态管理学生和课程的信息。这将涉及到文件I/O、指针以及更复杂的数据结构知识。 在实际开发过程中,良好的编程习惯和错误处理也是必不...
3.5.4 字符数据在内存中的存储形式及使用方法 41 3.5.5 字符串常量 41 3.5.6 符号常量 42 3.6 变量赋初值 42 3.7 各类数值型数据之间的混合运算 43 3.8 算术运算符和算术表达式 44 3.8.1 C运算符简介 44 3.8.2 算术...
在这个文档“数据结构-3期(KC002) 结构体简单应用.docx”中,我们探讨的是C语言中的一个关键概念——结构体(struct)及其应用。结构体允许我们将相关的数据项组合成一个单一的实体,便于管理和操作。以下是对这个...
这里可能会用到链表或数组等数据结构来存储待预约的挂号信息,包括患者姓名、联系方式、预约时间等。同时,可能需要设计一个查询界面,让患者能根据医生信息、科室或时间查找合适的挂号。这需要掌握C语言中的输入...
结构体在C++中非常有用,可以用于组织复杂的数据结构,如链表、树或其他自定义的数据结构。结构体变量可以通过点运算符`.`来访问其成员,如`student1.num`访问学号,`student1.name`访问姓名等。 此外,结构体还...
综上所述,本项目虽然未使用链表这种更灵活的数据结构,但通过结构体数组实现学生通信录的基本功能,仍展示了数据结构在实际问题中的应用。结构体数组简化了数据表示,而数组操作则实现了通信录的核心功能。不过,...
游戏的实现可能包括用户界面、算法逻辑、数据结构(如链表、数组)等元素,这些都是学习C++的好实践。 7. **实例解析**:书中通过逐步解析Dcryptix游戏的代码,帮助读者理解和运用所学知识。这将涉及到如何设计游戏...
### 数据结构与算法分析——Java语言描述_第2版无密码 #### 一、Java与面向对象程序设计 本章节主要介绍了Java语言的基础知识以及其面向对象的特点。 **1.1 Java语言基础知识** - **1.1.1 基本数据类型及运算** ...
10. **数据结构(Data Structures)**:虽然C语言没有内置的高级数据结构,但开发者可以使用数组、链表或其他自定义结构来实现。在这个案例中,通讯录条目可能会被组织成某种形式的列表,以便于遍历和管理。 总的来...
本报告将围绕C语言在销售管理与设计程序管理中的应用进行深入探讨,旨在通过实例——学生信息管理系统和商品销售管理,解析C语言在数据结构、控制逻辑和程序设计上的核心知识。 首先,学生信息管理系统是运用C语言...
CS(计算机科学)知识体系 ...6. 编写使用以下各种数据结构的程序:数组、记录、字符串、链表、栈、队列和哈希表。 7. 比较并说明动态和静态数据结构实现的代价和收益的不同。 8. 为指定问题的建模选择适当的数据结构。
在C程序中,结构体常用于表示复杂的数据结构,如链表、树、图等。 6. **文件操作** C语言提供了标准输入输出流(stdio)库,可以进行文件的读写操作。通过文件指针,你可以读取、写入文本或二进制文件,这对于数据...
学习如何定义和使用它们,可以让你创建更复杂的数据结构,如链表、树等。 最后,不要忽视错误处理和调试技巧。学会使用printf进行输出调试,理解编译器的错误信息,以及如何使用调试工具,这些都将使你在解决问题时...
本话题聚焦于一个具体的实例——停车场管理系统,该系统的设计与实现充分利用了C语言和数据结构的知识。通过对这个案例的深入探讨,我们可以了解如何将理论知识应用于实际问题的解决。 首先,我们要理解“数据结构...
链表是另一种重要的数据结构,它在内存中不连续存储,而是通过指针链接各个元素。虽然实验没有直接涉及链表,但在实际编程中,链表常用于动态数据存储,如添加、删除和查找元素,特别是在数据量不确定或需要高效插入...