普通高等教育“十一五”国家级规划教材
• /*初始化数组A*/
1. Status InitialArray(Array &A, int Adim) 2. /*如果维数Adim和数组各维的长度bounds合法，构造相应的数组A， 并返回OK值*/ 3. { /*如果维数Adim不合法，返回值为error */ 4. if (Adim<1||Adim> MAXDIM) 5. return error ; 6. A.dim=Adim; 7. A.bounds=(int* )malloc(Adim*sizeof(int)); 8. if (!A.bounds) 9. exit (overflow); 10. /*如果各维长度合法，则存入A.bounds，并求出A的元素总数 totalnum*/ 11. totalnum=1; 12. va_start(ap, Adim); /*ap为存放变长参数表信息的数组，其类 型为va_list*/
• 推广到n维数组:
普通高等教育“十一五”国家级规划教材
A0 (1)
A1(1)
An-1 (1)
以列序为主序
以行序为主序
普通高等教育“十一五”国家级规划教材
•
1. 2. 3. 4. 5. 6. 7.
/*数组的顺序存储表示*/
typedef struct { ElemType *base; /*数组元素初始地址，由初始化操作实 现*/ int dim; /*数组的维数*/ int *bounds; /*数组各维的长度，也由初始化操作实现*/ int *const ; /*数组的映象函数常量的初始地址，由初始化操 作实现*/ } Array;
片连续的存储单元中
• 二维数组有两种存储方式：以列序为主序（column
major order）的存储方式，如图6-2(a)所示和以行序为 主序（row major order）的存储方式，如图6-2(b)所示
• 地址计算：以行序为主序的存储方式为例
LOC[i,j]=LOC[0,0]+(b2i+j) L
解答：
• (1) 由于C语言数组的行、列下界均为0，该数组行上 界为5－1＝4，列上界为4－1=3，所以该数组的元素 共有5×4＝20个 • (2)由于C语言采用行序为主的存储方式，根据式子6-1 : ,LOC[3,2]=LOC[0,0]+(b2i+j)L=2400+（4×3+2） ×4=2456
13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. }
for(i=0;i<Adim;++i) { A.bounds[i]=va_arg(ap,int); if(A.bounds[i]<0) return (underflow); totalnum* = A.bounds[i]; } va_end(ap); A.base=(ElemType*)malloc(dim*sizeof(ElemType)); if(!A.base) exit(overflow); /*求映象函数的常，把结果存入A.const [i-1],i=1,…,Adim*/ A.const=(int*)malloc(dim*sizeof(int)); if(!A.const) exit(overflow); A.const [Adim-1]=1; /*指针的增减以元素的大小为单位*/ for(i=Adim-2;i>=0,i--) A.const [i]=A.bounds[i+1]*A.const [i+1]; return OK;
• 数组（Array）：由一组类型相同的数据元素构成的
有限序列，且该有限序列存储在一块地址连续的内存单 元中
• 一维数组 ：数组只有一个下标 • 二维数组 ：数组元素都含有两个下标 ，形如：
普通高等教育“十一五”国家级规划教材
• 二维数组与一维数组的关系：
一个二维数组看成是每个数据元素都是相同类型的 一维数组的一维数组
普通高等教育“十一五”国家级规划教材
• 例6-2: 现有m名考生，每人参加n门课程考试，试写出
任一考生的总分数和任一门课程总分数的算法
• 解答：
1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. # define M 200 /*考生的人数*/ # define N 5 /*每个考生参加考试的课程门数*/ int Ascore[M][N] ; /*存放考生成绩的二维数组*/ /*求第i名考生的总分数*/ int StuScore ( int Ascore [ ][N] , int i) { int j , StuSum; StuSum = 0; /*赋初值*/ for ( j = 0 ; j < N ; j++ ) StuSum = StuSum +Ascore [ i-1][j]; /*求第i名考生的总分*/ return ( StuSum); }
普通高等教育“十一五”国家级规划教材
第6章 数组与广义表
• • • • • • 6.1 数组的定义及其基本操作 6.2 数组的顺序存储结构 6.3 矩阵的压缩存储 6.4 广义表的概念 6.5 广义表的存储结构表示 6.6 广义表的运算
Hale Waihona Puke 6.1 数组的定义及其基本操作 6.1.1 数组的定义
普通高等教育“十一五”国家级规划教材
普通高等教育“十一五”国家级规划教材
普通高等教育“十一五”国家级规划教材
例题6-1
对二维数组float array[5][4]，计算： (1) 数组array中的数组元素数目 (2) 若数组array的起始地址为2400，且每个数组元素长 度为32位（即四个字节），数组元素array [3][2]的内 存地址
普通高等教育“十一五”国家级规划教材
6.1.2 数组的基本操作
• 随机存：给定一组下标，存一个数据元素到该组下标
对应的内存单元中
• 随机取：从给定的一组下标所对应的内存单元中取出
一个数据元素
普通高等教育“十一五”国家级规划教材
6.2 数组的顺序存储结构
• 数组的顺序存储结构：将数组元素顺序地存放在一
• 事例：m行n列的二维数组，可以看成是一个线形表
A=(a1,a2,…,ap) (p=m 或 n) 即：
普通高等教育“十一五”国家级规划教材
•
1. 2. 3. 4.
数组的性质：
数组中的数据元素数目固定 数组中的数据元素具有相同的数据类型。 数组中的每个数据元素都和一组唯一的下标值对应。 数组是一种随机存储结构，可随机存取数组中的任意 数据元素