数据结构【四】:特殊数组（C++）

发表于 更新于 分类于   |   字数统计: 1.4k(字)   |   阅读时长≈ 7(分)

多维数组

多维数组的地址计算:https://blog.csdn.net/jinaoasher/article/details/78637689

特殊矩阵

对称矩阵的压缩矩阵

Array[i*(i+1)/2+j] = Martix([i])([j])(下三角存储i>=j)

Array[i*(2n-i-1)/2+j] = Martix([i])([j])(上三角存储i>=j)

上三角地址=（2n-i+1）i/2+j-i=i(2n-i-1)/2+j

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<iostream>
using namespace std;
template <class T>
class SymmetryMatrix
{
	public:
		SymmetryMatrix(T **a,int n);		//动态创建一维数组储存下三角数据 
		T Access(int i,int j);				//给定元素位置通过一位数组访问该数据 
		void display();						//输出该对称矩阵 
	protected:
		T *data;
		int size;	
};
template <class T>
SymmetryMatrix<T>::SymmetryMatrix(T **a,int n)
{
	int i,j,t=0;
	size=n;
	data=new T[n*(n+1)/2];
	for(i=0;i<n;i++)
	for(j=0;j<=i;j++)
	{
		data[t++]=a[i][j];
	}
}
template <class T>
T SymmetryMatrix<T>::Access(int i,int j)
{
	i-=1;
	j-=1;
	if(i>=j)
	return data[i*(i+1)/2+j];
	else
	return data[j*(j+1)/2+i];
}
template <class T>
void SymmetryMatrix<T>::display()
{
	int i,j;
	for(i=1;i<=size;i++)
	{
		for(j=1;j<=size;j++)
		{
			cout<< Access(i,j)<<" ";
		}
		cout<<endl;
	}
}
int main()
{
	int n,i,j;
	cout<<"请输入矩阵大小："; 
	cin>>n;
	int **a=new int*[n];
	
	for(i=0;i<n;i++)
	a[i]=new int[n];
	cout<<"请输入矩阵："<<endl; 
	for(i=0;i<n;i++)
	for(j=0;j<n;j++)
	cin>>a[i][j];		
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		cout<<a[i][j];
		cout<<endl;
	}

	SymmetryMatrix<int> test(a,n);
	test.display();	
	test.Access(2,3);
}t

动态分配二维数组:https://blog.csdn.net/KYJL888/article/details/77846122

二维数组作为参数传递：https://blog.csdn.net/kangxidagege/article/details/79475537

稀疏矩阵的压缩矩阵（三元组）和转置

稀疏矩阵的普通转置与快速转置算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include<iostream>
using namespace std;
const int defaultSize=10;
template <class T>
struct Triple
{
	int row,col;				//记录该元素的行列值 
	T data;					//记录该元素的值 
};
template <class T>
class Matrix
{
	public:
		Matrix(int size=defaultSize);
		void input();
		void outputAsMatrix();		//矩阵形式输出	
		void output();
		Matrix<T> transpose(); 
		Matrix<T> quickTranspose();
	protected:
		Triple<T> *Array;				//三元组 
		int maxSize;			//三元组储存的数据的个数 
		int row,col;			//原矩阵行列数 ，避免产生如最后几行全为0，三元组不输入，误判数组少了几行
		int notZero;			//记录非0元素个数	 
};
template <class T>
Matrix<T>::Matrix(int size)				
{
	maxSize=size;
	Array=new Triple<T> [size];
	row=col=0;
}
template <class T>
Matrix<T> Matrix<T>::quickTranspose()
{
	Matrix<T> B(maxSize);					//四步创建除了转置三元组外配置完成的稀疏矩阵类 
	B.col=row;
	B.row=col;
	B.notZero=notZero;
	if(notZero>0)							//只有非0元素大于0才进行下面转置操作 
	{
		int *num1=new int[col];					//第一个数组记录每个列的非0元素个数 
		int *num2=new int[col];					//第二个数组记录每个列的第一个非0元素存放在顺序表中第几个位置 
		 for(int i=0;i<col;i++)
		 {
	 		num1[i]=0;							//初始化0 
		 }
		 for(int i=0;i<notZero;i++)
		 {
		 	num1[Array[i].col]++;				//利用三元组矩阵元素的列值作为数组的下标直接计算非0元素 
		 }	
		 num2[0]=0;								//初始化第一个元素为0
		for(int i=1;i<col;i++)
		{
			num2[i]=num1[i-1]+num2[i-1];		//第i列的第一个非0元素存放位置是上一列的非0元素位置加这一列的非0元素个数； 
		} 
		int t;									//储存非0元素所在列数 
		for(int i=0;i<notZero;i++)
		{
			t=num2[Array[i].col];				//********直接利用三元组数组排序号的列调用储存第i列的非0元素初始位置,画图分析更容易********// 
			B.Array[t].col=Array[i].row;
			B.Array[t].row=Array[i].col;
			B.Array[t].data=Array[i].data;	
			num2[Array[i].col]++;
		} 	
		delete []num1;
		delete []num2;
		return B;	 	  
	}	
}
template <class T>
void Matrix<T>::input()
{
	cout<<"输入原矩阵行、列、非零元素个数";
	cin>>row>>col>>notZero;
	cout<<"按顺序输入全部非零元素的行、列、值"<<endl;
	for(int i=0;i<notZero;i++)
	cin>>Array[i].row>>Array[i].col>>Array[i].data;
}
template <class T>
void Matrix<T>::output()
{
	cout<<"原矩阵为"<<row<<"行"<<col<<"列"<<notZero<<"个非0元素"<<endl ;
	for(int i=0;i<notZero;i++)
	cout<<"Array["<<Array[i].row<<"]"<<"["<<Array[i].col<<"]"<<"="<<Array[i].data<<endl;
}
template <class T>
Matrix<T> Matrix<T>::transpose()
{
	Matrix<T> Trans(maxSize);
	Trans.col=col;
	Trans.row=row;
	Trans.notZero=notZero;

	int t=1,i,j;		
	for(i=1;i<=col;i++)									//列是从小到大排列好的，按列从小到大查询 
	{
		for(j=1;j<=notZero;j++)							// 每一列都在三元组中遍历查询，从小到大移动到新三元组中 这样重复col次 将全部数据移动完毕 
	{
		if(i==Array[j-1].col)
		{
			Trans.Array[t-1].col=Array[j-1].row;
			Trans.Array[t-1].row=Array[j-1].col;
			Trans.Array[t-1].data=Array[j-1].data;
			t++;
		}	
	}
		if(t>notZero)						//转置以经结束，后面可以直接结束了，节省时间 
		break; 	
	}
	return Trans;
}
template <class T>
void Matrix<T>::outputAsMatrix()
{
	cout<<"储存的矩阵为:"<<endl;
	int i,j,t=1;
	for(i=1;i<=row;i++)
	{
		for(j=1;j<=col;j++)
		{
		if(t<=notZero)
		{
			if(Array[t-1].row==i&&Array[t-1].col==j)
			{
				cout<<Array[t-1].data<<" ";
				t++;
			}
			else
			cout<<"0 ";			
		}
		else
		cout<<"0 ";
		}
		cout<<endl;
	}

}
int main()
{
	Matrix<int> test;
	test.input();
	test.output();	
	test.outputAsMatrix();
	test.transpose().outputAsMatrix();
	test.quickTranspose().output();

}
-----------------------本文结束 感谢阅读-----------------------
坚持原创技术分享，您的支持将鼓励我继续创作！恰饭^.^~