数据结构_数组
不要小瞧数组:
数组基础:把数据码成一排进行存放,并且添加数据索引
Scores[2]代表第三个数据.
索引是可以有语义的,也可以是没有语义.
数组最大优点:快速查询,数组最好应用于有语义的情况.
并非所有有语义的索引都适用于数组(比如太大的索引).
我们在这一章,主要处理索引没有语义的情况数组的使用.
索引没有语义,如何表示没有的元素
如何添加元素?如何删除元素?
基于Java的数组,二次封装属于我们的数组类.
Array类
实例变量 private int[] data;
数组长度 private int size;
创建构造函数:
//构造函数,传入数组容量capacity构造Array
Public Array(int capacity){
Data=new int[capacity];
Size=0;
}
//默认构造函数,默认数组容量为capacity=10
Public Array(){
This(10);
}
//用户查询信息,获取数组中元素个数
Public int getSize(){
Return size;
}
//获取数容量
Public int getCapacity(){
Return data.length;
}
//判断数组为空
Public Boolean isEmpty(){
Return size==0;
}
向数组中添加元素:
Data[0]=66;
Size++;
//向所有元素末尾添加元素
Public void addList(int e){
If(size==data.length)
Throw new IlleagalArgumentException(“AddLast failed .Array is full”)
Data[size]=e;
Size++;
}
//复用
Public void addList(int e){
Add(size,e);
}
//
Public void addFrist(int e){
Add(0,e);
}
//将指定元素插入到指定索引的位置.
Public void add(int index,int e){
If(size==data.length)
Throw new IlleagalArgumentException(“AddLast failed .Array is full”)
if(index<0||index>size)
Throw new IlleagalArgumentException(“AddLast failed .Require index>=0”)
For(int i=size-1;i>=index;i--)
Data[i+1]=data[i];
Data[index]=e;
}
///////////查询和修改数组中的元素//////////////////////////////////////////////////
//添加标注
@Override代表重载
Public String toString(){
StringBuilder res=new StringBuilder();
Res.append(String.format(“Array: size=%d,capacity =%d\n”,size,data));
Res.append(‘[’);
For(int i=0;i<size;i++){
Res.append(data[i]);
If(i!=size-1)
Res.append(“, ”);
}
Res.append(‘)’);
Return res.toString();
}
/////////////////////////////////////////////////////////////////////////////////////////////////
获取index索引位置的元素
Int get(int index){
If(index<0||index>=size)
Throw new IlleagalArgumentException();
Return data[index];
}
/////////修改index索引位置的元素为e
Void set(index ,e){
//判断索引是否合法
Data[size]=e;
}
/////////////////////数组中的查找包含和删除//////////////////////////////
Public Boolean contains(int e){
遍历数组,对比元素,返回值
}
Public int find(int e){
//查找到索引返回相应的索引
没有查到返回-1;
}
//删除索引为1的元素,从2开始将所有元素向前移动,size减一.
Public int remove(int index){
//判断索引是否合法
//从数组中删除index元素,返回删除的值
待删除的元素赋值给一个变量
}
Public int removeFrist(){
Return remove(0);
}
//
Public int removeLast(){
Return remove(size-1)
}
//删除元素,首先判断元素是否存在
Public void removeElement(int e){
Find(e);
If(index!=-1)
Remove(index)
}
-----------------------------------------------------------------------------------------------------
使用泛型:
1.目的:让我们的数据结构可以存放任意数据类型.
2.不可以是基本数据类型(byte,short,int,long,double,float,Boolean,char),
只能是类对象.
3.修改代码,支持泛型.
1.在类名上添加<E>
2.在逻辑中添加类型E
3.新创建一个泛型类型的数组,是不能直接写的,可以这样写
(E[])New Object[capacity];
4.从数组中删除一个元素之后,我们应该将size减一个位置,然后将data[size]释放
动态数组:内部使用的静态数组,我们怎么让数组变得可伸缩?
- 当空间用完之后,将数组扩容,处理size和capacity的关系.
- If(size==capacity),那么进行扩容resize(2*data.length)
- 扩容函数的逻辑:传入newCapacity
- 创建新的数组,让后旧数组中的值传递给新的数组.
- 默认容量10个元素
- 删除元素函数中,如果size==data.length/2,那么数组则进行缩容
时间复杂度分析:
研究生,博士生需要了解时间复杂度.
简单的时间复杂度分析:
为什么要用O,叫做O(n)?忽略常数,实际时间T=c1*n+c2
T=2*n+2----------àO(n)
T=2000*n+1000àO(n)
T=1*n*n+0------ào(n^2)
O代表渐进时间复杂度,描述的是n趋近于无穷的情况.
n如果比较小的话,那么可以选择高阶函数.
添加操作的时间复杂度:
addLast(e) O(1);
addFirst(e) O(n);
add(index,e) O(n/2)=O(n)
严格计算需要一些概率论知识.
添加操作是一个O(n)级别算法,但是添加操作有O(1),为什么要说O(n)呢?
因为时间复杂度,我们一般考虑最差的情况.
另外还有resize函数.
删除操作:
RemoveLast(e) O(1)
RemoveFrist(e) O(n)
Remove(index,e) O(n)
删除操作时间复杂度为O(n)
修改操作:
Set(index,e) O(1):支持随机访问
已知索引为O(1);未知索引为O(n)
查询操作:
Get(index) O(1):
Contains(e) O(n)时间复杂度(遍历数组,挨个比较)
Find(e) O(n):时间复杂度
查询操作未知索引时间复杂度为O(n),如果知道索引那么时间复杂度为O(1)
Resize复杂度分析:
复杂度震荡:
出现问题原因:removeLast时resize过于着急(Eager),
解决方案,使用Lazy策略.
用户添加数据添加到数组上限之后,数组扩容,扩容成二倍.
用户在删除数据,删除数据的数量到扩容后数组长度的1/2时,
不着急缩容,而是等到数量达到数组的1/4时才缩容.缩容到1/2.
Remove中,当size==capacity/4时,才将capacity减半.
算法未修改之前,数组的震荡.
结束震荡.