时间: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的辛勤劳动。
分享到:
相关推荐
算法基础算法基础算法基础算法基础算法基础算法基础算法基础算法基础算法基础算法基础算法基础算法基础
计算机图形学的算法基础,教程
算法设计与分析基础.part2 算法设计与分析基础.part2
计算机动画的算法基础part5,共6部分 国家九五重点图书 鲍虎军,金小刚,彭群生著 浙江大学出版社
计算机动画的算法基础part2,共6部分 国家九五重点图书 鲍虎军,金小刚,彭群生著 浙江大学出版社
算法导论(中文版)(现代计算机常用数据结构和算法).part1.rar算法导论(中文版)(现代计算机常用数据结构和算法).part1.rar算法导论(中文版)(现代计算机常用数据结构和算法).part1.rar算法导论(中文版)(现代计算机常用...
matlab算法大全-算法大全.part2.rar 本帖最后由 nisky 于 2012-4-17 23:42 编辑 算法大全.part4.rar 算法大全.part3.rar 算法大全.part2.rar ...
零基础学算法.part1 零基础学算法.part1 零基础学算法.part1 零基础学算法.part1 零基础学算法.part1 零基础学算法.part1
算法导论(中文版)(现代计算机常用数据结构和算法).part3.rar算法导论(中文版)(现代计算机常用数据结构和算法).part3.rar算法导论(中文版)(现代计算机常用数据结构和算法).part3.rar算法导论(中文版)(现代计算机常用...
算法大全.part2.rar 算法大全.part1.rar 算法大全第02章 整数规划.pdf 算法大全第29章_多元分析.pdf 算法大全第30章__偏最小二乘回归.pdf 算法...
【原 书 名】 Procedural Elements for Computer Graphics (2E) 【作 者】 (美)David F.Rogers 【译 者】 石教英 彭群生 本书从图形学最基础的光栅扫描、区域填充、画直线和圆弧等算法讲起,详细...
MIT 算法导论part2MIT 算法导论part2MIT 算法导论part2MIT 算法导论part2
【原 书 名】 Procedural Elements for Computer Graphics (2E) 【作 者】 (美)David F.Rogers 【译 者】 石教英 彭群生 本书从图形学最基础的光栅扫描、区域填充、画直线和圆弧等算法讲起,详细...
计算机动画的算法基础part3,共6部分 国家九五重点图书 鲍虎军,金小刚,彭群生著 浙江大学出版社
零基础学算法.part2 对于 没有基础的人 学习算法 这本书算是一个救星了 因为实在太大 所以 大家给点辛苦分吧 四部分一起下载完了才可以解压 高清
计算机图形学的算法基础,教程
计算机图形学的算法基础,教程
计算机图形学的算法基础,教程
计算机图形学的算法基础,教程
计算机图形学的算法基础,教程