我也想热闹，可是对手被吓跑了, 前面还气势汹汹的。
我只好孤零零的一个人给大家表演一段，以对得起大家的捧场。
构造一棵抽象的树，最好使用动态数组或者链表，或者二者组合。这对于没有内存管理的编程环境无疑很痛苦。嵌入式的内存空间往往分为code (ROM) 和 data (RAM), 程序员这时必须考虑一个现实，数据如何存放。可以把数据和管理者tree 都放入ROM 里，形成一棵石化树；也可以把数据放入 ROM 里，而把数据管理者tee枝干放入RAM 里。PC 下，动态数组或者链表里只是包含一串指针，这样可以实现动态的变更数据的组织结构。
假设一个简单MenuItem 的结构：
struct MenuItem
{
int id;
char* name;
};
下面的两种定义方式，可以体现出程序员对待MenuItem数据的考量，这些以后再讲。
MenuItem menu[];
MenuItem* menu[];
如何产生一棵石化树呢，看看下面的struct：
struct MenuItem
{
int id;
char* name;
struct MenuItem* subMenu;
int subMenuCount;
};
说穿了，很简单，就是每个子项下面放置一个自身指针(或者是指针的指针)，指针指向一个MenuItem集合，这里的集合将是一个数组，并记录数组的尺寸。数组的尺寸可以用一个宏来计算：
#define ARRAYSIZE(a) (sizeof(a) / sizeof(a[0]))
C++ 下，一棵tree 往往分为节点，节点集合以及修剪工几个部分以实现更为复杂的数据操纵以及方便未来的扩展（一棵抽象的树必须有足够的适应性和可扩展性）。而这里，用单一的一个结构来实现一棵树，更容易理解，而且C 的函数与C++的成员函数不同，数据和代码是分离的。
首先，定义两个“小小叶子“：
MenuItem menu1[] =
{
{1, "1", NULL, 0},
{2, "2", NULL, 0}
};
MenuItem menu2[] =
{
{3, "3", NULL, 0},
{4, "4", NULL, 0}
};
再定义一个圈圈, 把小小叶子 放进去：
MenuItem OO[] =
{
{5, "5", menu1, ARRAYCOUNT(menu1)},
{6, "6", menu2, ARRAYCOUNT(menu2)}
};
最后，根：
MenuItem root =
{
0, "root", OO, ARRAYCOUNT(OO)
};
以此类推，可以 形成一棵枝叶繁茂的大树。
既然MenuItem 包含一个MenuItem 的集合，那么可以理直气壮的使用递归。事实上，递归是处理 tree 上最常见的方法。递归使得代码异常简洁，虽然会在效率上，以及在嵌入式cpu上要当心stack overflow/overwrite.
例如，遍历显示所有MenuItem ：
void DisplayMenuItems(MenuItem* pMenu)
{
int i;
printf("ID: %d, Name: %s
", pMenu->id, pMenu->name);
for (i=0; i<pMenu->subMenuCount; i++) {
DisplayMenuItems(&pMenu->subMenu);
}
}
运行函数， DisplayMenuItems(&root) 的结果：
ID: 0, Name: root
ID: 5, Name: 5
ID: 1, Name: 1
ID: 2, Name: 2
ID: 6, Name: 6
ID: 3, Name: 3
ID: 4, Name: 4
明天继续 .......
|
|
楼主
