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

  1. Toy模板網(wǎng)首頁
  2. >Toy博客

【數(shù)據(jù)結(jié)構(gòu)】稀疏矩陣的壓縮存儲（三元組表、十字鏈表）（C語言）

2年前作者：素錦流年つ分類：Toy博客閱讀(26)違法舉報

這篇具有很好參考價值的文章主要介紹了【數(shù)據(jù)結(jié)構(gòu)】稀疏矩陣的壓縮存儲（三元組表、十字鏈表）（C語言）。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。


稀疏矩陣是指矩陣中大多數(shù)元素為零的矩陣。從直觀上講，當非零元素個數(shù)低于總元素的30%時，這樣的矩陣為稀疏矩陣。

1. 三元組表

1.1 三元組表的存儲結(jié)構(gòu)

稀疏矩陣的三元組表表示法是指只存儲非零元素，同時存儲該非零元素在矩陣中所處的行號和列號的位置信息。
【數(shù)據(jù)結(jié)構(gòu)】稀疏矩陣的壓縮存儲（三元組表、十字鏈表）（C語言）為方便處理，將稀疏矩陣中非零元素對應的三元組按“行序為主序”的一維結(jié)構(gòu)體數(shù)組進行存放，將矩陣的每一行（行由小到大）的全部非零元素的三元組按列號遞增存放，得到矩陣的三元組表。
【數(shù)據(jù)結(jié)構(gòu)】稀疏矩陣的壓縮存儲（三元組表、十字鏈表）（C語言）
代碼

# define MAXSIZE 1000				//設非零元素的個數(shù)最多為1000
/*三元組的存儲結(jié)構(gòu)*/
typedef struct {
	int row, col;					//該非零元素的行下標和列下標
	int e;							//該非零元素的值
}Triple;
/*三元組表的存儲結(jié)構(gòu)*/
typedef struct {
	Triple data[MAXSIZE + 1];		//非零元素的三元組表，下標從1開始
	int m, n, len;					//矩陣的行數(shù)、列數(shù)和非零元素的個數(shù)
}TSMatrix;

1.2 基于三元組表的矩陣轉(zhuǎn)置

① 三元組表中的三元組行列互換。
② 三元組表重新按照行下標遞增排序。

1.2.1 列序遞增轉(zhuǎn)置法
采用按照被轉(zhuǎn)置矩陣三元組表A的列序遞增的順序進行轉(zhuǎn)置，并依次送入轉(zhuǎn)置后矩陣的三元組表B中。
【數(shù)據(jù)結(jié)構(gòu)】稀疏矩陣的壓縮存儲（三元組表、十字鏈表）（C語言）

/*轉(zhuǎn)置：列序遞增轉(zhuǎn)置法*/
void TransposeTSMatrix(TSMatrix* A, TSMatrix* B) {
	int i, j, k;
	B->m = A->n;
	B->n = A->m;
	B->len = A->len;
	if (B->len > 0) {
		j = 1;											//記錄轉(zhuǎn)置后的三元組在三元組表B中的下標值
		for (k = 1; k <= A->n; k++) {
			for (i = 1; i < A->len; i++) {				//從頭至尾掃描三元組表A，尋找col值為k的三元組進行轉(zhuǎn)置
				if (A->data[i].col == k) {
					B->data[j].row = A->data[i].col;
					B->data[j].col = A->data[i].row;
					B->data[j].e = A->data[i].e;
					j++;
				}
			}
		}
	}
}

1.2.2 一次快速轉(zhuǎn)置法
只對三元組表A掃描一次，就使A中所有非零元的三元組“一次定位”直接放到三元組B中的正確位置上。

num[col]：用來存放三元組表A第col列中非零元素總個數(shù)
position[col]：用來存放轉(zhuǎn)置前三元組表A中第col列中第一個非零元素在三元組表B中的存儲位置（下標值）
position[1] = 1
position[col] = position[col - 1] + num[col - 1]（col > 1）
【數(shù)據(jù)結(jié)構(gòu)】稀疏矩陣的壓縮存儲（三元組表、十字鏈表）（C語言）

/*一次定位快速轉(zhuǎn)置法*/
void FastTransposeTSMatrix(TSMatrix* A, TSMatrix* B) {
	int col, t, p, q;
	int num[MAXSIZE], position[MAXSIZE];
	B->m = A->n;
	B->n = A->m;
	B->len = A->len;
	if (B->len) {
		for (col = 1; col <= A->n; col++)				//初始化num數(shù)組
			num[col] = 0;
		for (t = 1; t <= A->len; t++)
			num[A->data[t].col]++;						//掃描三元組表A，求num數(shù)組
		position[1] = 1;
		for (col = 2; col < A->n; col++)				//根據(jù)num數(shù)組求position數(shù)組
			position[col] = position[col - 1] + num[col - 1];

		for (p = 1; p <= A->len; p++) {					//掃描三元組表A，實現(xiàn)轉(zhuǎn)置
			col = A->data[p].col;
			q = position[col];
			B->data[q].row = A->data[p].col;
			B->data[q].col = A->data[p].row;
			B->data[q].e = A->data[p].e;
			position[col]++;							//表示該列的下一個非零元素
		}
	}
}

1.3 完整實現(xiàn)代碼

# include<stdio.h>
# define MAXSIZE 1000				//設非零元素的個數(shù)最多為1000

/*三元組*/
/*三元組的存儲結(jié)構(gòu)*/
typedef struct {
	int row, col;					//該非零元素的行下標和列下標
	int e;							//該非零元素的值
}Triple;
/*三元組表的存儲結(jié)構(gòu)*/
typedef struct {
	Triple data[MAXSIZE + 1];		//非零元素的三元組表
	int m, n, len;					//矩陣的行數(shù)、列數(shù)和非零元素的個數(shù)
}TSMatrix;

/*根據(jù)數(shù)組創(chuàng)建三元組表*/
void CreateTSMatrix(TSMatrix* A, int arry[][7], int m, int n) {
	int i, j, k = 1;
	for (i = 0; i < m; i++) {
		for (j = 0; j < n; j++) {
			if (arry[i][j] != 0) {
				A->data[k].row = i + 1;
				A->data[k].col = j + 1;
				A->data[k].e = arry[i][j];
				k++;
			}
		}
	}
	A->len = k - 1;
	A->m = m;
	A->n = n;
}

/*轉(zhuǎn)置：列序遞增轉(zhuǎn)置法*/
void TransposeTSMatrix(TSMatrix* A, TSMatrix* B) {
	int i, j, k;
	B->m = A->n;
	B->n = A->m;
	B->len = A->len;
	if (B->len > 0) {
		j = 1;											//記錄轉(zhuǎn)置后的三元組在三元組表B中的下標值
		for (k = 1; k <= A->n; k++) {
			for (i = 1; i < A->len; i++) {				//從頭至尾掃描三元組表A，尋找col值為k的三元組進行轉(zhuǎn)置
				if (A->data[i].col == k) {
					B->data[j].row = A->data[i].col;
					B->data[j].col = A->data[i].row;
					B->data[j].e = A->data[i].e;
					j++;
				}
			}
		}
	}
}

/*一次定位快速轉(zhuǎn)置法*/
/* num[col]用來存放三元組表A第col列中非零元素總個數(shù)
   position[col]用來存放轉(zhuǎn)置前三元組表A中第col列中第一個非零元素在三元組表B中的存儲位置（下標值）
   position[col]=position[col-1]+num[col-1]（col>1） */
void FastTransposeTSMatrix(TSMatrix* A, TSMatrix* B) {
	int col, t, p, q;
	int num[MAXSIZE], position[MAXSIZE];
	B->m = A->n;
	B->n = A->m;
	B->len = A->len;
	if (B->len) {
		for (col = 1; col <= A->n; col++)				//初始化num數(shù)組
			num[col] = 0;
		for (t = 1; t <= A->len; t++)
			num[A->data[t].col]++;						//掃描三元組表A，求num數(shù)組
		position[1] = 1;
		for (col = 2; col < A->n; col++)				//根據(jù)num數(shù)組求position數(shù)組
			position[col] = position[col - 1] + num[col - 1];

		for (p = 1; p <= A->len; p++) {					//掃描三元組表A，實現(xiàn)轉(zhuǎn)置
			col = A->data[p].col;
			q = position[col];
			B->data[q].row = A->data[p].col;
			B->data[q].col = A->data[p].row;
			B->data[q].e = A->data[p].e;
			position[col]++;							//表示該列的下一個非零元素
		}
	}
}

/*根據(jù)三元組表輸出稀疏矩陣*/
void Display(TSMatrix* A) {
	int i, j, k = 1;
	for (i = 1; i <= A->m; i++) {
		for (j = 1; j <= A->n; j++) {
			if (i == A->data[k].row && j == A->data[k].col) {
				printf("%3d", A->data[k].e);
				k++;
			}
			else
				printf("  0");
		}
		printf("\n");
	}
}

int main() {
	int M[6][7] = { {0,12,9,0,0,0,0},
				{0,0,0,0,0,0,0},
				{-3,0,0,0,0,14,0},
				{0,0,24,0,0,0,0},
				{0,18,0,0,0,0,0},
				{15,0,0,-7,0,0,0} };
	TSMatrix A, B, C;
	CreateTSMatrix(&A, M, 6, 7);
	TransposeTSMatrix(&A, &B);
	printf("列序遞增轉(zhuǎn)置法：\n");
	Display(&B);
	FastTransposeTSMatrix(&A, &C);
	printf("\n一次定位快速轉(zhuǎn)置法：\n");
	Display(&C);
	return 0;
}

1.4 運行結(jié)果

【數(shù)據(jù)結(jié)構(gòu)】稀疏矩陣的壓縮存儲（三元組表、十字鏈表）（C語言）

2. 十字鏈表

2.1 十字鏈表的存儲結(jié)構(gòu)

十字鏈表是稀疏矩陣的鏈式存儲法。矩陣的每一個非零元素用一個結(jié)點表示，該結(jié)點除了（row，col，vaule）以外，還要添加兩個鏈域：right 用于鏈接同一行中的下一個非零元素，down 用于鏈接同一列中的下一個非零元素。
【數(shù)據(jù)結(jié)構(gòu)】稀疏矩陣的壓縮存儲（三元組表、十字鏈表）（C語言）【數(shù)據(jù)結(jié)構(gòu)】稀疏矩陣的壓縮存儲（三元組表、十字鏈表）（C語言）代碼實現(xiàn)

/*十字鏈表的存儲結(jié)構(gòu)*/
typedef struct OLNode {
	int row, col;						//非零元素的行和列下標
	int vaule;
	struct OLNode* right, * down;		//非零元素所在行表、列表的后繼鏈域
}OLNode, *OLink;

typedef struct {
	OLink* row_head, * col_head;		//行、列鏈表的頭指針向量
	int m, n, len;						//稀疏矩陣的行數(shù)、列數(shù)、非零元素個數(shù)
}CrossList;

參考：耿國華《數(shù)據(jù)結(jié)構(gòu)——用C語言描述（第二版）》

更多數(shù)據(jù)結(jié)構(gòu)內(nèi)容關(guān)注我的《數(shù)據(jù)結(jié)構(gòu)》專欄：https://blog.csdn.net/weixin_51450101/category_11514538.html?spm=1001.2014.3001.5482文章來源地址http://www.zghlxwxcb.cn/news/detail-414982.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】稀疏矩陣的壓縮存儲（三元組表、十字鏈表）（C語言）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！

本文來自互聯(lián)網(wǎng)用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權(quán)，不承擔相關(guān)法律責任。如若轉(zhuǎn)載，請注明出處： 如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實不符，請點擊違法舉報進行投訴反饋，一經(jīng)查實，立即刪除！

領(lǐng)支付寶紅包贊助服務器費用

相關(guān)文章

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

支付寶掃一掃打賞

博客贊助

微信掃一掃打賞

請作者喝杯咖啡吧~博客贊助

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

二維碼1

領(lǐng)取紅包

二維碼2

領(lǐng)紅包