数据结构：数组

     数组是应用最广泛的数据结构。

 

数组中不允许重复值的情况

1. 数组的插入：由于新的数据项总是插在数组中第一个空位子上，并且数组中已有数据项个数已知，所以算法知道这个空位的具体位置，新的数据项只是简单地插入到下一个可用空间中。
2. 查找：查找算法必须平均搜索一半的数据项来查找特定的数据值。查数组头部的数据项快，查数组尾部的数据项慢，若数据项个数为N，则一个数据项的平均查找长度为N/2,在最坏的情况下，待查的数据相在数组的最后，需要N步才能查的到。执行算法的时间长度与执行步数成正比，所以执行算法的时间要比插入（一步）长很多。通过索引访问数组极快（o(1)）
3. 删除：只有找到某一数据项后才能删除它。删除算法暗含着一个假设，及数组中不允许有洞。如果有则算法会变得更加复杂。当找到特定数据项并将其删除后，会将随后的数据项都向前移，填补这个洞。删除需要查找N/2个数据项，并平均移动剩下N/2个数据项。总共是N步(o(n))。

数组是最不浪费内存的数据结构

 

数组中允许重复值的情况：

1. 查找：通常用需要执行N步（o(n)）
2. 插入：一次移动
3. 删除：N次比较，多于N/2次移动

      在java中数组是一个对象，所以他的名字是是数组的一个引用，并不是数组本身，数组存储在内存中的其他地址中。

 

有序数组

查找比较方便，但插入和删除比较繁琐

 

 

 

 

分享到：

数据结构：栈和队列 | 00.数据结构综述

• 2009-01-05 11:13
• 浏览 1093
• 评论(0)
• 查看更多