D4-数组

1.只有引用型操作，即只改变数组元素中的值，没有加工型操作，即不做插入删除操作

2.数组是多维结构，存储空间是一维结构

顺序映象方式：

1.行序为主序（低下标优先）

2.列序为主序（高下标优先）

eg：若三维数组[0,1][0,1,2][0,1]，以行序为主序，排列为（0,0,0）,（0,0,1）,（0,1,0）,（0,1,1）..

以列序为主序，排列为（0,0,0）,(1,0,0),(0,1,0),(1,1,0),(0,2,0),(1,2,0)...

假设每个元素占用L个存储单元，二维数组任意元素存储位置：LOC[i,j]=LOC[0,0]+(b2*i+j)*L;LOC[0,0]称基址或基地址

推广到n维：LOC[j1,j2,j3...]=LOC[0,0,0...]+L*该元素前的所有元素数，因此，数组元素的存储位置是线性函数，只要每个维度的长度确定，存储位置就确定，此时计算每个元素存储位置的时间相等，存储每个元素的时间是一样的，称其为顺序存储。

对于一个m行n列的数组，若其中存有t个非零元素，设t/（m*n）为稀疏因子，一般设稀疏因子小于0.05的矩阵为稀疏矩阵。稀疏矩阵存储时有大量的零，浪费存储空间，此外对稀疏矩阵做运算时对每个元素都需要判断与零的运算，大幅增大运算时间，因此需要对稀疏矩阵进行讨论，尽可能减少与零元素的计算，尽可能少存零元素，此外还要尽快找到所需要的元素。

矩阵转置的经典算法时间复杂度O（mu*nu），下面的算法会减少时间的使用

1.三元组法

#define MAXSIZE 12500
typedef struct {
	int i, j;//行数和列数
	int e;//元素值
}Triple;
typedef struct {
	int mu, nu, tu;//三元组行数、列数、非零元素个数
	Triple data[MAXSIZE + 1];//data[0]储存长度
}TSMatrix;

在Triple的基础上定义第二个结构体TSMatrix有利于某些矩阵运算如计算转置矩阵等，求转置矩阵的时间复杂度为O（mu*nu），代码双重循环即可实现。

表示方式：（（arr1，col1，num1），（arr2，col2，num2），（arr3，col3，num3）...）即可得到唯一的数组。

在双重循环求三元组的基础上可以加上两个辅助变量，首先按列求出相同列的元素数目记为Num为一个一维数组，再创建一个新数组cPot记录从第一列开始前n列非零元素之和。

下图为示例，左边为按行增序排列，右边为按列增序排列

 代码实现如下

int FastTransposeMatrix(TSMatrix T, TSMatrix* S) {
	S->mu = T.mu;
	S->nu = T.nu;
	S->tu = T.tu;
	int num[MAXSIZE], cpot[MAXSIZE], i ,col;
	for (i = 1; i <= T.nu; i++)
		num[i] = 0;
	for (i = 1; i <= T.tu; i++)
		num[T.data[i].j]++;
	cpot[1] = 1;
	for (i = 2; i <= T.nu; i++)
		cpot[i] = cpot[i - 1] + num[i + 1];
	//双重循环转置矩阵
}

若随机存取则从头查找，可以方便处理按顺序存储的矩阵

2.行逻辑连接的顺序表

给出结构定义

#define MAXMN 500
typedef struct {
	int mu, nu, tu;//三元组行数、列数、非零元素个数
	Triple data[MAXSIZE + 1];//data[0]储存元素个数
	int rpos[MAXMN + 1];
}RLSMatrix;

在快速算法中，虽然加快了速度，但是在M或N对应元素相乘时，若某一元素为零，结果显然为零，快速算法没有考虑到这种情况，因此用rpos存储有关信息进而加速。

实际操作时，使用累加器ctemp，假设M矩阵有i行j列，i从1到n，对每一行都先检测是否有N矩阵的列与其相乘结果不为零，即M（i，j）与N（j，k）相乘，并对于不同的k将接过放在不同的累加器中。对每一行都可以将乘出的Q（i，k）存储进Q.data中。Q.data视做一个一维数组，rpos记录每行第一个非零元素在Q.data中的位置。

代码实现如下

int MultSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix* Q) {
	int arow, brow, tp, p, q, tq, ccol;
	int ctmp[];//累加器
	if (M.nu != N.mu) {
		printf("ERROR");
		return 0;
	}

	Q->mu = M.mu, Q->nu = N.nu, Q->tu = 0;
	if (M.mu * N.nu != 0) {
		for (arow = 1; arow = M.mu + 1; arow++) {
			ctmp[arow] = 0;
			if (arow < M.mu)
				tp = M.rpos[arow + 1];
			else
				tp = M.tu + 1;
			for (p = M.rpos[arow]; p < M.rpos[arow] + 1; p++) {
				if (brow < N.mu)
					tq = N.rpos[arow + 1];
				else
					tq = N.tu + 1;
				for (q = N.rpos[arow] + 1; q < tq; q++) {
					ccol = N.data[q].j;
					ctmp[ccol] += M.data[p].i * N.data[q].j;
				}
			}
		}


		for (ccol = 1; ccol <= Q->nu; ccol++) {
			if (ctmp[ccol]){
				Q->data[Q->tu] = (arow, ccol, ctmp[ccol]);
				if (Q->tu++ > MAXSIZE) {
					printf("ERROR");
					return 0;
				}
			}
		}
	}
	return 1;
}

该方法的时间复杂度为O（M.mu*N.nu）。

3.十字链表

若矩阵中非零元个数变化较大时，宜使用十字链表。例如两个矩阵相加，此时可能非零元素变为零元素，或零元素变为非零元素，若使用上面两种算法，元素的位置变化会比较多且繁杂。

十字链表总体需要五个变量：非零元素，该元素所在的行列数和系数矩阵的行列数。每存储一个非零元素，有right和down指针指向同一行和同一列的下一个非零元素；为便于寻找数据，用一维数组mhead和rhead存储每一行、列的头指针。由此得出结构体定义

typedef struct _ONode {
	int i, j;//非零元素所在的行号列号
	int e;//非零元素的值
	struct _ONode* right, * down;//指向右和向下的指针
}ONode, * OLink;

typedef struct {
	OLink* mhead, * rhead;
	int mu, nu, tu;//稀疏矩阵的行数、列数、非零元素个数
}CrossList;

*对pq定义类型存疑

建立十字链表

int CreateMatrixLink(CrossList* M) {
	if (M)
		free(M);
	int m, n, t;
	scanf("%d %d %d", &m, &n, &t);
	M->mu = m, M->nu = n, M->tu = t;

	//初始化结点
	if (!(M->mhead = (OLink*)malloc(sizeof(OLink) * (m + 1))))
		exit(OVERFLOW);
	if (!(M->chead = (OLink*)malloc(sizeof(OLink) * (n + 1))))
		exit(OVERFLOW);
	M->mhead = M->chead = NULL;

	int i, j, e;

	for (scanf(&i, &j, &e);i!=0; scanf(&i, &j, &e)) {
		if(!(p=(ONode*)malloc(sizeof(ONode))))
			exit(OVERFLOW);
		p.i = i, p.j = j, p.e = e;

		//p从行头插入，第i行无元素或M.head[i]结点在p右边的情况
		if (M->mhead[i] == NULL || M->mhead[i]->j > j) {
			p.right = M->mhead[i];
			M->mhead[i] = p;
		}
		//M.head[i]在p左边（一般情况）
		else {
			//对第i列进行行插入
			for (q = M.mhead[i]; (q.right.j < j) && (q.right); q = q.right) {
				p.right = q.right;
				q.right = p;
			}
		}

		//对列做相同操作
		if (M->chead[j] == NULL || M->chead[j]->i > i) {
			p.down = M->chead[j];
			M->chead[j] = p;
		}
		else {
			for (q = M.chead[j]; (q.down.i < i) && (q.down); q = q.down) {
				p.down = q.down;
				q.down = p;
			}
		}
	}

	return 1;
}

 对稀疏矩阵相加有四种情况：

1.a矩阵元素为零，则结点值为b矩阵元素值

2.b矩阵元素为零，则结点值不变

3.元素值变为ab矩阵元素值相加

4.值变为0，删除该结点地址

实现时，设指针pa，pb指向某行，pa==NULL表示该行没有非零元

pa->j < pb->j
//向右移动pa即可，递推

(pa->j == pb->j) && (pa->e + pb->e == 0)
//删除pa指向的结点地址，同时要注意改变pa前一个的right值和上一个的down值（指向另外的结点地址）

(pa->j == pb->j) && (pa->e + pb->e != 0)
//改变pa指向的结点值即可

pa->j > pb->j || pa == NULL;
//在pa前增加一个结点地址，改变同一行中前一个结点的right和同一列中上一个节点的down

代码实现较容易，不过多叙述