经典抽象数据类型

经典抽象数据类型

       C语言中的抽象数据类型ADT:链表、堆栈、队列和树。

内存分配

       获取内存来存储值的三种方案:

l  静态数组:静态数组要求结构的长度固定,而且,这个长度是在编译时就要确定的。但是这个方案最为简单,而且最不容易出错;

l  动态分配的数组:可以在运行时才决定数据的度,而且,如果需要的话,可以通过分配一个新的、更大的数组,把原来数组的元素复制到新数组中,然后删除原先的数组,从而达到动态改变数组长度的目的。在决定是否采用动态数组时,你需要在由此增加的复杂性和随之产生的灵活性之间做一番平衡;

l  动态分配的链式结构提供了最大程度的灵活性。每个元素在需要时才单独进行分配,所以除了不能超过机器的可用内存之外,这种方式对元素的数量几乎没有什么限制。但是,链式结构的链接字段需要消耗一定的内存,在链式结构中访问一个特定元素的效率不如数组

堆栈

       堆栈stack数据的鲜明特点就是后进先出last in first outLIFO方式。堆栈基本操作通常称为pushpop

队列

       队列和堆栈的顺序不同:队列是一种先进先出(FIFOFirst in First out)的结构。

树的遍历

       最常见的几种遍历为前序pre-order、中序in-order、后序post-order和层次遍历breadth-first。各种遍历的顺序为(可以看出,名字的选取主要由根节点决定):

l  前序pre-order:根节点、左节点、右节点

l  中序in-order:左节点、根节点、右节点

l  后序post-order:左节点、右节点、根节点

l  层次遍历breadth-first:逐层扫描。

实现二叉搜索树

       队列的链式实现消除了数组空间利用不充分的问题,这是通过为每个新值动态分配内存并把这些结构链接到树中实现的。因此,不存在不使用的内存