python实现动态数组的示例代码
实现一个支持动态扩容的数组并完成其增删改查
#通过python实现动态数组 """ 数组特点: 占用一段连续的内存空间,支持随机(索引)访问,且时间复杂度为O(1) 添加元素时间复杂度:O(n) 删除元素时间复杂度:O(n) """ classArr: def__init__(self,capacity=10): """ 构造函数 :paramcapacity:数组最大容量,不指定的话默认为10 """ self._capacity=capacity self._size=0#数组有效元素的数目,初始化为0 self._data=[None]*self._capacity#由于python的list是动态扩展的,而我们要实现底层具有固定容量、占用一段连续的内存空间的数组,所以用None来作为无效元素的标识 def__getitem__(self,item): """让Arr类支持索引操作""" returnself._data[item] defgetSize(self): """返回数组有效元素的个数""" returnself._size defgetCapacity(self): """返回当前数组的容量""" returnself._capacity defisEmpty(self): """判断当前数组是否为空""" returnself._size==0 defadd(self,index,elem): """ 向数组中添加一个元素,注意数组占用的是一段连续的内存空间,所以在添加元素后,数组还是要保证这个特点的,因此需要将后面的元素都向后挪一个位置,而且要注意要先从 尾部开始挪,防止元素之间的覆盖 时间复杂度:O(n) :paramindex:添加的元素所在的索引 :paramelem:所要添加的元素 """ ifindex<0orindex>self._size:#插入的位置无效 raiseException('AddFiled.Require0<=index<=self._size') ifself._size==self._capacity:#满了 self._resize(self._capacity*2)#默认扩容当前容量的二倍。容量翻倍要比容量加上一个固定值要好,这样做均摊复杂度为O(1)。具体请百度 foriinrange(self._size-1,index-1,-1):#从尾部开始挪动元素,在index处腾出一个空间 #一定要注意在步长为负数的情况下,区间是左开右闭区间,即(index,self._size-1],所以是index-1,与正常的左闭右开区间是相反的! self._data[i+1]=self._data[i] self._data[index]=elem#将该位置赋值为elem self._size+=1#数组有效元素数加1 defaddLast(self,elem): """ 向数组尾部添加元素 时间复杂度:O(1) :paramelem:所要添加的元素 """ self.add(self._size,elem)#直接调用add方法,注意不用再次判定合法性了,因为add函数中已经判断过了 defaddFirst(self,elem): """ 想数组头部添加元素 时间复杂度:O(n) :paramelem:所要添加的元素 """ self.add(0,elem)#同理直接调用add方法 defget(self,index): """ 获得索引index处的元素 时间复杂度:O(1) :paramindex:数组索引 :return:数组索引处的值 """ ifindex<0orindex>=self._size:#判断index的合法性 raiseException('Getfailed.Indexisillegal.') returnself._data[index] defgetFirst(self): """ 获得数组首位置元素的值 :return:首位置元素的值 """ returnself.get(0)#直接调用get函数,安全可靠 defgetLast(self): """ 获得数组末尾元素的值 :return:末尾元素的值 """ returnself.get(self._size-1)#直接调用get函数,安全可靠 defset(self,index,elem): """ 将索引为index的元素的值设为elem 时间复杂度:O(1) :paramindex:索引 :paramelem:新的值 """ ifindex<0orindex>=self._size:#判断index的合法性 raiseException('Satfailed.Indexisillegal.') self._data[index]=elem defcontains(self,elem): """ 查看数组中是否存在元素elem,最好不要传入一个浮点数,你懂得。。 时间复杂度:O(n) :paramelem:目标元素 :return:bool值,存在为真 """ foriinrange(self._size):#遍历 ifself._data[i]==elem: returnTrue#找到了就返回True returnFalse#遍历完了还没找到,就返回False deffind(self,elem): """ 在数组中查找元素,并返回元素所在的索引。(如果数组中存在多个elem,只返回最左边elem的索引) 时间复杂度:O(n) :paramelem:目标元素 :return:元素所在的索引,没找到则返回-1(无效值) """ foriinrange(self._size):#遍历数组 ifself._data[i]==elem: returni#找到就返回索引 return-1#没找到返回-1 deffindAll(self,elem): """ 找到值为elem全部元素的索引 :paramelem:目标元素 :return:一个列表,值为全部elem的索引 """ ret_list=Arr()#建立一个新的数组用于存储索引值 foriinrange(self._size):#遍历数组 ifself._data[i]==elem: ret_list.addLast(i)#找到就将索引添加进ret_list returnret_list defremove(self,index): """ 删除索引为index的元素。index后面的元素都要向前移动一个位置 时间复杂度:O(n) :paramindex:目标索引 :return:位于该索引的元素的值 """ ifindex<0orindex>=self._size:#index合法性检查 raiseException('Removefailed.Require0<=indexself._data[max_elem_index]:#如果当前索引的值大于最大值索引处元素的值 max_elem_index=i#更新max_elem_index,这样它还是当前最大值的索引 returnmax_elem_index#遍历完后,将数组的最大值的索引返回 defremoveMax(self): """ 删除数组中的最大元素,返回最大元素的值,如果有多个最大值,默认值删除最左边那个 时间复杂度:O(n) :return:最大元素 """ returnself.remove(self.get_Max_index())#直接调用remove函数删除最大值 defget_Min_index(self): """ 获取数组中的最小元素的索引,返回最小元素的索引值,如果有多个最小值,默认返回最左边那个的索引 时间复杂度:O(n) :return:最小元素的索引 """ ifself.isEmpty(): raiseException('Error,arrayisEmpty!') min_elem_index=0#记录最小值的索引,初始化为0 foriinrange(1,self.getSize()):#从索引1开始遍历,一直到数组尾部 ifself._data[i] =self._sizeorindex2>=self._size:#合法性检查 raiseException('Indexisillegal') self._data[index1],self._data[index2]=self._data[index2],self._data[index1]#交换元素 defprintArr(self): """对数组元素进行打印""" foriinrange(self._size): print(self._data[i],end='') print('\nSize:%d-----Capacity:%d'%(self.getSize(),self.getCapacity())) #private def_resize(self,new_capacity): """ 数组容量放缩至new_capacity,私有成员函数 :paramnew_capacity:新的容量 """ new_arr=Arr(new_capacity)#建立一个新的数组new_arr,容量为new_capacity foriinrange(self._size): new_arr.addLast(self._data[i])#将当前数组的元素按当前顺序全部移动到new_arr中 self._capacity=new_capacity#数组容量变为new_capacity self._data=new_arr._data#将new_arr._data赋值给self._data,从而完成数组的容量放缩操作
测试代码
importArray importnumpyasnp np.random.seed(7) test=Array.Arr() print(test.getSize()) print(test.getCapacity()) print(test.isEmpty()) foriinrange(8): test.add(0,np.random.randint(5)) test.printArr() test.addLast(2) test.printArr() print(test.get(3)) test.set(3,10) test.printArr() print(test.contains(10)) print(test.find(4)) test.findAll(1).printArr() test.remove(3) test.printArr() test.removeFirst() test.removeLast() test.printArr() test.removeElement(4) test.printArr() test.removeAllElement(3) test.printArr() foriinrange(30): test.addLast(np.random.randint(10)) test.printArr() print(test[3]) test.swap(0,1) test.printArr()
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持毛票票。