首页 > 代码库 > 第五章:1.数组和广义表 -- 数组

第五章:1.数组和广义表 -- 数组

前言:  

  2、3、4章讨论的线性结构中的数据元素都是非结构的原子类型,元素的值是不再分解的。本章讨论的两种数据结构---数组和广义表可以看成是线性表在下述含以上的扩展:表中的数据元素本身也是一个数据结构。 

  其中、数组是一种比较熟知的数据类型,几乎所有程序语言都把数组类型设定为固有类型,前两节节以抽象数据类型的形式讨论数组的定义和实现,使读者加深对数组的理解。  

 

目录:

  1.数组的定义

  2.数组的顺序表示和实现

  3.矩阵的压缩存储

  4.广义表的定义

  5.广义表的存储结构

  6.m元多项式的表示

  7.广义表的递归算法    

 

正文:

  一、数组的定义

    类似于线性表,抽象数据类型数组可形式地定义为:

    ADT  Array{

      数据对象:

            ji=0,... ,bi-1, i=1,2,...,n

            D={aj1 j2 ... jn | n(>0) 称为数组的维数,bi 是数组第 i 维的长度,ji 是数组元素的第 i 维下标, aj1 j2 ... jn ∈ElmeSet}

      数据关系:

            R={R1,R2...Rn}

            Ri={

                < aj1 ... ji ... jn ,aj1 ... ji+1 ... jn  > | 

                  0<= j<=bk-1,1<= k <=n 且 k <> i

                  0<= j<=bk-2,

                  aj1 ... ji ... jn ,aj1 ... ji+1 ... jn ∈ D ,i = 2 ,  ...  n

              }

      基本操作:

            InitArray();

            DestoryArray();

            Value();

            Assign();

    }ADT   Array;

 

   二、数组的顺序表示及实现

    由于数组一般不作插入和删除操作,也就是说,一旦建立了数组,则结构中的数据元素和元素之间的关系就不再变动。因此,采用顺序存储结构表示数组是自然而然的事了

    由于存储单元是一维的结构,而数组是多维的结构,则用一组连续的存储单元存放数组的数据元素有个次序问题。

    例如、对于二维数组来说,可以看成是一维数组,一维数组的每一个数组元素又是一个一维数组。对应的对于二维数组有两种存储方式:

      1.以列序为主序的存储方式

      2.以行序为主序的存储方式

      技术分享

    由此,对于数组,一旦规定了他的维度和各维度的长度,便可为它分配存储空间。反之,至于给出一组下标便可求出相应数组元素的存储位置。

    大部分程序设计语言都采用了以行序为主序的存储方式。以下采用以行序为主序的存储方式为例予以说明

      假设每个数据元素占L个存储单元,则二维数组A 中任一元素 aij 的存储位置可由下式确定:

      LOC(i , j) =  LOC(0,0) + (b2 * i +j )*L

      LOC(i , j)是 a ij 的存储位置, LOC(0,0) 是a00 的存储位置,即二维数组A 的起始存储位置,也称基址,基地址。

    将其推广到一般,得n 维数组的数据元素存储位置的公式为:

      LOC(j1, ...jn) = LOC(0,...0) + (b2*b3*...*bn*j1+ b3*b4*...*bn*j2+  ...  + bn*jn-1 + jn) * L

      =LOC(0,...0) + ∑ ci ji  其中 cn=L , ci-1 = bi * ci  ,1< i <n

    LOC(0,...0) + ∑ ci ji 称为 n维数组的映像函数。一旦确定了数组的各维长度,ci 就是一个常数。

 

    数组的顺序存储结构:

typedef struct{
    ElemType *base;                 //数组元素基址,由InitArray 分配
    int dim;                        //数组维数
    int *bounds;                    //数组维界基址,由InitArray 分配
    int *constants;                 //数组映像函数常量基址,由InitArray 分配(constants[i]=ci)
}Array;

 

    代码实现:

#include<stdio.h>
#include<stdlib.h>
#include<stdarg.h>
//stdarg.h 头文件定义了一个变量类型 va_list 和三个宏,
//这三个宏可用于在参数个数未知(即参数个数可变)时获取函数中的参数。

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define UNDERFLOW -3

#define MAX_ARRAY_DIM 8
//Status是函数的类型,其值是函数结果状态码
typedef int Status;
typedef char ElemType;

typedef struct{
    ElemType *base;                 //数组元素基址,由InitArray 分配
    int dim;                        //数组维数
    int *bounds;                    //数组维界基址,由InitArray 分配
    int *constants;                 //数组映像函数常量基址,由InitArray 分配(constants[i]=ci)
}Array;

//初始化数组A]
Status InitArray(Array &A,int dim,...){
    if(dim<1||dim>MAX_ARRAY_DIM)
        return ERROR;

    A.dim=dim;
    A.bounds=(int *)malloc(dim*sizeof(int));
    if(!A.bounds) exit(OVERFLOW);
    
    //初始化每一维度的长度,并计算总的元素个数
    int ElemTotal=1;
    va_list ap;
    va_start(ap, dim);
    for(int i=0;i<dim;i++){
        A.bounds[i]=va_arg(ap, int);                //依次接收dim 参数后面的未确定的参数
        if(A.bounds[i]<0) return UNDERFLOW;
        ElemTotal *= A.bounds[i];                    //计算元素总数( 累乘维度 )
    }
    va_end(ap);


    //为dim 维数组A 分配所有的存储空间
    A.base=(ElemType *)malloc(ElemTotal*sizeof(ElemType));
    if(!A.base) exit(OVERFLOW);

    A.constants=(int *)malloc(dim*sizeof(int));
    if(!A.constants) exit(OVERFLOW);

    A.constants[dim-1]=sizeof(ElemType);
    for(int j=dim-2;j>=0;j--){
        A.constants[j]=A.bounds[j+1]*A.constants[j+1];
    }    

    return OK;
}

Status DestoryArray(Array &A){
    //销毁数组A
    if(!A.base) return ERROR;
    free(A.base);
    A.base=NULL;

    if(!A.bounds) return ERROR;
    free(A.bounds);
    A.bounds=NULL;

    if(!A.constants) return ERROR;
    free(A.constants);
    A.constants=NULL;

    return OK;
}

//计算 元素在 A 的相对位置,并用off返回
Status LocateArray(Array &A,va_list ap,int &off){
    off=0;
    for(int i=0;i<A.dim;i++){
        int locate=va_arg(ap, int);
        if(locate<0||locate>A.bounds[i])
            return OVERFLOW;
        off+=A.constants[i]*locate;
    }
    return OK;    
}

//返回某个合法下标对应的值。
Status Value(Array &A,ElemType *e,...){
    va_list ap;
    va_start(ap,e);
    int off;
    LocateArray(A,ap,off);
    va_end(ap);    
    *e=*(A.base+off);
    return OK;
}

//给A数组的合法下标赋值
Status Assign(Array &A,ElemType e,...){
    va_list ap;
    va_start(ap, e);
    int off;
    LocateArray(A,ap,off);
    va_end(ap);    
    *(A.base+off)=e;
    return OK;
}


void main(){
    Array A;
    InitArray(A,4,3,4,5,6);
    //赋值
    Assign(A,b,2,1,4,1);

    ElemType e;
    //取值
    Value(A,&e,2,1,4,1);
    printf("value:%c\n",e);
}

 

第五章:1.数组和广义表 -- 数组