《算法基础讲座》part2

 

时间：2009-11-20 16:30

地点：JE群9770785     extjs群88403922     sm.net群75462710

 

 

 

三 基本数据结构

 

 

集合

 

上回我们讲了基本的数据类型和数组这个基本结构，今天开始我们讲常用的数据结构。

常用的简单数据结构有stack queue list等。

这三个数据结构都是最简单的线性结构，跟Array一样，用来保存一组一维的数据。

我们知道数组需要在初始化时就指定固定大小。并且一般都难以动态调整和扩展。而实际使用的数据，一般很可能随时间的流逝而不断的变化。向现有数据添加一个数据项，或是移除一个数据项，某个数据项被修改。

数组本身不太支持动态的扩展（直接修改是支持的），在我们不确定数据量的时候，使用数组一般都是不方便的。比如常见的一般c/c++语言基础教程，经常见到char[255]之类的东西。

对于固定的一个数组，当它已经满负荷的时候，再也装不下一个数据项了。我们需要扩张它的容量。一般是再new一个比它大一点的数组。然后把旧数组的数据复制到新数组，释放旧数组的资源。然后再将要添加的数据添加到新的数组里。

大家可以注意到，一个数组的扩容需要创建新数组，复制所有的旧数组数据，释放旧数组资源，这些如果频繁操作，系统的cpu和存储开销成本都远远比一般情况添加一个元素大的多。

这个过程还有一个值得注意的问题是，在我们往数组中插入元素时，我们都有意无意的使用了数组下标的跟踪计数。每次我们插入数据的时候，都在考虑下一个可用位置的下标号。在一个简单的for循环的数组赋值中，我们一般用的i++就是用来跟踪保存这个序号的，虽然更一般的说，出了这个for循环，i这个变量就没意义了。

特别是对一个数组，多次独立的给数组中的一部分赋值或是删除值的情况下，我们需要显示的记录元素的位置和空位置，以便操作。

从上面这些现象出发，我们把经验总结起来，常见的操作和技术封装起来，集合类就出现了

我们可以从一个简单的数组出发，创建一些新的结构，内部使用额外的变量或是指针记录位置，封装常见的插入、修改、删除数据的方法，甚至使用合理的设计技巧和策略，实在比较高效的动态扩张和压缩的方法。

比如一个简单的Stack, 我们可以用一个数组加一个表示位置的变量来实现。

ArrayList复杂一点，要考虑扩张。

Queue则可以用一个数组加两个表示位置的变量实现。

 

Stack

Stack的实现中，我们用一个固定大小的数组来存储数据。例如，我们用位置-1，表示栈底，用另一个变量p表示当前栈顶的元素，则，初始的时候，p =-1, 当一个新元素入栈的时候，在下个位置即p+1的地方存入这个新元素，并使p=p+1, 这样就往栈里添加了一个新元素。注意，栈的大小一般都是有限的，所以需要在插入数据前，检查p+1这个位置是不是已经超出了数组大小了。

数据的出栈就简单了，如果p==-1，说明是空栈，没有数据，否则就取出当然位置的数据，再令p=p-1（栈顶的位置下移）并返回这个数据。

这就是一个用数组实现的简单的栈。

Queue

 

用数组来实现Queue的原理跟上面说的栈的原理一样。

不过一般可以用两个指针来记录队列的起点和队尾。

为什么都是线性结构，栈需要记录一个位置，而队列需要两个呢？其实队列只要一个指针也可以，但是由于栈只需要移动一端，另一端是固定的，可以一直放在数组的一段不动。而队列是两头都要操作数据的。一头添加数据，另一头移除数据，如果也用数组0位置作为队列的一端，那么这个地方在插入或是移除数据时，就需要调整整个数据的所有数据位置。

多用一个记录位置的变量，就不需要调整数据了，大大提高了执行效率。同时，我们可以把数组的0位置和终点位置看做连续的，这样我们无论怎样都不用调整任何元素的位置，队列无论都操作了多少次，两个位置变动了多少次，在这两个位置上操作添加和移除数据的操作，还是正确的。

ArrayList

用数组实现的简单的list，一般叫ArrayList、

表是最常用的集合之一。他表示一批数据，并提供一系列的简单操作。

ArrayList内部也是用一个数组来实现。默认一般是长度是16，跟一般的栈和队列的固定大小和在首尾操作不同的是，list提供了添加任意个元素的功能（动态增加容量），在任意位置插入或是删除元素的操作。

一样的记录当前元素位置，每一次不指定位置的插入，都直接插在当前位置，指针加1，在指定的位置插入元素，需要先把此位置以后到表尾的所有元素后移一位。然后在这个腾出来的空位插入新元素。

删除元素一样的道理，不过是此元素到表尾所有的元素都向前移动一位。

同时表尾当前元素的指针加一（插入时）或是减一（删除时）。

当插入的数据量达到目前数组的最大容量的时候，装不下更多数据了，就需要扩容了。一般的扩容策略是当前的容量乘以2，以指数形式扩张。

我们知道，每次扩张容量时，都需要将旧数据如数的复制到新数组，然后释放旧数组的资源，如果每次扩张的幅度太小了，那么频繁增加数据时，系统创建新数组和复制旧数据的开销巨大。如果每次扩张的太大，那么如果新添加的数据较少，大量新添加的存储空间被浪费掉了。

所以，选择扩大1倍是个合理的数字。如果你的数据量比较大，并且是多次一个个的插入到ArrayList中的，最好再创建ArrayList时就指定容量。 如果你的数据的变化形式比较特殊，你可以通过简单的代码就实现有自己扩容形式的ArrayList结构。

从这里我们还可以知道，ArrayList中数据的中间插入或是移除数据，需要移动其后面的所有数据，这个成本虽然比扩容的成本小，但也是比较大的。

 

LinkedList

数组实现的线性的基本数据结构，最常见的就是这三种。list里还有一种常见的线性表，那就是链表，LinkedList

一般来说，各语言中的集合类的实现原理基本都一样。某些具体的策略和调整参数略有不同。

链表是一种线性表，其实本质上更是一棵光棍的树。

由于他不用数组实现，所以有一些数组没有的神奇性质。

借助数组实现的数据结构，一般都依靠数组下标的位置关系来维持元素的顺序。而树一般不需要这样。树是一些节点的集合。而这些节点本身保存其跟他们节点关系的描述。

我们一般把数组实现的结构中的数据项叫元素，而把树结构中的数据项叫节点。节点是一个包含有意义的数据以及数据间关系的结构。

这些关系常见的有父子关系，兄弟关系，前驱后继等等。其实叫什么名字无所谓，本质都是从一个节点，可以获取到其他的一些确定的节点。

例如，一个简单的单链表，每一个节点都直接指向下一个节点，一直到表尾的元素，其没有下个节点。

它跟ArrayList明显不同的是，
1、不需要扩容能直接在表尾或是中间添加任意个数据项
2、插入和删除都是不需要移动任何数据的。在某两个节点间插入，只需要将前一节点的后继指向新节点，并将新节点的后继指向下一节点即可。

LinkedList在扩展和动态的增删数据上，有很好的性能。

但是，应该指出的是，它不能像数组或是ArrayList那样直接获取指定序号的元素。

获取或是操作第几个元素，我们需要先从头来搜索每一个元素并计数。

搜索的问题，我们将在hash和tree的课程中详细讲。

今天到此为止，下课，下一节讲排序。 

 

 

-----------------------

 

 谢谢同步信息的Elementstorm的辛勤劳动。

评论

1 楼 tterry 2010-11-29  

感谢kimmking童鞋