|
西交《数据结构》FAQ(五)
第五章 数组和广义表
1、什么是数组,有哪些基本操作?
1)数组=(数据,顺序)。数组在程序设计中,为了处理方便,把具有相同类型的若干变量按有序的形式组织起来。这些按序排列的同类数据元素的集合称为数组。在C语言中,数组属于构造数据类型。一个数组可以分解为多个数组元素,这些数组元素可以是基本数据类型或是构造类型。因此按数组元素的类型不同,数组又可分为数值数组、字符数组、指针数组、结构数组等各种类别。
2)基本操作4个
InitArray (&A,n,bound1,…,boundn)建A 若维数n和各维长度合法,则构造相应的数组A,并返回OK
DestroyArray(&A)删A 销毁数组A
Value(A,&e,index1,…,indexn)取a A是n维数组,e为元素变量,随后是n个下标值。若各下标不超界,将e赋值为所指定的A的元素值,并返回OK
Assign(&A,e,index1,…,indexn)a←e赋值A是n维数组,e为元素变量,随后是n个下标值。若每个下标不超界,则将e的值赋给指定的A的元素,并返回OK
2、什么是稀疏矩阵,如何存储?
如果在矩阵中,多数的元素并没有数据,称此矩阵为稀疏矩阵(sparse matrix)。
矩阵在程序中常使用二维阵列表示,二维阵列的大小与使用的存储器空间成正比,如果多数的元素没有数据,则会造成存储器空间的浪费,为此,必须设计稀疏矩阵的阵列储存方式,利用较少的存储器空间储存完整的矩阵数据。
3、稀疏矩阵的优点。
稀疏矩阵的优点:稀疏矩阵的计算速度更快,因为M AT L A B只对非零元素进行操作,这是稀疏矩阵的一个突出的优点。假设矩阵A,B中的矩阵一样.计算2*A需要一百万次的浮点运算,而计算2*B只需要2 0 0 0次浮点运算。
对于一个用二维数组存储的稀疏矩阵Amn,如果假设存储每个数组元素需要L个字节,那么存储整个矩阵需要m*n*L个字节.但是,这些存储空间的大部分存放的是0元素,从而造成大量的空间浪费.为了节省存储空间,可以只存储其中的非0元素.
对于矩阵Amn的每个元素aij,知道其行号i和列号j就可以确定其位置.因此对于稀疏矩阵可以用一个结点来存储一个非0元素.该结点可以定义如下:[i,j,aij] 该结点由3个域组成,i:行号,j:列号;aij元素值.这样的结点被称为三元组结点。矩阵的每一个元素Qij,由一个三元组结点(i,j,aij)唯一确定。
4、数组使用中的几个注意点。
对于数组类型说明应注意以下几点:
1) 数组的类型实际上是指数组元素的取值类型。对于同一个数组,其所有元素的数据类型都是相同的。
2) 数组名的书写规则应符合标识符的书写规定。
3) 数组名不能与其它变量名相同,例如:
void main()
{ int a;
float a[10];
……
} 是错误的。
4) 方括号中常量表达式表示数组元素的个数,如a[5]表示数组a有5个元素。但是其下标从0开始计算。因此5个元素分别为a[0],a[1],a[2],a[3],a[4]。
5) 不能在方括号中用变量来表示元素的个数, 但是可以是符号常数或常量表达式。例如:
#define FD 5
void main()
{ int a[3+2],b[7+FD];
……
} 是合法的。但是下述说明方式是错误的。
void main()
{ int n=5;
int a[n];
……
}
6) 允许在同一个类型说明中,说明多个数组和多个变量。
5、对数组赋值时需要注意什么?
C语言对数组的初始赋值还有以下几点规定:
1) 可以只给部分元素赋初值。当{ }中值的个数少于元素个数时,只给前面部分元素赋值。例如: static int a[10]={0,1,2,3,4};表示只给a[0]~a[4]5个元素赋值,而后5个元素自动赋0值。
2) 只能给元素逐个赋值,不能给数组整体赋值。 例如给十个元素全部赋1值,只能写为: static int a[10]={1,1,1,1,1,1,1,1,1,1};而不能写为: static int a[10]=1;
3) 如不给可初始化的数组赋初值,则全部元素均为0值。
4) 如给全部元素赋值,则在数组说明中, 可以不给出数组元素的个数。例如: static int a[5]={1,2,3,4,5};可写为: static int a[]={1,2,3,4,5};动态赋值可以在程序执行过程中,对数组作动态赋值。这时可用循环语句配合scanf函数逐个对数组元素赋值。
6、数组的降维存放示意图
7、数组的定位公式
1维Loc(ai)=Loc(a1)+(i-1)×L 线性表的顺序存储
2维Loc(ai,j)=Loc(c1,c2)+[(b2-c2+1)×(i-C1)+(j-c2)]×L源于此式
=Loc(a0,0)+ [ (b2-c2+1)×i+j]×L简化后公式
Loc(i,j)=Loc(0,0)+ [ (b2+1)×i+j]×L
Loc(i,j)=Loc(0,0)+(b2×i+j)×L
元素个数(b1-c1+1)(b2-c2+1)本内容由易百网整理发布
网址 www.openhelp100.com
QQ 515224986
|
|