2019-03-17 18:20:59 qq_25775935 阅读数 1595
  • C语言从入门到精通+贪吃蛇游戏开发实战

    掌握C语言数据类型,printf,scanf函数,运算符,if语句,switch语句,for,while,do...while循环语句;常用数学函数应用;一维数组,多维数组,查找和常用排序算法,结构体与指针,自定义函数的定义与使用,函数的实参与形参;用户图形界面,大量的上课习题,深入浅出的详细讲解,结合开发贪吃蛇游戏实战项目,能达到精通C语言的目标。

    18787 人正在学习 去看看 赖国荣

前面学习数据结构的过程中,总是使用数组作为顺序表的底层实现,给我们一种 "数据结构中,数组的作用就是实现顺序表" 的错误认识。其实,数组的作用远不止于此。

本节将从数据结构的角度讲解数组存储结构。

本节所讲的数组,要将其视为一种存储结构,与平时使用的数组基本数据类型区分开。

什么是数组

一说起数组,我们的印象中数组往往是某一门编程语言中包含的具体数据类型,其实不然。

从本质上讲,数组与顺序表、链表队列一样,都用来存储具有 "一对一" 逻辑关系数据的线性存储结构。只因各编程语言都默认将数组作为基本数据类型,使初学者对数组有了 "只是基本数据类型,不是存储结构" 的误解。

不仅如此,数组和其他线性存储结构不同,顺序表、链表、栈和队列存储的都是不可再分的数据元素(如数字 5、字符 'a' 等),而数组既可以用来存储不可再分的数据元素,也可以用来存储像顺序表、链表这样的数据结构。

比如说,数组可以直接存储多个顺序表。我们知道,顺序表的底层实现还是数组,因此等价于数组中继续存储数组。这与平时使用的二维数组类似。

根据数组中存储数据之间逻辑结构的不同,数组可细分为一维数组、二维数组、...、n 维数组:

  • 一维数组,指的是存储不可再分数据元素的数组,如 1 所示;

     

    一维数组存储结构示意图

                                                                   图 1 一维数组存储结构示意图

  • 二维数组,指的存储一维数组的一维数组,如图 2 所示;

     

    二维数组存储结构示意图

                                                                    图 2 二维数组存储结构示意图

  • n 维数组,指的是存储 n-1 维数组的一维数组;

注意,无论数组的维数是多少,数组中的数据类型都必须一致。

由此,我们可以得出这样一个结论,一维数组结构是线性表的基本表现形式,而 n 维数组可理解为是对线性存储结构的一种扩展。

2019-05-01 21:02:47 yang1780409810 阅读数 42
  • C语言从入门到精通+贪吃蛇游戏开发实战

    掌握C语言数据类型,printf,scanf函数,运算符,if语句,switch语句,for,while,do...while循环语句;常用数学函数应用;一维数组,多维数组,查找和常用排序算法,结构体与指针,自定义函数的定义与使用,函数的实参与形参;用户图形界面,大量的上课习题,深入浅出的详细讲解,结合开发贪吃蛇游戏实战项目,能达到精通C语言的目标。

    18787 人正在学习 去看看 赖国荣

文章来源参考:慕课网视频


 

数据结构-数组

数组

  • 数据结构中最基本的一个结构就是线性结构,而线性结构又分为连续存储结构和离散存储结构。所谓的连续存储结构其实就是数组。

  • 优点:插入块如果知道坐标可以快速去地存取

  • 缺点:查找慢,删除慢,大小固定

二次封装数组的增删改查

基类的定义

  • 定义一个工具类名称-Array

  • 接受的参数包括基本类型和自定义类型(用泛型来接受,基本类型用包装类)

  • 自定义属性两个:size用来表示数组的大小,data用来表示一个准确的集合

  • 概念区分:size表示数组的大小,capacity表示数组容量的大小

  • 构造函数:有参构造,接受一个int值,用来初始化数组容量;无参构造:给容量一个默认值

  • toString()方法,输出数组的大小和数组容量的大小,以及数组中的值

  • getSize()方法,调用方通过方法来获取数组的大小

  • getCapacity()方法,调用方通过方法来获取数组容量的大小

  • isEmpty()方法,调用方通过方法来判断数组是否为空(指的是数组中是否有值,没值就为空)

基类的代码

package com.datastructure.array;

/**
 * @program: test
 * @description: 自定义数组封装工具类
 * @author: Mr.Yang
 * @create: 2019-05-01 15:36
 **/
public class Array<E> {

    private Integer size;

    private E[] data;




    /**
     * 有参构造函数
     * @param capacity  封装data的容量值
     */
    public Array(Integer capacity){
        data= (E[]) new Object[capacity];
        size=0;
    }

    /**
     * 无参构造函数,设置默认容量为10
     */
    public Array(){
        this(10);
    }

    /**
     * 获取数组中的元素个数
     * @return
     */
    public Integer getSize(){
        return size;
    }

    /**
     * 获取数组的容量
     * @return
     */
    public Integer getCapacity(){
        return data.length;
    }

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

    @Override
    public String toString(){
        StringBuffer sb = new StringBuffer();
        sb.append(String.format("Array: size = %d , capacity = %d\n",size,data.length));
        sb.append("[");
        for(int i =0;i<size;i++){
            sb.append(data[i]);
            if(i !=size-1){
                sb.append(", ");
            }
        }
        sb.append("]");
        return sb.toString();
    }
}

添加的方法

  • add()方法,两个参数,添加元素的索引位置,和元素的值

  • addFirst()方法,在所有元素的最前面添加

  • addLast()方法,在所有元素的最后面添加

添加的代码(增)

/**
     * 在索引为index的位置,插入param
     * 1.假如在索引为2的位置插入元素
     * 2.需要将原来索引为2及其以后的位置向后移动一整位
     * 3.移动完成之后,在索引为2的位置插入指定的值
     * 4.因为数组中多了一个值,所以size需要+1
     *
     * @param index 元素的索引
     * @param param 值
     */
    public void add(int index, E param) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("添加失败,索引的值不能小于0,并且索引的值不能大于数组的大小");
        }
        if (size == data.length) {
            throw new IllegalArgumentException("添加失败,数组的大小已经等于了数组容量的大小");
        }
        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }
        data[index] = param;
        size++;
    }

    /**
     * 在所有元素之前添加值
     *
     * @param param
     */
    public void addFirst(E param) {
        add(0, param);
    }

    /**
     * 在所有元素之后添加值
     *
     * @param param
     */
    public void addLast(E param) {
        add(size, param);
    }

测试代码

package com.datastructure.array;

/**
 * @program: test
 * @description:
 * @author: Mr.Yang
 * @create: 2019-05-01 16:46
 **/
public class ArrayTest {

    public static void main(String[] args) {
        Array<Integer> integerArray = new Array<Integer>(20);
        for(int i = 0; i < 10 ; i ++){
            integerArray.addLast(i);
        }
        System.out.println(integerArray);

        System.out.println("--------------------索引为3的地方添加元素-----------------------");
        integerArray.add(3,666);
        System.out.println(integerArray);

        System.out.println("--------------------所有元素的最后面添加值-----------------------");
        integerArray.addLast(10000);
        System.out.println(integerArray);

        System.out.println("--------------------所有元素的最前面添加值-----------------------");
        integerArray.addFirst(-1);
        System.out.println(integerArray);
    }
}

测试结果

Array: size = 10 , capacity = 20
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
--------------------索引为3的地方添加元素-----------------------
Array: size = 11 , capacity = 20
[0, 1, 2, 666, 3, 4, 5, 6, 7, 8, 9]
--------------------所有元素的最后面添加值-----------------------
Array: size = 12 , capacity = 20
[0, 1, 2, 666, 3, 4, 5, 6, 7, 8, 9, 10000]
--------------------所有元素的最前面添加值-----------------------
Array: size = 13 , capacity = 20
[-1, 0, 1, 2, 666, 3, 4, 5, 6, 7, 8, 9, 10000]

添加的方法

  • set,两个参数,修改的元素的索引位置,和将要修改的值

添加的代码(改)

/**
     * 修改数组中元素的值
     * @param index
     * @param param
     */
    public void set(int index,E param){
        if(index<0 || index>= size){
            throw new IllegalArgumentException("获取失败,索引值无效");
        }
        data[index]=param;
    }

测试代码

package com.datastructure.array;

/**
 * @program: test
 * @description:
 * @author: Mr.Yang
 * @create: 2019-05-01 16:46
 **/
public class ArrayTest {

    public static void main(String[] args) {
        Array<Integer> integerArray = new Array<Integer>(20);
        for (int i = 0; i < 10; i++) {
            integerArray.addLast(i);
        }
        System.out.println(integerArray);

        System.out.println("--------------------索引为3的地方修改值为1010-----------------------");
        integerArray.set(3, 1010);
        System.out.println(integerArray);

    }
}

测试结果

Array: size = 10 , capacity = 20
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
--------------------索引为3的地方修改值为1010-----------------------
Array: size = 10 , capacity = 20
[0, 1, 2, 1010, 4, 5, 6, 7, 8, 9]

添加的方法

  • get()方法,一个参数,索引值,根据索引返回对应的值

  • contains()方法,一个参数,判断数组中是否包含某个元素

  • find()方法,一个参数,查找数组中是否包含param,如果包含返回索引值,不包含返回-1

  • findAll()方法,一个参数,查找数组中是否包含param,返回包含的索引数组

添加的代码(查)

 /**
     * 获取索引位置的元素
     * @param index
     * @return
     */
    public E get(Integer index){
        if(index<0 || index>=size){
            throw new IllegalArgumentException("获取失败,索引的值不能小于0,并且索引的值不能大于等于数组的大小");
        }
        return data[index];
    }

    /**
     * 查看数组中是否包含某个元素
     * @param param
     * @return
     */
    public boolean contains(E param){
        for(int i = 0 ; i < size ; i++){
            if(data[i] == param){
                return true;
            }
        }
        return false;
    }


    /**
     * 查找数组中是否包含param,如果包含返回索引值,不包含返回-1
     * @param param
     * @return
     */
    public Integer find(E param){
        for(int i = 0 ; i < size ; i++){
            if(data[i] == param){
                return i;
            }
        }
        return -1;
    }

    /**
     * 查找数组中是否包含param
     * 1.创建一个int数组用来接收返回的索引值
     * 2.索引容量最大为数组的大小
     * 3.用临时变量来存储int数组的大小
     * 4.如果相等,给 int数组 为临时变量的元素赋值(相等的索引),临时变量自增
     * @param param
     * @return
     */
    public Integer[] findAll(E param){
        int intTemp=0;
        Integer[] integers = new Integer[size];
        for(int i = 0 ; i < size ; i++){
            if(data[i] == param){
                integers[intTemp]=i;
                intTemp++;
            }
        }
        return integers;
    }

测试代码

package com.datastructure.array;

import java.util.Arrays;

/**
 * @program: test
 * @description:
 * @author: Mr.Yang
 * @create: 2019-05-01 16:46
 **/
public class ArrayTest {

    public static void main(String[] args) {
        Array<Integer> integerArray = new Array<Integer>(20);
        for (int i = 0; i < 10; i++) {
            integerArray.addLast(i);
        }
        integerArray.addLast(3);

        System.out.println(integerArray);

        System.out.println("--------------------得到索引为3的值-----------------------");
        System.out.println(integerArray.get(3));

        System.out.println("--------------------判断是否包含有包含3的值-----------------------");
        System.out.println(integerArray.contains(3));

        System.out.println("--------------------查找是否包含参数,并返回索引-----------------------");
        System.out.println(integerArray.find(3));

        System.out.println("--------------------查找是否包含参数,并返回索引数组-----------------------");
        System.out.println(Arrays.asList(integerArray.findAll(3)));

    }
}

测试结果

Array: size = 11 , capacity = 20
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 3]
--------------------得到索引为3的值-----------------------
3
--------------------判断是否包含有包含3的值-----------------------
true
--------------------查找是否包含参数,并返回索引-----------------------
3
--------------------查找是否包含参数,并返回索引数组-----------------------
[3, 10, null, null, null, null, null, null, null, null, null]

添加的方法

  • remove()方法,数组中删除index位置的元素,并且返回对应的值

  • removeFirst()方法,删除第一位元素

  • removeLast()方法,删除最后一位元素

  • removeElement()方法,查看某个值是否在数组中存在,如果存在,删除并返回true,如果不存在 返回false、

  • removeLast()方法, 查找所有元素,获取所有相等的索引,遍历移除

添加的代码(删)

/**
     * 从数组中删除index位置的元素,并且返回对应的值
     * 1.假如删除索引为3的元素
     * 2.需要将索引大于3的元素向前移动一位
     * 3.因为数组中少了一个值,所以元素-1
     * 4.用临时变量来存储删除的值,用来返回
     * @param index
     * @return
     */
    public E remove(int index){
        if(index<0 || index>=size){
            throw new IllegalArgumentException("删除失败,索引的值不能小于0,并且索引的值不能大于等于数组的大小");
        }
        E temp=data[index];
        for(int i = index+1 ; i < size ; i++){
            data[i-1]=data[i];
        }
        size--;
        return temp;
    }

    /**
     * 删除第一位元素
     * @return
     */
    public E removeFirst(){
        return remove(0);
    }

    /**
     * 删除最后一位元素
     */
    public E removeLast(){
        return remove(size-1);
    }

    /**
     * 查看某个值是否在数组中存在,如果存在,删除并返回true,如果不存在 返回false
     * @param param
     */
    public boolean removeElement(E param){
        Integer index = find(param);
        if(index != -1){
            remove(index);
            return true;
        }
        return false;
    }

   /**
     * 遍历数组,移除元素
     * @param param
     */
    public void removeAllElement(E param){
        for(E d:data){
            removeElement(param);
        }
    }

测试代码

package com.datastructure.array;

import java.util.Arrays;

/**
 * @program: test
 * @description:
 * @author: Mr.Yang
 * @create: 2019-05-01 16:46
 **/
public class ArrayTest {

    public static void main(String[] args) {
        Array<Integer> integerArray = new Array<Integer>(20);
        for (int i = 0; i < 10; i++) {
            integerArray.addLast(i);
        }
        integerArray.addLast(3);
        integerArray.addLast(4);

        System.out.println(integerArray);

        System.out.println("--------------------数组中删除6位置的元素,并且返回对应的值-----------------------");
        System.out.println(integerArray.remove(6));
        System.out.println(integerArray);

        System.out.println("--------------------删除第一位元素-----------------------");
        System.out.println(integerArray.removeFirst());
        System.out.println(integerArray);

        System.out.println("--------------------删除最后一位元素-----------------------");
        System.out.println(integerArray.removeLast());
        System.out.println(integerArray);

        System.out.println("--------------------查看8是否在数组中存在,返回true和fals-----------------------");
        System.out.println(integerArray.removeElement(8));
        System.out.println(integerArray);

        System.out.println("--------------------查找所有元素,获取所有相等的索引,遍历移除-----------------------");
        integerArray.removeAllElement(3);
        System.out.println(integerArray);

    }
}

测试结果

Array: size = 12 , capacity = 20
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 3, 4]
--------------------数组中删除6位置的元素,并且返回对应的值-----------------------
6
Array: size = 11 , capacity = 20
[0, 1, 2, 3, 4, 5, 7, 8, 9, 3, 4]
--------------------删除第一位元素-----------------------
0
Array: size = 10 , capacity = 20
[1, 2, 3, 4, 5, 7, 8, 9, 3, 4]
--------------------删除最后一位元素-----------------------
4
Array: size = 9 , capacity = 20
[1, 2, 3, 4, 5, 7, 8, 9, 3]
--------------------查看8是否在数组中存在,如果存在,删除并返回true,如果不存在 返回false、-----------------------
true
Array: size = 8 , capacity = 20
[1, 2, 3, 4, 5, 7, 9, 3]
--------------------查找所有元素,获取所有相等的索引,遍历移除-----------------------
Array: size = 6 , capacity = 20
[1, 2, 4, 5, 7, 9]

数组动态扩容

添加的方法

  • resize()方法,定义为私有,调用方不能通过方法来调用,去修改,否则容易造成BUG

  • 扩容倍数,如果用固定值,不好抉择。比如:100容量,扩容10个,没有意义,很快就满了;100容量,扩充1000个,太多了,容易早证浪费。最好选择倍数,都在同一个单位级别,这里代码选择的是2倍

  • 添加的时候需要判断扩容,删除的时候需要删除容量,减少资源浪费

  • 删除的时候,当元素减少到容量的1/4的时候开始缩,缩减到容量的1/2

  • 如果选择1/2的时候开始缩减,然后缩减到1/2会有一定的问题,例如:容量10,现在容量满了,来了一个元素,需要扩容,按照设置的扩容机制,会扩容2倍,也就是20容量,如果删除了一个元素,元素达到了容量的1/2,我们开始进行缩减,缩减1/2,容量又变为10。如果一直在这个临界值,那么元素会一直进行扩容缩减扩容缩减,性能影响太大。

  • 如果选择1/4的时候开始缩减,然后缩减到1/2,这样能够较好的避开以上问题,例如:容量10,容量满了,来了一个元素,扩容容量到了20,如果删除一个元素,还不到容量的1/4,所以还不会进行缩减,如果真的到了容量的1/4的时候,我们选择缩减1/2,容量也需要一定的元素,才会进行扩容,防止了容量一直扩容或者缩减

添加的代码

    /**
     * 扩容方法
     * 1.需要new一个object,new E[i]  java不支持这样写
     * 2.object是所有类的基类,用object然后强转一下就可以
     * 3.扩展之后,需要将原数组中的值,放入扩展之后的数组中
     * @param 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;
    }

修改的代码

  • add() 和 remove()

/**
     * 在索引为index的位置,插入param
     * 1.假如在索引为2的位置插入元素
     * 2.需要将原来索引为2及其以后的位置向后移动一整位
     * 3.移动完成之后,在索引为2的位置插入指定的值
     * 4.因为数组中多了一个值,所以size需要+1
     *
     * @param index 元素的索引
     * @param param 值
     */
    public void add(int index, E param) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("添加失败,索引的值不能小于0,并且索引的值不能大于数组的大小");
        }
        if (size == data.length) {
            resize(2 * data.length);
        }
        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }
        data[index] = param;
        size++;
    }


/**
     * 从数组中删除index位置的元素,并且返回对应的值
     * 1.假如删除索引为3的元素
     * 2.需要将索引大于3的元素向前移动一位
     * 3.因为数组中少了一个值,所以元素-1
     * 4.用临时变量来存储删除的值,用来返回
     * @param index
     * @return
     */
    public E remove(int index){
        if(index<0 || index>=size){
            throw new IllegalArgumentException("删除失败,索引的值不能小于0,并且索引的值不能大于等于数组的大小");
        }
        E temp=data[index];
        for(int i = index+1 ; i < size ; i++){
            data[i-1]=data[i];
        }
        size--;
        if(size == data.length / 4 ){
            resize(data.length / 2 );
        }
        return temp;
    }

测试代码

package com.datastructure.array;

import java.util.Arrays;

/**
 * @program: test
 * @description:
 * @author: Mr.Yang
 * @create: 2019-05-01 16:46
 **/
public class ArrayTest {

    public static void main(String[] args) {
        Array<Integer> integerArray = new Array<Integer>(10);
        for (int i = 0; i < 10; i++) {
            integerArray.addLast(i);
        }
        System.out.println(integerArray);

        System.out.printf("--------------------将容量设置为10,添加10个元素,元素的容量 : %d -------------------\r\n",integerArray.getCapacity());

        integerArray.addLast(21);
        System.out.printf("--------------------元素+1,元素的容量 : %d --------------------\r\n",integerArray.getCapacity());


        integerArray.removeLast();
        System.out.printf("--------------------元素-1,元素的容量 : %d --------------------\r\n",integerArray.getCapacity());

        integerArray.removeLast();
        System.out.printf("--------------------元素-1,元素的容量 : %d --------------------\r\n",integerArray.getCapacity());

        for(int x=0;x<=5;x++){
            integerArray.removeLast();
        }
        System.out.printf("--------------------元素-1/4,元素的容量 : %d --------------------\r\n",integerArray.getCapacity());


    }
}

测试结果

Array: size = 10 , capacity = 10
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
--------------------将容量设置为10,添加10个元素,元素的容量 : 10 -------------------
--------------------元素+1,元素的容量 : 20 --------------------
--------------------元素-1,元素的容量 : 20 --------------------
--------------------元素-1,元素的容量 : 20 --------------------
--------------------元素-1/4,元素的容量 : 10 --------------------

 


关注公众号  JAVA知识总结与分享 ,回复  ai  ,即可领取129G人工智能资源

 

 

 


关注公众号 JAVA知识总结与分享  发送关键字  复仇者联盟4   可以观看免费视频

 

 

 

 

 

 

2019-08-17 07:26:24 baidu_30130783 阅读数 27
  • C语言从入门到精通+贪吃蛇游戏开发实战

    掌握C语言数据类型,printf,scanf函数,运算符,if语句,switch语句,for,while,do...while循环语句;常用数学函数应用;一维数组,多维数组,查找和常用排序算法,结构体与指针,自定义函数的定义与使用,函数的实参与形参;用户图形界面,大量的上课习题,深入浅出的详细讲解,结合开发贪吃蛇游戏实战项目,能达到精通C语言的目标。

    18787 人正在学习 去看看 赖国荣

1、数组定义:

数组是java语言中最基本的数据存储结构。数组是一块连续的内存空间,用于存储相同类型的数据。基本上掌握的数组的这个定义里包含的特点。也就掌握的了数组

(1)连续的内存空间:因为连续,导致内存空间利用率差。若声明一个数组,大小为10m的连续的一块空间 byte[] arr=new byte[1024*10] 。即使这时候内存空间大于10m,但腾不出一块连续内存空间(存在内存碎片)。也会导致数组申明失败。

(2)存储相同类型的数据:申明数组时便指定了数组只能存储那种数据类型 int[] arr=new int[10];Object[] arr=new Object[10];

2、数组特点:

(1)查询:连续的内存空间铸造数组能高效的通过下标随机访问元素的特点

通过下标随机访问的时间复杂度为O(1)

通过特定元素访问:通过for循环遍历

  • 若查找的元素再数组第0个下标位置,则时间复杂度为O(1)
  • 若查找的元素再数组第n-1个下标位置,则时间复杂度为O(n)
  • 有序数组通过二分查找,时间复杂度为O(longn)

(2)增删:

若插入数据x,在数组第0个下标位置,其他下标的元素向后移动一位,所以时间复杂度为O(n)

若插入数据x,在数组第n-1个下标位置,其他下标的元素都不动,所以时间复杂度为O(1)

优化:无序数据在插入数据时,直接将第 k 位的数据搬移到数组元素的最后,把要插入的元素直接放入第 k 个位置。时间复杂度就会降为 O(1)

(3)删除同理,区别在于元素是向前移动。

删除数组末尾的数据,则最好情况时间复杂度为 O(1);

删除开头的数据,则最坏情况时间复杂度为 O(n);

删除平均情况时间复杂度也为 O(n)。

3、数组的下标为什么从0开始?

(1)、历史遗留问题,c语言下标从0开始

(2)、若从1开始,通过寻址公式,计算数组元素所在地址时,会多做一次运算,降低效率。

若申明一个数组:int[] arr=new int[5]

数组寻址公式:arr[i]_address = base_address + i * data_type_size

base_address :计算机给这块内存分配的首地址

data_type_size:数据大小。int类型及为4。

计算机给数组 arr[5],分配了一块连续内存空间 1000~1016,其中,内存块的首地址为 base_address = 1000。 

那么arr[0]_address=1000+0*4=1000

arr[1]_address=1000+1*4=1000

...

若下标从1开始:则寻址公式:arr[i]_address = base_address + (i-1)* data_type_size。多做一次 i-1的运算

4、小结:

数组是一块连续的内存空间,用于存储相同数据类型的数据结构。根据下标随机访问的时间复杂度为O(1),根据特定值访问,最好时间复杂度为O(1)(元素在数组首位位置),最坏时间复杂度为O(n),(元素在数组末位的位置)。

插入元素到指定位置,和删除指定位置的元素,保证数据连续的特点(不是删除后该位置便为空,插入后直接替换该位置的元素),需要将数据做相应的移动。所以在插入和删除,最好时间复杂度为O(1)(操作的元素在数组末尾位置),最坏时间复杂度为O(n),(操作的元素在数组首位的位置)。

5、数组练习:

【剑指offer】在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是第一个重复的数字2。

 

 

 

2018-03-21 14:49:13 qq_33764491 阅读数 127
  • C语言从入门到精通+贪吃蛇游戏开发实战

    掌握C语言数据类型,printf,scanf函数,运算符,if语句,switch语句,for,while,do...while循环语句;常用数学函数应用;一维数组,多维数组,查找和常用排序算法,结构体与指针,自定义函数的定义与使用,函数的实参与形参;用户图形界面,大量的上课习题,深入浅出的详细讲解,结合开发贪吃蛇游戏实战项目,能达到精通C语言的目标。

    18787 人正在学习 去看看 赖国荣

数组作为最为基础的数据结构,以线性结构来存储固定大小、相同类型的数据。
Java中已经为我们封装好了ArrayList来描述各种操作,下面将自定义类分装并描述数组的操作。

  • 数组操作之增删改查
package Array;

public class MyArray {
    private long[] arr;
    //表示有效数据的长度
    private int elements;

    public MyArray() {
        arr = new long[50];
    }

    public MyArray(int maxsize) {
        arr = new long[maxsize];
    }

    /**
     * 添加数据
     * @param value
     */
    public void insert(long value){
        arr[elements] = value;
        elements++;
    }

    /**
     * 显示数据
     */
    public void display(){
        System.out.print("[ ");
        for (int i = 0; i < elements; i++){
            System.out.print(arr[i] + " ");
        }
        System.out.println("]");
    }

    /**
     * 查找数据,根据值来查询
     * 线性查找,从头到尾的查
     * @param value
     */
    public int search(long value){
        int i;
        for (i = 0; i < elements; i++) {
            if(value == arr[i]){
                break;
            }
        }
        if(i == elements){
            return -1;
        } else {
            return i;
        }
    }

    /**
     * 查询数据,根据索引来查询
     * @param index
     * @return
     */
    public long get(int index){
        if (index >= elements || index < 0){
            throw new ArrayIndexOutOfBoundsException();
        } else {
            return arr[index];
        }
    }

    /**
     * 删除数据
     * @param index
     */
    public void delete(int index){
        if (index >= elements || index < 0){
            throw new ArrayIndexOutOfBoundsException();
        } else {
            for (int i = index; i < elements; i++) {
                arr[index] = arr[index+1];
            }
            elements--;
        }
    }

    /**
     * 更新数据
     * @param index
     * @param newvalue
     */
    public void change(int index, int newvalue){
        if (index >= elements || index < 0){
            throw new ArrayIndexOutOfBoundsException();
        } else {
            arr[index] = newvalue;
        }
    }
}
  • 构建有序数组
    构建有序的数组,需要注意的点是在添加元素的时候需要进行值得判断,并从后向前的进行值的交换。
/**
     * 添加数据
     * @param value
     */
    public void insert(long value){
        int i;
        for (i = 0; i < elements; i++) {
            if (arr[i] > value) {
                break;
            }
        }
        for (int j = elements; j > i; j--) {
            arr[j] = arr[j-1];
        }
        arr[i] = value;
        elements++;
    }
  • 二分法查找数据
    二分法顾名思义即将数组切为两部分,通过比较查询值与中间值,来判断查询值所处范围,来进一步缩小查询范围,直到查询值等于中间值为止。
    二分法查找的使用前提是为有序的数组。
    /**
     * 二分法查找
     * @param value
     * @return
     */
    public int binarySearch(long value){
        int middle = 0;
        int low = 0;
        int pow = elements;

        while (true) {
            middle = (pow + low) / 2;
            if (value == arr[middle]) {
                return middle;
            } else if (low > pow) {
                return -1;
            } else {
                if (value < arr[middle]) {
                    pow = middle - 1;
                } else {
                    low = middle + 1;
                }
            }
        }
    }
  • 测试类
package Array;

public class TestMyArray {
    public static void main(String[] args) {
/*        MyArray arr = new MyArray();
        arr.insert(13);
        arr.insert(23);
        arr.insert(54);

        arr.display();
        System.out.println(arr.search(23));

        System.out.println(arr.get(1));

        arr.delete(1);
        arr.display();

        arr.change(0,22);
        arr.display();*/

        MyOrderArray arr = new MyOrderArray();
        arr.insert(76);
        arr.insert(45);
        arr.insert(96);
        arr.insert(31);
        arr.display();

        System.out.println(arr.binarySearch(96));
    }
}
2019-10-05 13:19:19 qq_42605751 阅读数 17
  • C语言从入门到精通+贪吃蛇游戏开发实战

    掌握C语言数据类型,printf,scanf函数,运算符,if语句,switch语句,for,while,do...while循环语句;常用数学函数应用;一维数组,多维数组,查找和常用排序算法,结构体与指针,自定义函数的定义与使用,函数的实参与形参;用户图形界面,大量的上课习题,深入浅出的详细讲解,结合开发贪吃蛇游戏实战项目,能达到精通C语言的目标。

    18787 人正在学习 去看看 赖国荣

数组性质

1.数组中的数据元素数目是固定的,一旦定义了一个数组,其数据元素数目不再有增减的变化
2.数组中的数据元素具有相同的数据元素类型
3.数组中的每个数据元素都和一组唯一的下标对应
4.数组是一种随机的存储结构,可随机存储数组中的任意数据元素。

数组的类型与定义方式

1.数组类型

数组类型 默认初始值
byte 0
short 0
int 0
long 0
char 编码为0的字符
String(引用类型) null
float 0
double 0

2.一维数组的定义方式

2.1数组声明的俩种方式:

1.int[] array;
2.int array[];

2.2数组初始化

//分配长度为4个int型的内存空间,并分别赋初始值1,2,3,4
int[] array = {1,2,3,4};
int[] array = {1,2,3,4};
//分配长度为4的内存空间,并全部赋为0
int[] array = new int[4]
int[] array =new int{4,0,0,0};

3.二维数组的定义方式
3.1.二维数组的理解

一个二维数组,有二个1维数组组成,每一个一维数组有3个元素,即如下定义:
int[][]a={{1,2,3},{6,5,4}};

3.2.二维数组的初始化形(可以在声明数组的同时进行初始化(静态初始化),也可以在声明以后进行初始化(动态初始化))

形式1.动态初始化
数据类型 数组名 [ ][ ] = new 数据类型[m][n]
数据类型 [ ][ ]  数组名 = new 数据类型[m][n]
数据类型 [ ]   数组名 [ ] = new 数据类型[m][n]
举例:int [ ][ ]  arr=new  int [4][3];  也可以理解为“43列”。
形式2、 静态初始化
数据类型 [ ][ ]   数组名 = {{元素1,元素2....},{元素1,元素2....},{元素1,元素2....}.....};
举例:int [ ][ ]  arr={{22,15,32,20},{12,21,25,19},{14,58,34,24},}

数组的增删改查

数组代码需求(贴的代码可能达不到要求,有点菜,有大佬看见还希望可以帮帮忙嘿嘿):
1.数组的键盘输入元素以及下标添加元素
2.数组的键盘输入元素查找元素
3.数组的键盘输入元素查找元素下标
4.根据数组下标删除元素,根据数组元素删除元素
package shuzudemo;

import java.util.Arrays;
import java.util.Scanner;

public class querydemo{
	//查询元素
	public static int querycha(int arr[],int ele) {
		int index = -1;
		for(int i=0;i<arr.length;i++) {
			if(arr[i]==ele) {
				index = i;
				break;
			}
		}
		return index;
	}
	
	//插入元素
	public static int[] add(int[] arr,int ele,int index) {
		int[] newArr = new int[arr.length+1];
		if(index >= 0 && index<newArr.length) {
			for(int i = 0;i<index;i++) {
				newArr[i] = arr[i];
			}
			newArr[index] = 100;
			for(int i=index;i<arr.length;i++) {
				newArr[i+1]=arr[i];
			}
		}else {
			System.out.println("索引超出范围");
			return arr;
		}
		return newArr;
	}
	//根据下标删除元素
	public static int[] del(int[] arr,int ele,int index) {
		if(index>=0 && index<arr.length) {
			for(int i=index;i<arr.length-1;i++) {
				arr[arr.length-1] = 0;
			}
		}else {
			System.out.println("没有此下标");
		}
		return arr;
	}
	//根据元素删除元素
	public static int delele(int[] arr,int ele) {
		int index = -1;
		for(int i=0;i<arr.length;i++) {
			if(ele == arr[i]) {
				index = i;
				break;
			}
		}
		if(index == -1) {
			return index;
		}
		for(int i =index;i<arr.length-1;i++) {
			arr[i]=arr[i+1];
		}
		arr[arr.length-1] = 0;
		return index;
	}
	private static void print(int[] arrs) {
		for(int i=0;i<arrs.length;i++) {
			System.out.println(arrs[i]);
		}
	}
	public static void main(String[] args) {
	    int ARRAYLENGTH = 4;
		int[] arr = new int[ARRAYLENGTH];
		int[] arrs = new int[ARRAYLENGTH-1];
		Scanner sc=new Scanner(System.in);
		System.out.println("请输入要输入的数组:");
		for(int i= 0;i<arr.length;i++) {
			arr[i]=sc.nextInt();
		}
		System.out.println("请输入你要查找的数组元素:");
		int c = sc.nextInt();
		System.out.println("你输入的是"+c+"对应的数组元素下标是"+arr[c]);
	    Scanner input = new Scanner(System.in);
		System.out.print("从键盘输入被删除的元素:");
				int a=input.nextInt();
				int n=0;
				for(int i=0;i<arr.length;i++)
				{
					if(arr[i]!=a)
					{
						arrs[n++]=arr[i];
					}	
				}
				print(arrs);
			}
	}

	

没有更多推荐了,返回首页