数组

最近在网上学习数据结构，打算在这里做一下学习笔记。（本文先按课上的Java代码实现，然后再用C++语言实现一遍）

数组基础

数组最大的优点：快速查询。数组与其他数据结构最大不同在于它有索引，可以方便直接访问第i个元素。数组最好应用于“索引有语意”的情况。但并非所用有语意的索引都适用于数组。故视实际情况而定。

本章课程主要是基于java的数组，二次封装属于我们自己的数组类。主要功能有：增、删、改、查。 Java

public class Array{ private int[] data;//使用private可保证类的封装性，使得外部无法修改 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; ｝ }

C++

class Arry{ private: int *data; int size; int capacity; public: Array(int capacity){ data = new int[capacity]; size = 0; this->capacity = capacity; } Array(){ data = new int[10]; size = 0; capacity = 10; } int getSize(){ return size; } int getCapacity(){ return capacity; } bool isEmpty(){ return size == 0; } }

向数组中添加元素

Java

//在所有元素后面添加一个新元素 public void addLast(int e){ //方法一：自己实现 if(size == data.length){ throw new IllegalArgumentException("添加失败.数组已满."); } data[size] = e; size++; //方法二：调用add函数 add(size,e); } //在所有元素前添加一个新元素 public void addFirst(int e){ add(0,e); } //在第index个位置插入一个新元素e public void add(int index,int e){ if(size == data.length){ throw new IllegalArgumentException("添加失败.数组已满."); } if(index < 0 || index >size){ //如果插入位置比size大的话会导致数组元素不连续，中间存在没插入的空格 throw new IllegalArgumentException("添加失败.需要index >= 0，并且index <= size"); } for(int i = size -1; i >= index; i--){ data[i+1] = data[i];//将index到size之间的所有数全部往后挪一个位置 } data[index] = e; size++; }

C++

public: void addLast(int e){ //方法一：自己实现 if(size == capacity){ printf("添加失败，数组已满."); } data[size] = e; size++; //方法二：调用add函数 add(size,e); } void add(int index,int e){ if(size == capacity){ printf("添加失败，数组已满."); } if(index < 0 || index > size){ printf("添加失败.需要index >= 0，并且index <= size"); } for(int i = size-1; i >= index; i--){ data[i + 1] = data[i]; } data[index] = e; size++; }

数组中查询元素和修改元素

Java

//获取index索引位置的元素 int get(int index){ if(index < 0 || index >= size) throw new IllegalArgumentException("获取失败.需要index >= 0，并且index <= size"); return data[index]; } //修改index索引位置的元素为e void set(int index,int e){ if(index < 0 || index >= size) throw new IllegalArgumentException("修改失败.需要index >= 0，并且index <= size"); data[index] = e; } //打印函数 @Override //覆盖覆盖父类的一个方法 public String toString(){ StringBuilder res = new StringBuilder(); res.append(String.format("Arrary: size = %d, capacity = %d\n",size,data.length)); res.append('['); for(int i = 0; i < size; i++){ res.append(data[i]); if(i != size - 1) res.append(","); } res.append(']'); return res.toString(); } //Main.java public class Main{ pubilc static void main(String[] args){ Array arr = new Array(20); for(int i = 0; i < 10; i++) arr.addLast(i); System.out.println(arr);//打印 } }

C++

public: int get(int index){ if(index < 0 || index >= size) printf("获取失败.需要index >= 0，并且index <= size"); return data[index]; } void set(int index,int e){ if(index < 0 || index >= size) printf("修改失败.需要index >= 0，并且index <= size"); data[index] = e; } //打印数组的所有元素 void printf(){ std::cout<<"Array ： size = "<<size<<",capacity = "<<getCapacity()<<std::endl; std::cout<<"["; for(int i = 0; i < size; i++){ std::cout<<data[i]; if(i != size - 1){ std::cout<<","; } } std::cout<<"]"<<endl; }

数组中的包含，搜索和删除元素

Java

//查找数组中是否有元素e public boolean contains(int e){ for(int i = 0; i <size;i++){ if(data[i] == e) return true; } return false; } //查找数组中元素e所在的索引，如果不存在元素e，则返回-1 public int find(int e){ for(int i = 0; i <size;i++){ if(data[i] == e) return i; } return -1; } //从数组中删除index位置的元素，返回删除的元素 public int remove(int index){ if(index < 0 || index >= size){ throw new IllegalArgumentException("删除失败.index不合法."); } int ret = data[index]; //将index后面的元素全部往前移一位 for(int i = index +1; i < size; i++){ data[i - 1] = data[i]; } size--; return ret } //从数组中删除第一个元素，返回删除的元素 public int removeFirst(){ return remove(0); } //从数组中删除最后一个元素，返回删除的元素 public int removeLast(){ return remove(size - 1); } //从数组中删除元素e，若有多个元素e只删除最开头的那一个 public void removeElement(int e){ int index = find(e); if(index != -1) remove(intdex); }

C++

//查找数组中是否有元素e public: bool contains(int e){ for(int i = 0; i <size;i++){ if(data[i] == e) return true; } return false; } int find(int e){ for(int i = 0; i <size;i++){ if(data[i] == e) return i; } return -1; } int remove(int index){ if(index < 0 || index >= size){ printf("删除失败.index不合法."); } int ret = data[index]; //将index后面的元素全部往前移一位 for(int i = index +1; i < size; i++){ data[i - 1] = data[i]; } size--; return ret } int removeFirst(){ return remove(0); } int removeLast(){ return remove(size - 1); } void removeElement(int e){ int index = find(e); if(index != -1) remove(intdex); }

使用泛型

让我们的数据结构可以放置“任何”数据类型不可以是基本数据类型，只能是类对象。即不能是boolean,byte,char,short,int,long,float,double每个基本数据类型都有对应的包装类，Boolean,Byte,Char, Short,Int,Long,Float,Double Java public class Array<E>{ private E[] data;//使用private可保证类的封装性，使得外部无法修改 private int size; //构造函数，传入数组的容量capacity构造Array public Array(int capacity){ data =(E[]) new Object[capacity];//Java不支持new一个泛型的数组 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; ｝ //在所有元素后面添加一个新元素 public void addLast(E e){ //方法一：自己实现 if(size == data.length){ throw new IllegalArgumentException("添加失败.数组已满."); } data[size] = e; size++; //方法二：调用add函数 add(size,e); } //在所有元素前添加一个新元素 public void addFirst(E e){ add(0,e); } //在第index个位置插入一个新元素e public void add(int index,E e){ if(size == data.length){ throw new IllegalArgumentException("添加失败.数组已满."); } if(index < 0 || index >size){ //如果插入位置比size大的话会导致数组元素不连续，中间存在没插入的空格 throw new IllegalArgumentException("添加失败.需要index >= 0，并且index <= size"); } for(int i = size -1; i >= index; i--){ data[i+1] = data[i];//将index到size之间的所有数全部往后挪一个位置 } data[index] = e; size++; } //获取index索引位置的元素 E get(int index){ if(index < 0 || index >= size) throw new IllegalArgumentException("获取失败.需要index >= 0，并且index <= size"); return data[index]; } //修改index索引位置的元素为e void set(int index, E e){ if(index < 0 || index >= size) throw new IllegalArgumentException("修改失败.需要index >= 0，并且index <= size"); data[index] = e; } //查找数组中是否有元素e public boolean contains(E e){ for(int i = 0; i <size;i++){ if(data[i].equals(e))//两个类对象进行值的比较 return true; } return false; } //查找数组中元素e所在的索引，如果不存在元素e，则返回-1 public int find(E e){ for(int i = 0; i <size;i++){ if(data[i].equals(e))//两个类对象进行值的比较 return i; } return -1; } //从数组中删除index位置的元素，返回删除的元素 public E remove(int index){ if(index < 0 || index >= size){ throw new IllegalArgumentException("删除失败.index不合法."); } E ret = data[index]; //将index后面的元素全部往前移一位 for(int i = index +1; i < size; i++){ data[i - 1] = data[i]; } size--; data[size] = null;//loitering objects != memory leak return ret } //从数组中删除第一个元素，返回删除的元素 public E removeFirst(){ return remove(0); } //从数组中删除最后一个元素，返回删除的元素 public E removeLast(){ return remove(size - 1); } //从数组中删除元素e，若有多个元素e只删除最开头的那一个 public void removeElement(E e){ int index = find(e); if(index != -1) remove(intdex); } //打印函数 @Override //覆盖覆盖父类的一个方法 public String toString(){ StringBuilder res = new StringBuilder(); res.append(String.format("Arrary: size = %d, capacity = %d\n",size,data.length)); res.append('['); for(int i = 0; i < size; i++){ res.append(data[i]); if(i != size - 1) res.append(","); } res.append(']'); return res.toString(); } } //Main.java public class Main{ pubilc static void main(String[] args){ Array<Integer> arr = new Array<>(20); for(int i = 0; i < 10; i++) arr.addLast(i); System.out.println(arr);//打印 } }

C++

//Array.h #include <cassert> #include <iostream> template<class T> class Array{ private: T *data; int size; int capacity; public: Array(int capacity) { data = new T[capacity]; size = 0; this->capacity = capacity; } Array() { data = new T[10]; size = 0; capacity = 10; } int getCapacity() { return capacity; } int getSize() { return size; } bool isEmpty() { return size == 0; } void add(int index, T e) { assert(size < capacity && index >= 0 && index <= size); for (int i = size - 1; i >= index; --i) { data[i + 1] = data[i]; } data[index] = e; size++; } void addFirst(T e) { add(0, e); } void addLast(T e) { add(size, e); } T get(int index) { assert(index >= 0 && index < size); return data[index]; } void set(int index, T e) { assert(index >= 0 && index < size); data[index] = e; } bool contains(T e) { for (int i = 0; i < size; ++i) { if (data[i] == e) { return true; } } return false; } int find(T e) { for (int i = 0; i < size; ++i) { if (data[i] == e) { return i; } } return -1; } T remove(int index) { assert(index >= 0 && index < size); T ret = data[index]; for (int i = index + 1; i < size; ++i) { data[i - 1] = data[i]; } size--; return ret; } T removeFirst() { return remove(0); } T removeLast() { return remove(size - 1); } void removeElement(T e) { int index = find(e); if (index != -1) { remove(index); } } //打印数组的所有元素 void printf(){ std::cout<<"Array ： size = "<<size<<",capacity = "<<getCapacity()<<std::endl; std::cout<<"["; for(int i = 0; i < size; i++){ std::cout<<data[i]; if(i != size - 1){ std::cout<<","; } } std::cout<<"]"<<endl; } }

动态数组

Java

//在第index个位置插入一个新元素e public void add(int index,E e){ if(index < 0 || index >size){ throw new IllegalArgumentException("添加失败.需要index >= 0，并且index <= size"); } if(size == data.length){ throw new IllegalArgumentException("添加失败.数组已满."); } for(int i = size -1; i >= index; i--){ resize(2 * data.length);//扩容两倍 } data[index] = e; size++; } //从数组中删除index位置的元素，返回删除的元素 public E remove(int index){ if(index < 0 || index >= size){ throw new IllegalArgumentException("删除失败.index不合法."); } E ret = data[index]; //将index后面的元素全部往前移一位 for(int i = index +1; i < size; i++){ data[i - 1] = data[i]; } size--; data[size] = null;//loitering objects != memory leak //当现在使用的空间减小到总容量的一半 if(size == data.length / 2) resize(data.length / 2); return ret; } private void resize(int newCapacity){ E[] newData = (E[])new Object[newCapacity]; for(int i = 0; i < size; i++){ newData[i] = data[i];//将原本data里面所有元素放进newData中 } data = newData;//将data指向newData空间 }

C++

public： void add(int index,E e){ if(index < 0 || index >size){ printf("添加失败.需要index >= 0，并且index <= size"); } if(size == data.length){ resize(2 * data.length);//扩容两倍 } for(int i = size -1; i >= index; i--){ data[i+1] = data[i]; } data[index] = e; size++; } T remove(int index){ if(index < 0 || index >= size){ throw new IllegalArgumentException("删除失败.index不合法."); } T ret = data[index]; //将index后面的元素全部往前移一位 for(int i = index +1; i < size; i++){ data[i - 1] = data[i]; } size--; //当现在使用的空间减小到总容量的一半 if(size == data.length / 2) resize(data.length / 2); return ret; } private: void resize(int newCapacity){ T newData = new T[newCapacity]; for(int i = 0; i < size; i++){ newData[i] = data[i];//将原本data里面所有元素放进newData中 } data = newData;//将data指向newData空间 capacity = newcapacity; }

简单的时间复杂度分析

O(1),O(n),O(lgn),O(nlogn),O(n^2)大O描述的是算法的运行时间和输入数据之间的关系。O翻译成中文为渐进时间复杂度，描述n趋近于无穷的情况。

数组添加操作 O(n) 数组删除操作 O(n) 数组修改操作 O(1) 由于支持随机访问。 数组查找操作 O(1)

均摊复杂度和防止复杂度的震荡

resize O(n) addLast的均摊复杂度为O(1) removeLast的均摊复杂度为O(1)

由于有可能存在刚好每次addLast一个元素，或removeLast一个元素刚好在n。会导致不停的调用resize()操作，进而导致时间复杂度为O(n)，这种问题称为复杂度震荡。 出现问题的原因：removeLast时resize过于着急。 改为size == capacity/4时，才将capacity减半。

Java

//从数组中删除index位置的元素，返回删除的元素 public E remove(int index){ if(index < 0 || index >= size){ throw new IllegalArgumentException("删除失败.index不合法."); } E ret = data[index]; //将index后面的元素全部往前移一位 for(int i = index +1; i < size; i++){ data[i - 1] = data[i]; } size--; data[size] = null;//loitering objects != memory leak //当现在使用的空间减小到总容量的四分之一时再缩容 if(size == data.length / 4 && data.length / 2 != 0) resize(data.length / 2); return ret; }

本文来源于慕课网上bobo老师上课内容。