数据结构与算法基础（数据结构与算法）
数据结构与算法基础（数据结构与算法）数组：是一种顺序存储的线性表，所有元素的内存地址是连续的。 int[] array=new int[]{11 22 33}； 定义一个含有11 22 33 的数组。数组栈堆内存空间图如上图所示：a1是首节点 ，an 是尾结点，a1是a2的前驱 ， a2是a1的后继。 日常中有很多线性表的例子： 比如冰糖葫芦，排成一列的乒乓球等等。7.数组大O表示法来描述复杂度 它表示是数据规模n对应的复杂度 仅仅只是一种粗略的分析模型。 注：忽略常数、系数、低阶。 9 >> O(1) 2n 3 >> O(n) n*n 2n 5 O(n*n) 4n*n*n 3n*n 22n 100 >> O(n*n*n)5.数据结构数据结构是计算机存储、组织数据的方式 包括：线性结构：线性表 （数组、链表、栈、哈希表） 树形结构：二叉树、A
1.算法： 是用于解决特定问题的一系列的执行步骤。
2.评价算法
如何评判一个算法的好坏，一般从以下维度进行评估算法的优劣：
1.正确性、可读性、健壮性（对不合理的反应的解决能力）。
2.时间复杂度：估算程序指令的执行次数（执行时间）。
3.空间复杂度： 估算所需占用的存储空间。
注：每日的数据结构与算法采用JAVA来进行实现与讲解。
3.时间复杂度
估算程序指令的执行次数：
如：
1.for(int i=0;i<n ; i )
int i =0 ； 执行一次
i< n ; 执行 n次
i ; 执行 n 次
总的执行次数为 2n 1
2. for(int i=0;i<n ; i ) {
for (int j = 0; j < n; j ) {
System.out.println("test");
}
}
总的执行次数为 3n^2 3n 1
3. while((n=n/2)>0){
System.out.println("test");
}
分析：
8 /2 4
4/ 2 2
2 / 2 1
总的执行次数为 log2(n)。
4.大O表示法
大O表示法来描述复杂度 它表示是数据规模n对应的复杂度 仅仅只是一种粗略的分析模型。
注：忽略常数、系数、低阶。
9 >> O(1)
2n 3 >> O(n)
n*n 2n 5 O(n*n)
4n*n*n 3n*n 22n 100 >> O(n*n*n)
5.数据结构
数据结构是计算机存储、组织数据的方式
包括：线性结构：线性表 （数组、链表、栈、哈希表）
树形结构：二叉树、AVL树、红黑树、B树、堆、Tree、哈夫曼树
图形结构：邻接矩阵、邻接表
我们先从线性结构说起。
6.线性表：具有n个相同类型元素的有限序列。（n>=0）
线性表图例
如上图所示：a1是首节点 ，an 是尾结点，a1是a2的前驱 ， a2是a1的后继。
日常中有很多线性表的例子： 比如冰糖葫芦，排成一列的乒乓球等等。
7.数组
数组：是一种顺序存储的线性表，所有元素的内存地址是连续的。
int[] array=new int[]{11 22 33}； 定义一个含有11 22 33 的数组。
数组栈堆内存空间图
数组存在一个致命的缺点：无法动态修改容量，而我们在实际开发中希望容量可以动态改变，所以
进行动态数组的创建，实现数据可以动态修改容量。
8.动态数组创建
创建一个动态数组实现的是可以向数组中进行增删改查，并且当增加值时数组内存地址可以保证够用，
当数组内存地址不够用时，可以随时进行添加，所以一个动态数组需要包含：
1.指向堆空间一数组地址
2.数组的长度
动态数组包含属性
9.实现常用功能
动态数组基本常用功能（参考jdk源码 ArrayList源码） 这里数组中存储就以整数来进行举例。
int size(); //元素的数量
boolean isEmpty(); //是否为空
boolean contains(int element); // 是否包含某个元素
void add(int element); // 添加元素到最后面
int get(int index); // 返回index位置对应的元素
int set(int index int element); // 设置index位置添加元素
void add(int index int element); // 往index位置添加元素
int remove(int index); // 删除index位置对应的元素
int indexOf(int element); //查看元素的位置
void clear(); // 清除所有的元素
10.动态数组初始化
public class DynamicArray implements PublicInterface { publicInterface 是实现功能方法接口
/**
* 元素的数量
*/
private int size;
/**
* 所有的元素
*/
private int[] elements;
// 数组默认长度 这里设置默认长度为10 可自行调整
private static final int NOT_DATA_FIND =10 ;
// 定义 传值的构造方法 如果传入的值大于 默认值 采用创建传入值的数组长度
public DynamicArray (int capacity){
capacity = (capacity < DEFAULT_CAPACITY ) ? DEFAULT_CAPACITY: capacity;
elements = new int[capacity];
}
// 默认创建为10 的数组
public DynamicArray (){
this(DEFAULT_CAPACITY);
}
11.元素数量、 是否为空等功能实现
/**
* 元素的数量
*/
@Override
public int size() {
return size; // 直接返回size显示数组长度
}
// 如果size 为 0 代表动态数组为空
/**
* 是否为空
* @return
*/
@Override
public boolean isEmpty() {
return size == 0;
}
/**
* 查看元素所在的位置
* @param element
* @return
*/
@Override
public int indexOf(int element) {
for (int i=0 ; i < size ;i ){
if (elements[i] == element ) return i;
}
return NOT_DATA_FIND; // 静态常量为-1
}
/**
* 是否包含某个元素
* @param element
* @return
*/
@Override
public boolean contains(int element) {
return indexOf(element) == NOT_DATA_FIND; // 静态常量为-1
}
/**
* 清除所有的元素
*/
@Override
public void clear() {
size = 0 ; // 重复利用内存空间
}
注： 这里情况数组直接设置size为0 即可：
DynamicArray array = new DynamicArray();
array.add(11); // add实现方法下面会进行讲解 当调用添加方法是 size ，如果将size设置为0
调用获取数据或其他方法就不可以实现，从程序外部来看数据已经被清空了，因为这里数组存储的是
整数，如果存储的是对象，需要遍历数组将每个对象设置为null，再设置size为0 ，防止内存一直占用。
12.元素位置 、元素添加等功能实现
/**
* 返回index位置对应的元素
* @param index
* @return
*/
@Override
public int get(int index) {
if(index < 0 || index >= size){
// 不符合条件抛出异常
throw new IndexOutOfBoundsException("Index:" index " " "Size" size);
}
return elements[index];
}
/**
* 设置index位置元素
* @param index
* @param element
* @return
*/
@Override
public int set(int index int element) {
if(index < 0 || index >= size){
throw new IndexOutOfBoundsException("Index:" index " " "Size" size);
}
// 获取以前位置元素
int old = elements[index];
elements[index] = element;
return old;
}
/**
* 往index位置添加元素
* @param index
* @param element
*/
@Override
public void add(int index int element) {
// 这里如果是在size位置上添加，所以可以包含size
if(index < 0 || index > size){
throw new IndexOutOfBoundsException("Index:" index " " "Size" size);
}
for (int i = size - 1 ; i >= index ; i--){
elements[i 1] = elements[i];
}
elements[index] = element ;
size ;
}
/**
* 添加元素到最后面
* @param element
*/
@Override
public void add(int element) {
add(size element);
}
插入元素原则按照size进行
错误添加覆盖顺序（从后往前）
13.动态数组元素删除实现
/**
* 删除index位置对应的元素
* @param index
* @return
*/
@Override
public int remove(int index) {
if(index < 0 || index >= size){
throw new IndexOutOfBoundsException("Index:" index " " "Size" size);
}
int old = elements[index];
for (int i = index 1 ; i <= size -1 ; i ) {
elements[i - 1] = elements[i];
}
size -- ;
return old;
}
删除元素前移元素
14.扩容
当向动态数组中进行添加元素时，需要进行判断数组内存地址是否够用，不够用需要进行扩容。
// 不够用时新创建一个新的数组，是原有的1.5倍，再将数据元素迁移到新的数组地址。
private void Ensurecapacity(int capacity){
int oldCapacity = elements.length;
if(oldCapacity >= capacity) return;
// 新容量为旧容量的1.5倍
int newCapacity = oldCapacity (oldCapacity >> 1);
int[] newElements = new int[newCapacity];
for (int i = 0 ; i < size ; i ){
newElements[i] = elements[i];
}
elements = newElements;
System.out.println("扩容" elements.length);
}
在添加元素时调用检查。
