ITPub博客

首页 > 应用开发 > IT综合 > 数据结构学习(C++)——树(总结) (转)

数据结构学习(C++)——树(总结) (转)

原创 IT综合 作者:amyz 时间:2007-11-13 12:32:53 0 删除 编辑
数据结构学习(C++)——树(总结) (转)[@more@]

才刚开了个头,就要说再见了——在树这里,除了二叉树,别的都还没有讲。为什么可以总结了呢?因为前面已经涉及到了树的两个基本用途,而如果再讲B+、B-,就不能不提到搜索,如果是胜者树就不能不提到排序。为此,把这部分放到后面。我前面所做的努力,只是让你有个基本概念,什么时候记得用树。

树的两个基本用途,可以用物质和精神来比喻。

一个用途是做为数据储存,储存具有树结构的数据——目录、族谱等等。为了在实际上是线性的储存载体上(内存磁盘)储存非线性的树结构,必须有标志指示出树的结构。因此,只要能区分根和子树,树可以采取各种方法来储存——多叉链表、左子女-右兄弟二叉链表、广义表、多维数组。由于操作的需求,储存方法并不是随意选取的。比如,在并查集的实现上,选取的是双亲链表。

一个用途是做为逻辑判断,此时会常常听到一个名词——判定树。最常用的结构是二叉树,一个孩子代表true,一个孩子代表false。关于多叉判定树,有个例子是求8皇后的全部解——这个连高斯都算错了(一共是92组解,高斯最开始说76组解),我们比不上高斯,但是我们会让computer代劳。

就像哲学界到现在还纠缠于物质和精神本源问题,实际上在树这里也是如此。有些情况下,并不能区分是做为储存来用还是做为判断来用,比如搜索树,既储存了数据,还蕴涵着判断。

和后面的图相比,树更基本,也更常用。你可以不知道最短路径怎么求,却每时每刻都在和树打交道——看看你电脑里的文件夹吧。

最后,附带一个求N皇后的全部解的程序

#include

#define N 8

int layout[N];//布局

int key = 0;

int judge(int row, int col)//判断能否在(row,col)放下

{

  int i;

  for (i = 0; i < row; i++)

  {

  if (layout[i] == col) return 0;//同一列

  if (i - layout[i] == row - col) return 0;//同一条主对角线

  if (i + layout[i] == row + col) return 0;//同一条副对角线

  }

  return 1;

}

void lay(int row)//在row行上放Queen

{

  int i;

  if (row == N)//放完N个Queen输出布局

  {

    printf("n%02d ", ++key);

    for (i = 0; i < N; i++) printf("%c%d ", layout[i] + 'a', i + 1);

  }

  else

  {

    for (i = 0; i < N; i++)//在i列上放Queen

  {

    layout[row] = i;

    if (judge(row, i)) lay(row + 1);

  }

  }

}

 XML:namespace prefix = o ns = "urn:schemas-microsoft-com:Office:office" />

int main()

{

  lay(0);

  return 0;

}


来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/10752019/viewspace-982143/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论
  • 博文量
    3984
  • 访问量
    7335573