《恋上数据结果与算法》- 动态数组

什么是数据结构

  • 数据结构是计算机存储，组织数据的方式

线性结构

  • 包括 线性表，数组，链表，栈，队列，哈希表
image.png

树形结构

  • 包括二叉树，AVL树，红黑树，B树，堆，Trie，哈夫曼树，并查集
image1.png

图形结构

  • 包括 邻接矩阵，邻接表
image2.png

线性表

  • 线性表是具有n个相同类型元素的有限序列(n >= 0)
image3.png
  • a1是首节点（首元素），an是尾节点（尾元素）
  • a1是a2的前驱，a2是a1的后继
  • 常见的线性表有
    • 数组
    • 链表
    • 栈
    • 队列
    • 哈希表（散列表）

数组

  • 数组是一种顺序存储的线性表，所有元素的内存地址都是连续的。
  • 例如:
int [] array = new int []{11,22,33};
  • 内存地址表现形式如下:
image4.png

注意：

  • 在很多编程语言中，数组都有一个致命的缺点，无法动弹修改容量
  • 在实际开发中，我们更期望数组的容量是可以动态改变的。
  • 解决方案：自己写一个动态数组

动态数组（Dynamic Array）接口设计

  • 需要的接口
    • int size(); // 元素的数量
    • boolean isEmpty(); // 是否为空
    • boolean contains(E element); // 是否包含某个元素
    • void add(E element); // 添加元素到最后面
    • E get(int index); // 返回index位置对应的元素
    • E set(int index, E element); // 设置index位置的元素
    • void add(int index, E element); // 往index位置添加元素
    • E remove(int index); // 删除index位置对应的元素
    • int indexOf(E element); // 查看元素的位置
    • void clear(); // 清除所有元素

动态数组的设计

  • 代码示例：
public class ArrayList<E> {
    /**
     * 元素的数量
     */
    private int size;
    /**
     * 所有的元素
     */
    private E[] elements;
    
    private static final int DEFAULT_CAPACITY = 10;
    private static final int ELEMENT_NOT_FOUND = -1;
    
    public ArrayList(int capaticy) {
        capaticy = (capaticy < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capaticy;
        elements = (E[]) new Object[capaticy];
    }
    
    public ArrayList() {
        this(DEFAULT_CAPACITY);
    }
    
    /**
     * 清除所有元素
     */
    public void clear() {
        for (int i = 0; i < size; i++) {
            elements[i] = null;
        }
        size = 0;
    }

    /**
     * 元素的数量
     * @return
     */
    public int size() {
        return size;
    }

    /**
     * 是否为空
     * @return
     */
    public boolean isEmpty() {
         return size == 0;
    }

    /**
     * 是否包含某个元素
     * @param element
     * @return
     */
    public boolean contains(E element) {
        return indexOf(element) != ELEMENT_NOT_FOUND;
    }

    /**
     * 添加元素到尾部
     * @param element
     */
    public void add(E element) {
        add(size, element);
    }

    /**
     * 获取index位置的元素
     * @param index
     * @return
     */
    public E get(int index) {
        rangeCheck(index);
        return elements[index];
    }

    /**
     * 设置index位置的元素
     * @param index
     * @param element
     * @return 原来的元素ֵ
     */
    public E set(int index, E element) {
        rangeCheck(index);
        
        E old = elements[index];
        elements[index] = element;
        return old;
    }

    /**
     * 在index位置插入一个元素
     * @param index
     * @param element
     */
    public void add(int index, E element) {
        rangeCheckForAdd(index);
        
        ensureCapacity(size + 1);
        
        for (int i = size - 1; i >= index; i--) {
            elements[i + 1] = elements[i];
        }
        elements[index] = element;
        size++;
    }

    /**
     * 删除index位置的元素
     * @param index
     * @return
     */
    public E remove(int index) {
        rangeCheck(index);
        
        E old = elements[index];
        for (int i = index + 1; i <= size - 1; i++) {
            elements[i - 1] = elements[i];
        }
        elements[--size] = null;
        return old;
    }

    /**
     * 查看元素的索引
     * @param element
     * @return
     */
    public int indexOf(E element) {
        if (element == null) {
            for (int i = 0; i < size; i++) {
                if (elements[i] == null) return i;
            }
        } else {
            for (int i = 0; i < size; i++) {
                if (element.equals(elements[i])) return i;
            }
        }
        return ELEMENT_NOT_FOUND;
    }
    
    /**
     * 保证要有capacity的容量
     * @param capacity
     */
    private void ensureCapacity(int capacity) {
        int oldCapacity = elements.length;
        if (oldCapacity >= capacity) return;
        
        // 新容量为旧容量的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        E[] newElements = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newElements[i] = elements[i];
        }
        elements = newElements;
        
        System.out.println(oldCapacity + "扩容为" + newCapacity);
    }
    
    private void outOfBounds(int index) {
        throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
    }
    
    private void rangeCheck(int index) {
        if (index < 0 || index >= size) {
            outOfBounds(index);
        }
    }
    
    private void rangeCheckForAdd(int index) {
        if (index < 0 || index > size) {
            outOfBounds(index);
        }
    }
    
    @Override
    public String toString() {
        // size=3, [99, 88, 77]
        StringBuilder string = new StringBuilder();
        string.append("size=").append(size).append(", [");
        for (int i = 0; i < size; i++) {
            if (i != 0) {
                string.append(", ");
            }
            
            string.append(elements[i]);
            
//          if (i != size - 1) {
//              string.append(", ");
//          }
        }
        string.append("]");
        return string.toString();
    }
}
分析：
  • 首先要有成员变量，至少包含两个成员变量，一个是size元素的数量，一个是存放元素的elements；
/**
     * 元素的数量
     */
    private int size;
    /**
     * 所有的元素
     */
    private int[] elements;
image6.png
分析：
  • 首先要有成员变量，至少包含两个成员变量，一个是size元素的数量，一个是存放元素的elements；
/**
     * 元素的数量
     */
    private int size;
    /**
     * 所有的元素
     */
    private int[] elements;
  • 构造函数传入容量，然后开辟内存；
private static final int DEFAULT_CAPACITY = 10;
    private static final int ELEMENT_NOT_FOUND = -1;
    
    public ArrayList(int capaticy) {
        capaticy = (capaticy < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capaticy;
        elements = new int[capaticy];
    }
    
    public ArrayList() {
        this(DEFAULT_CAPACITY);
    }

增加元素 - add(E element)

  • 当size等于什么的时候，往什么位置存元素；
image7.png

打印数组

  • 如果想打印数组，string.toString()这个方法；

    • 重写toString方法
    • 在toString方法中将元素拼接成字符串
    • 字符串拼接建议使用StringBuilder

  • 代码示例：

@Override
public String toString() {
    // size=3, [99, 88, 77]
    StringBuilder string = new StringBuilder();
    string.append("size=").append(size).append(", [");
    for (int i = 0; i < size; i++) {
        if (i != 0) {
            string.append(", ");
        }
            
        string.append(elements[i]);
            
//      if (i != size - 1) {
//          string.append(", ");
//      }
    }
    string.append("]");
    return string.toString();
}

删除元素 - remove(int index)

image8.png
  • 本质：是往前挪一位，后面的赋值前面的，让size--;
  • 代码示例
/**
     * 删除index位置的元素
     * @param index
     * @return
     */
    public E remove(int index) {
        rangeCheck(index);
        
        E old = elements[index];
        for (int i = index + 1; i <= size - 1; i++) {
            elements[i - 1] = elements[i];
        }
        elements[--size] = null;
        return old;
    }
  • 最后一个元素：不做处理；

增加元素 - add(int index, E element)

  • 代码示例：
/**
* 在index位置插入一个元素
* @param index
* @param element
*/
public void add(int index, E element) {
    rangeCheckForAdd(index);
        
    ensureCapacity(size + 1);//保证容量
        
    for (int i = size - 1; i >= index; i--) {
        elements[i + 1] = elements[i];
    }
    elements[index] = element;
    size++;
}
  • 封装范围方法
private void outOfBounds(int index) {
    throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
}
    
private void rangeCheck(int index) {
    if (index < 0 || index >= size) {
        outOfBounds(index);
    }
}

private void rangeCheckForAdd(int index) {
    if (index < 0 || index > size) {
        outOfBounds(index);
    }
}
  • 添加末尾元素
/**
* 添加元素到尾部
* @param element
*/
public void add(E element) {
        add(size, element);
}

如何扩容

image10.png
  • 代码示例：
/**
     * 保证要有capacity的容量
     * @param capacity
     */
private void ensureCapacity(int capacity) {
    int oldCapacity = elements.length;
    if (oldCapacity >= capacity) return;
        
    // 新容量为旧容量的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    E[] newElements = (E[]) new Object[newCapacity];
    for (int i = 0; i < size; i++) {
        newElements[i] = elements[i];
    }
    elements = newElements;
        
    System.out.println(oldCapacity + "扩容为" + newCapacity);
}
  • 补充：oldCapacity >> 1位运算

位运算

  • 概述
    • 从现代计算机中所有的数据二进制的形式存储在设备中。即0、1两种状态，计算机对二进制数据进行的运算(+、-、*、/)都是叫位运算，即将符号位共同参与运算的运算。
    • 相比在代码中直接使用(+、-、*、/)运算符，合理的运用位运算更能显著提高代码在机器上的执行效率。
符号 描述 运算规则
& 与 两个位都为1时，结果才为1
l 或 两个位都为0时，结果才为0
^ 异或 两个位相同为0，相异为1
~ 取反 0变1，1变0
<< 左移 各二进位全部左移若干位，高位丢弃，低位补0
>> 右移 各二进位全部右移若干位，对无符号数，高位补0，有符号数，各编译器处理方法不一样，有的补符号位（算术右移），有的补0（逻辑右移）

泛型

  • 使用泛型技术可以让动态数组更加通用，可以存放任何数据类型
  • 在java里面用E表示，如下：
image11.png

对象数组

  • 实质是放的内存地址；

Object[] object = new Object[7];
image12.png
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 206,839评论 6赞 482
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 88,543评论 2赞 382
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 153,116评论 0赞 344
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 55,371评论 1赞 279
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 64,384评论 5赞 374
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 49,111评论 1赞 285
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,416评论 3赞 400
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 37,053评论 0赞 259
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 43,558评论 1赞 300
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,007评论 2赞 325
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,117评论 1赞 334
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,756评论 4赞 324
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,324评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,315评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,539评论 1赞 262
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 45,578评论 2赞 355
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,877评论 2赞 345