写在前面
偷懒，先写了数组，列表要画图，所以今天就先不写了
数组的定义
数组是由n个相同类型的数据元素构成的有限序列。每个数据元素被称为一个数组元素，每个元素在n个线性关系中的序号称为该元素的下标，下标的取值范围称为数组的维界。
数组与线性表的关系：数组是线性表的推广。一维数组可视为一个线性表，二维数组可视为其元素是定长数组的线性表。因此，除结构的初始化和销毁外，数组只会有存取元素和修改元素的操作。
数组的顺序存储
一维数组
以(A[0 dots n-1])为例，其存储结构关系式为：
其中，(L)是每个数组元素所占的存储单元。
多维数组
以二维数组为例。设二维数组的行下标与列下标的范围分别为([0, h_1])和([0,h_2])。
按行优先
先行后列，先存储行号较小的元素，行号相等先存储列号较小的元素。存储结构关系式为：
]
例如对于数组(A_{[2][3]})。它按行优先方式在内存中的存储形式如下所示：
begin{matrix}
a_{[0][0]} & a_{[0][1]} & a_{[0][2]}
a_{[1][0]} & a_{[1][1]} & a_{[1][2]}
end{matrix}
right]
]
| (a_{[0][0]}) | (a_{[0][1]}) | (a_{[0][2]}) | (a_{[1][0]}) | (a_{[1][1]}) | (a_{[1][2]}) |
|---|
列优先
存储结构关系式为：
]
例如对于数组(A_{[2][3]})。它按行优先方式在内存中的存储形式如下所示：
begin{matrix}
a_{[0][0]} & a_{[0][1]} & a_{[0][2]}
a_{[1][0]} & a_{[1][1]} & a_{[1][2]}
end{matrix}
right]
]
| (a_{[0][0]}) | (a_{[1][0]}) | (a_{[0][1]}) | (a_{[1][1]}) | (a_{[0][2]}) | (a_{[1][2]}) |
|---|
特殊矩阵的压缩存储
压缩存储：指为多个值相同的元素只分配一个存储空间，对零元素不分配空间；
特殊矩阵：指具有许多相同矩阵元素或零元素，并且这些相同矩阵元素或零元素的分布具有一定规律性的矩阵；
特殊矩阵的压缩存储：找出特殊矩阵中值相同的矩阵元素的分布规律，把那些呈现规律性分布的、值相同的多个矩阵元素压缩存储到一个存储空间中。
对称矩阵
对一个n阶矩阵(A)中的任意一个元素(a_{i,j})都有(a_{i, j} = a_{j, i}(1 leq i, j leq n))，则称其为对称矩阵
begin{matrix}
a_{1,1} & a_{1,2} & cdots & a_{1,n}
a_{2,1} & a_{2,2} & cdots & a_{2,n}
vdots & vdots & ddots & vdots
a_{n,1} & a_{n,2} & cdots & a_{n,n}
end{matrix}
right]
]
很显然，对于n阶对称矩阵，上三角区所有元素和下三角区的对应元素相同，采用二维数组存放，会造成大范围的空间浪费，因此我们把其存放在一维数组(B[frac{n(n+1)}{2}])中。
比如只存放下三角部分的元素：
在数组(B)中，位于元素(a_{i, j})前的元素个数为：
第1行：1个（(a_{1,1})）
第2行：2个（(a_{2,1},a_{2,2})）
(dots)
第(i-1)行：(i-1)个（(a_{i-1,1},a_{i-1,2} dots ,a_{i-1,i-1})）
第(i)行：(j-1)个（(a_{i,1},a_{i,2}, dots , a_{i,j-1})）
因此，元素(a_{i,j})在数组(B)中的下标(k = 1 + 2 + dots + (i – 1) + j – 1 = frac{i(i – 1)}{2} + j – 1)
因此，元素下标之间对应关系如下：
begin{cases}
frac{i(i-1)}{2} + j – 1&, qquad i geq j
frac{j(j-1)}{2} + i – 1&, qquad i
三角矩阵
下三角矩阵
begin{matrix}
a_{1,1}
a_{2,1} & a_{2,2}
vdots & vdots & ddots
a_{n,1} & a_{n,2} & cdots a_{n,n}
end{matrix}
right]
]
上三角区为统一常量。元素下标之间的对应关系为：
begin{cases}
frac{i(i-1)}{2} + j – 1 &, qquad i geq j
frac{n(n-1)}{2} &, qquad i
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | (cdots) | (frac{n(n+1)}{2}) | ||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 元素 | (a_{1,1}) | (a_{2,1}) | (a_{2,2}) | (a_{3,1}) | (a_{3,2}) | (a_{3,3}) | (cdots) | (a_{n,1}) | (a_{n,2}) | (cdots) | (a_{n,n}) | (c) |
| 行号 | 第一行 | 第二行 | 第二行 | 第三行 | 第三行 | 第三行 | (cdots) | 第n行 | 第n行 | (cdots) | 第n行 | 常数项 |
上三角矩阵
begin{matrix}
a_{1,1} & a_{1,2} & cdots & a_{1,n}
& a_{2,2} & cdots & a_{2,n}
& & ddots & vdots
& & & a_{n,n}
end{matrix}
right]
]
与上文类似地，位于元素(a_{i,j}(i leq j))前面的元素个数为：
第1行：(n)个
第2行：(n-1)个
(dots)
第(i-1)行：(n – i + 2)个
第(i)行：(j-1)个
因此，元素(a_{i,j})在数组(B)中的下标(k = n + (n – 1) + dots + (n – i + 2) + (j – i + 1) – 1)
因此，元素下标之间对应关系如下：
begin{cases}
frac{(i-1)(2n – i + 2)}{2} + j – i &, qquad i leq j
frac{n(n+1)}{2} &, qquad i > j
end{cases}
]
| 下标 | 0 | 1 | (cdots) | (frac{n(n+1)}{2}) | |||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| 元素 | (a_{1,1}) | (a_{1,2}) | (cdots) | (a_{1,n}) | (a_{2,2}) | (a_{2,3}) | (cdots) | (a_{2,n}) | (cdots) | (a_{n,n}) | (c) |
| 行号 | 第一行 | 第一行 | 第一行 | 第一行 | 第二行 | 第二行 | 第二行 | 第二行 | (cdots) | 第n行 | 常数 |
三对角矩阵
对n阶矩阵(A)中的任意元素(a_{i,j})，都有当(|i-j| >1)时，(a_{i,j} = 0)。
begin{matrix}
a_{1,1} & a_{1,2}
a_{2,1} & a_{2,2} & a_{2,3} & & 0
& a_{3,2} & a_{3,3} & a_{3,4}
& & ddots & ddots & ddots
& 0 & & a_{n-1服务器托管网,n-2} & a_{n-1,n-1} & a_{n-1,n}
& & & & a_{n,n-1} & a_{n, n}
end{matrix}
right]
]
稀疏矩阵
矩阵中非零元素的个数t，相对于矩阵元素的个数s来说非常少，即(s >> t)的矩阵称为稀疏矩阵
我们可以用对应的三元组线性表来存储稀疏矩阵，如下例：
left[
begin{matrix}
4 & 0 & 0 & 0
0 & 0 & 6 & 0
0 & 9 & 0 & 0
0 & 23 &0 & 0
end{matrix}
right]
]
对应的三元组为：
begin{matrix}
i & j & a_{i,j}
0 & 0 & 4
1 & 2 & 6
2 & 1 & 9
3 & 1 & 23
end{matrix}
right)
]
下面，上代码，可以实现稀疏矩阵的输入、输出，稀疏矩阵对应三元组的加法、乘法、转置：
#include
#include
#define MAXSIZE 10000
typedef int ElemType;
typedef struct {
int i, j;
ElemType e;
}Triple;
typedef struct {
Triple data[MAXSIZE + 1];
int mu, nu, tu; //矩阵行数，列数和非0元个数
}TSMatrix;
//输入稀疏矩阵数据
void InPutM(TSMatrix& M) {
printf("输入稀疏矩阵的 行数, 列数, 非0元个数 :n");
scanf_s("%d %d %d", &M.nu, &M.mu, &服务器托管网amp;M.tu);
printf("输入矩阵非0元素的 所在行i, 所在列j, 值e:n");
for (int k = 1; k b.data[j + 1].j)
{
c.data[k + 1].i = b.data[j + 1].i;
c.data[k + 1].j = b.data[j + 1].j;
c.data[k + 1].e = b.data[j + 1].e;
k++;
j++; //前往下一个b中的非0元
}
//行相同的第三种情况
else
{
v = a.data[i + 1].e + b.data[j + 1].e;
if (v != 0)
{
c.data[k + 1].i = a.data[i + 1].i;
c.data[k + 1].j = a.data[i + 1].j;
c.data[k + 1].e = v;
k++;
}
i++;
j++;
}
}
//若行不相同 的两种情况
else if (i == a.tu || a.data[i + 1].i > b.data[j + 1].i && j != b.tu)
{
c.data[k + 1].i = b.data[j + 1].i;
c.data[k + 1].j = b.data[j + 1].j;
c.data[k + 1].e = b.data[j + 1].e;
k++;
j++; //前往下一个b的非0元
}
else if (j == b.tu || a.data[i + 1].i 2024-02-06 16:50
PlutoWan
阅读(0)
评论(0)
编辑
收藏
举报
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net
前言 说到代理你首选会想到什么： 不方便自己做的事，要不要找个代理？比如说：美国人的代理人战争 自己搞不定或者不擅长的事，要不要找个代理？比如说：代汽车上牌、房产中介、黄牛等； 没错，这就是代理。当然这篇文章主要是来盘一盘设计模式中的代理模式。 什么是代理模式…
