数据结构（相关搜索：树形存储结构）

Question

设计一个可实现某单位行政机构管理的查询系统，单位中各级行政机构信息采用合适的树形存储结构存放。每个部门的基本信息包括：部门名称、业务简介、办公电话和办公地址。可以本校的行政机构设置情况为例设计该系统（登录校园网查询本校行政机构基本设置情况）
 设计要求：
该查询系统应包含以下功能：
（1）已知一个部门查询该部门的直接上级部门；
（2）已知一个部门查询它的直接下属部门；
（3）查询一个部门的级别；
（4）查询一个部门的兄弟部门信息；
（5）查询某部门的所有各级别的上级部门信息。

Answer 1

【相关推荐】

• 你可以参考下这个问题的回答, 看看是否对你有帮助, 链接: https://ask.csdn.net/questions/7810261
• 除此之外, 这篇博客: 线程的共享资源和私有资源：全局变量 局部变量 堆 栈中的 全局变量、局部变量、静态全局变量、静态局部变量在内存里的区别以及栈与堆的区别 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

  一、先由程序的内存分配说起，一个完整的C/C++程序在运行时会占用的内存分为几个部分。

  1. 栈（stack）：由编译器自动分配释放，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈。
  2. 堆（heap） ：一般由程序员分配释放， 若程序员不释放，程序结束时可能由OS回收 。注意它与数据结构中的堆是两回事，分配方式倒是类似于链表。malloc和new等操作实际上就是在堆中申请内存，对象使用完后要手动释放，否则只能等待程序结束时由系统回收，会产生内存泄漏。
  3. 全局区（静态区）（static）：全局变量和静态变量是存储在一起的，初始化过的全局变量和静态变量在同一块区域，未初始化的全局变量和静态变量存放在一块相邻的区域内。此区域由系统在程序结束后释放。
  4. 文字常量区：常量字符串存放于此，在程序结束后由系统释放。字符常量就是像这样的 char* str=”abc”;其中的”abc”。在实际情况中，是会复用的，比如变量a和b都赋值为”abc”则实际上他们指向同一块地址。
  5. 程序代码区：存放函数体的二进制代码。

  二、再从作用域上来区分它们。

  1. 全局变量具有全局作用域。全局变量只需在一个源文件中定义，就可以作用于所有的源文件。当然，其他不包含全局变量定义的源文件需要用extern 关键字再次声明这个全局变量。
  2. 局部变量也只有局部作用域，它是自动对象（auto），它在程序运行期间不是一直存在，而是只在函数执行期间存在，函数的一次调用执行结束后，变量被撤销，其所占用的内存也被收回。
  3. 静态局部变量具有局部作用域，它只被初始化一次，自从第一次被初始化直到程序运行结束都一直存在，它和全局变量的区别在于全局变量对所有的函数都是可见的，而静态局部变量只对定义自己的函数体始终可见。
  4. 静态全局变量也具有全局作用域，它与全局变量的区别在于如果程序包含多个文件的话，它作用于定义它的文件里，不能作用到其它文件里，即被static关键字修饰过的变量具有文件作用域。这样即使两个不同的源文件都定义了相同名字的静态全局变量，它们也是不同的变量。

  从分配内存空间看：全局变量，静态局部变量，静态全局变量都在静态存储区分配空间，而局部变量在栈里分配空间。

  从以上分析可以看出， 把局部变量改变为静态变量后是改变了它的存储方式即改变了它的生存期。把全局变量改变为静态变量后是改变了它的作用域，限制了它的使用范围。因此static 这个说明符在不同的地方所起的作用是不同的。

  三、总的来说，全局变量、局部变量、静态全局变量、静态局部变量的区别是：

  1. 生存周期不同
  2. 作用范围不同
  3. 分配方式不同

  四、再来分析下堆和栈的不同：

  1. 分配方式不同
  2. 空间大小不同
  3. 分配效率不同
  4. 能否产生碎片不同
  5. 生长方向不同

  1、分配方式不同：

  栈: 由系统自动分配。 例如，声明在函数中一个局部变量 int b; 系统自动在栈中为b开辟空间
  堆: 需要程序员自己申请，并指明大小，在c中malloc函数
  如p1 = (char *)malloc(10);
  在C++中用new运算符
  如p2 = (char *)new(10);
  但是注意p1、p2本身是在栈中的。

  2、空间大小不同：

  一般来讲在32位系统下，堆内存可以达到4G的空间，从这个角度来看堆内存几乎是没有什么限制的。但是对于栈来讲，一般都是有一定的空间大小的，例如，在VC6下面，默认的栈空间大小是1M。

  3、分配效率不同：

  栈是机器系统提供的数据结构，计算机会在底层对栈提供支持：分配专门的寄存器存放栈的地址，压栈出栈都有专门的指令执 行，这就决定了栈的效率比较高。堆则是C/C++函数库提供的，它的机制是很复杂的，例如为了分配一块内存，库函数会按照一定的算法（具体的算法可以参考 数据结构/操作系统）在堆内存中搜索可用的足够大小的空间，如果没有足够大小的空间（可能是由于内存碎片太多），就有可能调用系统功能去增加程序数据段的 内存空间，这样就有机会分到足够大小的内存，然后进行返回。显然，堆的效率比栈要低得多。

  4、碎片问题：

  栈：只要栈的剩余空间大于所申请空间，系统将为程序提供内存，否则将报异常提示栈溢出。
  堆：首先应该知道操作系统有一个记录空闲内存地址的链表，当系统收到程序的申请时，
  会遍历该链表，寻找第一个空间大于所申请空间的堆结点，然后将该结点从空闲结点链表中删除，并将该结点的空间分配给程序，另外，对于大多数系统，会在这块 内存空间中的首地址处记录本次分配的大小，这样，代码中的delete语句才能正确的释放本内存空间。另外，由于找到的堆结点的大小不一定正好等于申请的 大小，系统会自动的将多余的那部分重新放入空闲链表中。

  对于堆来讲，频繁的new/delete势必会造成内存空间的不连续，从而造成大量的碎片，使程序效率降低。对于栈来讲，则不会存在这个问题，因为栈是先进后出的队列，他们是如此的一一对应，以至于永远都不可能有一个内存块从栈中间弹出，在他弹出之前，在他上面的后进的栈内容已经被弹出。

  5、生长方向：

  对于堆来讲，生长方向是向上的，也就是向着内存地址增加的方向；对于栈来讲，它的生长方向是向下的，是向着内存地址减小的方向增长。

  堆和栈相比，由于大量new/delete的使用，容易造成大量的内存碎片；由于没有专门的系统支持，效率很低；由于可能引发用户态和核心态的切换，内存的申请，代价变得更加昂贵。所以栈在程序中是应用最广泛的，就算是函数的调用也利用栈去完成，函数调用过程中的参数，返回地址，EBP和局部变量都采用栈的方式存放。所以，我们推荐大家尽量用栈，而不是用堆。虽然栈有如此众多的好处，但是由于和堆相比不是那么灵活，有时候分配大量的内存空间，还是用堆好一些。

   

  参考链接：

  https://www.cnblogs.com/binxindoudou/archive/2013/04/20/3032119.html

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^