2 pengyangxiaobai pengyangxiaobai 于 2013.10.11 09:30 提问

基于数组的算法分析之增删查改

  使用一个数组来描述集合,需要把集合中的每个元素映射到数组的具体位置上。下面我们用一个数学公式来确定每个元素的位置。一个简单的映射公式如下:
                 location(i)=i-1 (2-1)
  公式(2-1)指明集合中第i个元素(如果存在的话)位于数组中i-1位置处。为了完整的描述集合,使用变量length作为集合的长度。
  在这种数据结构中,搜索一个元素只需根据公式(2-1)进行映射就能实现,其平均时间复杂度是O (1),性能非常理想。
  为了在集合中删除第k个元素,需要首先确认集合中包含了第k个元素(如果不存在第k个元素,则引发一个异常),将元素k+1,k+2,…,length依次向前移动一个位置,并将length的值减1,从而删除第k个元素。删除操作的平均时间复杂度为O(length)。
为了在集合中第k个元素后面插入一个新元素,首先要把k+1至length元素往后移动一个位置,然后把新元素插入到k+1位置处。插入操作的平均时间复杂度为O(length)。此外,插入操作是,如果数组已经满了,则会引发一个异常。
  采用数组来描述一个集合实现起来非常简单。执行搜索的平均时间复杂度为常数,非常理想。执行删除和插入的时候,有一个和集合的大小呈线性关系的平均时间复杂度,在大部分情况下也是可以接受的。利用数组来描述集合,使用在删除和插入操作少,搜索操作多的场合有非常优异的表现。
  但是,这种描述方法有一个非常大的缺点是空间的低効利用。必须要预测集合的最大可能尺寸,根据最大可能尺寸分配数组。考察如下情况,我们需要一个集合,它的最大可能尺寸是5000,但平均尺寸只有100,那么空间的利用率就只有2%。在实际应用中,可能发生的情况会比这更极端。

用上述算法写出此算法的检索、插入和删除指定位置元素的操作的函数。

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!