Python+Java+Go实现数据结构第一篇：数组
Java中的数组回顾
package com.eric.array;
public class Main {
public static void main(String[] args) {
// Java中数组只能声明同一种类型
int[] arr = new int[10];
for(int i = 0 ; i < arr.length ; i ++)
arr[i] = i;
int[] scores = new int[]{100, 99, 66, 88};
for(int i = 0 ; i < scores.length ; i ++)
System.out.println(scores[i]);
//java中的for each 循环
for(int score: scores)
System.out.println(score);
// 赋值
scores[0] = 96;
for (int score: scores) {
System.out.println(score);
}
}
}
package com.eric.array;
public class 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 getCapacity(){
return data.length;
}
// 获取数组中的元素个数
public int getSize(){
return size;
}
// 返回数组是否为空
public boolean isEmpty(){
return size == 0;
}
}
package com.eric.array;
public class 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 getCapacity(){
return data.length;
}
// 获取数组中的元素个数
public int getSize(){
return size;
}
// 返回数组是否为空
public boolean isEmpty(){
return size == 0;
}
// 向所有元素后添加一个新元素
public void addLast(int e){
// if(size == data.length)
// throw new IllegalArgumentException("AddLast failed. Array is full.");
//
// data[size] = e;
// size ++;
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("Add failed. Array is full.");
if(index < 0 || index > size)
throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");
for(int i = size - 1; i >= index ; i --)
data[i + 1] = data[i];
data[index] = e;
size ++;
}
}
查询
package com.eric.array;
public class 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 getCapacity(){
return data.length;
}
// 获取数组中的元素个数
public int getSize(){
return size;
}
// 返回数组是否为空
public boolean isEmpty(){
return size == 0;
}
// 向所有元素后添加一个新元素
public void addLast(int e){
// if(size == data.length)
// throw new IllegalArgumentException("AddLast failed. Array is full.");
//
// data[size] = e;
// size ++;
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("Add failed. Array is full.");
if(index < 0 || index > size)
throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");
for(int i = size - 1; i >= index ; i --)
data[i + 1] = data[i];
data[index] = e;
size ++;
}
// 获取index索引位置的元素
public int get(int index){
if(index < 0 || index >= size)
throw new IllegalArgumentException("Get failed. Index is illegal.");
return data[index];
}
// 修改index索引位置的元素为e
public void set(int index, int e){
if(index < 0 || index >= size)
throw new IllegalArgumentException("Set failed. Index is illegal.");
data[index] = e;
}
@Override
public String toString(){
StringBuilder res = new StringBuilder();
res.append(String.format("Array: 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();
}
}
使用泛型
public class Array<E> {
private E[] data;
private int size;
// 构造函数，传入数组的容量capacity构造Array
public Array(int capacity){
data = (E[])new Object[capacity];
size = 0;
}
// 无参数的构造函数，默认数组的容量capacity=10
public Array(){
this(10);
}
// 获取数组的容量
public int getCapacity(){
return data.length;
}
// 获取数组中的元素个数
public int getSize(){
return size;
}
// 返回数组是否为空
public boolean isEmpty(){
return size == 0;
}
// 在index索引的位置插入一个新元素e
public void add(int index, E e){
if(size == data.length)
throw new IllegalArgumentException("Add failed. Array is full.");
if(index < 0 || index > size)
throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");
for(int i = size - 1; i >= index ; i --)
data[i + 1] = data[i];
data[index] = e;
size ++;
}
// 向所有元素后添加一个新元素
public void addLast(E e){
add(size, e);
}
// 在所有元素前添加一个新元素
public void addFirst(E e){
add(0, e);
}
// 获取index索引位置的元素
public E get(int index){
if(index < 0 || index >= size)
throw new IllegalArgumentException("Get failed. Index is illegal.");
return data[index];
}
// 修改index索引位置的元素为e
public void set(int index, E e){
if(index < 0 || index >= size)
throw new IllegalArgumentException("Set failed. Index is illegal.");
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("Remove failed. Index is illegal.");
E ret = data[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
public void removeElement(E e){
int index = find(e);
if(index != -1)
remove(index);
}
@Override
public String toString(){
StringBuilder res = new StringBuilder();
res.append(String.format("Array: 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();
}
}
编写student类
public class Student {
private String name;
private int score;
public Student(String studentName, int studentScore){
name = studentName;
score = studentScore;
}
@Override
public String toString(){
return String.format("Student(name: %s, score: %d)", name, score);
}
public static void main(String[] args) {
Array<Student> arr = new Array<>();
arr.addLast(new Student("Alice", 100));
arr.addLast(new Student("Bob", 66));
arr.addLast(new Student("Charlie", 88));
System.out.println(arr);
}
}
测试
public class Main {
public 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);
arr.add(1, 100);
System.out.println(arr);
arr.addFirst(-1);
System.out.println(arr);
// [-1, 0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]
arr.remove(2);
System.out.println(arr);
arr.removeElement(4);
System.out.println(arr);
arr.removeFirst();
System.out.println(arr);
}
}
动态数组
public class Array<E> {
private E[] data;
private int size;
// 构造函数，传入数组的容量capacity构造Array
public Array(int capacity){
data = (E[])new Object[capacity];
size = 0;
}
// 无参数的构造函数，默认数组的容量capacity=10
public Array(){
this(10);
}
// 获取数组的容量
public int getCapacity(){
return data.length;
}
// 获取数组中的元素个数
public int getSize(){
return size;
}
// 返回数组是否为空
public boolean isEmpty(){
return size == 0;
}
// 在index索引的位置插入一个新元素e
public void add(int index, E e){
if(index < 0 || index > size)
throw new IllegalArgumentException("Add failed. Require index >= 0 and 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 ++;
}
// 向所有元素后添加一个新元素
public void addLast(E e){
add(size, e);
}
// 在所有元素前添加一个新元素
public void addFirst(E e){
add(0, e);
}
// 获取index索引位置的元素
public E get(int index){
if(index < 0 || index >= size)
throw new IllegalArgumentException("Get failed. Index is illegal.");
return data[index];
}
// 修改index索引位置的元素为e
public void set(int index, E e){
if(index < 0 || index >= size)
throw new IllegalArgumentException("Set failed. Index is illegal.");
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("Remove failed. Index is illegal.");
E ret = data[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;
}
// 从数组中删除第一个元素, 返回删除的元素
public E removeFirst(){
return remove(0);
}
// 从数组中删除最后一个元素, 返回删除的元素
public E removeLast(){
return remove(size - 1);
}
// 从数组中删除元素e
public void removeElement(E e){
int index = find(e);
if(index != -1)
remove(index);
}
@Override
public String toString(){
StringBuilder res = new StringBuilder();
res.append(String.format("Array: 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();
}
// 将数组空间的容量变成newCapacity大小
private void resize(int newCapacity){
E[] newData = (E[])new Object[newCapacity];
for(int i = 0 ; i < size ; i ++)
newData[i] = data[i];
data = newData;
}
}
测试
public class Main {
public static void main(String[] args) {
Array<Integer> arr = new Array<>();
for(int i = 0 ; i < 10 ; i ++)
arr.addLast(i);
System.out.println(arr);
arr.add(1, 100);
System.out.println(arr);
arr.addFirst(-1);
System.out.println(arr);
arr.remove(2);
System.out.println(arr);
arr.removeElement(4);
System.out.println(arr);
arr.removeFirst();
System.out.println(arr);
}
}
Python版本
# -*- coding: utf-8 -*-
# @Time : 2019/11/15 15:30
# @Author : Eric Lee
# @File : array.py
# @Software: PyCharm
class Array(object):
def __init__(self, arr=None, capacity=10):
if isinstance(arr, list):
self._data = arr[:]
self._size = len(arr)
return
self._data = [None] * capacity
self._size = 0
def get_size(self):
return self._size
def get_capacity(self):
return len(self._data)
def is_empty(self):
return self._size == 0
def add_last(self, e):
self.add(self._size, e)
def add_first(self, e):
self.add(0, e)
def add(self, index, e):
"""从后往前"""
if not 0 <= index <= self._size:
raise ValueError(
'add failed. Require index >= 0 and index <= array sise.')
if self._size == len(self._data):
if self._size == 0:
self._resize(1)
else:
self._resize(2 * len(self._data))
for i in range(self._size - 1, index - 1, -1):
self._data[i + 1] = self._data[i]
self._data[index] = e
self._size += 1
def get(self, index):
if not 0 <= index < self._size:
raise ValueError('get failed. Index is illegal.')
return self._data[index]
def get_last(self):
return self.get(self._size - 1)
def get_first(self):
return self.get(0)
def set(self, index, e):
if not 0 <= index < self._size:
raise ValueError('set failed. Index is illegal.')
self._data[index] = e
def contains(self, e):
for i in range(self._size):
if self._data[i] == e:
return True
return False
def find_index(self, e):
for i in range(self._size):
if self._data[i] == e:
return i
return -1
def remove(self, index):
if not 0 <= index < self._size:
raise ValueError('remove failed. Index is illegal.')
ret = self._data[index]
for i in range(index + 1, self._size):
self._data[i - 1] = self._data[i]
self._size -= 1
# len(self._data)如果为1，len(self._data) // 2就会为0，不合理。
if (self._size == len(self._data) // 4 and len(self._data) // 2 != 0):
self._resize(len(self._data) // 2)
return ret
def remove_first(self):
return self.remove(0)
def remove_last(self):
return self.remove(self._size - 1)
def remove_element(self, e):
index = self.find_index(e)
if index != -1:
self.remove(index)
def _resize(self, new_capacity):
new_data = [None] * new_capacity
for i in range(self._size):
new_data[i] = self._data[i]
self._data = new_data
def swap(self, i, j):
if i < 0 or i >= self._size or j < 0 or j >= self._size:
raise ValueError('Index is illegal.')
self._data[i], self._data[j] = self._data[j], self._data[i]
def __str__(self):
return str('<chapter_02_Array.array.Array> : {}, capacity: {}'.format(self._data[:self._size], self.get_capacity()))
def __repr__(self):
return self.__str__()
if __name__ == '__main__':
arr = Array()
for i in range(10):
arr.add_last(i)
print(arr.get_capacity())
# arr.add_last('zhe')
# arr.add_last('wang')
# arr.add_last('zwang')
arr.add(1, 'zwang')
print(arr.get_capacity())
arr.remove_element('zwang')
print(arr)
arr.add_first(-1)
print(arr)
arr.remove_element(8)
print(arr)
arr.remove_element('zhe')
print(arr)
Go语言版本
package Array
import (
"bytes"
"fmt"
)
type Array struct {
data []interface{}
size int
}
// 构造函数，传入数组的容量capacity构造Array
func Constructor(capacity int) *Array {
return &Array{
data: make([]interface{}, capacity),
}
}
// 获取数组的容量
func (this *Array) GetCapacity() int {
return len(this.data)
}
// 获得数组中的元素个数
func (this *Array) GetSize() int {
return this.size
}
// 返回数组是否为空
func (this *Array) IsEmpty() bool {
return this.size == 0
}
// 在第 index 个位置插入一个新元素 e
func (this *Array) Add(index int, e interface{}) {
if index < 0 || index > this.size {
panic("Add failed. Require index >= 0 and index <= size.")
}
if this.size == len(this.data) {
this.resize(2 * this.size)
}
for i := this.size - 1; i >= index; i-- {
this.data[i+1] = this.data[i]
}
this.data[index] = e
this.size++
}
// 向所有元素后添加一个新元素
func (this *Array) AddLast(e interface{}) {
this.Add(this.size, e)
}
// 向所有元素前添加一个新元素
func (this *Array) AddFirst(e interface{}) {
this.Add(0, e)
}
// 获取 index 索引位置的元素
func (this *Array) Get(index int) interface{} {
if index < 0 || index >= this.size {
panic("Get failed. Index is illegal.")
}
return this.data[index]
}
// 修改 index 索引位置的元素
func (this *Array) Set(index int, e interface{}) {
if index < 0 || index >= this.size {
panic("Set failed. Index is illegal.")
}
this.data[index] = e
}
// 查找数组中是否有元素 e
func (this *Array) Contains(e interface{}) bool {
for i := 0; i < this.size; i++ {
if Interfaces.Compare(this.data[i], e) == 0 {
return true
}
}
return false
}
// 查找数组中元素 e 所在的索引，不存在则返回 -1
func (this *Array) Find(e interface{}) int {
for i := 0; i < this.size; i++ {
if Interfaces.Compare(this.data[i], e) == 0 {
return i
}
}
return -1
}
// 查找数组中元素 e 所有的索引组成的切片，不存在则返回 -1
func (this *Array) FindAll(e interface{}) (indexes []int) {
for i := 0; i < this.size; i++ {
if Interfaces.Compare(this.data[i], e) == 0 {
indexes = append(indexes, i)
}
}
return
}
// 从数组中删除 index 位置的元素，返回删除的元素
func (this *Array) Remove(index int) interface{} {
if index < 0 || index >= this.size {
panic("Set failed. Index is illegal.")
}
e := this.data[index]
for i := index + 1; i < this.size; i++ {
this.data[i-1] = this.data[i]
}
this.size--
this.data[this.size] = nil //loitering object != memory leak
if this.size == len(this.data)/2 {
this.resize(len(this.data) / 2)
}
return e
}
// 从数组中删除第一个元素，返回删除的元素
func (this *Array) RemoveFirst() interface{} {
return this.Remove(0)
}
// 从数组中删除最后一个元素，返回删除的元素
func (this *Array) RemoveLast() interface{} {
return this.Remove(this.size - 1)
}
// 从数组中删除一个元素 e
func (this *Array) RemoveElement(e interface{}) bool {
index := this.Find(e)
if index == -1 {
return false
}
this.Remove(index)
return true
}
// 从数组中删除所有元素 e
func (this *Array) RemoveAllElement(e interface{}) bool {
if this.Find(e) == -1 {
return false
}
for i := 0; i < this.size; i++ {
if Interfaces.Compare(this.data[i], e) == 0 {
this.Remove(i)
}
}
return true
}
// 为数组扩容
func (this *Array) resize(newCapacity int) {
newData := make([]interface{}, newCapacity)
for i := 0; i < this.size; i++ {
newData[i] = this.data[i]
}
this.data = newData
}
// 重写 Array 的 string 方法
func (this *Array) String() string {
var buffer bytes.Buffer
buffer.WriteString(fmt.Sprintf("Array: size = %d, capacity = %d\n", this.size, len(this.data)))
buffer.WriteString("[")
for i := 0; i < this.size; i++ {
// fmt.Sprint 将 interface{} 类型转换为字符串
buffer.WriteString(fmt.Sprint(this.data[i]))
if i != (this.size - 1) {
buffer.WriteString(", ")
}
}
buffer.WriteString("]")
return buffer.String()
}
测试
package main
import (
"Play-with-Data-Structures/02-Arrays/07-Dynamic-Array/src/Array"
"fmt"
)
func main() {
arr := Array.Constructor(10)
for i := 0; i < 10; i++ {
arr.AddLast(i)
}
fmt.Println(arr)
arr.Add(1, 100)
fmt.Println(arr)
arr.AddFirst(-1)
fmt.Println(arr)
}
