当前位置：文档之家› 稀疏矩阵基本操作实验报告

稀疏矩阵基本操作实验报告

一、实验内容

稀疏矩阵的压缩储存结构，以及稀疏矩阵的三元组表表示方法下的转置、相加、相

乘等算法

二、实验目的

1. 熟悉数组、矩阵的定义和基本操作

2. 熟悉稀疏矩阵的储存方式和基本运算

3. 理解稀疏矩阵的三元组表类型定义，掌握稀疏矩阵的输入、输出和转置算法

三、实验原理

1. 使用三元组储存矩阵中的非零元素（三元组分别储存非零元素的行下标，列下标和

元素值）。除了三元组表本身，储存一个稀疏矩阵还需要额外的三个变量，分别储

存矩阵的非零元个数，矩阵的行数和矩阵的列数。

2. 稀疏矩阵的创建算法：

第一步：根据矩阵创建一个二维数组，表示原始矩阵

第二步：取出二维数组中的元素（从第一个元素开始取），判断取出元素是否为非零元素，如果为非零元素，把该非零元素的数值以及行下标和列下表储存到三元数

组表里，否则取出下一个元素，重复该步骤。

第三步：重复第二步，知道二维数组中所有的元素已经取出。

3. 稀疏矩阵倒置算法：

第一步：判断进行倒置的矩阵是否为空矩阵，如果是，则直接返回错误信息。

第二步：计算要倒置的矩阵每列非零元素的数量，存入到num 数组（其中num[i] 代表矩阵中第i 列非零元素的个数）。以及倒置后矩阵每行首非零元的位置，存入cpot 数组中（其中cpot 表示倒置后矩阵每行非零元的位置，对应表示原矩阵每列中第

一个非零元的位置）。

第三步：确定倒置后矩阵的行数和列数。

第四步：取出表示要导致矩阵中三元组表元素{e, I, j} （第一次取出第一个，依次取出下一个元素），从第二步cpot 数组中确定该元素倒置后存放的位置（cpot[j] ），把该元素的行下标和列下标倒置以后放入新表的指定位置中。cpot[j] 变量加一。

第五步：重复第四步，直到三元组表中所有的元素都完成倒置。

第六步：把完成倒置运算的三元组表输出。

4. 稀疏矩阵加法算法：

第一步：检查相加两个矩阵的行数和列数是否相同，如果相同，则进入第二步，否

则输出错误信息。

第二步：定义变量i 和j，用于控制三元组表的遍历。

第三步：比较变量矩阵M 中第i 个元素和矩阵N 中第j 个元素，如果两个元素是同一行元素，如果不是则进入第四步，如果是，再继续比较两个元素是否为同一列元

素，如果是，把两个元素值相加，放到三元组表中；否则把列下表小的元素依次放

到三元组表中。进入第五步

第四步：如果矩阵M 中第i 个元素的行下标大于矩阵N 中第j 个元素的行下标，则把矩阵N 中第j 个元素所在行的所有非零元素添加到三元组表中；如果矩阵M 中第

i 个元素的行下标小于矩阵N 中第j 个元素的下标，则把M 中第i 个元素所在行的

所有非零元素依次添加到三元组表中。

第五步：重复第三步，直到矩阵M 和矩阵N 中所有元素都非零元素添加到三元组表中。

第六步：输出运算结果

5. 稀疏矩阵乘法算法：

第一步：检查矩阵M 和矩阵N 能否参与乘法运算（即矩阵M 的列数等于矩阵N 的行数），如果两个矩阵可以参与乘法运算，进入下一步，否则输出错误信息

第二步：检查两个矩阵相乘以后是否为零矩阵，如果相乘结果是零矩阵，直接返回

一个零矩阵。

第三步：分别计算矩阵M 和矩阵N 中每行非零元的个数（分别存放到num_m 和num_n 数组中），并计算出每行首非零元的位置（分别存放到cpot_m 和cpot_n 中）。

第四步：依次取矩阵M 中的非零元（第一次取出矩阵M 中的第一个非零元），求出该非零元所在行和所在列乘积的和，然后把值放到结果三元组表的特定位置。

第五步：重复第四步，直到矩阵M 中所有非零元都已经参与运算。

第六步：输出结果

四、程序流程图

五、实验结果

5.1 程序主菜单

5.2 稀疏矩阵三元组的创建和倒置

5.3 稀疏矩阵的加法运算并以三元组输出结果

5.4 稀疏矩阵的乘法运算并以矩阵方式输出结果

六、操作说明

1. 在创建稀疏矩阵的时候，可以每次输入一个数据，也可以一次输入多个数据，程序

会自动根据输入元素的个数对矩阵数据进行填充

2. 每次矩阵运算失败时（无论是输入的矩阵不符合矩阵运算的条件，参与运算其中一

个矩阵为空矩阵，或者分配不到临时空间），程序都会返回到主菜单。输入的数据都会被清空。

七、附录：代码

#include

#define MAXSIZE 1000

#define OK 0

#define MALLOC_FAIL -1 // 表示分配空间时发生错误

#define EMPTY_MATRIX -2 // 表示正尝试对一个空矩阵进行运算操作

#define MATRIX_NOT_MATCH -3 // 表示尝试对不符合运算条件的矩阵进行运算操作（例如非相同行数列数矩阵相加）

/* ----------- 结构体声明部分------------- */

typedef struct

{

int row; // 非零元的行下标

int col; // 非零元的列下标

int e; // 非零元的值

} Triple;

typedef struct

{

Triple *data; // 非零元素的元素表

int rownum; // 矩阵的行数

int colnum; // 矩阵的列数

int num; // 矩阵非零元的个数

} TSMatrix, *PTSMatrix;

/* ----------- 函数声明部分-------------- */

// 初始化稀疏矩阵结构

int TSMatrix_Init(TSMatrix *M);

// 以三元组的方式输出稀疏矩阵

void TSMatrix_PrintTriple(TSMatrix *M);

// 以矩阵的方式输出稀疏矩阵

void TSMartix_PrintMatrix(TSMatrix *M);

// 从一个二维数组（普通矩阵）创建一个稀疏矩阵

TSMatrix *TSMatrix_Create(int *a, int row, int col);

// 从键盘录入数据创建一个稀疏矩阵

TSMatrix *TSMatrix_CreateFromInput();

// 求稀疏矩阵M 的转置矩阵T

int TSMatrix_FastTranspose(TSMatrix M, TSMatrix *T);

// 如果稀疏矩阵M 和N 的行数的列数相同，计算Q = M + N int TSMatrix_Add(TSMatrix M, TSMatrix N, TSMatrix *Q);

// 如果稀疏矩阵M 的列数等于N 的行数，计算Q = M x N; int TSMatrix_Multply(TSMatrix M, TSMatrix N, TSMatrix *Q);

// 把光标位置移动到该行行首

void ResetCursor();

/* ----------- 程序主函数--------------- */

int main(void)

{

int info;

char ch;

// 从一个二维数组创建一个系数矩阵

TSMatrix *M;

TSMatrix *N;

// 用来接收运算结果的空间

TSMatrix *T = (TSMatrix *)malloc(sizeof(TSMatrix));

while (1)

{

fflush(stdin);

system("cls");

printf(" 稀疏矩阵基本操作演示\n");

printf("1. 矩阵的创建和转置\n");

printf("2. 矩阵的加法运算并以三元组输出结果\n");

printf("3. 矩阵的乘法运算并以矩阵输出结果\n");

printf("\n");

printf("Q. 退出程序\n");

printf("\n");

printf(" 请输入选项：");

scanf("%c", &ch);

switch (ch)

{

case '1':

system("cls");

M = TSMatrix_CreateFromInput();

if (M != NULL)

{

printf("\n\n 以三元组输出稀疏矩阵：\n");

TSMatrix_PrintTriple(M);

printf("\n 倒置后稀疏矩阵的三元组输出：\n");

TSMatrix_FastTranspose(*M, T);

TSMatrix_PrintTriple(T);

system("pause");

}

else

{

printf(" 创建矩阵过程发生错误");

system("pause");

}

break;

case '2':

system("cls");

M = TSMatrix_CreateFromInput();

N = TSMatrix_CreateFromInput();

if (M == NULL || N == NULL)

{

printf(" 创建矩阵过程中发生错误！\n");

system("pause");

break;

}

info = TSMatrix_Add(*M, *N, T);

if (info == MATRIX_NOT_MATCH)

{

printf(" 这两个矩阵不能运算呢！！⊙﹏⊙\n");

}

else if (info == OK)

{

printf("\n 运算结果：\n");

TSMatrix_PrintTriple(T);

}

system("pause");

break;

case '3':

system("cls");

M = TSMatrix_CreateFromInput();

N = TSMatrix_CreateFromInput();

if (M == NULL || N == NULL)

{

printf(" 创建矩阵过程中发生错误！\n");

system("pause");

break;

}

info = TSMatrix_Multply(*M, *N, T);

if (info == MATRIX_NOT_MATCH)

{

printf(" 这两个矩阵不能运算呢！！⊙﹏⊙\n");

}

else if (info == OK)

{

printf("\n 运算结果：\n");

TSMartix_PrintMatrix(T);

}

system("pause");

break;

case 'q':

case 'Q':

exit(0);

}

return 0;

}

// 初始化稀疏矩阵结构

int TSMatrix_Init(TSMatrix *M)

{

M->data = (Triple *)malloc(MAXSIZE * sizeof(Triple));

if (!M->data)

return MALLOC_FAIL;

M->num = 0;

M->colnum = 0;

M->rownum = 0;

return OK;

}

// 从一个二维数组创建一个稀疏矩阵

TSMatrix *TSMatrix_Create(int *a, int row, int col)

{

int i, j;

TSMatrix *P = (TSMatrix *)malloc(sizeof(TSMatrix));

TSMatrix_Init(P);

// 设置稀疏矩阵的行数和列数

P->rownum = row;

P->colnum = col;

for (i = 0; i < row; i++)

{

for (j = 0; j < col; j++)

{

// 如果第i+1 行第i+1 列元素是非零元素

if (0 != *(a + i * col + j))

{

// 把非零元的元素和位置信息保存到稀疏矩阵中

P->data[P->num].e = *(a + i * col + j);

P->data[P->num].row = i + 1;

P->data[P->num].col = j + 1;

// 把稀疏矩阵中的非零元个数加一

P->num++;

}

return P;

}

// 以三元组的方式输出稀疏矩阵

void TSMatrix_PrintTriple(TSMatrix *M)

{

int i;

if (0 == M->num)

{

printf(" 稀疏矩阵为空！\n");

return;

}

printf(" i j v \n");

printf("===============\n");

for (i = 0; i < M->num; i++)

{

printf("%3d %3d %3d\n", M->data[i].row, M->data[i].col, M->data[i].e);

}

printf("===============\n");

}

// 求稀疏矩阵M 的转置矩阵T

int TSMatrix_FastTranspose(TSMatrix M, TSMatrix *T)

{

int *num, *cpot, i, t;

// 如果矩阵M 为空矩阵，返回错误信息

if (M.num == 0)

return EMPTY_MATRIX;

// 分配临时的工作空间

num = (int *)malloc((M.colnum + 1) * sizeof(int));

cpot = (int *)malloc((M.colnum + 1) * sizeof(int));

// 如果临时的工作空间分配不成功

if (num == NULL || cpot == NULL)

return MALLOC_FAIL;

// 初始化临时工作空间（把num 数组用0 填充）

for (i = 1; i <= M.rownum; i++)

num[i] = 0;

// 统计倒置后每行的元素数量（即统计倒置前矩阵每列元素的数量）

for (i = 1; i <= M.num; i++)

num[M.data[i - 1].col]++;

// 设置T 矩阵每行首个非零元的位置

cpot[1] = 0;

for (i = 2; i <= M.colnum; i++)

cpot[i] = cpot[i - 1] + num[i - 1];

// 把T 矩阵的信息清空

TSMatrix_Init(T);

// 把矩阵M 的信息填充到T 中。

// 矩阵倒置以后，T 的行数等于M 的列数，T 的列数等于M 的行数

T->num = M.num;

T->colnum = M.rownum;

T->rownum = M.colnum;

// 对M 矩阵中每个非零元素进行转置操作

for (i = 0; i < M.num; i++)

{

t = cpot[M.data[i].col];

T->data[t].col = M.data[i].row;

T->data[t].row = M.data[i].col;

T->data[t].e = M.data[i].e;

++cpot[M.data[i].col];

}

// 转置完成后释放临时工作空间

free(num);

free(cpot);

return OK;

}

// 如果稀疏矩阵M 和N 的行数的列数相同，计算Q = M + N int TSMatrix_Add(TSMatrix M, TSMatrix N, TSMatrix *Q)

{

int i = 0, j = 0, k = 0;

if (M.colnum != N.colnum || M.rownum != N.rownum)

return MATRIX_NOT_MATCH;

// 填充结果矩阵信息

TSMatrix_Init(Q);

Q->colnum = M.colnum;

Q->rownum = M.rownum;

Q->num = 0;

while (i < M.num && j < N.num)

{

// 如果i j 指向元素是同一行的元素

if (M.data[i].row == N.data[j].row)

{

// 如果i 和j 指向的元素指向的是同一个元素

if (M.data[i].col == N.data[j].col)

实现稀疏矩阵(采用三元组表示)的基本运算实验报告

操作结果：创建稀疏矩阵M PrintSMatrix(M) 初始条件：稀疏矩阵M已经存在操作结果：打印矩阵M DestroySMatrix(&M) 初始条件：稀疏矩阵M已经存在操作结果：销毁矩阵M CopySMatrix(M, &T) 初始条件：稀疏矩阵M已经存在操作结果：复制矩阵M到T AddSMatrix(M, N, &Q) 初始条件：稀疏矩阵M、N已经存在操作结果：求矩阵的和Q=M+N SubSMatrix(M, N, &Q) 初始条件：稀疏矩阵M、N已经存在操作结果：求矩阵的差Q=M-N TransposeSMatrix(M, & T) 初始条件：稀疏矩阵M已经存在

操作结果：求矩阵M的转置T MultSMatrix(M, N, &Q) 初始条件：稀疏矩阵M已经存在操作结果：求矩阵的积Q=M*N }ADT SparseMatrix 3.2存储结构的定义 #define N 4 typedef int ElemType; #define MaxSize 100 //矩阵中非零元素最多个数typedef struct { int r; //行号 int c; //列号 ElemType d; //元素值 } TupNode; //三元组定义 typedef struct { int rows; //行数值 int cols; //列数值 int nums; //非零元素个数

图的遍历操作实验报告

. .. . .. .. 实验三、图的遍历操作一、目的掌握有向图和无向图的概念；掌握邻接矩阵和邻接链表建立图的存储结构；掌握DFS及BFS对图的遍历操作；了解图结构在人工智能、工程等领域的广泛应用。二、要求采用邻接矩阵和邻接链表作为图的存储结构，完成有向图和无向图的DFS 和BFS操作。三、DFS和BFS 的基本思想深度优先搜索法DFS的基本思想：从图G中某个顶点Vo出发，首先访问Vo，然后选择一个与Vo相邻且没被访问过的顶点Vi访问，再从Vi出发选择一个与Vi相邻且没被访问过的顶点Vj访问，……依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则回退到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点W，从W出发按同样方法向前遍历。直到图中所有的顶点都被访问。广度优先算法BFS的基本思想：从图G中某个顶点Vo出发，首先访问Vo，然后访问与Vo相邻的所有未被访问过的顶点V1，V2，……，Vt；再依次访问与V1，V2，……，Vt相邻的起且未被访问过的的所有顶点。如此继续，直到访问完图中的所有顶点。四、示例程序 1．邻接矩阵作为存储结构的程序示例

#include"stdio.h" #include"stdlib.h" #define MaxVertexNum 100 //定义最大顶点数 typedef struct{ char vexs[MaxVertexNum]; //顶点表 int edges[MaxVertexNum][MaxVertexNum]; //邻接矩阵，可看作边表int n,e; //图中的顶点数n和边数e }MGraph; //用邻接矩阵表示的图的类型 //=========建立邻接矩阵======= void CreatMGraph(MGraph *G) { int i,j,k; char a; printf("Input VertexNum(n) and EdgesNum(e): "); scanf("%d,%d",&G->n,&G->e); //输入顶点数和边数 scanf("%c",&a); printf("Input Vertex string:"); for(i=0;in;i++) { scanf("%c",&a); G->vexs[i]=a; //读入顶点信息，建立顶点表 }

MATLAB基本操作实验报告

南昌航空大学数学与信息科学学院实验报告课程名称：数学实验实验名称： MATLAB基本操作实验类型：验证性■综合性□ 设计性□ 实验室名称：数学实验室班级学号： 10 学生姓名：钟 X 任课教师（教师签名）：成绩：实验日期： 2011-１０- 1０

一、实验目的 1、熟悉MATLAB基本命令与操作 2、熟悉MATLAB作图的基本原理与步骤 3、学会用matlab软件做图二、实验用仪器设备、器材或软件环境计算机MATLAB软件三、实验原理、方案设计、程序框图、预编程序等问题1：在区间【0,2π】画sinx 实验程序: >> x=linspace(0,2*pi,30); >> y=sin(x); >> plot(x,y) 问题2：在【0,2π】用红线画sinx,用绿圈画cosx,实验程序:

>> x=linspace(0,2*pi,30); >> y=sin(x); >> z=cos(x); >> plot(x,y,'r',x,z,'co') >> 问题3：在【0，π】上画y=sinx的图形。实验程序: >> ezplot('sin(x)',[0,pi]) >> 问题4：在【0，π】上画x=cos3t,y=sin3t星形图形。

实验程序: >> ezplot('cos(t).^3','sin(t).^3',[0,pi]) >> 问题5：[-2,0.5]，[0,2]上画隐函数实验程序: >> ezplot('exp(x)+sin(x*y)',[-2,0.5,0,2]) >> 问题6：在[－２，２]范围内绘制tanh的图形。实验程序: >> fplot('tanh',[-2,2])

算法分析_实验报告3

兰州交通大学《算法设计与分析》实验报告3 题目03-动态规划专业计算机科学与技术班级计算机科学与技术2016-02班学号201610333 姓名石博洋

第3章动态规划 1. 实验题目与环境 1.1实验题目及要求 (1) 用代码实现矩阵连乘问题。给定n个矩阵{A1,A2,…,A n}，其中A i与A i+1是可乘的，i=1,2,…,n-1。考察这n 个矩阵的连乘积A1A2…A n。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序，这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，则可以依此次序反复调用2个矩阵相乘的标准算法（有改进的方法，这里不考虑）计算出矩阵连乘积。确定一个计算顺序，使得需要的乘的次数最少。 (2) 用代码实现最长公共子序列问题。一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列X= < x1, x2,…, xm>，则另一序列Z= < z1, z2,…, zk>是X的子序列是指存在一个严格递增的下标序列< i1, i2,…, ik>，使得对于所有j=1,2,…,k有Xij=Zj 。例如，序列Z=是序列X=的子序列，相应的递增下标序列为<2,3,5,7>。给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。例如，若X= < A, B, C, B, D, A, B>和Y= < B, D, C, A, B, A>，则序列是X和Y的一个公共子序列，序列也是X和Y的一个公共子序列。而且，后者是X和Y的一个最长公共子序列，因为X和Y没有长度大于4的公共子序列。 (3) 0-1背包问题。现有n种物品，对1<=i<=n，已知第i种物品的重量为正整数W i，价值为正整数V i，背包能承受的最大载重量为正整数W，现要求找出这n种物品的一个子集，使得子集中物品的总重量不超过W且总价值尽量大。（注意：这里对每种物品或者全取或者一点都不取，不允许只取一部分）使用动态规划使得装入背包的物品价值之和最大。 1.2实验环境： CPU：Intel(R) Core(TM) i3-2120 3.3GHZ 内存：12GB 操作系统：Windows 7.1 X64 编译环境：Mircosoft Visual C++ 6 2. 问题分析 (1) 分析。

算法分析与设计实验报告

算法设计与分析实验报告班级：计科0902班姓名：张华敏学号：0909090814

矩阵连乘问题一，实验内容：二，写一个完整的代码来完整的实现矩阵连乘问题。三，算法设计：在矩阵连乘问题中，根据老师所讲和自己看书对动态规划方法的理解，通过最优子结构性质。再结合书上的算法，便可顺利的写出了代码四，遇到的问题及解决方案：只根据算法写出具体的实现过程刚开始觉得很难，觉得无从下手，不知道该用什么结构形式来存放各个参数，也不知道该怎样具体的实施算法的细节，但是课本上给出了一段实现代码给了我很大的启发，通过借鉴树上的代码实现再结合自己的努力，才终于完成了矩阵连乘全部的代码实现，包括最少连乘次数以及剖分方法。五，源代码 package suanfa; public class Juzhen { public void matrixchain(int p[],int m[][],int s[][]){ i nt n=p.length-1; f or(int i=1;i<=n;i++){ m[i][i]=0; } f or(int r=2;r<=n;r++){ for(int i=1;i<=n-r+1;i++){ int j=i+r-1;

m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j]; s[i][j]=i; for(int k=i+1;k

矩阵转置及相加实验报告

一、实验内容和要求 1、稀疏矩阵A,B均采用三元组表示，验证实现矩阵A快速转置算法，设计并验证A,B相加得到矩阵C的算法。（1）从键盘输入矩阵的行数和列数，随机生成稀疏矩阵。（2）设计算法将随机生成的稀疏矩阵转换成三元组顺序表示形式存储。（3）设计算法将快速转置得到的与相加得到的三元组顺序表分别转换成矩阵形式。（4）输出随机生成的稀疏矩阵A,B及其三元组顺序表、快速转置得到的与相加得到的三元组顺序表及其矩阵形式。二、实验过程及结果一、需求分析 1、将随机生成的数定义为int型（为方便起见设定范围为-20至20（不含0），可修改），三元组存储的元素分别为非零元的行下标、列下标及该位置的元素值，零元不进行存储。实际上在生成稀疏矩阵时是随机选取一些位置生成非零元然后存入三元组中。 2、从键盘输入矩阵的行数和列数后应能输出三元组顺序表及相应矩阵（按行和列排列形式输出）。 3、程序能实现的功能包括： ①随机产生稀疏矩阵；②输出阵列形式的矩阵；③输出三元组顺序表；④将矩阵快速转置；⑤将两个稀疏矩阵相加生成新的矩阵。二、概要设计 1、稀疏矩阵的抽象数据类型定义： ADT TSMatrix{ 数据对象：D={ aij|i=1,2,…,m,j=1,2,…,n; Ai,j∈ElemSet,m和n分别称为矩阵的行数和列数}数据关系：R={Row，Col} Row={|1≤i≤m, 1≤j≤n-1} Col ={|1≤i≤m-1, 1≤j≤n} 基本操作: CreateTSMatrix(&M) 操作结果：创建矩阵M PrintTSMatrix(M) 初始条件：矩阵M已存在操作结果：输出矩阵M中三元组形式的非零元素 PrintTSMatrix1(M) 初始条件：矩阵M已存在操作结果：以阵列形式输出矩阵 UnZore(M, row, col) 初始条件：矩阵M已存在操作结果：若位置(row,col)处存在非零元素，则返回该元素存储在矩阵中的序号

图的遍历实验报告

实验四：图的遍历题目：图及其应用——图的遍历班级：姓名：学号：完成日期：一.需求分析 1.问题描述：很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序，演示在连通的无向图上访问全部结点的操作。 2.基本要求：以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集。 3.测试数据：教科书图7.33。暂时忽略里程，起点为北京。 4.实现提示：设图的结点不超过30个，每个结点用一个编号表示（如果一个图有n个结点，则它们的编号分别为1,2,…,n）。通过输入图的全部边输入一个图，每个边为一个数对，可以对边的输入顺序作出某种限制，注意，生成树的边是有向边，端点顺序不能颠倒。 5.选作内容：（1）.借助于栈类型（自己定义和实现），用非递归算法实现深度优先遍历。（2）.以邻接表为存储结构，建立深度优先生成树和广度优先生成树，再按凹入表或树形打印生成树。二.概要设计 1.为实现上述功能，需要有一个图的抽象数据类型。该抽象数据类型的定义为： ADT Graph { 数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系R： R={VR} VR={ | v，w v且P(v，w)，表示从v到w得弧，谓词P(v，w)定义了弧的意义或信息} } ADT Graph 2.此抽象数据类型中的一些常量如下： #define TRUE 1 #define FALSE 0 #define OK 1 #define max_n 20 //最大顶点数 typedef char VertexType[20]; typedef enum{DG, DN, AG, AN} GraphKind; enum BOOL{False,True}; 3.树的结构体类型如下所示：

实验报告1windows的基本操作范例

实验名称：Windows的基本操作一、实验目的 1.掌握桌面主题的设置。 2.掌握快捷方式的创建。 3.掌握开始菜单的组织。 4.掌握多任务间的数据传递——剪贴板的使用。 5.掌握文件夹和文件的创建、属性查看和设置。 6.掌握文件夹和文件的复制、移动和删除与恢复。 7.熟悉文件和文件夹的搜索。 8.熟悉文件和文件夹的压缩存储和解压缩。二、实验环境 1.中文Windows 7操作系统。三、实验内容及步骤通过上机完成实验4、实验5所有内容后完成该实验报告 1.按“实验4--范例内容(1)”的要求设置桌面，将修改后的界面复制过来。注：没有桌面背景图“Autumn”的，可选择其它背景图。步骤：在桌面空白区域右击，选择菜单中的“个性化”，在弹出的窗口中点击“桌面背景”，在背景栏内选中“某一张图片”，单击“确定”。修改后的界面如下图所示： 2.将画图程序添加到“开始”菜单的“固定项目列表”上。步骤：右击“开始/所有程序/附件”菜单中的画图程序项，在弹出的快捷菜单中选“附到「开始」菜单”命令。 3.在D盘上建立以“自己的学号+姓名”为名的文件夹（如01108101刘琳）和其子文件夹sub1，然后：

步骤：选定D:\为当前文件夹，选择“文件/新建/文件夹”命令，并将名字改为“学号+姓名”；选定“ D:\学号+姓名”为当前文件夹，选择“文件/新建/文件夹”命令，并将名字改为“sub1” ①在C:\WINDOWS中任选2个TXT文本文件，将它们复制到“学号+姓名”文件夹中；步骤：选定“C:\WINDOWS”为当前文件夹，随机选取2个文件, CTRL+C复制，返回“D:\学号+姓名”的文件夹，CTRL+V粘贴 ②将“学号+姓名”文件夹中的一个文件移到其子文件夹sub1中；步骤：选定“ D:\学号+姓名”为当前文件夹，选中其中任意一个文件将其拖拽文件到subl ③在sub1文件夹中建立名为“”的空文本文档；步骤：选定“ D:\学号+姓名\ sub1”为当前文件夹，在空白处单击右键，选择“新建\文本文档”，把名字改为test，回车完成。 ④删除文件夹sub1，然后再将其恢复。步骤：选定“ D:\学号+姓名”为当前文件夹，右键单击“sub1”文件夹，选择“删除”，然后打开回收站，右键单击“sub1”文件夹，在弹出的快捷菜单中选择“还原”。 4.搜索C:\WINDOWS\system文件夹及其子文件夹下所有文件名第一个字母为s、文件长度小于10KB且扩展名为exe的文件，并将它们复制到sub1文件夹中。步骤：选定“ C:\WINDOWS\system”为当前文件夹，单击“搜索”按钮，在左侧窗格选择“所有文件和文件夹”，在“全部或部分文件名”中输入“s*.exe”，在“大小”中，选择“0~10KB”。 5.用不同的方法，在桌面上创建名为“计算器”、“画图”和“剪贴板”的三个快捷方式，它们应用程序分别为：、和。并将三个快捷方式复制到sub1文件夹中。步骤：①在"开始"菜单的"所有程序"子菜单中找到"计算器"，单击右键，在弹出的快捷菜单中选择“发送到\桌面快捷方式”。 ②在"开始"菜单的"所有程序"子菜单中找到"画图"，将其拖至桌面空白处。 ③在桌面上单击右键，在弹出的快捷菜单中选择“新建\快捷方式”，在“创建快捷方式”

矩阵连乘问题算法分析与设计

矩阵连乘问题《算法分析与设计》

设计性实验报告课程名称：《算法分析与设计》矩阵连乘问题实验题目：长：组员一：成二：成员成员三：数学与计算机科学系别：系专业班级：指导教师：实验日期：一、实验目的和要求

实验目的熟悉动态规划算法设计思想和设计步骤，掌握基本的程序设计方法，培养学生用计算机解决实际问题的能力。实验要求 1、根据实验内容，认真编写源程序代码、上机调试程序，书写实验报告。 2、本实验项目考察学生对教材中核心知识的掌握程度和解决实际问题的能力。 3、实验项目可

以采用集中与分散实验相结合的方式进行，学生利用平时实验课时间和课外时间进行实验，要求在学期末形成完整的项目程序设计报告。二、实验内容提要矩阵连乘问题给定n个矩阵{A,A,…,A}，其中，Ai与Ai+1是可乘的，n21A,A,…,A。由于矩阵乘法满足结n-1。考查这n个矩阵的连乘积i=1,2，…，n12合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归地定义为：（1）单个矩阵是完全加括号的；（2）矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=（BC）。三、实验步骤下面考虑矩阵连乘积的最优计算次序问题的动态规划方法。（1）分析最优解的结构（最优子结构性质）设计求解具体问题的动态规划算法的第一步是刻画该问题的最优解结构特征。对于矩阵乘积的最优计算次序问题也不例外。首先，为方便起见，降- 1 - 矩阵乘积Ai Ai+1…Aj简记为A[i:j]。

数据结构实验报告稀疏矩阵运算

教学单位计算机科学与技术学生学号 5 数据结构课程设计报告书题目稀疏矩阵运算器学生豹专业名称软件工程指导教师志敏

实验目的：深入研究数组的存储表示和实现技术，熟悉广义表存储结构的特性。需要分析：稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。要求以带“行逻辑信息”的三元组顺序表存储稀疏矩阵，实现两矩阵的相加、相减、相乘等运算。输入以三元组表示，输出以通常的阵列形式列出。软件平台：Windows 2000，Visual C＋＋ 6.0或WINTC 概要设计：ADT Array { 数据对象: D = {aij | 0≤i≤b1-1, 0 ≤j≤b2-1} 数据关系: R = { ROW, COL } ROW = {| 0≤i≤b1-2, 0≤j≤b2-1} COL = {| 0≤i≤b1-1, 0≤ j≤b2-2} 基本操作： CreateSMatrix(&M); //操作结果:创建稀疏矩阵M. Print SMatrix(M); //初始化条件: 稀疏矩阵M存在. //操作结果:输出稀疏矩阵M. AddSMatrix(M,N,&Q); //初始化条件: 稀疏矩阵M与N的行数和列数对应相等. //操作结果:求稀疏矩阵的和Q=M+N. SubSMatrix(M,N,&Q); //初始化条件: 稀疏矩阵M与N的行数和列数对应相等. //操作结果:求稀疏矩阵的差Q=M-N. MultSMatrix(M,N,&Q); //初始化条件: 稀疏矩阵M的列数等于N的行数. //操作结果:求稀疏矩阵的乘积Q=M*N. } ADT Array

数据结构实验图的基本操作

浙江大学城市学院实验报告课程名称数据结构实验项目名称实验十三/十四图的基本操作学生姓名专业班级学号实验成绩指导老师（签名）日期2014/06/09 一.实验目的和要求 1、掌握图的主要存储结构。 2、学会对几种常见的图的存储结构进行基本操作。二.实验内容 1、图的邻接矩阵定义及实现：建立头文件test13_AdjM.h，在该文件中定义图的邻接矩阵存储结构，并编写图的初始化、建立图、输出图、输出图的每个顶点的度等基本操作实现函数。同时建立一个验证操作实现的主函数文件test13.cpp（以下图为例），编译并调试程序，直到正确运行。 2、图的邻接表的定义及实现：建立头文件test13_AdjL.h，在该文件中定义图的邻接表存储结构，并编写图的初始化、建立图、输出图、输出图的每个顶点的度等基本操作实现函数。同时在主函数文件test13.cpp中调用这些函数进行验证（以下图为例）。

3、填写实验报告，实验报告文件取名为report13.doc。 4、上传实验报告文件report13.doc到BB。注: 下载p256_GraphMatrix.cpp(邻接矩阵)和 p258_GraphAdjoin.cpp(邻接表)源程序，读懂程序完成空缺部分代码。三. 函数的功能说明及算法思路（包括每个函数的功能说明，及一些重要函数的算法实现思路）四. 实验结果与分析（包括运行结果截图、结果分析等）

五.心得体会

程序比较难写，但是可以通过之前的一些程序来找到一些规律（记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。）【附录----源程序】 256: //p-255 图的存储结构以数组邻接矩阵表示, 构造图的算法。 #include #include #include #include typedef char VertexType; //顶点的名称为字符 const int MaxVertexNum=10; //图的最大顶点数 const int MaxEdgeNum=100; //边数的最大值 typedef int WeightType; //权值的类型 const WeightType MaxValue=32767; //权值的无穷大表示 typedef VertexType Vexlist[MaxVertexNum]; //顶点信息，定点名称 typedef WeightType AdjMatrix[MaxVertexNum][MaxVertexNum]; //邻接矩阵typedef enum{DG,DN,AG,AN} GraphKind; //有向图,有向网,无向图,无向网typedef struct{ Vexlist vexs; // 顶点数据元素 AdjMatrix arcs; // 二维数组作邻接矩阵 int vexnum, arcnum; // 图的当前顶点数和弧数 GraphKind kind; // 图的种类标志 } MGraph; void CreateGraph(MGraph &G, GraphKind kd)// 采用数组邻接矩阵表示法，构造图G {//构造有向网G int i,j,k,q; char v, w; G.kind=kd; //图的种类 printf("输入要构造的图的顶点数和弧数：\n"); scanf("%d,%d",&G.vexnum,&G.arcnum); getchar();//过滤回车 printf("依次输入图的顶点名称ABCD...等等：\n"); for (i=0; i

矩阵连乘实验报告

华北电力大学科技学院实验报告实验名称矩阵连乘问题课程名称计算机算法设计与分析专业班级：软件12K1 学生姓名：吴旭学号：121909020124 成绩：指导老师：刘老师实验日期：2014.11.14

一、实验内容矩阵连乘问题，给定n个矩阵{A1,A2,…,A n}，其中A i与A i+1是可乘的，i=1,2,3…,n-1。考察这n个矩阵的连乘A1,A2,…,A n。二、主要思想由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已经完全加括号，则可依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归的定义为： (1)单个矩阵是完全加括号的； (2)矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=(BC)。运用动态规划法解矩阵连乘积的最优计算次序问题。按以下几个步骤进行 1、分析最优解的结构设计求解具体问题的动态规划算法的第1步是刻画该问题的最优解的结构特征。为方便起见，将矩阵连乘积简记为A[i:j]。考察计算A[1:n]的最优计算次序。设这个计算次序矩阵在A k和A k+1之间将矩阵链断开，1n,则其相应的完全加括号方式为((A1…A k)(A k+1…A n))。依此次序，先计算A[1:k]和A[k+1:n],然后将计

算结果相乘得到A[1:n]。 2、建立递归关系设计动态规划算法的第二步是递归定义最优值。对于矩阵连乘积的最优计算次序问题，设计算A[i:j]，1i n，所需的最少数乘次数为m[i][j]，原问题的最优值为m[1][n]。当i=j时，A[i:j]=A i为单一矩阵，无需计算，因此m[i][i]=0，i=1,2,…n。当i

数据结构稀疏矩阵基本运算实验报告

课程设计课程：数据结构题目：稀疏矩阵4 三元组单链表结构体(行数、列数、头) 矩阵运算重载运算符优班级：姓名：学号：设计时间：2010年1月17日——2010年5月XX日成绩：指导教师：楼建华

一、题目二、概要设计 1.存储结构 typedef struct{ int row,col;//行，列 datatype v;//非0数值 }Node; typedef struct{ Node data[max];//稀疏矩阵 int m,n,t;//m 行，n 列，t 非0数个数 … … 2.基本操作 ⑴istream& operator >>(istream& input,Matrix *A)//输入 ⑵ostream& operator <<(ostream& output,Matrix *A){//输出 ⑶Matrix operator ~(Matrix a,Matrix b)//转置 ⑷Matrix operator +(Matrix a,Matrix b)//加法 ⑸Matrix operator -(Matrix a,Matrix b)//减法 ⑹Matrix operator *(Matrix a,Matrix b)//乘法 ⑺Matrix operator !(Matrix a,Matrix b)//求逆三、详细设计（1）存储要点 position[col]=position[col-1]+num[col-1]; 三元组表(row ，col ，v) 稀疏矩阵（（行数m ，列数n ，非零元素个数t ），三元组，...，三元组） 1 2 3 4 max-1

数据结构实验报告图实验

邻接矩阵的实现 1. 实验目的（1）掌握图的逻辑结构（2）掌握图的邻接矩阵的存储结构（3）验证图的邻接矩阵存储及其遍历操作的实现2. 实验内容（1）建立无向图的邻接矩阵存储（2）进行深度优先遍历（3）进行广度优先遍历3．设计与编码MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template class MGraph { public: MGraph（DataType a[], int n, int e）; ~MGraph（）{ void DFSTraverse(int v); void BFSTraverse(int v); private: DataType vertex[MaxSize]; int arc[MaxSize][MaxSize]; }

int vertexNum, arcNum; }; #endif MGraph.cpp #include using namespace std; #include "MGraph.h" extern int visited[MaxSize]; template MGraph::MGraph(DataType a[], int n, int e) { int i, j, k; vertexNum = n, arcNum = e; for(i = 0; i < vertexNum; i++) vertex[i] = a[i]; for(i = 0;i < vertexNum; i++) for(j = 0; j < vertexNum; j++) arc[i][j] = 0; for(k = 0; k < arcNum; k++) { cout << "Please enter two vertexs number of edge: " cin >> i >> j; arc[i][j] = 1; arc[j][i] = 1; } }

数字图像处理实验报告

目录实验一：数字图像的基本处理操作 (4) ：实验目的 (4) ：实验任务和要求 (4) ：实验步骤和结果 (5) ：结果分析 (8) 实验二：图像的灰度变换和直方图变换 (9) ：实验目的 (9) ：实验任务和要求 (9) ：实验步骤和结果 (9) ：结果分析 (13) 实验三：图像的平滑处理 (14) ：实验目的 (14) ：实验任务和要求 (14) ：实验步骤和结果 (14) ：结果分析 (18) 实验四：图像的锐化处理 (19) ：实验目的 (19) ：实验任务和要求 (19) ：实验步骤和结果 (19) ：结果分析 (21)

实验一：数字图像的基本处理操作：实验目的 1、熟悉并掌握MATLAB、PHOTOSHOP等工具的使用； 2、实现图像的读取、显示、代数运算和简单变换。 3、熟悉及掌握图像的傅里叶变换原理及性质，实现图像的傅里叶变换。：实验任务和要求 1.读入一幅RGB图像，变换为灰度图像和二值图像，并在同一个窗口内分成三个子窗口来分别显示RGB图像和灰度图像，注上文字标题。 2.对两幅不同图像执行加、减、乘、除操作，在同一个窗口内分成五个子窗口来分别显示，注上文字标题。 3.对一幅图像进行平移，显示原始图像与处理后图像，分别对其进行傅里叶变换，显示变换后结果，分析原图的傅里叶谱与平移后傅里叶频谱的对应关系。 4.对一幅图像进行旋转，显示原始图像与处理后图像，分别对其进行傅里叶变换，显示变换后结果，分析原图的傅里叶谱与旋转后傅里叶频谱的对应关系。：实验步骤和结果 1.对实验任务1的实现代码如下： a=imread('d:\'); i=rgb2gray(a); I=im2bw(a,; subplot(1,3,1);imshow(a);title('原图像'); subplot(1,3,2);imshow(i);title('灰度图像'); subplot(1,3,3);imshow(I);title('二值图像'); subplot(1,3,1);imshow(a);title('原图像'); 结果如图所示：

算法分析实验三报告

《算法设计与分析》实验报告

目录一、实验内容描述和功能分析. 二、算法过程设计. 三、程序调试及结果（附截图）. 四、源代码（附源代码）.

一、实验内容描述和功能分析. 1.矩阵连乘问题内容描述：给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1,2 ,…,n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。功能分析：输入包含多组测试数据。第一行为一个整数C，表示有C 组测试数据，接下来有2*C行数据，每组测试数据占2行，每组测试数据第一行是1个整数n，表示有n个矩阵连乘,接下来一行有n+1 个数,表示是n个矩阵的行及第n个矩阵的列,它们之间用空格隔开。输出应该有C行，即每组测试数据的输出占一行，它是计算出的矩阵最少连乘积次数。例如：输入：1输出：7500 3 10 100 5 50 2.Pebble Merging 内容描述：在一个圆形操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。试设计一个算法，计算出将n堆石子合并成一堆的最小得分和最大得分。编程任务：对于给定n堆石子,编程计算合并成一堆的最小得分和最大得分。功能分析：输入由多组测试数据组成。每组测试数据输入的第1 行是正整数n，1≤n≤100，表示有n堆石子。第二行有n个数，分别表示每堆石子的个数。对应每组输入，输出的第1 行中的数是最小得分；第2 行中的数是最大得分。例如：输入：4 输出：43 4 4 5 9 54

二、算法过程设计. 1.矩阵连乘问题矩阵连乘问题是通过设置数组，利用数组的横竖坐标来进行矩阵对应行与列的计算。 2.Pebble Merging 这个问题也是跟数组相关，通过寻找数组中的最大和最小值来进行计算。三、程序调试及结果（附截图）. 1.矩阵连乘问题 2.Pebble Merging

数字图像处理实验报告

实现稀疏矩阵(采用三元组表示)的基本运算实验分析报告

实现稀疏矩阵(采用三元组表示)的基本运算实验报告

————————————————————————————————作者：————————————————————————————————日期： 2

实现稀疏矩阵（采用三元组表示）的基本运算实验报告一实验题目: 实现稀疏矩阵（采用三元组表示）的基本运算二实验要求: （1）生成如下两个稀疏矩阵的三元组 a 和 b；（上机实验指导 P92 ）（2）输出 a 转置矩阵的三元组；（3）输出a + b 的三元组；（4）输出 a * b 的三元组；三实验内容: 3.1 稀疏矩阵的抽象数据类型: ADT SparseMatrix { 数据对象:D={aij| i = 1,2,3,….,m; j =1,2,3,……,n; ai,j∈ElemSet,m和n分别称为矩阵的行数和列数 } 数据关系 : R={ Row , Col } Row ={ | 1≤ i≤m , 1≤ j≤ n-1} Col ={| 1≤i≤m-1,1≤j≤n} 基本操作: CreateSMatrix(&M) 操作结果：创建稀疏矩阵M PrintSMatrix(M) 初始条件：稀疏矩阵M已经存在操作结果：打印矩阵M DestroySMatrix(&M) 初始条件：稀疏矩阵M已经存在操作结果：销毁矩阵M CopySMatrix(M, &T) 初始条件：稀疏矩阵M已经存在操作结果：复制矩阵M到T AddSMatrix(M, N, &Q) 初始条件：稀疏矩阵M、N已经存在操作结果：求矩阵的和Q=M+N SubSMatrix(M, N, &Q) 3