数据结构与算法(3)线性表中的顺序表
最近在预习数据结构与算法，记录一下学习的知识。
线性表是最基本、最简单、也是最常用的一种数据结构。一个线性表是n个具有相同特性的数据元素的有限序列。
前驱元素、后继元素:
若A在B的前面，则A为B的前驱元素,若B在A的后面，则称B为A的后继元素
线性表的特征:数据元素之间具有一种“一对一”的逻辑关系。
1.第一个数据元素没有前驱，这个数据元素被称为头节点；
2.最后一个数据元素没有后继，这个数据元素被称为尾节点；
3.除了第一个和最后一个元素外，其他数据元素有且仅有一个前驱和后继。
顺序表：
顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元，依次存储线性表中的各个元素，使得线性表中在逻辑结构上响铃的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。
(1)顺序表API设计：
(第一次用Java)
public class Sequencelist<T>
{ //存储元素的数组
private T[] eles;
//记录当前顺序表中的元素个数
private int N;
//构造方法
public Sequencelist(int capacity)
{ //初始化数组
this.eles=(T[])new object[capacity];//(T[])是强转类型
//初始化长度
this.N=0;
}
//将一个线性表置为空表
public void clear()
{
this.N=0;
}
//判断当线性表是否为空表
public boolean isEmpty()
{
return N==0;
}
//获取线性表的长度
public int length()
{
return N;
}
//获取指定位置的元素
public T get(int i)
{
return eles[i];
}
//向线性表中添加元素t
public void insert(T t)
{
eles[N++]=t;//不能是++N！！
}
//在i元素处插入元素t
public void insert(i,T t)
{
//先把i索引处的元素及其后面的元素依次向后移动一位
for(int index=N-1;index>i;index--)//N-1是最后一个元素的索引
{
eles[index]=eles[index-1];
}
//再把t元素放到i索引处即可
eles[i]=t;
}
//删除指定位置i处的元素，并返回该元素
public T remove(int i)
{
//记录索引i处的值
int current = eles[i];
//索引i后面的元素依次向前移动一位即可
for(int index=i;index<N-1;index++)
{
eles[index]=eles[index+1];
}
//元素个数-1
N--;
return current;
}
//查找t元素第一次出现的位置
public int indexOf(T t)
{
for(int i=0;i<N;i++)
{ if(eles[i].equals(t))
{
return i;
}
}
return -1;
}
}(2) 顺序表的测试:
public class SequenceList
{
public static void main(string[] args)
{
SequenceList<string> sl =new SequenceList<>(capacity 10);
//测试插入
sl.insert(t:"姚明");
sl.insert(t:"科比");
sl.insert(t:"麦迪");
sl.insert(i:1,t:"詹姆斯");
//测试获取
String getRuslt=sl.get(1);
System.out.println("获取1处的索引值为："+getResult);
//测试删除
String removeResult =sl.remove(0);
System.out.println("删除的元素是："+removeResult);
//测试清空
sl.clear();
System.out.println("清空后线性表中的元素个数为："+sl.length());
}
}(3)顺序表的遍历
一般作为容器存储数据，都需要向外部提供遍历方式，因此我们需要给顺序表提供遍历方式。
在Java中，遍历集合的方式一般都用的是foreach循环，如果想让我们得SequenceList也能支持foreach循环，则需要如下操作：
1.让SequenceList实现iterable接口，重写iterator方法；
2.让SequenceList内部提供一个内部类Slterator,实现iterator接口,重写hasNext方法和next方法。
public class Sequencelist<T> implements Iterable<T>
{ //存储元素的数组
private T[] eles;
//记录当前顺序表中的元素个数
private int N;
//构造方法
public Sequencelist(int capacity)
{ //初始化数组
this.eles=(T[])new object[capacity];//(T[])是强转类型
//初始化长度
this.N=0;
}
//将一个线性表置为空表
public void clear()
{
this.N=0;
}
//判断当线性表是否为空表
public boolean isEmpty()
{
return N==0;
}
//获取线性表的长度
public int length()
{
return N;
}
//获取指定位置的元素
public T get(int i)
{
return eles[i];
}
//向线性表中添加元素t
public void insert(T t)
{
eles[N++]=t;//不能是++N！！
}
//在i元素处插入元素t
public void insert(i,T t)
{
//先把i索引处的元素及其后面的元素依次向后移动一位
for(int index=N-1;index>i;index--)//N-1是最后一个元素的索引
{
eles[index]=eles[index-1];
}
//再把t元素放到i索引处即可
eles[i]=t;
//元素个数+1
N++;//不然结果中"麦迪"打印不出来
}
//删除指定位置i处的元素，并返回该元素
public T remove(int i)
{
//记录索引i处的值
int current = eles[i];
//索引i后面的元素依次向前移动一位即可
for(int index=i;index<N-1;index++)
{
eles[index]=eles[index+1];
}
//元素个数-1
N--;
return current;
}
//查找t元素第一次出现的位置
public int indexOf(T t)
{
for(int i=0;i<N;i++)
{ if(eles[i].equals(t))
{
return i;
}
}
return -1;
}
@override//重写
public Iterator<T> iterator()
{
return new SIterator();
}
private class SIterator implements Iterator
{
private int cusor;
public SIterator()
{
this.cusor=0;
}
@override
public boolean hasNext()//判断容器中还有没有下一个元素
{
return cusor<N;
}
@override
public object next()//获取容器中的下一个元素
{
return eles[cusor++];
}
}
}public class SequenceList
{
public static void main(string[] args)
{
SequenceList<string> sl =new SequenceList<>(capacity 10);
//测试插入
sl.insert(t:"姚明");
sl.insert(t:"科比");
sl.insert(t:"麦迪");
sl.insert(i:1,t:"詹姆斯");
sl.for(String s : sl)
{
System.out.println(s);
}
System.out.println("-------------------------------------------");//区分线
//测试获取
String getRuslt=sl.get(1);
System.out.println("获取1处的索引值为："+getResult);
//测试删除
String removeResult =sl.remove(0);
System.out.println("删除的元素是："+removeResult);
//测试清空
sl.clear();
System.out.println("清空后线性表中的元素个数为："+sl.length());
}
}(4)顺序表的容量可变
在之前的实现中，当我们使用SequenceList时，先 new SequenceList<>(capacity 10)创建一个对象，创建对象时就需要指定容器大小，初始化指定大小的数组来存储元素，当我们插入元素时，如果已经插入了10个元素，还要继续插入数据，就会报错，不能插入了。这种设计不符合容器的设计理念，因此我们在设计顺序表时，应该考虑它的容量的伸缩性。
我们需要在添加元素、移除元素时考虑改变存储数据元素的数组大小。
public class Sequencelist<T> implements Iterable<T>
{ //存储元素的数组
private T[] eles;
//记录当前顺序表中的元素个数,不是数组长度！！！！！
private int N;
//构造方法
public Sequencelist(int capacity)
{ //初始化数组
this.eles=(T[])new object[capacity];//(T[])是强转类型
//初始化长度
this.N=0;
}
//将一个线性表置为空表
public void clear()
{
this.N=0;
}
//判断当线性表是否为空表
public boolean isEmpty()
{
return N==0;
}
//获取线性表的长度
public int length()
{
return N;
}
//获取指定位置的元素
public T get(int i)
{
return eles[i];
}
//向线性表中添加元素t
public void insert(T t)
{ if(N==eles.length())
{
resize(newSize:2*eles.length);//不够要扩容
}
eles[N++]=t;//不能是++N！！
}
//在i元素处插入元素t
public void insert(i,T t)
{
//先把i索引处的元素及其后面的元素依次向后移动一位
for(int index=N-1;index>i;index--)//N-1是最后一个元素的索引
{
eles[index]=eles[index-1];
}
//再把t元素放到i索引处即可
eles[i]=t;
//元素个数+1
N++;//不然结果中"麦迪"打印不出来
}
//删除指定位置i处的元素，并返回该元素
public T remove(int i)
{
//记录索引i处的值
int current = eles[i];
//索引i后面的元素依次向前移动一位即可
for(int index=i;index<N-1;index++)
{
eles[index]=eles[index+1];
}
//元素个数-1
N--;
if(N<eles.length/4)
{
resize(newSize:eles.length/2);//元素太少要减容
}
return current;
}
//查找t元素第一次出现的位置
public int indexOf(T t)
{
for(int i=0;i<N;i++)
{ if(eles[i].equals(t))
{
return i;
}
}
return -1;
}
//根据参数newSize，重置eles的大小
public void resize(int newSize)//改变顺序表的容量
{ //定义一个临时数组指向原数组
T[] temp=eles;
//创建新数组
eles =new Object[newsize];
//把原数组的数据拷贝到新数组
for(int i=0;i<N;i++)
{
eles[i]=temp[i];
}
}
@override//重写
public Iterator<T> iterator()
{
return new SIterator();
}
private class SIterator implements Iterator
{
private int cusor;
public SIterator()
{
this.cusor=0;
}
@override
public boolean hasNext()//判断容器中还有没有下一个元素
{
return cusor<N;
}
@override
public object next()//获取容器中的下一个元素
{
return eles[cusor++];
}
}
}再写一个SequenceListTest2来检验扩容缩容的操作是否正确:
public class SequenceListTest2
{
public static void main(string[] args)
{
SequenceList<String> sl =new SequenceList<>(capacity:3);
sl.insert(t:"张三");
sl.insert(t:"李四");
sl.insert(t:"王五");
sl.insert(t:"赵六");
}
}(5)顺序表的时间复杂度
get(i):不难看出，不论N有多大，只要一次eles[i]就可以获取到对应的元素，所以时间复杂度为O(1)
insert(int i,T t):每一次插入，都需要把i位置后面的元素移动一次，随着元素个数N的增大，移动的元素也就越多，时间复杂度为O(n);
remove(int i):每一次删除，都需要把i位置后面的元素移动一次，随着元素个数N的增大，移动的元素也就越多，时间复杂度为O(n);
由于顺序表的底层由数组实现，数组的长度是固定的，所以在操作的过程中涉及到了容器的扩容缩容操作。这样会导致顺序表在使用过程中的时间复杂度不是线性的，在某些需要扩容的结点处，耗时会突增，元素越多，问题越明显。
(链表会把这个问题解决掉)