数据结构基础-阿里云开发者社区

开发者社区> rhwayfun> 正文

数据结构基础

简介:
+关注继续查看

在Java研发工程师招聘中,数据结构与算法是必考的题目,不久看到一篇文章《为什么面试总喜欢考算法题》提到:面试考算法是一个基准点,因为算法是计算机学科中最基础的学科。本着不死也脱层皮的想法就买了本算法书开始啃,虽然其中很多题目我就是想破脑汁也想出来,可我居然能沉浸在这样的状态中自得其乐。“算法虐我千百遍,我仍待它如初恋”。

顺序存储结构

顺序存储结构数据存在内存地址连续的一块区域,数组便是这种存储结构的典型表现。由于是在一块的内存区域,只要确定第一个元素的内存地址,后面的元素就可以在这快区域上随机存取。下面的示意图展示了顺序存储结构在内存中的存储形式:

顺序存储结构

数组实现顺序存储结构

使用数组实现顺序存储结构的主要操作有:查找数据、插入数据和删除数据,其中插入数据和删除数据是本算法中更为核心的部分,因为在数组中要要插入一个数据,必须把数据往后面移动,而且还要考虑是否会出现数组下标越界的情况。删除操作也是一样,要从一个数组中删除一个数据不是不是一件易事(至少从计算机层面来讲是这样的),每次删除一个数据需要把数据往前面移动。下面请看核心代码实现:

    public class ListArray implements List {

    //数组容量
    private int len = 8;
    //数组中元素的个数
    private int size;
    //数组之间元素的比较策略
    private Strategy strategy;
    //用于装载数据元素的数组
    private Object[] elements;

    public ListArray(){
        this(new DefaultStrategy());
    }

    public ListArray(Strategy strategy) {
        this.strategy = strategy;
        size = 0;
        elements = new Object[len];
    }
    //获取第i位置上元素
    public Object get(int i) {
        if(i < 0 || i > size){
            System.out.println("下标越界,获取失败!");
            return null;
        }
        return elements[i];
    }
    //在第i个位置插入数据元素e
    public boolean insert(int i, Object e) throws OutOfBoundException {
        if(i < 0 || i > size){
            System.out.println("下标越界,插入失败!");
            return false;
        }else{
            //如果数组中元素的大小超过了数组的容量,则增大数组的容量
            if(size >= elements.length){
                expandSpace();
            }
            //把从第i位置的元素开始到最后一个元素,都往后移动一个位置
            for(int j = size - 1; j > i; j--){
                elements[j] = elements[j-1];
            }
            //把第i位置的值改为e
            elements[i] = e;
            //把数组元素的格式增加1
            size++;
            return true;
        }
    }

    //动态扩展数组容量
    private void expandSpace() {
        Object[] newArray = new Object[elements.length*2];
        for (int i = 0; i < elements.length; i++) {
            newArray[i] = elements[i];
        }
        elements = newArray;
    }

    //移除数组中第i位置的元素并返回
    public Object remove(int i) throws OutOfBoundException {
        Object e = get(i);
        if(i < 0 || i > size){
            System.out.println("下标越界,删除失败!");
            return null;
        }
        for (int j = i; j < size - 1; j++) {
            elements[j] = elements[j + 1];
        }
        //把数组的元素个数减少1
        elements[--size] = null;
        return e;
    }

    //删除元素e,并判断是否删除成功
    public boolean remove(Object e) {
        boolean isRemove = false;
        //判断数组中是否存在元素e
        if(contains(e)){
            //获取该元素的下标
            int i = indexOf(e);
            for (int j = i; j < size - 1; j++) {
                elements[j] = elements[j + 1];
            }
            isRemove = true;
        }
        return isRemove;
    }
    //定位元素e的位置
    public int indexOf(Object e) {
        for (int i = 0; i < size; i++) {
            if(strategy.equal(elements[i], e)){
                return i;
            }
        }
        return -1;
    }

    }

链式存储结构

链式存储结构区别于顺序存储结构的一点就是数据是存放内存中任意一个地址中,每个数据除了有自己的数据属性还有下一个数据内存地址的引用,所以得到一个数据就可以知道下一个数据在哪个位置,显然这种存储方式的最有利的一点就是删除和插入比较有效率,这也是链式存储结构的应用的优势,在Java中,有一种数据结构————链表,就很好体现了这种存储方式,下面就用链表来实现链式存储结构

链表实现链式存储结构

前面提到,链表的一大优势就是删除和插入比较给力,为了便于理解下面的代码,我截了两张图说明链表删除以及插入的具体过程:

链表插入

需要注意的是,执行链表插入的时候要先判断插入位置的下标防止下标越界的情况,这个时候可以抛出异常来解决,下面来看链表删除的具体过程:

链表删除

下面是具体的核心代码实现:

    public class LinkedSTList implements List {

    //单链表数据元素比较策略
    private Strategy strategy;
    //头结点
    private STNode head;
    //单链表中元素的个数
    private int size;

    public LinkedSTList(){
        this(new DefaultStrategy());
    }

    public LinkedSTList(Strategy strategy){
        this.strategy = strategy;
        head = new STNode();
        size = 0;
    }

    //定位元素e在链表中的下标
    public int indexOf(Object e) {
        STNode p = head.getNext();
        int index = 0;
        while(p != null){
            if(strategy.equal(p.getData(), e)){
                return index;
            }else{
                index++;
                p = p.getNext();
            }
        }
        return -1;
    }

    //在单链表的第i位置插入元素e
    public boolean insert(int i, Object e) throws Exception {
        STNode s = new STNode(e,null);
        if(i <= 0 || i >= size){
            throw new OutOfBoundException("下标越界,插入失败");
        }
        STNode p = getPre(i);
        STNode self = (STNode) get(i);
        p.setNext(s);
        s.setNext(self);
        size++;
        return true;
    }

    //获取第i位置的前一个节点
    private STNode getPre(int i) throws OutOfBoundException {
        if(i < 0 || i >= size){
            throw new OutOfBoundException("下标越界,插入失败");
        }
        /*if(i == 0){
            return head;
        }else{
            STNode p = head.getNext();
            int index = 1;
            while(i != index){
                p = p.getNext();
                index++;
            }
            return p;
        }*/
        STNode p = head;
        for(;i > 0; i--){
            p = p.getNext();
        }
        return p;
    }

    //获取元素e的前一个元素节点
    private STNode getPre(Object e) {
        STNode p = head;
        while(p != null){
            if(strategy.equal(p.getNext().getData(), e)){
                return p;
            }else{
                p = p.getNext();
            }
        }
        return null;
    }

    //删除第i位置的元素并返回
    public Object remove(int i) throws Exception {
        if(i < 0 || i >=size){
            throw new OutOfBoundException("下标越界,删除失败");
        }
        /*STNode s = (STNode) get(i);
        if(i == 0){
            head = head.getNext();
            size--;
        }else if(i == size-1){
            STNode p = getPre(i);
            p.setNext(p.getNext().getNext());
            size--;
        }else{
            STNode q = getPre(i);
            q.setNext(s.getNext());
            size--;
        }*/
        STNode p = getPre(i);
        Object obj = p.getNext().getData();
        p.setNext(p.getNext().getNext());
        size--;
        return obj;
    }

    public boolean remove(Object e) {
        if(contains(e)){
            STNode s = getPre(e);
            s.setNext(s.getNext().getNext());
            size--;
            return true;
        }
        return false;
    }

    }

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
数据结构与算法——图论基础与图存储结构 | 算法必看系列三十一
图是数据结构中重要内容。相比于线性表与树,图的结构更为复杂。在线性表的存储结构中,数据直接按照前驱后继的线性组织形式排列。在树的结构中,数据节点以层的方式排列,节点与节点之间是一种层次关系。但是,在图的结构中数据之间可以有任意关系,这就使得图的数据结构相对复杂。
2228 0
【算法与数据结构】在n个数中取第k大的数(基础篇)
(转载请注明出处:http://blog.csdn.net/buptgshengod) 题目介绍           在n个数中取第k大的数(基础篇),之所以叫基础篇是因为还有很多更高级的算法,这些以后再讨论。本文用两种最基本的方法来解决这个问题。使用java语言描述。例子是十个数中取第三大的。 算法一              用冒泡法将n个数从大到小排序,再取第k大。
638 0
MySQL 基础---数据操作
数据的操作(CRUD): 插入数据记录(CREATE) 查询数据记录(READ) 更新数据记录(UPDATE) 删除数据记录(DELETE) 插入数据记录("INSERT INTO") 插入数据: 插入完整数据记录、插入数据记录一部分、插入多条数据记录、插入查询结果。
477 0
数据仓库3NF基础理论和实例
一、引言   最近在梳理大数据模式下的数据仓库数据模型,花了点时间,系统的回顾一下传统数据仓库数据模型设计的理论,作为笔记分享给大家,很多资料来自互联网和读过的数据仓库理论和实践相关的熟悉,无剽窃之心,共勉吧。
657 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
4425 0
[Java 基础]数据类型
基本类型和引用类型 Java中的数据类型有两类: l  基本类型(又叫内置数据类型,或理解为值类型) l  引用类型   基本类型和引用类型的区别 1.  从概念方面来说 基本类型:变量名指向具体的数值 引用类型:变量名指向存数据对象的内存地址 2.  从内存构建方面来说 基本类型:变量在声明之后java就会立刻分配给他内存空间 引用类型:它以特殊的方式(类似C指针)指向对象实体(具体的值),这类变量声明时不会分配内存,只是存储了一个内存地址。
510 0
+关注
111
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载