数据结构
研究数据如何在计算机中进行组织和存储,从而高效的获取数据和修改数据
数据结构分为三类:
线性结构:数组、队列、栈、链表、哈希表...
树型结构:二叉树、二分搜索树、AVL树、红黑树、堆、Trie、线段树、并查集...
图结构:邻接矩阵、邻接表
数组
一、数组基础
1、数组的概念:用来存储一组相同数据类型的数据;
2、数组在内存中分配连续的空间,数组创建时要指定容量(大小);
3、初始化:数据类型[] 数组名 = new int[6];
数据类型[] 数组名 = {1,2,3,4,5,6};
4、索引--访问数组时通过索引进行操作
5、索引从0开始,最大为array.length-1
6、常见的数组:字符串、对象数组、哈希表
7、空指针:nullPoint NullPointException
8、数组越界:outofindex ArrayIndexOutOfBoundsException
- 使用数组时,最重要的就是数组的索引,通过索引可以对数组进行改和查操作。
索引:可以有语义,也可以没有语义(理解),
数组最好运用于索引有语义的情况;
数组最大的优点:快速查询。
三、基于java中的数组,进行二次封装,制作可变数组
- 定义属于自己的数组:
public class MySelfArray{ //数据容器 private T[] data; //实际保存数据的个数 private int size; MySelfArray(){ this(20); } MySelfArray(int capacity){ this.size = 0; data =(T[]) new Object [capacity]; } //判断数组是否为空 public boolean isEmpty() { return this.size == 0; }
- 向数组中添加元素
public void addTail(T ele) {
add(this.size,ele);
}
public void addHead(T ele) {
add(0,ele);
}
public void add(int index,T ele) {
//如果数组已满,进行扩容操作
if(index < 0 || index > size) {
throw new IllegalArgumentException("index is error");
}
if(this.size == data.length) {
resize(2 * data.length);
}
for (int i = size-1; i >= index; i--) {
data[i + 1] = data[i];
}
data[index] = ele;
this.size++;
}
向数组尾部添加元素
向指定位置添加元素
在指定位置添加元素
public T remove(int index) {
if(index < 0 || index >= size) {
throw new IllegalArgumentException("index is invalid");
}
T result = data[index];
for (int i = index + 1; i < size; i++) {
data[i-1] = data[i];
}
this.size -= 1;
data[size] = null;
//进行缩容操作
if(this.size == data.length / 2 && data.length / 2 > 0) {
resize(data.length/2);
}
return result;
}
public T removeHead() {
return remove(0);
}
public T removeTile() {
return remove(this.size -1);
}
public int removeEle(T ele) {
int index = isContains(ele);
if(index == -1) {
remove(index);
}
return index;
}
删除指定位置的元素
更改数组的容积:
public void resize(int newCapacity) {
T[] newData = (T[])new Object[2* data.length];
for (int i = 0; i < this.size; i++) {
newData[i] = data[i];
}
this.data = newData;
}
获取指定位置的元素:
public T getEleByIndex(int index) {
if(index < 0 || index >= size) {
throw new IllegalArgumentException("Index is error");
}
return data[index];
}
修改指定位置的元素:
public void updateByIndex(int index,T ele) {
if(index < 0 || index >= size) {
throw new IllegalArgumentException("Index is error");
}
data[index] = ele;
}
判断是否包含指定的元素内容:
public int isContains(T ele) {
for (int i = 0; i < this.size; i++) {
if(this.data[i].equals(ele)) {
return i;
}
}
return -1;
}
调用方法验证:
public static void main(String[] args) {
MySelfArray mySelfArray = new MySelfArray<>(10);
long startTime = System.nanoTime();
//进行添加操作
int cout = 100;
Random random = new Random();
for (int i = 0; i < cout; i++) {
mySelfArray.addTail(random.nextInt(Integer.MAX_VALUE));
}
System.out.println("数组" + mySelfArray);
while(!mySelfArray.isEmpty()) {
mySelfArray.removeTile();
}
long endTime = System.nanoTime();
System.out.println("总耗时:" + (endTime - startTime)/100000000.0);
//判断10是否存在于数组中
System.out.println("10是否存在: " + (mySelfArray.isContains(10) == -1 ? false : true));
MySelfArray strArray = new MySelfArray<>(5);
strArray.addTail("apple");
strArray.addTail("pear");
strArray.addTail("banana");
strArray.addTail("pineapple");
strArray.addTail("watermelon");
System.out.println(strArray);
System.out.println(strArray.isContains("watermelon") == -1 ? false : true);
}
}
练习:
package com.company.Demo01;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;
public class MySelfArray {
public static void main(String[] args) {
String[] fruits = {"apple","pear","watermelon","banana","pineapple"};
//Arrays.stream(fruits).forEach(System.out::println);
//Arrays.stream(fruits).forEach(item-> System.out.println(item));
int[] nums = new int[1000];
Random random = new Random();
for (int i = 0; i < 1000; i++) {
nums[i] = random.nextInt(100000);
}
//1.对每个数据+10
//2.过滤奇数
Arrays.stream(nums).map(item->item+10).filter(item->item%2>0).forEach(System.out::println);
String str = "ababccdddfghjhytrdcvv";
//统计每个字符出现的次数(字符串中只包含小写字母)
int[] counts = new int[26];
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
counts[c-'a']++;
}
for (int item: counts) {
System.out.println(item);
}
Map map = new HashMap<>();
}
}
简单的时间复杂度的分析
O(1),O(n),O(lgn),O(nlogn),O(n^2)
大O描述的是算法的运行时间和输入数据之间的关系
O(n)--忽略实际时间T = c1*n + c2
T = 2*n + 2
T = 2000*n + 1000 渐进时间复杂度
T = 1*n*n + 0 描述n趋近于无穷的情况
分析动态数组的时间复杂度
·添加操作 O(n)
删除操作:
修改操作:
查找操作:
增、删、改、查



