數(shù)組：矩陣快速轉置矩陣相加三元組順序表/三元矩陣隨機生成稀疏矩陣壓縮矩陣【C語言，數(shù)據(jù)結構】（內含源代碼）

這篇具有很好參考價值的文章主要介紹了數(shù)組：矩陣快速轉置矩陣相加三元組順序表/三元矩陣隨機生成稀疏矩陣壓縮矩陣【C語言，數(shù)據(jù)結構】（內含源代碼）。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

目錄

題目：

題目分析：

概要設計：

二維矩陣數(shù)據(jù)結構：

三元數(shù)組\三元順序表順序表結構：

詳細設計：

三元矩陣相加：

三元矩陣快速轉置：

調試分析：

用戶手冊：

測試結果：

?源代碼：

主程序：

?頭文件SparseMatrix.h：

?頭文件Triple.h：

總結：

題目：

稀疏矩陣A，B均采用三元組順序表表示，驗證實現(xiàn)矩陣A快速轉置算法，并設計、驗證矩陣A、B相加得到矩陣C的算法。

題目分析：

1.從鍵盤輸入矩陣的行數(shù)、列數(shù)，隨機生成稀疏矩陣。

2.生成矩陣A、B后需先轉換成三元順序表，然后用三元順序表來進行之后的操作。

3.在三元順序表的基礎上使用快速轉置（非二維矩陣）。

4.得到三元矩陣相加的結果C。

5.不僅需要輸出三元矩陣，還需要把結果轉換成二維矩陣輸出，以便題目觀察結果。

6.程序執(zhí)行的命令包括：(1)根據(jù)輸入構造二維矩陣 (2)根據(jù)二維矩陣轉換成相應的三元矩陣 (3)根據(jù)三元矩陣轉換為相應的二維矩陣 (4)輸出程序 (5)三元矩陣相加 (6)三元矩陣快速轉置

7.測試用例：

1
(內置測試用例測試，主要包括相加為0的矩陣測試)

2
5 5
5 5
(測試5*5和5*5的矩陣)

2
8 9
9 8
(兩個矩陣大小不同，不能進行相加運算，應該有相應的報錯)

2
9 8
9 8
(正常的矩陣測試)

概要設計：

二維矩陣數(shù)據(jù)結構：

數(shù)組：矩陣快速轉置矩陣相加三元組順序表/三元矩陣隨機生成稀疏矩陣壓縮矩陣【C語言，數(shù)據(jù)結構】（內含源代碼）

如圖，把這種數(shù)據(jù)結構可視化就是這樣的，完全是按照人類習慣的一種存儲方式?<(￣ˇ￣)/

typedef struct {
	Elemtype **D;
	int m, n;
	int tu;
} SparseMatrix, M;

老師說：數(shù)據(jù)結構決定算法。所以在這里在二維矩陣數(shù)據(jù)結構中增加行數(shù)m、列數(shù)n，就可以在進入函數(shù)，傳參的時候少傳入n和m兩個值。

tu記錄矩陣中非0元素的個數(shù)，可以更方便地進行三元數(shù)組的轉換。

三元數(shù)組\三元順序表順序表結構：

數(shù)組：矩陣快速轉置矩陣相加三元組順序表/三元矩陣隨機生成稀疏矩陣壓縮矩陣【C語言，數(shù)據(jù)結構】（內含源代碼）

?把上面的二維矩陣轉換一下，對應的三元矩陣就長這樣，只存了非0元的行、列和數(shù)據(jù)￣へ￣

三元數(shù)據(jù)結構的主要作用是將存儲信息密度低的二維矩陣，以一種密度更高的方式儲存在計算機中。

typedef struct {
	int i, j;
	Elemtype e;
} Triple;

typedef struct {
	Triple data[MAXSIZE + 1];
	int mu, nu, tu;
} TSMatrix;

首先三元數(shù)組數(shù)據(jù)結構中，三元數(shù)組的定義，首先要定義“三元”。

三元Triple?由數(shù)據(jù)的行i，列j，數(shù)據(jù)e組成。

三元數(shù)組數(shù)據(jù)結構中同樣存儲著行數(shù)mu，列數(shù)nu，非零元個數(shù)tu。

詳細設計：

三元矩陣相加：

首先，在矩陣相加中有許多操作相同的代碼，為了降低代碼復用性，所以提取代碼中用圖相同的代碼，做成GO函數(shù)當當~?O(∩_∩)O~~

其次，因為大小不同的矩陣不能相加，所以在函數(shù)里，可以不用判斷兩個矩陣的大小，就默認兩個矩陣是一樣大的。別問我為什么還有注釋掉的判斷?╥﹏╥...

最后是最重要的，兩個數(shù)相加，如果兩個答案為0，則不存入，因為他已經(jīng)成為零元惹(。﹏。*)

然后是相加部分的判斷。當兩個元素是相同位置的時候，兩個執(zhí)行相加操作，當A的元素在B的后面的時候，則執(zhí)行前面的B的輸入。相反也同理。注意：這里的位置并不是在三元順序表中的位置，而是在二維數(shù)組中的位置，所以不僅可以通過我這種i和j的判斷，還可以通過A.data[i][j]-A.data[0][0]得到在數(shù)組中的第幾位，這種更高級的判斷，為什么我沒有用捏，因為老師要檢查代碼，為了更高的閱讀性，我選擇用傳統(tǒng)的i和j的方式( *︾▽︾)

Status GO(int *t, int *q, TSMatrix A, TSMatrix *C) {
	C->data[*q].i = A.data[*t].i;
	C->data[*q].j = A.data[*t].j;
	C->data[*q].e = A.data[*t].e;
	(*q)++, (*t)++;
	return OK;
}

Status AddTripleSMatrix(TSMatrix A, TSMatrix B, TSMatrix *C) {
	//add two tripleM
	int ta = 0, tb = 0, q = 0, tool;
	C->mu = A.mu;
	C->nu = A.nu;
//	if(B.mu > C->mu) {
//		C->mu = B.mu;
//	}
//	if(B.nu > C->nu) {
//		C->nu = B.nu;
//	}
	while(ta < A.tu && tb < B.tu) {
		if(A.data[ta].i == B.data[tb].i) {
			if(A.data[ta].j == B.data[tb].j) {
				tool = A.data[ta].e+B.data[tb].e;
				if(C->data[q].e != 0) {
					C->data[q].i = A.data[ta].i;
					C->data[q].j = A.data[ta].j;
					C->data[q].e = A.data[ta].e+B.data[tb].e;
					q++;
				}
				ta++, tb++;
			} else if(A.data[ta].j > B.data[tb].j) {
				GO(&tb, &q, B, C);
			} else if(A.data[ta].j < B.data[tb].j) {
				GO(&ta, &q, A, C);
			}
		} else if(A.data[ta].i > B.data[tb].i) {
			GO(&tb, &q, B, C);
		} else if(A.data[ta].i < B.data[tb].i) {
			GO(&ta, &q, A, C);
		}
	}
	while(ta < A.tu) {
		GO(&ta, &q, A, C);
	}
	while(tb < B.tu) {
		GO(&tb, &q, B, C);
	}
	C->tu = q;
	return OK;
}

三元矩陣快速轉置：

首先轉置有個要求，三元矩陣轉置后i要求從小到大排列，所以并不是簡單的i =?j，j =?i就行了。

快速轉置前，先看普通轉置，知道為什么快速

數(shù)組：矩陣快速轉置矩陣相加三元組順序表/三元矩陣隨機生成稀疏矩陣壓縮矩陣【C語言，數(shù)據(jù)結構】（內含源代碼）

這是普通轉置，可以看到，就是簡單的暴力搜索，用了雙重循環(huán)，時間是N^2，n的平方。為了降低時間復雜度，所以有了快速轉置：( ˇ?ˇ )

這個呢就是書上的算法，直接上書上的原圖吧。

數(shù)組：矩陣快速轉置矩陣相加三元組順序表/三元矩陣隨機生成稀疏矩陣壓縮矩陣【C語言，數(shù)據(jù)結構】（內含源代碼）

?這里講的是什么意思呢，大致說人話就是：

用num數(shù)組存儲轉置后每一行有多少個數(shù)（非零元），用num數(shù)組是為了快速求出cpot數(shù)組

cpot數(shù)組存儲轉置后每一行第一個元素在三元表里的位置。( ‵▽′)ψ

然后再根據(jù)cpot數(shù)組，把每個元素送到三元表里對應的地方。

這樣說不好理解，舉個例子吧┗|*｀0′*|┛ ：

數(shù)組：矩陣快速轉置矩陣相加三元組順序表/三元矩陣隨機生成稀疏矩陣壓縮矩陣【C語言，數(shù)據(jù)結構】（內含源代碼）

?這個矩陣二維和三元長這樣，轉置前。

?現(xiàn)在先處理num數(shù)組，我就遍歷三元組j這一列，num數(shù)組一開始里面全是0，遍歷的時候num[j]++，這樣num[j]存的就是（轉置前第j列）轉置后第i行的非零元數(shù)量。

比如第一個j = 2，那么num[2]++;就代表j = 2行多一個數(shù)。

第二步，確定cpot數(shù)組，?? ???

?cpot[0] = 0;
?? ??? ?for(col = 1; col < Mx.nu; col++) {
?? ??? ??? ?cpot[col] = num[col - 1] + cpot[col - 1];
?? ??? ?}

是的，簡單的運算就行就這么簡單。

第三步，根據(jù)cpot數(shù)組，把對應的元素送到合適的地方，讓轉置后i能從小到大排列。

具體做法是：從上到下，遍歷j ，遍歷到的第一個j?就是j?列的第一個數(shù)【暫停，想一下為什么就是第一個】(⊙3⊙)

以此類推第二個j?就是?j列的第二個。

舉例，第一個j = 2是第一個，那么根據(jù)cpot數(shù)組能確定，j = 2，在轉置后是三元組里的第幾個元。當我掃描到下一個j = 2的時候，就是轉置后j = 2?的第二個元。(⊙ω⊙)

數(shù)組：矩陣快速轉置矩陣相加三元組順序表/三元矩陣隨機生成稀疏矩陣壓縮矩陣【C語言，數(shù)據(jù)結構】（內含源代碼）

以下是實現(xiàn)

Status TransposeSMatrix(TSMatrix Mx, TSMatrix *T) {
	//TransposeSM normally
	int col, num[Mx.nu], cpot[Mx.nu], t, p, q;
	T->mu = Mx.nu;
	T->nu = Mx.mu;
	T->tu = Mx.tu;
	if(T->tu) {
		for(col = 0; col < Mx.nu; col++) {
			num[col] = 0;
		}
		for(t = 0; t < Mx.tu; t++) {
			num[Mx.data[t].j]++;
		}
		cpot[0] = 0;
		for(col = 1; col < Mx.nu; col++) {
			cpot[col] = num[col - 1] + cpot[col - 1];
		}
		for(p = 0; p < Mx.tu; p++) {
			col = Mx.data[p].j;
			q = cpot[col];
			T->data[q].i = Mx.data[p].j;
			T->data[q].j = Mx.data[p].i;
			T->data[q].e = Mx.data[p].e;
			cpot[col]++;
		}
	}
	return OK;
}

調試分析：

1.數(shù)組為了我們計算方便，我們是從0開始存的，但是為了我們看起來更符合數(shù)學邏輯，更美觀，我們要輸出i+1，這樣輸出就是從1開始的。

2.其他就沒什么嗦的了，O__O "…

用戶手冊：

dos操作系統(tǒng)

先選擇模式，輸入1為測試模式，測試用例會包含所有特殊情況，可以看到結果都能正確處理。

輸入2為正常模式，根據(jù)提示，輸入兩個矩陣的長和寬。

1和2模式都會輸出原矩陣A，B和他的三元矩陣。AB相加得到的矩陣C和C的三元矩陣。A轉置得到的矩陣TA和TA的三元矩陣。

若2模式下，兩矩陣A、B大小不同，則無法進行相加操作，輸出數(shù)組不等大的報錯。

測試結果：

輸入：

數(shù)組：矩陣快速轉置矩陣相加三元組順序表/三元矩陣隨機生成稀疏矩陣壓縮矩陣【C語言，數(shù)據(jù)結構】（內含源代碼）

?輸入：

2
8 9
9 8

? 數(shù)組：矩陣快速轉置矩陣相加三元組順序表/三元矩陣隨機生成稀疏矩陣壓縮矩陣【C語言，數(shù)據(jù)結構】（內含源代碼）

?輸入：

2
5 5 
5 5

數(shù)組：矩陣快速轉置矩陣相加三元組順序表/三元矩陣隨機生成稀疏矩陣壓縮矩陣【C語言，數(shù)據(jù)結構】（內含源代碼）

這里B的隨機結果為0個非零元，比較特殊。

輸入：

2
8 9
8 9

? 數(shù)組：矩陣快速轉置矩陣相加三元組順序表/三元矩陣隨機生成稀疏矩陣壓縮矩陣【C語言，數(shù)據(jù)結構】（內含源代碼）

?源代碼：

主程序：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef int Status;
#define OK 1
#define ERROR 0

typedef int Elemtype;

#include "Triple.h"
#include "SparseMatrix.h"

Status RandInitSM(M *);	//scan in m & n ,and Random init a sparseMatrix
Status TranslateToTM(M, TSMatrix *);	//translate M to TM;
Status TranslateToM(TSMatrix, M *);	//translate TM to M;
Status TransposeSMatrix(TSMatrix, TSMatrix *);	//TransposeSM normally
Status AddTripleSMatrix(TSMatrix, TSMatrix, TSMatrix *);	//add two tripleM
Status TestInit(M *, M *);	//test init;

int main() {
	M MB, MA, MC, TMA;
	TSMatrix A, B, C, TA;
	int chiose = 0;
	printf("Start Modle: 1-test 2-Normal running\n");
	scanf("%d", &chiose);
	if(chiose == 1) {
		TestInit(&MA, &MB);
	} else if(chiose == 2) {
		//Create a Sparsematrix;
		printf("How big the matrix will you create?(m & n):\n");
		RandInitSM(&MA);
		printf("How big the next matrix will you create?(m & n):\n");
		RandInitSM(&MB);
	} else {
		printf("\n ERROR!!\n");
		return 0;
	}
	if(MA.m != MB.m || MA.n != MB.n) {
		printf("\n Not the same size!!\n");
		return 0;
	}


	//Make M to TM;
	TranslateToTM(MA, &A);
	//Make M to TM;
	TranslateToTM(MB, &B);

	//transposeSMatrix
	TransposeSMatrix(A, &TA);
	TranslateToM(TA, &TMA);

	//C = A+B;
	AddTripleSMatrix(A, B, &C);
	//Make TM to M;
	TranslateToM(C, &MC);

	printf("MA:");
	PrintSMatrix(MA);
	printf("MB:");
	PrintSMatrix(MB);
	printf("MC:");
	PrintSMatrix(MC);

	printf("A:\n");
	PrintTM(A);
	printf("B:\n");
	PrintTM(B);
	printf("C:\n");
	PrintTM(C);

	printf("\n------------------\n");
	printf("MA:");
	PrintSMatrix(MA);
	printf("TMA:");
	PrintSMatrix(TMA);

	printf("A:\n");
	PrintTM(A);
	printf("TA:\n");
	PrintTM(TA);


	return 0;
}

Status TestInit(M *MA, M *MB) {
	//test init;
	InitSMatrix(3, 4, MA);
	InitSMatrix(3, 4, MB);

//	A
//	 1  0  0  2
//	 0 -1  0  2
//	 0  0  0  3
//	B
//	 0  1  0 -1
//	 1  1  0  0
//	 0  0  0  0
	MA->tu = 5;
	MA->D[0][0] = 1;
	MA->D[0][3] = 2;
	MA->D[1][1] = -1;
	MA->D[1][3] = 2;
	MA->D[2][3] = 3;
	MB->tu = 4;
	MB->D[0][1] = 1;
	MB->D[0][3] = -1;
	MB->D[1][0] = 1;
	MB->D[1][1] = 1;
	return 0;
}

Status RandInitSM(M *M) {
	//scan in m & n ,and Random init a sparseMatrix
	int m, n;
	int randN;
	int i, j, k;
	srand((unsigned)time(NULL));

	scanf("%d %d", &m, &n);
	InitSMatrix(m, n, M);

	M->tu = rand() % (m + n) * 2;
	for(k = 0; k < M->tu; k++) {
		i = rand() % m;
		j = rand() % n;
		randN = rand() % 20;
		M->D[i][j] = randN;
	}

	return OK;
}

Status TranslateToTM(M M, TSMatrix *TM) {
	//translate M to TM;
	int i, j, cot = 0;
	TM->mu = M.m;
	TM->nu = M.n;
	for(i = 0; i < M.m; i++) {
		for(j = 0; j < M.n; j++) {
			if(M.D[i][j] != 0) {
				TM->data[cot].e = M.D[i][j];
				TM->data[cot].i = i;
				TM->data[cot].j = j;
				cot++;
			}
		}
	}
	TM->tu = cot;
	return OK;
}
Status TranslateToM(TSMatrix C, M *MC) {
	//translate TM to M;
	int i;
	MC->m = C.mu;
	MC->n = C.nu;
	MC->tu = C.tu;
	InitSMatrix(C.mu, C.nu, MC);
	for(i = 0; i < C.tu; i++) {
		MC->D[C.data[i].i][C.data[i].j] = C.data[i].e;
	}
	return OK;
}

Status TransposeSMatrix(TSMatrix Mx, TSMatrix *T) {
	//TransposeSM normally
	int col, num[Mx.nu], cpot[Mx.nu], t, p, q;
	T->mu = Mx.nu;
	T->nu = Mx.mu;
	T->tu = Mx.tu;
	if(T->tu) {
		for(col = 0; col < Mx.nu; col++) {
			num[col] = 0;
		}
		for(t = 0; t < Mx.tu; t++) {
			num[Mx.data[t].j]++;
		}
		cpot[0] = 0;
		for(col = 1; col < Mx.nu; col++) {
			cpot[col] = num[col - 1] + cpot[col - 1];
		}
		for(p = 0; p < Mx.tu; p++) {
			col = Mx.data[p].j;
			q = cpot[col];
			T->data[q].i = Mx.data[p].j;
			T->data[q].j = Mx.data[p].i;
			T->data[q].e = Mx.data[p].e;
			cpot[col]++;
		}
	}
	return OK;
}

Status GO(int *t, int *q, TSMatrix A, TSMatrix *C) {
	C->data[*q].i = A.data[*t].i;
	C->data[*q].j = A.data[*t].j;
	C->data[*q].e = A.data[*t].e;
	(*q)++, (*t)++;
	return OK;
}

Status AddTripleSMatrix(TSMatrix A, TSMatrix B, TSMatrix *C) {
	//add two tripleM
	int ta = 0, tb = 0, q = 0, tool;
	C->mu = A.mu;
	C->nu = A.nu;
	if(B.mu > C->mu) {
		C->mu = B.mu;
	}
	if(B.nu > C->nu) {
		C->nu = B.nu;
	}
	while(ta < A.tu && tb < B.tu) {
		if(A.data[ta].i == B.data[tb].i) {
			if(A.data[ta].j == B.data[tb].j) {
				tool = A.data[ta].e+B.data[tb].e;
				if(C->data[q].e != 0) {
					C->data[q].i = A.data[ta].i;
					C->data[q].j = A.data[ta].j;
					C->data[q].e = A.data[ta].e+B.data[tb].e;
					q++;
				}
				ta++, tb++;
			} else if(A.data[ta].j > B.data[tb].j) {
				GO(&tb, &q, B, C);
			} else if(A.data[ta].j < B.data[tb].j) {
				GO(&ta, &q, A, C);
			}
		} else if(A.data[ta].i > B.data[tb].i) {
			GO(&tb, &q, B, C);
		} else if(A.data[ta].i < B.data[tb].i) {
			GO(&ta, &q, A, C);
		}
	}
	while(ta < A.tu) {
		GO(&ta, &q, A, C);
	}
	while(tb < B.tu) {
		GO(&tb, &q, B, C);
	}
	C->tu = q;
	return OK;
}

?頭文件SparseMatrix.h：

#include <stdlib.h>

typedef struct {
	Elemtype **D;
	int m, n;
	int tu;
} SparseMatrix, M;

Status InitSMatrix(int, int, M *);	//Init M;
Status PrintSMatrix(M);

Status InitSMatrix(int m, int n, M *M) {
	//Init M;
	M->m = m;
	M->n = n;
	M->D = (Elemtype **)malloc(m * sizeof(Elemtype *));
	for ( int i = 0; i < m; i++) {
		M->D[i] = (Elemtype *)malloc(n * sizeof(Elemtype));
	}
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			M->D[i][j] = 0;
		}
	}
	if(M->D) {
		return OK;
	}
	return ERROR;
}

Status PrintSMatrix(M M) {
	int i, j;
	for(i = 0; i < M.m; i++) {
		printf("\n");
		for(j = 0; j < M.n; j++) {
			printf("%2d ", M.D[i][j]);
		}
	}
	printf("\n");
	return OK;
}

?頭文件Triple.h：

#define MAXSIZE 12500
typedef struct {
	int i, j;
	Elemtype e;
} Triple;

typedef struct {
	Triple data[MAXSIZE + 1];
	int mu, nu, tu;
} TSMatrix;

Status PrintTM(TSMatrix);

Status PrintTM(TSMatrix TM) {
	int i;
	printf("|  i |  j |  v |\n");
	for(i = 0; i < TM.tu; i++) {
		printf("| %2d | %2d | %2d |\n", TM.data[i].i + 1, TM.data[i].j + 1, TM.data[i].e);
	}
	return OK;
}

總結：

可以看到兩個頭文件里其實沒什么東西，因為上機實驗要展示的東西太多了，也就是說這道題其實不好╮(╯﹏╰)╭，就是要硬考你數(shù)據(jù)結構。

o_O???

加油↖(^ω^)↗?一起努力。文章來源地址http://www.zghlxwxcb.cn/news/detail-425358.html

到了這里，關于數(shù)組：矩陣快速轉置矩陣相加三元組順序表/三元矩陣隨機生成稀疏矩陣壓縮矩陣【C語言，數(shù)據(jù)結構】（內含源代碼）的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！

国产无码综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

Toy模板網(wǎng)

數(shù)組：矩陣快速轉置矩陣相加三元組順序表/三元矩陣隨機生成稀疏矩陣壓縮矩陣【C語言，數(shù)據(jù)結構】（內含源代碼）

題目：

題目分析：

概要設計：

二維矩陣數(shù)據(jù)結構：

三元數(shù)組\三元順序表順序表結構：

詳細設計：

三元矩陣相加：

三元矩陣快速轉置：

調試分析：

用戶手冊：

測試結果：

?源代碼：

主程序：

?頭文件SparseMatrix.h：

?頭文件Triple.h：

總結：

覺得文章有用就打賞一下文章作者

支付寶掃一掃打賞

微信掃一掃打賞

支付寶掃一掃領取紅包，優(yōu)惠每天領

二維碼1

二維碼2

數(shù)組：矩陣快速轉置 矩陣相加 三元組順序表/三元矩陣 隨機生成稀疏矩陣 壓縮矩陣【C語言，數(shù)據(jù)結構】（內含源代碼）

題目：

題目分析：

概要設計：

二維矩陣數(shù)據(jù)結構：

三元數(shù)組\三元順序表順序表結構：

詳細設計：

三元矩陣相加：

三元矩陣快速轉置：

調試分析：

用戶手冊：

測試結果：

?源代碼：

主程序：

?頭文件SparseMatrix.h：

?頭文件Triple.h：

總結：

相關文章

覺得文章有用就打賞一下文章作者

支付寶掃一掃打賞

微信掃一掃打賞

支付寶掃一掃領取紅包，優(yōu)惠每天領

二維碼1

二維碼2

數(shù)組：矩陣快速轉置矩陣相加三元組順序表/三元矩陣隨機生成稀疏矩陣壓縮矩陣【C語言，數(shù)據(jù)結構】（內含源代碼）

支付寶掃一掃領取紅包，優(yōu)惠每天領