1.1 数组的定义和初始化

1、定义

数组是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据。

线性表就是数据排成像一条线一样的结构,每个线性表上的数据最多只有前和后两个方向。
线性表结构:数组,链表,队列,栈

数组可分为一维数组、二维数组和多维数组。一维数组的定义有以下两种方式

数组类型[] 数组名;
数组类型 数组名[];

二维数组的定义方式如下:

数组类型[][] 数组名;
数组类型 数组名[][];

在定义数组时,[]可以放在类型后面,也可以放在变量名后面,示例代码如下:

int[] arr1;
String[] arr2;
float arr3[];
String[][] arr4;

我在通常使用的时候会习惯将它放在数据类型后面,我认为这样更加直观,先定义一个什么样的数据,然后是数据叫什么名字。

注意:在数组定义中不能指定数组的长度,在数组的创建阶段需要指定大小,用于分配存储空间。

2、静态初始化和动态初始化

1. 静态初始化

静态初始化是指在定义时同时指定数组元素内容,示例如下

int[] arr1 = {1,2,3,4,5,6,7};
String[] arr2 = {"张三","李四","王五"};
String[][] arr3 = {{"张三","老师"},{"李四","警察"},{"王五","医生"}};

在静态初始化时,不需要指定数组的大小,系统会根据指定的内容的数量自动分配大小。

2. 动态初始化

动态初始化是指在定义时首先通过new关键字开辟指定大小的存储空间,然后再为存储单元指定内容,示例如下:

//动态初始化一维数组
int[] arr1 = new int[3];
arr1[0] = 1;
arr1[1] = 2;
arr1[2] = 3;
//动态初始化二维数组
String[][] arr2 = new String[2][3];
arr2[0][0]="张三";
arr2[0][1]="老师";
arr2[0][2]="湖北";
arr2[1][0]="李四";
arr2[1][1]="警察";
arr2[1][2]="四川";

在通过new关键字创建多维数组时,不必指定每一维的大小,而只需要指定最左边的维的大小即可。如果指定了某一维的大小,那么处于这一维左边的各维大小都需要指定,否则将编译出错,代码如下:

//错误
String[][] arr1 = new String[][3];
//正确
String[][] arr2 = new String[2][];
//正确
String[][] arr3 = new String[2][3];

1.2 作为抽象数据类型的数组

先来看看这个例子,我们先定义一个抽象类Shape,再定义两个子类继承这个抽象类,目的是求矩形的圆形的面积,代码如下:

public abstract class Shape  {
    public abstract double area();//求面积
}

//矩形
public class Rectangular extends Shape {

    private double width;
    private double height;

    public Rectangular(double w,double h){
        this.width = w;
        this.height = h;
    }

    @Override
    public double area() {
        double res = 0;
        res = width * height;
        return res;
    }
}

//圆形
public class Circle extends Shape {

    private double radius;//半径

    public Circle(double r){
        this.radius = r;
    }

    @Override
    public double area() {
        return Math.PI*radius*radius;
    }
}

//测试类
public class Test1 {
    public static void main(String[] args) {
        Shape shape = new Shape();//报错'Shape' is abstract; cannot be instantiated
        Shape[] shapes = new Shape[2];//重要
        shapes[0] = new Rectangular(3,4);
        shapes[1] = new Circle(2);

        System.out.println("矩形的面积为"+shapes[0].area());//矩形的面积为12.0
        System.out.println("圆形的面积为"+shapes[1].area());//圆形的面积为12.566370614359172
    }

}

抽象类的定义是不能直接new的,但是他可以通过抽象数组的方式创建。这是因为抽象类只是给数组的元素制定了数据类型,规定了它只能存放该类型的数据或引用。

数组中存放的是这些元素的首地址,这个过程中并没有对象创建的步骤。

而new对象的时候系统会给该对象分配内存进行初始化,然后将变量指向初始化后的对象。

1.3 数组的顺序存储方式

#include<stdarg.h>  
#define MAX_ARRAY_DIM 8 //假设数组维数的最大值为8 
typedef struct {
 ElemType *base;  //数组元素基址,由InitArray分配
 int dim;  //数组维数
 int *bounds;  //数组维界基址,由InitArray分配
 int *constants;  //数组映象函数常量基址,由InitArray分配
}Array;

Status InitArray(Array &A,int dim,...){//这里用的是“可变参”形参方式。它主要解决维数不定的问题。
//举例:设有4维数组,各维分别是:4,5,6,7(这些数字是随意给的),那么,调用方式:
//InitArray(ar, 4, 4, 5, 6, 7);
//ar其中,ar也是假设的变量名称, 4表示数组有4维, 4, 5, 6, 7这4个数是各维大小
//如果是5维的,那么就这样:
//InitArray(ar, 5, 第一维数,第二维数,第三维数,第四维数,第五维数);
//若维数dim和随后的各维长度合法,则构造相应的数组A,并返回OK。
if (dim<1 ||dim>MAX_ARRAY_DIM) return ERROR;
A.dim=dim;
A.bounds=(int *)malloc(dim*sizeof(int));
if (!A.bounds) exit(OVERFLOW);
//若各维长度合法,则存入A.bounds,并求出A的元素总数elemtotal。
elemtotal=1;
va_start(ap,dim); //ap为va_list类型,是存放变长参数表信息的数组。
for (i=0;i<dim;++i){
 A.bounds[i]=va_arg(ap,int);//从这里可以看出,A.bounds数组中,存放的是各维的大小
 if (A.bounds[i]<0) return UNDERFLOW;
 elemtotal * = A.bounds[i];//各维数之积,自然是数组中元素的总个数
}
va_end(ap);
A.base=(ElemType *)malloc(elemtotal *sizeof(ElemType));//这个就是“多维数组”的存储本质:一维数组!
//用一维方式表示多维数组后(其实,从管理和使用的角度看,内存就只有一维这么一种形式),存在如何按“多维”的逻辑角度定位元素的问题。再说清楚些:假设前面所讲的4维数组,其元素用下标形式表示,范围为:(0,0,0,0)到(3,4,5,6)。对于任意下标(在有效范围内)(i1, i2, i3, i4)所对应的元素,转换到“一维”空间后,其下标应该是什么?这就是这个程序后面要处理的主要问题。
if (!A.base) exit (OVERFLOW):
//求映象函数的常数ci(i为下标),并存入A.constants[i-1],i=1,...dim。
A.constants=(int *)malloc(dim *sizeof(int));
if (!A.constants)exit (OVERFLOW);
//以前面的4维数组为例子,其中A.bounds[0]=4,A.bounds[1]=5,A.bounds[2]=6,A.bounds[3]=7。
//跟踪下面的程序:
A.constants[dim-1]=1;//A.constants[3] = 1
for (i=dim-2;i>=0;--i)//A.constants[2] = 7,A.constants[1] = 6*7,A.constants[0] = 5*6*7
 A.constants[i]=A.bounds[i+1] * A.constants[i+1];
//说到这里,这个问题就清晰了:A.constants中的元素,是帮助定位用的。比如说:对于(2,0,0,0)这个下标的元素,应该越过前面的(0,0,0,0)~(0,4,5,6)和(1,0,0,0)~(1,4,5,6)这两大块,而这两大块中的每一块都有5*6*7个元素,这正好就是A.constants[0]中所存放的数据啊!
//现在应该明白了吧!
return OK;
}

status Locate(Array A,va_list ap,int &off){
//若ap指示的各下标值合法,则求出该元素在A中相对地址off。
 off=0;
 for (i=0;i<A.dim;++i){
 ind=va_arg(ap,int);
 if (ind<0 || ind>=A.bounds[i]) return OVERFLOW;
 off + = A.constants[i] * ind;
 }
 return OK;
Last modification:October 24th, 2020 at 02:51 pm
如果觉得我的文章对你有用,请随意赞赏