我需要构建一个数据结构来表示文件中存在的类的继承图。这是为仅支持单一继承的语言编写编译器的一部分。
存在的所有类的名称都存储在一个链表中。我需要遍历该列表并从中构建一个继承图。 然后我需要检查继承是否有循环,例如 如果
B inherits A
C inherits B
然后
A cannot inherit C.
像这样的循环在语言中是不允许的。
什么数据结构最适合这个?
最佳答案
在单一继承约束下,您的图形是一个森林,即一组树。您的问题在文献中被称为图中的循环检测 http://en.wikipedia.org/wiki/Cycle_%28graph_theory%29#Cycle_detection
关于表示单继承的 C++ 数据结构,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30153950/