数组和稀疏矩阵

实验二 矩阵和数组的操作

叶松庆

一.实验环境

计算机 MATLAB软件。

二.实验目的

1.掌握矩阵和数组的一般操作，包括创建、保存、修改和调用等。

2.学习矩阵和数组的加减运算与乘法。

3.掌握对数组中元素的寻访与赋值，会对数组进行一般的操作。

三．预备知识

1.常用的产生特殊矩阵的函数。

2.通过矩阵的结构变换，获得新矩阵。

3.数组（矩阵）操作

四．实验内容与步骤

1.用三种方法创建一个3×3矩阵，然后利用矩阵编辑器，将其扩充为4×5矩阵，并保

存，试着调用它。

（1）直接输入法。

如在命令区输入A=[3,2,1;4,5,6;7,8,9]。

（2）直接利用MATLAB提供的函数创建一个3×3矩阵。

如在命令区输入rand(3,3)记得到一个3×3矩阵。

实验结果如图1所示。

（a）直接输入 （b）利用rand函数

图1 实验结果

（3）利用MATLAB提供的“Matrix Editor”完成输入。

步骤1 在命令区输入A=1

步骤2 用鼠标单击工具栏的工作区浏览器，MATLAB弹出变量浏览器，选中变

量A，鼠标左键双击A，打开矩阵编辑器。

步骤3 在左下角的两个文本框中输入分别输入希望得到的矩阵行数和列数：3

行3列。

步骤4 要将上面的矩阵改为一个4×5矩阵，只需修改矩阵的行数和列数即可。

步骤5 在命令区输入save data A（data为我们给变量文件起的名称，系统会自动

沿设定好的路径—“.mat”格式存储文件），即可保存上面例子中创建的矩阵A。

步骤6 在命令区输入load data即可把保存在文件中的矩阵读到MATLAB的工作

去的内存中来。

实验结果如图2所示。

（a）输入A

（b）数组编辑器

（c）载入变量A

图2 实验结果

2.建立一个等差数列，然后由它产生一个对角阵。

步骤1 在命令区输入a=linspace(0,1.5,5)产生一个等差数列。

步骤2 在命令区输入B=diag(a)产生一个对角阵。

数值计算功能

向量及其运算

1、向量生成

（1）、直接输入

向量元素用“[ ]”括起来，用空格或逗号生成行向量，用分号生成列向量

a1=[11 14 17 18]

a2=[11,14,17,18]

a2=[11;14;17;18] %列向量

用“’”可以进行向量转置

a1=[11 14 17 18]

a4=a1' %a1行向量，a4列向量

也可以用组合方法：

A=[1 2 3];

B=[7 8 9];

C=[A 4 ones(1,2) B]

（2）、等差元素向量生成

冒号生成法：Vec=Vec0:n:Vecn，其中Vec表示生成的向量，Vec0表示第一个元素，n表示步长，Vecn表示最后一个元素

使用linespace函数：Vec=linespace(Vec0,n,Vecn)，其中Vec表示生成的向量，Vec0表示第一个元素，n表示生成向量元素个数（默认n=100），Vecn表示最后一个元素

vec1=10:5:50

vec2=50:-5:10

vec3=linspace(10,50,6)

2、向量的基本运算

（1）、向量与数的四则运算

向量中每个元素与数的加减乘除运算（除法运算时，向量只能作为被除数，数只能作为除数）

vec1=linspace(10,50,6)

vec1+100

vec2=logspace(0,10,6) %对数等分向量

vec2/100

（2）、向量与向量之间的加减运算

向量中的每个元素与另一个向量中相对应的元素的加减运算

vec1=linspace(10,50,6)

vec2=logspace(0,2,6)

vec3=vec1+vec2

（3）、点积、叉积和混合机

点积：dot函数，注意向量维数的一致性

x1=[11 22 33 44]

x2=[1 2 3 4] a=dot(x1,x2)

sum(x1.*x2) %还可以采用sum函数计算向量的点积

叉积：cross函数，注意向量维数的一致性（由几何意义可知，向量维数只能为3）

稀疏矩阵——三元组顺序表⽬录

稀疏矩阵

假设m*n的矩阵中，有t的⾮零元，令s=t/m * n,当，s<=0.05时，称此矩阵为稀疏矩阵，简单理解就是⾮零元特别少的矩阵

//⼀般矩阵a

1 2 3

a= 4 5 6

7 8 9

//稀疏矩阵s

0 0 0 0 0

0 2 0 0 5

s= 0 0 3 0 0

0 0 0 0 4

矩阵的转置

⼀个m * n的矩阵转置后变为 n * m的矩阵

//3*2的矩阵-转置前

1 2

4 5

7 8

//转置后变为2*3

1 4 7

2 5 8

转置后的矩阵每个元素的下表与原来的下表刚好相反，例如上⾯4转置前的下标为（2，1），转置后变为（1，2）；

矩阵压缩存储-三元组顺序表

之所以引⼊三元组顺序表，是因为，对于稀疏矩阵⽽⾔，⽤传统的存储⽅法会造成存储空间的浪费

0 12 9 0 0 0 0

0 0 0 0 0 0 0

-3 0 0 0 0 14 0

M= 0 0 24 0 0 0 0

0 18 0 0 0 0 0

15 0 0 -7 0 0 0

//上⾯矩阵⽤三元组表⽰

i j v

1 2 12

1 3 9

3 1 -3

3 6 14

4 3 24

5 2 18

6 1 15

6 4 -7

typedef struct

{

int i,j; //⾏坐标、列坐标

ElemType e; //元素

}Triple;

typedef struct

{

Triple date[MAXSIZE+1]; //0不存储元素

int mu,nu,tu; //⾏数、列数、⾮零元个数

}TSMatrix;

稀疏矩阵的转置传统⽅法的转置算法时遍历矩阵的每⼀项，交换其下标值即可

for(col=1;col<=nu;col++)

{

for(row=1;row<=mu;row++)

{

T[col][row]=M[row][col]

}

}

//时间复杂度 : O(nu*mu)

利⽤三元组顺序表进⾏存储的稀疏矩阵要想实现转置显然不能⽤上⾯的算法，下⾯介绍两种⽅法：

十字链表法存储稀疏矩阵

稀疏矩阵是指其中大部分元素为0的矩阵。在实际应用中，稀疏矩阵的存储和计算都会带来一定的困扰。为了高效地存储和处理稀疏矩阵，我们可以使用十字链表法。

一、稀疏矩阵的特点

稀疏矩阵的特点是其中绝大部分元素为0，而只有少部分非零元素。这导致稀疏矩阵的存储空间浪费很大，因此需要采取一种有效的存储方式。

二、十字链表法的原理

十字链表法是一种组合了链表和线性表的数据结构，用于存储稀疏矩阵。具体实现如下：

1. 定义两个链表headRow和headCol，分别用于存储行和列的头节点；

2. 每个非零元素都对应一个结点，结点包含四个属性：行号row、列号col、值value以及指向下一个非零元素的指针nextRow和nextCol；

3. headRow链表中的每个节点都指向同一行中的第一个非零元素，而headCol链表中的每个节点都指向同一列中的第一个非零元素；

4. 非零元素之间通过nextRow和nextCol指针连接。

通过这种方式，我们可以高效地存储稀疏矩阵，并可以方便地进行矩阵的各种操作。

三、十字链表法的优势

相比于其他存储稀疏矩阵的方法，十字链表法有以下几个优势：

1. 空间利用率高：相比于使用二维数组存储，十字链表法可以大大减少存储空间的浪费，因为只存储非零元素及其位置信息；

2. 支持高效的插入和删除操作：十字链表法可以通过调整指针的指向来进行插入和删除操作，而不需要像其他方法那样移动元素；

3. 方便进行矩阵操作：通过十字链表法，我们可以方便地进行稀疏矩阵的各种操作，如矩阵相加、矩阵相乘等。

四、十字链表法的应用

十字链表法广泛地应用于各个领域，特别是在图论和网络分析中。在这些领域中，往往需要处理大规模的稀疏矩阵，而十字链表法能够有效地解决这个问题。

以社交网络为例，社交网络中的用户和用户之间往往存在着复杂的关系。通过将社交网络建模成稀疏矩阵，可以使用十字链表法来存储和处理这些关系。这样可以方便地进行各种网络分析操作，如查找某个用户的好友、计算两个用户之间的距离等。