程序=算法 数据结构,由此不难看出,数据结构在程序设计中具有非常重要的意义。
“数据结构”是计算机及其相关专业极为重要的一门课程,但是目前讲授的内容大多是20世纪70年代前后形成的相对成熟的知识,其已严重滞后于当前科研成果。作者在从事间隙约束模式匹配方面研究的过程中提出了一种新型数据结构——网树结构,其是一种多树根、多双亲的拓展树结构。网树结构在现实生活中也有诸多重要应用,如在描述亲缘关系中,由于我们每个人都有父母双亲,因此采用单双亲的树结构难以描述;若采用多双亲的网树结构进行描述,则更为直观方便。作者与其合作伙伴应用网树结构解决了若干模式匹配(串匹配)问题、序列模式挖掘问题及图论问题,研究成果先后发表在IEEE Transactions on Cybernetics、Science China Information Sciences、Applied Intelligence、Journal of Information Science、《计算机学报》、《软件学报》、《通信学报》等刊物上。
串匹配和树结构都是“数据结构”课程中极为重要的知识。此外,序列模式挖掘是数据挖掘中一种常用的分析和挖掘方法。作者希望将这些研究成果介绍给普通读者,使读者能及时了解相关的国际前沿问题。
本书共5章,第1章介绍网树结构的概念;第2章介绍间隙约束通配符与传统通配符之间的关系,进而对间隙约束模式匹配问题进行分类,在此基础上,介绍几种间隙约束模式匹配问题的求解算法;第3章介绍关联规则挖掘和序列模式挖掘的基本原理,在此基础上,介绍几种间隙约束序列模式挖掘问题的求解算法;第4章介绍几种图问题的求解算法;第5章对网树研究进行总结与展望。第2~4章各自独立,读者可以根据自己的兴趣和时间进行选择性阅读。
本书第1~3章后均有一定数量的习题,可帮助读者巩固所学知识,引导读者做进一步的探索和研究。
本书的出版得到国家自然科学基金项目(项目编号:61976240、61673159、91746209)的资助。本书力图通过大量实例和插图,将许多晦涩难懂的科学前沿问题通俗易懂地呈现给广大读者,使广大读者易于理解相关概念、应用价值和算法的求解原理。
非常感谢对本书做了大量工作的人员,他们是丁薇、范金泉、耿萌、郭磊、户倩、菅博境、江贺、雷荣、李艳、刘茜、刘亚伟、罗岚方、闵帆、任家东、单劲松、沈丛、孙乐、唐志强、仝瑶、王玲玲、王晓慧、王月华、于磊、袁朱、朱昌瑞、朱怀忠、朱兴全。
由于作者水平有限,书中难免存在不妥和疏漏之处,敬请广大读者批评指正。
作 者
2021年8月