第6章 数组与广义表 6.1 数组的定义及其基本操作 6.2 数组的顺序存储结构 6.3 矩阵的压缩存储 6.4 广义表的概念 第6章 数组与广义表 6.1 数组的定义及其基本操作 6.2 数组的顺序存储结构 6.3 矩阵的压缩存储 6.4 广义表的概念 6.5 广义表的存储结构表示 6.6 广义表的运算

6.1 数组的定义及其基本操作 6.1.1 数组的定义 数组（Array）：由一组类型相同的数据元素构成的有限序列，且该有限序列存储在一块地址连续的内存单元中 一维数组 ：数组只有一个下标 二维数组 ：数组元素都含有两个下标 ，形如：

二维数组与一维数组的关系： 一个二维数组看成是每个数据元素都是相同类型的一维数组的一维数组 事例：m行n列的二维数组，可以看成是一个线形表 A=(a1,a2,…,ap) (p=m 或 n) 即：

数组的性质： 数组中的数据元素数目固定 数组中的数据元素具有相同的数据类型。 数组中的每个数据元素都和一组唯一的下标值对应。 数组是一种随机存储结构，可随机存取数组中的任意数据元素

随机存：给定一组下标，存一个数据元素到该组下标对应的内存单元中 随机取：从给定的一组下标所对应的内存单元中取出一个数据元素 6.1.2 数组的基本操作 随机存：给定一组下标，存一个数据元素到该组下标对应的内存单元中 随机取：从给定的一组下标所对应的内存单元中取出一个数据元素

6.2 数组的顺序存储结构 数组的顺序存储结构：将数组元素顺序地存放在一片连续的存储单元中 6.2 数组的顺序存储结构 数组的顺序存储结构：将数组元素顺序地存放在一片连续的存储单元中 二维数组有两种存储方式：以列序为主序（column major order）的存储方式，如图6-2(a)所示和以行序为主序（row major order）的存储方式，如图6-2(b)所示 地址计算：以行序为主序的存储方式为例 推广到n维数组: LOC[i,j]=LOC[0,0]+(b2i+j) L

A0 (1) A1(1) An-1 (1) 以列序为主序 以行序为主序

/*数组的顺序存储表示*/ typedef struct { ElemType *base; /*数组元素初始地址，由初始化操作实现*/ int dim; /*数组的维数*/ int *bounds; /*数组各维的长度，也由初始化操作实现*/ int *const ; /*数组的映象函数常量的初始地址，由初始化操作实现*/ } Array;

/*初始化数组A*/ Status InitialArray(Array &A, int Adim) /*如果维数Adim和数组各维的长度bounds合法，构造相应的数组A，并返回OK值*/ { /*如果维数Adim不合法，返回值为error */ if (Adim<1||Adim> MAXDIM) return error ; A.dim=Adim; A.bounds=(int* )malloc(Adim*sizeof(int)); if (!A.bounds) exit (overflow); /*如果各维长度合法，则存入A.bounds，并求出A的元素总数totalnum*/ totalnum=1; va_start(ap, Adim); /*ap为存放变长参数表信息的数组，其类型为va_list*/

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;

例题6-1 解答： 对二维数组float array[5][4]，计算： (1) 数组array中的数组元素数目 (1) 由于C语言数组的行、列下界均为0，该数组行上界为5－1＝4，列上界为4－1=3，所以该数组的元素共有5×4＝20个 (2)由于C语言采用行序为主的存储方式，根据式子6-1 : ,LOC[3,2]=LOC[0,0]+(b2i+j)L=2400+（4×3+2）×4=2456

例6-2: 现有m名考生，每人参加n门课程考试，试写出任一考生的总分数和任一门课程总分数的算法 解答： # 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); }

/*求j门课程总分数*/ int CourseTotal ( int Ascore [ ][N] , int j) { int i , CourseSum ; CourseSum = 0; /*赋初值*/ for (i= 0 ; i< M ; i++ ) CourseSum = CourseSum +Ascore [ i][j-1]; /*求j门课程的总分*/ return (CourseSum); }

6.3 矩阵的压缩存储 特殊矩阵：具有许多相同的元素或者零元素且这些元素在矩阵中的分布有一定的规律的矩阵 6.3 矩阵的压缩存储 特殊矩阵：具有许多相同的元素或者零元素且这些元素在矩阵中的分布有一定的规律的矩阵 稀疏矩阵：一个矩阵中的非零元素远远少于零元素的矩阵 压缩存储：是指为多个值相同的元素只分配一个存储空间，而对零元素不分配存储空间，必须能够体现矩阵的逻辑结构

6.3.1 特殊矩阵的压缩存储 对称矩阵 三角矩阵 对角矩阵

对称矩阵的压缩存储 对称矩阵：若一个n阶矩阵A中的元素满足下述关系， aij=aji 1≤i,j≤n，形如： 对称矩阵存储方式（以行序为主序最为事例）： 以一维数组one[n(n+1)/2]作为n阶对称矩阵A的存储结构，则one[k]和矩阵中的元素aij之间存在着下述一一对应的关系：

数据元素和k之间的关系： 返回

三角矩阵的压缩存储 上三角矩阵：一个n阶方阵，它的主对角线的左下方元素均为零元素的矩阵，即当i>j时，aij=0 ，其地址k的计算公式： 下三角矩阵：一个n阶方阵，它的主对角线的右上方元素均为零元素的矩阵。即当i<j时，aij=0 事例： 返回

对角矩阵：所有的非零元均集中在以对角线为中心的带状区域中的n阶方阵 对角矩阵的压缩存储 对角矩阵：所有的非零元均集中在以对角线为中心的带状区域中的n阶方阵

6.3.2 稀疏矩阵的压缩存储 稀疏矩阵：一个阶数较大的矩阵中的非零元素个数相对于矩阵元素的总个数十分小时，形如： 稀疏矩阵的压缩存储—三元组(i,j,aij): (i,j)表示行列位置

三元组顺序表 三元组线性表：对稀疏矩阵，把它的每个非零元素表示为三元组，并按行号的递增排列，则构成稀疏矩阵的三元组线性表 三元组顺序表的存储结构定义 ： #define MAXSIZE 256 /*矩阵中非零元素个数的最大值*/ typedef struct { int i; /*矩阵元素中非零元的行下标*/ int j; /* 矩阵元素中非零元的列下标*/ ElemType e; /*矩阵元素的值*/ }Triple; /*三元组的定义*/

矩阵运算： 矩阵转置运算 矩阵相乘运算 typedef struct { int mu ; /*矩阵的行数*/ int nu ; /*矩阵的列数*/ int tu ; /*矩阵的非零元素个数*/ Triple data[MAXSIZE+1]; /*data为非零元三元组表，data[0]没有用*/ }Tabletype ; /*三元组顺序表的定义*/ 矩阵运算： 矩阵转置运算 矩阵相乘运算

矩阵转置运算 概念：对于一个m×n 的矩阵M，它的转置矩阵N是一个n×m的矩阵，且N(i,j)=M(j,i)，1≤i≤n，1≤j≤m ，形如： 实现步骤： 将矩阵的行列值相互交换； 将每个三元组中的i和j相互调换； 重新排列三元组之间的顺序便可实现矩阵的转置

第一种解决方法：是按照b.data中的三元组的次序，依次在a.data中找到相应的三元组，然后进行转置

算法： #include <stdio.h> #include <stdlib.h> #define MAXSIZE 20 /*假设矩阵中非零元个数的最大值为20*/ typedef struct { int i; /*矩阵元素中非零元的行下标*/ int j; /* 矩阵元素中非零元的列下标*/ int e; /*矩阵元素的值*/ }Triple; /*三元组的定义*/ int mu ; /*矩阵的行数*/ int nu ; /*矩阵的列数*/ int tu ; /*矩阵的非零元素个数*/ Triple data[MAXSIZE+1]; /*data为非零元三元组表，data[0]没有用*/ }Tabletype ; /*三元组顺序表的定义*/

/*输出矩阵m*/ void out_matrix(struct Tabletype m); void TransposeSMatrix(struct Tabletype a,struct Tabletype *b); /*主函数*/ main() { struct Tabletype a={6,7,8,{{1,2,12},{1,3,9},{3,1,- 3},{3,6,14},{4,3,24},{5,2,18},{6,1,15},{6,4,-7}}}; struct Tabletype b;/＊声明矩阵b＊/ out_matrix(a); TransposeSMatrix(a,&b);/*对矩阵a转置，并将结果存入矩阵b*/ printf("The followed matrix is the TransposeSMatrix of the front matrix\n"); out_matrix(b); exit(0); }

void out_matrix(struct Tabletype m) { int i,j,k; k=0; for(i=1;i<=m.mu;i++) for(j=1;j<=m.nu;j++) /*非零元素*/ if((m.data[k].i==i)&&(m.data[k].j==j)) printf("%5d",m.data[k].e); k++; } /*零元素*/ else printf("%5d",0); printf("\n");

void TransposeSMatrix(struct Tabletype a,struct Tabletype *b) { int p,q,col; (*b).mu=a.nu; (*b).nu=a.mu; (*b).tu=a.tu; if((*b).tu) q=0; /*b.data的下标*/ for(col=1;col<=a.nu;col++) for(p=0;p<a.tu;p++) /*p为a的下标*/ if( a.data[p].j==col) /*以*b.data[q]的i域次

{ (*b).data[q].i=a.data[p].j; (*b).data[q].j=a.data[p].i; (*b).data[q].e=a.data[p].e; q++; }

矩阵转置的第二种方法 方法：按照a.data中三元组的次序进行转置，然后将转置后的三元组置入b中恰当的位置 ；为确定位置，在转置前，应求出M中每一列中非零元素的个数，和每一列的第一个非零元在b.data中应有的位置；用num[col]表示矩阵M中第col列中非零元素的个数，cpot[col]表示M中第col列的第一个非零元素在b.data中的正确位置，得出下面一组公式 cpot[1]=1; cpot[col]=cpot[col-1]+num[col-1]; 2≤col≤a.nu

算法（矩阵的快速转置）： #include <stdio.h> #include <stdlib.h> #define MAXSIZE 20 typedef struct { int i; /*矩阵元素的行下标*/ int j; /* 矩阵元素的列下标*/ int e; /*矩阵元素的值*/ }Triple; /*三元组的定义*/ int mu ; /*矩阵的行数*/ int nu ; /*矩阵的列数*/ int tu ; /*矩阵的非零元素个数*/ Triple data[MAXSIZE+1]; }Tabletype ; /*三元组顺序表的定义*/

/*主函数*/ void out_matrix(struct Tabletype m);/*定义见程序6.1*/ void Fast_TransposeSMatrix(struct Tabletype a,struct Tabletype *b); /*主函数*/ main() { struct Tabletype a={6,7,8,{{1,2,12},{1,3,9},{3,1,- 3},{3,6,14},{4,3,24}, {5,2,18},{6,1,15},{6,4,-7}}}; struct Tabletype b; out_matrix(a); Fast_TransposeSMatrix(a,&b); printf("The followed matrix is the TransposeSMatrix of the front matrix e\n"); out_matrix(b); exit(0); }

/*用快速转置方法求稀疏矩阵a的转置矩阵*/ void Fast_TransposeSMatrix(struct Tabletype a,struct Tabletype *b) { int p,q,col,t; int num[MAXSIZE+1]; int cpot[MAXSIZE+1]; (*b).mu=a.nu; (*b).nu=a.mu; (*b).tu=a.tu; if((*b).tu) for(col=1;col<=a.nu;col++) num[col]=0;

/*求矩阵a中每一列中非零元的个数*/ for(t=1;t<=a.tu;t++) num[a.data[t].j]++; /*第col列中第一个非零元在 b.data中的序号*/ cpot[1]=1; for(col=2;col<=a.nu;col++) cpot[col]=cpot[col-1]+num[col-1]; for(p=0;p<a.tu;p++) { col=a.data[p].j; q=cpot[col]; (*b).data[q-1].i=a.data[p].j; (*b).data[q-1].j=a.data[p].i; (*b).data[q-1].e=a.data[p].e; cpot[col]++; }

矩阵乘法 已知M是m1×n1的矩阵，N是m2×n2的矩阵， 当n1=m2时，定义矩阵M和N的乘积为：Q=M×N，Q是m1×n2的矩阵 算法 6.2 矩阵相乘算法 for(i=1;i<=m1;i++) for(j=1;j<=n2;j++) { Q[i][j]=0; for(k=1;k<=n1;k++) Q[i][j]+=M[i][k]×N[k][j]; } 这个算法的时间复杂度为O(m1×n1×n2)

稀疏矩阵乘法 第一种情况 ：为求c(即Q)的值，只需在a.data(即M.data) 和b.data（即N.data）中找到相应的各对元素，即a.data中的j值和b.data中的i值相等的各对元素相乘 为在b.data 中寻找矩阵N中第k行的所有非零元，附设一个向量rpos[1..m2];(1)求出矩阵N中各行的非零元的个数num[1..m2]，(2)求得N中各行的第一个非零元在b.data中的位置，则有： rpos[1]=1 rpos[col]=rpos[col-1]+num[col-1] 2≤col<b.mu

第二种情况:对稀疏矩阵相乘，可按如下步骤来操作：(1) 对a中每个非零元素a. data[p](p=1,2,…,a 第二种情况:对稀疏矩阵相乘，可按如下步骤来操作：(1) 对a中每个非零元素a.data[p](p=1,2,…,a.tu)，在b中找到所有满足条件a.data[p].j=b.data[q].i的元素b.data[q] (2)求出a.data[p].e和b.data[q].e的乘积 为了便于操作，可以对每一元素增加一个存储累计和的变量，设其初始值为零，然后对数组a进行扫描，求得相应元素的乘积之后，并累加到适当的求累计和的变量上

算法： #include <stdio.h> #include <stdlib.h> #define MAXSIZE 20 #define MAXRC 10 /*假定矩阵的最大行数为10*/ struct Triple { int i; int j; int e; }; struct Tabletype int mu; int nu; int tu; struct Triple data[MAXSIZE+1]; int rpos[MAXRC+1]; /*各行第一个非零元的位置表*/

void out_matrix(struct Tabletype m); /*矩阵a1和矩阵b1相乘，并存储到指针c1*/ void multiMatrix(struct Tabletype a1,struct Tabletype b1,struct Tabletype c1) /*主函数*/ main( ) { /*声明并初始化矩阵a*/ struct Tabletype a={3,4,4,{{0,2,0,0},{0,0,1,0},{3,0,4,0}}}; /*声明并初始化矩阵*b/ struct Tabletype b={4,2,4,{{3,0},{0,1},{0,0},{0,2}}}; struct Tabletype c; out_matrix(a); out_matrix(b); multiMatrix(a,b,&c); printf("The followed matrix is the multiMatrix of front two matrixes\n"); out_matrix(c); exit(0); }

/*实现两矩阵相乘*/ void multiMatrix(struct Tabletype a1,struct Tabletype b1,struct Tabletype *c1) { int i, t; int p,q; int arow,brow,ccol; int ctemp[MAXRC+1]; if (a1.nu!=b1.mu) exit(1); /*对矩阵(*c1)初始化*/ (*c1).mu=a1.mu; (*c1).nu=b1.nu; (*c1).tu=0; if(a1.tu×b1.tu!=0)

/*矩阵(*c1)是非零矩阵时，执行下面代码*/ for(arow=1;arow<=a1.mu;arow++) { /*处理矩阵a1的每一行*/ for (i=0;i< MAXRC+1;i++) ctemp[i]=0; /*当前行各元素累加器清零*/ (*c1).rpos[arow]=(*c1).tu+1; for(p=a1.rpos[arow]; p<a1.rpos[arrow+1];p++) { /*对当前行中每一非零元，找到对应元在矩阵b1中的行号*/ brow=a1.data[p].j; if(brow<b1.nu) t=b1.rpos[brow+1]; else t=b1.tu+1; for (q=b1.rpos[brow];q<t;q++) { ccol=b1.data[q].j; /*乘积元素在矩阵（*c1）中的列号*/ ctemp[ccol]+=a1.data[p].e×b1.data[q].e; }/*for q*/ }

/*压缩存储该行非零元*/ for(ccol=1;ccol<=(*c1).nu;ccol++) if(ctemp[ccol]) { if(((*c1).tu)>MAXSIZE) exit(1); (*c1).data[(*c1).tu].i=arow; (*c1).data[(*c1).tu].j=ccol; (*c1).data[(*c1).tu].e=ctemp[ccol]; (*c1).tu++; }/*end if*/ }/*for arrow*/ }/*if*/ printf("%d",(*c1).tu); }

十字链表 概念：每个非零元素用一个结点表示，此结点有五个域，其中i,j和e三个域分别表示该非零元所在的行、列和非零元的值，right域用来指示同一行中的下一个非零元素，down域用来指示同一列中的下一个非零元素。行指针域将稀疏矩阵中同一行上的非零元素链接成一个线性链表，列指针将稀疏矩阵中同一列上的非零元素链接成一个线性链表，每一个非零元既是某个行链表上的一个结点，同时又是某个列链表上的一个结点，整个矩阵构成了一个十字交叉的链表，这样的存储结构为十字链表

事例：图6-9中的矩阵M的十字链表如图6-11所示 (错)

十字链表说明 typedef struct Node { int i；/*非零元的行下标＊/ int j; /*非零元的列下标*/ Elemtype e; /*非零元的数据元素值*/ struct Node *right; /*非零元所在行表的后继链域*/ struct Node *down; /*非零元所在列表的后继链域*/ }* OLink; typedef struct Node OLNode; typedef struct OLink *rhead;/*用于存放行表的头指针*/ OLink *chead;/*用于存放列表的头指针*/ int mu; /*表示矩阵的行数的个数*/ int nu; /*表示矩阵的列数*/ int tu; /*表示矩阵中非零元的个数*/ }CrossList;

建立稀疏矩阵的十字链表 /*主函数*/ /*创建由指针b指向的矩阵*/ void CreatSMatrix_OL(CrossList *b); /*输出由指针b指向的矩阵*/ void out_Matrix(CrossList *b); /*主函数*/ main() { CrossList M; CreatSMatrix_OL(&M); out_Matrix(&M); exit(0); }

void CreatSMatrix_OL(CrossList *b) { int i,j,e; int m,n,t; OLink p, q; scanf("%d%d%d",&m,&n,&t);/*输入矩阵的行数、列数和非零元素的个数*/ (*b).mu=m; (*b).nu=n; (*b).tu=t; if(!((*b).rhead=(OLink*)malloc((m+1)*sizeof(OLink)))) { printf("\ERROR\n"); exit(1); } if(!((*b).chead=(OLink*)malloc((n+1)*sizeof(OLink)))) { printf("\nERROR\n");

for(i=1;i<=m;i++) (*b).rhead[i]=NULL;/*初始化行头指针，各行链表为空链表*/ for(j=1;j<=n;j++) (*b).chead[j]=NULL; /*初始化列头指针，各列链表为空链表*/ /*按任意次序输入非零元*/ for(scanf("%d%d%d",&i,&j,&e);i!=0;scanf("%d%d%d",&i,&j,&e)) { if(!(p=(OLink )malloc(sizeof(OLink)))) printf("ERROR\n"); exit(1); } /*生成结点*/ p->i=i; p->j=j; p->e=e; p->right=NULL; p->down=NULL;

if((*b).rhead[i]==NULL) (*b).rhead[i]=p; else { /*寻找在行表中插入的位置*/ for(q=(*b).rhead[i];((q->right!=NULL)&&(q->right->j<j));q=q->right) p->right=q->right; q->right=p; } /*行插入完成*/ if((*b).chead[j]==NULL) (*b).chead[j]=p; { /*寻找在列表中插入的位置*/ for(q=(*b).chead[j];((q->down!=NULL)&&(q->down->i<i));q=q->down) p->down=q->down; q->down=p; } /*列插入完成*/ }

while(p!=NULL) void out_Matrix(CrossList *b) { int m,n,t; int i,j,e; OLNode *p,*q; m=(*b).mu; n=(*b).nu; t=(*b).tu; for(i=1;i<=m;i++) for (j=1;j<=n;j++) p=(*b).rhead[i]; while(p!=NULL)

if(p->j==j) break; p=p->right; } if(p!=NULL) printf("%5d ",p->e); else printf("%5d",0); printf("\n");

6.4 广义表的概念 广义表(Lists):是线性表的一种推广和扩充 ,允许元素具有独立的类型结构 6.4 广义表的概念 广义表(Lists):是线性表的一种推广和扩充 ,允许元素具有独立的类型结构 广义表一般记作 LS=(d1,d2,…,dn) LS:广义表的名称 n:是长度 di:可为单个元素，也可为广义表，分别称为广义LS的单元素和子表 当广义表LS非空时：d1称为LS的表头（Head），其余元素组成的表（d2,d3,…,dn）称作LS的表尾（Tail）

事例： A=（）—A是一个空表，其长度为零 B=（e）—广义表B只有一个单元素e，B的长度为1 C=（a , ( b , c ) )—广义表C的长度为2，两个元素分别为单元素a和子表（b , c） D=（A , B , C）—广义表D长度为3，三个元素都是子表。将子表的值代入后，有D=( ( ) , ( e ) , ( a , ( b , c ) ) ) L=( a , L )—一个递归的表，它的长度为2，第一个元素是单元素，第二个元素是L自身，展开后，L相当于一个无限的广义表，即L=( a , ( a , ( a , … ) ) )

广义表的重要特点： 广义表的元素可以是子表，而子表的元素还可以是子表 广义表可用其它广义表来表示 广义表可以是一个递归的表

结点的结构： 广义表的头尾链存储表示 广义表的扩展线性链表存储表示 6.5 广义表的存储结构表示 结点的结构： 广义表的头尾链存储表示 广义表的扩展线性链表存储表示

结点：元素结点，用以表示单元素 表结点，用以表示广义表 广义表的头尾链存储表示 结点：元素结点，用以表示单元素 表结点，用以表示广义表

/*广义表的存储表示*/ typedef enum { ATOM , LIST }ElemFlag; /*枚举类型ATOM=0表示单元素，LIST=1表示广义表*/ typedef struct GLNode ElemFlag flag； /*flag用于区分结点是单元素结点还是表结点*/ Union { /*单元素结点和表结点的联合部分*/ AtomType atom；/*atom是单元素结点的值域，AtomType是用户自定义类型*/

Struct { struct GLNode * headp ; /*指示表头的指针*/ struct GLNode *tailp ; /*指示表尾的指针*/ } lptr；/*lptr表示表结点的指针域，lptr.headp和lptr.tailp分别指示表头和表尾*/ }； }*Glist; /*定义一个广义表类型的变量*/

事例： 返回

广义表的扩展线性链表存储表示 存储结构： 事例：

/*广义表的扩展线性表存储表示*/ typedef enum { ATOM , LIST }Elemflag ; /*ATOM= =0表示单元素，LIST=1表示子表*/ typedef struct GLNode { Elemflag flag ; /* flag用于区分单元素结点和表结点*/ Union { /*单元素结点和表结点的联合部分*/ AtomType atom; /*atom是单元素结点的值域 */ struct GLNode * headp; /*表结点的表头指针*/ } struct GLNode *tailp; /*相当于线性链表中的next，指向下一个元素结点*/ }*Glist; /*定义一个广义表类型Glist，这个类型是一种扩展的线性链表*/

6.6 广义表的运算 基本运算：取表头head(Ls)，取表尾tail(Ls) 事例： head(L)=a， tail(L)=(b) head(B)=A， tail(B)=(y) 由于tail(L)是非空表，可继续分解得到： head(tail(L))=b， tail(tail(L))=()