常熟理工学院
《数据结构与算法》实验指导与报告书
_2017-2018_____学年第__1__ 学期
专业：物联网工程
实验名称：特殊矩阵和稀疏矩阵
实验地点： N6-210 指导教师：聂盼红
计算机科学与工程学院
2017
实验五特殊矩阵和稀疏矩阵
【实验目的】
1、掌握数组的结构类型（静态的内存空间配置）；通过数组的引用下标转换成该数据在内存中的地址；
2、掌握对称矩阵的压缩存储表示；
3、掌握稀疏矩阵的压缩存储-三元组表表示，以及稀疏矩阵的转置算法。
【实验学时】
2学时
【实验预习】
回答以下问题：
1、什么是对称矩阵？写出对称矩阵压缩存储sa[k]与aij之间的对应关系。
若n阶矩阵A中的元素满足下述性质：a ij=a ji，则称为n阶对称矩阵。
sa[k]与矩阵元素a ij之间存在着一一对应的关系：
若i>=j，k=i*(i+1)/2+j;
若i 0<=i, j<=n-1 0<=k<=n*(n+1)/2-1 2、什么是稀疏矩阵？稀疏矩阵的三元组表表示。 假设在m×n的矩阵中，有t个元素不为零，且t＜＜m×n，则称此矩阵为稀疏矩阵。 稀疏矩阵的三元组成表示: 矩阵的行数、列数和非零元个数 【实验内容和要求】 1、编写程序，将对称矩阵进行压缩存储。 （1）对称矩阵数组元素A[i][j]转换成为以行为主的一维数组sa[k]，请描述k与ij 的关系。（注意C程序中，i，j，k均从0开始） （2）调试程序与运行。对称矩阵存储下三角部分即i>=j。 对称矩阵为3,9,1,4,7 9,5,2,5,8 1,2,5,2,4 4,5,2,1,7 7,8,4,7,9 参考程序如下： #include<> #define N 5 int main() { int upper[N][N]= {{3,9,1,4,7}, {9,5,2,5,8}, {1,2,5,2,4}, {4,5,2,1,7}, {7,8,4,7,9} }; /*对称矩阵*/ int rowMajor[15]; /*存储转换数据后以行为主的数组*/ int Index; /*数组的索引值*/ int i,j; printf("Two dimensional upper triangular array:\n"); for (i=0; i { for(j=0; j printf("%3d",upper[i][j]); printf("\n"); } for(i=0; i for(j=0; j if(i>=j) /*下三角元素进行存储*/ { Index=i*(i+1)/2+j; /*ij与index的转换*/ rowMajor[Index]=upper[i][j]; } printf("\nRow Major one dimensional array:\n"); for(i=0; i<15; i++) /*输出转换后的一维数组*/ printf("%3d", rowMajor[i]); printf("\n"); return 1; } 2、完成程序，实现稀疏矩阵的三元组表存储及稀疏矩阵的转置。调试并给出结果： 补充完整程序，运行稀疏矩阵的一般转置算法； 完成稀疏矩阵的快速转置算法，并修改主函数的转置调用算法，验证快速转置算 法的正确性。 部分代码如下： #include<> #define MAXSIZE 20 /*非零元素个数最大值*/ typedef int ElemType; typedef struct { int i,j; ElemType e; }Triple; typedef struct { Triple data[MAXSIZE+1]; /*三元组表，data[0]不用*/ int mu,nu,tu; /*矩阵的行数、列数、非零元个数*/ }TSMatrix; void TransposeSMatrix(TSMatrix *T,TSMatrix *M); /*一般转置算法*/ void FastTransposeSMatrix(TSMatrix *M,TSMatrix *T); /*快速转置算法*/ int main() { int i,j,k,q,col,p; int temp[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 T,M; =6; =7; =0; k=1; for (i=0;i< ;i++) /*转换为稀疏矩阵的三元组表示*/ { for (j=0;j< ;j++) { if (temp[i][j]!=0) { [k].i=i+1; [k].j=j+1; [k].e=temp[i][j]; k++; } } } =k-1; FastTransposeSMatrix(&M,&T); /*调用转置算法进行转置*/ /*输出转置结果*/ printf("稀疏矩阵：\n"); for (i=0;i< ;i++) /*转换为稀疏矩阵的三元组表示*/ { for (j=0;j< ;j++) { printf("%3d",temp[i][j]); } printf("\n"); } printf("转置前M三元组表：\nmu\tnu\ttu\n"); printf("%d\t%d\t%d\n",,,; printf("\ni\tj\te\n"); for (i=1;i<=;i++) printf("%d\t%d\t%d\n",[i].i,[i].j,[i].e); printf("转置后T三元组表：\nmu\tnu\ttu\n"); printf("%d\t%d\t%d\n",,,; printf("\ni\tj\te\n"); for (i=1;i<=;i++) printf("%d\t%d\t%d\n",[i].i,[i].j,[i].e); } /*稀疏矩阵的转置*/ void TransposeSMatrix(TSMatrix *M,TSMatrix *T) { int q,col,p; T->mu=M->nu; T->tu=M->tu; if (T->tu) { q=1; for (col=1;col<=M->nu;++col) for (p=1;p<=M->tu;++p) if (M->data[p].j==col) { T->data[q].i=M->data[p].j; T->data[q].j=M->data[p].i; T->data[q].e=M->data[p].e; ++q; } } } /*稀疏矩阵的快速转置算法*/ void FastTransposeSMatrix(TSMatrix *M,TSMatrix *T) { int t,q,col,p,num[MAXSIZE],cpot[MAXSIZE]; T->mu=M->nu; T->nu=M->mu; if (T->tu) { /*快速转置过程的实现，请补充代码*/ for(col=1;col<=M->mu;++col) num[col]=0; ]; ; q=cpot[col]; T->data[q].i=M->data[p].j; T->data[q].j=M->data[p].i; T->data[q].e=M->data[p].e; ++cpot[col]; } } } 【实验小结】 本实验掌握了对称矩阵的压缩存储表示，稀疏矩阵的压缩存储-三元组表表示，以及稀疏矩阵的转置算法。明白了可以改变矩阵的储存方式来节省内存空间，今后可以利用这一思想来节省内存。 数据结构实验五矩阵的压缩存储与运算 第五章矩阵的压缩存储与运算 【实验目的】 1. 熟练掌握稀疏矩阵的两种存储结构(三元组表和十字链表)的实现； 2. 掌握稀疏矩阵的加法、转置、乘法等基本运算； 3. 加深对线性表的顺序存储和链式结构的理解。 第一节知识准备 矩阵是由两个关系（行关系和列关系）组成的二维数组，因此对每一个关系上都可以用线性表进行处理；考虑到两个关系的先后，在存储上就有按行优先和按列优先两种存储方式，所谓按行优先，是指将矩阵的每一行看成一个元素进行存储；所谓按列优先，是指将矩阵的每一列看成一个元素进行存储；这是矩阵在计算机中用一个连续存储区域存放的一般情形，对特殊矩阵还有特殊的存储方式。 一、特殊矩阵的压缩存储 1. 对称矩阵和上、下三角阵 若n阶矩阵A中的元素满足= （0≤i，j≤n-1 ）则称为n阶对称矩阵。对n阶对称矩阵，我们只需要存储下三角元素就可以了。事实上对上三角矩阵（下三角部分为零）和下三角矩阵（上三角部分为零），都可以用一维数组ma[0.. ]来存储A的下三角元素（对上三角矩阵做转置存储），称ma为矩阵A的压缩存储结构，现在我们来分析以下，A和ma之间的元素对应放置关系。 问题已经转化为：已知二维矩阵A[i，j]，如图5-1， 我们将A用一个一维数组ma[k]来存储，它们之间存在着如图5-2所示的一一对应关系。 任意一组下标(i,j)都可在ma中的位置k中找到元素m[k]= ；这里： k=i(i+1)/2+j (i≥j) 图5-1 下三角矩阵 a00 a10 a11 a20 … an-1,0 … an-1,n-1 k= 0 1 2 3 …n(n- 1)/2 …n(n+1)/2-1 图5-2下三角矩阵的压缩存储 反之，对所有的k=0,1，2,…,n(n+1)/2-1，都能确定ma[k]中的元素在矩阵A中的位置（i,j）。这里，i=d-1，（d是使sum= > k的最小整数），j= 。 2. 三对角矩阵 在三对角矩阵中，所有的非零元素集中在以主对角线为中心的带内状区域中，除了主对角线上和直接在对角线上、下方对角线上的元素之外，所有其它的元素皆为零，见图5-3。 图5-3 三对角矩阵A 与下三角矩阵的存储一样，我们也可以用一个一维数组ma[0..3n-2]来存放三对角矩阵A，其对应关系见图5-4。 a00 a01 a10 a11 a12 … an-1,n-2 an-1,n-1 k= 0 1 2 3 4 … 3n-3 3n-2 图5-4下三角矩阵的压缩存储 A中的一对下标(i,j)与ma中的下标k之间有如下的关系： 公式中采用了C语言的符号，int()表示取整，‘%’表示求余。 课程设计 课程：数据结构 题目：稀疏矩阵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、特殊矩阵计算器 问题描述：创建两个特殊矩阵 A 和 B，计算 A+B、A-B、A*B、B*A、A（或 B）的逆、A（或 B）的转置、A（或 B）的行列式等，具体要求如下：① A、B 均是压缩存储的特殊矩阵，如上/下三角矩阵、对称矩阵、对角矩阵、单位矩阵等。 ② A、B 的矩阵类型、行列数、各位置的元素值等信息均在运行时指定（对于不同类型的矩阵，要求输入的数据也不尽相同）。③各运算若可行，则打印结果；若不可行，则给出提示信息。④各运算需自己实现，禁止调用语言内建或第三方类库的矩阵 API。 涉及算法及知识：特殊矩阵的压缩存储、矩阵相关运算。 #include<> #include<> #define max 100 typedef struct{ int row,col;//定义矩阵行数、列数 int a[max][max]; }Matrix; //存储结构 typedef struct{ int array[max]; int n; //定义矩阵的阶 }M; Matrix A,B,C,D; M p; //*************矩阵的压缩存储*********************// int CompressMatrix(int m,int i,int j,int n){ int k; if(m==1){ if(i<=j) k=(2*n-i+1)*i/2+(j-i)+1; else k=0; return k; } if(m==2){ if(i>=j) k=i*(i+1)/2+j+1; else k=0; return k; } if(m==3){ if(i>=j) k=i*(i+1)/2+j; else k=j*(j+1)/2+i; return k; } if(m==4){ if(i!=j) k=0; else k=i+1; 常熟理工学院 《数据结构与算法》实验指导与报告书 _2017-2018_____学年第__1__ 学期 专业：物联网工程 实验名称：特殊矩阵和稀疏矩阵 实验地点： N6-210 指导教师：聂盼红 计算机科学与工程学院 2017 实验五特殊矩阵和稀疏矩阵 【实验目的】 1、掌握数组的结构类型（静态的内存空间配置）；通过数组的引用下标转换成该数据在内存中的地址； 2、掌握对称矩阵的压缩存储表示； 3、掌握稀疏矩阵的压缩存储-三元组表表示，以及稀疏矩阵的转置算法。 【实验学时】 2学时 【实验预习】 回答以下问题： 1、什么是对称矩阵？写出对称矩阵压缩存储sa[k]与aij之间的对应关系。 若n阶矩阵A中的元素满足下述性质：a ij=a ji，则称为n阶对称矩阵。 sa[k]与矩阵元素a ij之间存在着一一对应的关系： 若i>=j，k=i*(i+1)/2+j; 若i 的关系。（注意C程序中，i，j，k均从0开始） （2）调试程序与运行。对称矩阵存储下三角部分即i>=j。 对称矩阵为3,9,1,4,7 9,5,2,5,8 1,2,5,2,4 4,5,2,1,7 7,8,4,7,9 参考程序如下： #include<> #define N 5 int main() { int upper[N][N]= {{3,9,1,4,7}, {9,5,2,5,8}, {1,2,5,2,4}, {4,5,2,1,7}, {7,8,4,7,9} }; /*对称矩阵*/ int rowMajor[15]; /*存储转换数据后以行为主的数组*/ int Index; /*数组的索引值*/ int i,j; printf("Two dimensional upper triangular array:\n"); for (i=0; i 旋转变换（一）旋转矩阵 1. 简介 计算机图形学中的应用非常广泛的变换是一种称为仿射变换的特殊变换，在仿射变换中的基本变换包括平移、旋转、缩放、剪切这几种。本文以及接下来的几篇文章重点介绍一下关于旋转的变换，包括二维旋转变换、三维旋转变换以及它的一些表达方式（旋转矩阵、四元数、欧拉角等）。 2. 绕原点二维旋转 首先要明确旋转在二维中是绕着某一个点进行旋转，三维中是绕着某一个轴进行旋转。二维旋转中最简单的场景是绕着坐标原点进行的旋转，如下图所示： 如图所示点v 绕原点旋转θ角，得到点v’，假设v点的坐标是(x, y) ，那么可以推导得到v’点的坐标（x’, y’)(设原点到v的距离是r，原点到v点的向量与x轴的夹角是? ) x=rcos?y=rsin? x′=rcos(θ+?)y′=rsin(θ+?) 通过三角函数展开得到 x′=rcosθcos??rsinθsin? y′=rsinθcos?+rcosθsin? 带入x和y表达式得到 x′=xcosθ?ysinθ y′=xsinθ+ycosθ 写成矩阵的形式是： 尽管图示中仅仅表示的是旋转一个锐角θ的情形，但是我们推导中使用的是三角函数的基本定义来计算坐标的，因此当旋转的角度是任意角度（例如大于180度，导致v’点进入到第四象限）结论仍然是成立的。 3. 绕任意点的二维旋转 绕原点的旋转是二维旋转最基本的情况，当我们需要进行绕任意点旋转时，我们可以把这种情况转换到绕原点的旋转，思路如下： 1. 首先将旋转点移动到原点处 2. 执行如2所描述的绕原点的旋转 3. 再将旋转点移回到原来的位置 也就是说在处理绕任意点旋转的情况下需要执行两次平移的操作。假设平移的矩阵是T(x,y)，也就是说我们需要得到的坐标v’=T(x,y)*R*T(-x,-y)（我们使用的是列坐标描述点的坐标，因此是左乘，首先执行T(-x,-y)） 在计算机图形学中，为了统一将平移、旋转、缩放等用矩阵表示，需要引入齐次坐标。（假设使用2x2的矩阵，是没有办法描述平移操作的，只有引入3x3矩阵形式，才能统一描述二维中的平移、旋转、缩放操作。同理必须使用4x4的矩阵才能统一描述三维的变换）。 对于二维平移，如下图所示，P点经过x和y方向的平移到P’点，可以得到： x′=x+tx y′=y+ty 由于引入了齐次坐标，在描述二维坐标的时候，使用（x，y，w）的方式（一般w=1），于是可以写成下面矩阵的形式 按矩阵乘法展开，正好得到上面的表达式。也就是说平移矩阵是 如果平移值是（-tx，-ty）那么很明显平移矩阵式 我们可以把2中描述的旋转矩阵也扩展到3x3的方式，变为： 高考数学1几种特殊的矩阵变换专题1 2020.03 1,圆22 1x y +=在矩阵10102?????? ? ?对应的变换作用下的结果为 ． 2,当兔子和狐狸处于同一栖息地时，忽略其他因素，只考虑兔子数量和狐狸数量的相互影响，为了简便起见，不妨做如下假设： （1）由于自然繁殖，兔子数每年增长10%，狐狸数每年减少15%； （2）由于狐狸吃兔子，兔子数每年减少狐狸数的0.15倍，狐狸数每年增加兔子数的0.1倍； （3）第n 年时，兔子数量n R 用表示，狐狸数量用n F 表示； （4）初始时刻（即第0年），兔子数量有1000=R 只，狐狸数量有300=F 只。 请用所学知识解决如下问题： （1）列出兔子与狐狸的生态模型； （2）求出n R 、n F 关于n 的关系式； （3）讨论当n 越来越大时，兔子与狐狸的数量是否能达到一个稳定的平衡状态，说明你的理由。 3,在一次抗洪抢险中，准备用射击的方法引爆从桥上游漂流而下的一巨大汽油罐.已知只有5发子弹备用，且首次命中只能使汽油流出，再次命 中才能引爆成功，每次射击命中率都是3 2 .，每次命中与否互相独立. (1) 求油罐被引爆的概率. (2) 如果引爆或子弹打光则停止射击，设射击次数为ξ，求ξ的分布列及ξ的数学期望 4,在空间四边形ABCD 中， AC 和BD 为对角线，G 为ABC ?的重心，E 是BD 上一点，3BE ED =，以{ },,AB AC AD u u u r u u u r u u u r 为基底，则GE =u u u r ___ 5,设M 是把坐标平面上的点的横坐标伸长到2倍，纵坐标伸长到3倍的 伸压变换． 求逆矩阵1M -以及椭圆22 149x y +=在1M -的作用下的新曲线的 方程． 6,已知变换A ：平面上的点P （2，－1）、Q （－1，2）分别变换成点P 1（3，－4）、 Q 1（0，5） （1）求变换矩阵A ； （2）判断变换A 是否可逆，如果可逆，求矩阵A 的逆矩阵A －1；如不可逆，说明理由． 7,两个人射击，甲射击一次中靶概率是21，乙射击一次中靶概率是31 ， （Ⅰ）两人各射击一次，中靶至少一次就算完成目标，则完成目标概率是多少？ （Ⅱ）两人各射击2次，中靶至少3次就算完成目标，则完成目标的概率是多少？ （Ⅲ）两人各射击5次，是否有99％的把握断定他们至少中靶一次？ 8,如图，正方体ABCD －A 1B 1C 1D 1中，点E 是棱BC 的中点，点F 是棱CD 上的动点． （Ⅰ）试确定点F 的位置，使得D 1E ⊥平面AB 1F ； （Ⅱ）当D 1E ⊥平面AB 1F 时，求二面角C 1―EF ―A 的余弦值以及BA 1与面C 1EF 所成的角的大小． 稀疏矩阵 一、问题描述 假若在n m ?阶中，有t 个元素不为零，令n m t ?=δ称为矩阵的稀疏因子。通常认为≤δ0.05时称为稀疏矩阵。稀疏矩阵的研究大大的减少了数据在计算机中存储所需的空间，然而，它们的运算却与普通矩阵有所差异。通过本次实验实现稀疏矩阵的转置、加法和乘法等多种运算。 二、基本要求 1、稀疏矩阵采用三元组表示，建立稀疏矩阵，并能按矩阵和三元组方式输出; 2、编写算法，完成稀疏矩阵的转置操作； 3、编写算法，完成对两个具有相同行列数的稀疏矩阵进行求和操作； 4、编写算法，对前一矩阵行数与后一矩阵列数相等的两个矩阵,完成两个稀疏矩阵的相乘操作。 三、测试数据 1、转置操作的测试数据： ??????? ? ?00200013000010020100 2、相加操作的测试数据： ??????? ? ?002000130000100 20100 ??????? ??00200010000210030300 3、相乘操作的测试数据： ?????? ? ??000000030040 0021 ??????? ??001002000021 四、算法思想 1、三元组结构类型为Triple ，用i 表示元素的行，j 表示元素的列，e 表示元素值。稀疏矩阵的结构类型为TSMatrix ，用数组data[]表示三元组，mu 表示行数，nu 表示列数，tu 表示非零元个数。 2、稀疏矩阵转置的算法思想 将需要转置的矩阵a 所有元素存储在三元组表a.data 中，按照矩阵a 的列序来转置。 为了找到a的每一列中所有非零元素，需要对其三元组表a.data扫描一遍，由于a.data 是以a的行需序为主序来存放每个非零元的，由此得到的就是a的转置矩阵的三元组表，将其储存在b.data中。 3、稀疏矩阵相加的算法思想 比较满足条件(行数及列数都相同的两个矩阵)的两个稀疏矩阵中不为0的元素的行数及列数（即i与j），将i与j都相等的前后两个元素值e相加，保持i,j不变储存在新的三元组中，不等的则分别储存在此新三元组中。最后得到的这个新三元组表就是两个矩阵的和矩阵的三元组表。 4、稀疏矩阵相乘的算法思想 两个相乘的矩阵为M与N，对M中每个元素M.data[p](p=1,2,…,M.tu),找到N中所有满足条件M.data[p].j=N.data[q].i的元素N.data[q]，求得M.data[p].v和N.data[q].v 的乘积，又T(i,j)=∑M(i,k)×N(k,j),乘积矩阵T中每个元素的值是个累计和，这个乘积M.data[p].v×N.data[q].v只是T[i][j]中的一部分。为便于操作，应对每个元素设一累计和的变量，其初值是零，然后扫描数组M，求得相应元素的乘积并累加到适当的求累计和的变量上。由于T中元素的行号和M中元素的行号一致，又M中元素排列是以M的行序为主序的，由此可对T进行逐行处理，先求得累计求和的中间结果（T的一行），然后再压缩存储到Q.data中去。 五、模块划分 1、Status CreateM(TSMatrix *M, int a[],int row, int col)，创立三元组； 2、void PrintM(TSMatrix M)，按数组方式输出； 3、void PrintM3(TSMatrix M)，按三元组方式输出； 4、Status TransposeSMatrix(TSMatrix M, TSMatrix *T)，稀疏矩阵的转置； 5、Status MultSMatrix(TSMatrix M, TSMatrix N, TSMatrix *Q)，稀疏矩阵加法； 6、Status MultSMatrix(TSMatrix M, TSMatrix N, TSMatrix *Q)，稀疏矩阵相乘； 7、main(),主函数。 六、数据结构//(ADT) 1、三元组结构类型 typedef struct { int i,j; ElemType e; } Triple; 2、稀疏矩阵 typedef struct { Triple data[MAXSIZE+1]; /* c1.h (程序名) */ #include 教师学科教案[ 20 – 20 学年度第__学期] 任教学科：_____________ 任教年级：_____________ 任教老师：_____________ xx市实验学校 《1.2.3 几类特殊的矩阵变换》教案1 教学目标 1． 理解可以用矩阵来表示平面中常见的几何变换，掌握恒等、伸压、反射、旋转、投影、 切变变换的矩阵表示及其几何意义 2．理解二阶矩阵对应的几何变换是线性变换，了解单位矩阵 3.了解恒等、伸压、反射、旋转、投影、切变变换这六个变换之间的关系 教学重难点 了解并掌握几种特殊的矩阵变换，可以简单的运用。 教学过程 1．理解可以用矩阵来表示平面中常见的几何变换，掌握恒等、伸压、反射、旋转、投影、切变变换的矩阵表示及其几何意义 （１）一般地，对于平面向量变换T ，如果变换规则为T ：?? ? ???y x →??????''y x =??????++dy cx by ax ，那么根据二阶矩阵与平面列向量在乘法规则可以改写为T ：??? ???y x →??????''y x =??? ? ??d c b a ?? ????y x 的矩阵形式，反之亦然（a 、b 、c 、d ∈Ｒ） 由矩阵Ｍ确定的变换，通常记为T M ,根据变换的定义，它是平面内点集到自身的一个映射，平面内的一个图形它在T M ,的作用下得到一个新的图形. 在本节中研究的变换包括恒等变换、伸压变换、反射变换、旋转变换、投影变换、切变变换等六个变换． （２）由矩阵M=?? ? ???1001确定的变换T M 称为恒等变换，这时称矩阵M 为恒等变换矩 阵或单位矩阵，二阶单位矩阵一般记为E.平面是任何一点（向量）或图形，在恒等变换之下都把自己变为自己. （３）由矩阵M=??????100k 或M=?? ? ???k 001)0k (>确定的变换T M 称为（垂直）伸压变 换，这时称矩阵M=???? ??100k 或M=?? ????k 001伸压变换矩阵． 数据结构课后习题及解析第五章 第五章习题 5.1 假设有6行8列的二维数组A，每个元素占用6个字节，存储器按字节编址。已知A的基地址为 1000，计算： 数组A共占用多少字节； 数组A的最后一个元素的地址； 按行存储时元素A 36 的地址； 按列存储时元素A 36 的地址； 5.2 设有三对角矩阵A n×n ,将其三条对角线上的元素逐行地存于数组B(1:3n-2)中，使得B[k]= a ij ， 求： （1）用i,j表示k的下标变换公式； （2）用k表示i,j的下标变换公式。 5.3假设稀疏矩阵A和B均以三元组表作为存储结构。试写出矩阵相加的算法，另设三元组表C存放 结果矩阵。 5.4在稀疏矩阵的快速转置算法5.2中，将计算position[col]的方法稍加改动，使算法只占用一个 辅助向量空间。 5.5写一个在十字链表中删除非零元素a ij 的算法。 5.6画出下面广义表的两种存储结构图示： ((((a), b)), ((( ), d), (e, f))) 5.7求下列广义表运算的结果： （1）HEAD[((a,b),(c,d))]; （2）TAIL[((a,b),(c,d))]; （3）TAIL[HEAD[((a,b),(c,d))]]; （4）HEAD[TAIL[HEAD[((a,b),(c,d))]]]; （5）TAIL[HEAD[TAIL[((a,b),(c,d))]]]; 实习题 若矩阵A m×n 中的某个元素a ij 是第i行中的最小值，同时又是第j列中的最大值，则称此元素为该 矩阵中的一个马鞍点。假设以二维数组存储矩阵，试编写算法求出矩阵中的所有马鞍点。 第五章答案 5.2设有三对角矩阵A n×n,将其三条对角线上的元素逐行的存于数组B[1..3n-2]中，使得B[k]=a ij，求：（1）用i,j表示k的下标变换公式；（2）用k表示i、j的下标变换公式。 【解答】（1）k=2(i-1)+j (2) i=[k/3]+1, j=[k/3]+k%3 （[ ]取整，%取余） 5.4在稀疏矩阵的快速转置算法5.2中，将计算position[col]的方法稍加改动，使算法只占用一个辅助向量空间。 【解答】算法（一） FastTransposeTSMatrix(TSMartrix A, TSMatrix *B) {/*把矩阵A转置到B所指向的矩阵中去，矩阵用三元组表表示*/ int col,t,p,q; int position[MAXSIZE]; B->len=A.len; B->n=A.m; B->m=A.n; if(B->len>0) { position[1]=1; for(t=1;t<=A.len;t++) position[A.data[t].col+1]++; /*position[col]存放第col-1列非零元素的个数, 即利用pos[col]来记录第col-1列中非零元素的个数*/ /*求col列中第一个非零元素在B.data[ ]的位置，存放在position[col]中*/ for(col=2;col<=A.n;col++) position[col]=position[col]+position[col-1]; for(p=1;p 几类特殊线性变换及其二阶矩阵 【教学目标】 1．了解二阶矩阵的概念，线性变换与二阶矩阵之间的关系。 2．熟练运用旋转变换、反射变换、伸缩变换、投影变换、切变变换这五种变换的概念与矩阵表示解决具体问题。 3．亲历几类特殊线性变换的探索过程，体验分析归纳得出其二阶矩阵，进一步发展学生的探究、交流能力。 【教学重难点】 重点：掌握几类特殊线性变换及其二阶矩阵。 难点：旋转变换、反射变换、伸缩变换、投影变换、切变变换的实际应用。 【教学过程】 一、直接引入 师：今天这节课我们主要学习几类特殊线性变换及其二阶矩阵，这节课的主要内容有旋转变换、反射变换、伸缩变换、投影变换、切变变换，并且我们要掌握这些知识的具体应用，能熟练解决相关问题。 二、讲授新课 （1）教师引导学生在预习的基础上了解线性变换与二阶矩阵内容，形成初步感知。 （2）首先，我们先来学习线性变换及其相关概念，它的具体内容是： 在平面直角坐标系xoy 内，很多几何变换都具有下列形式：x ax by y cx dy '=+??'=+? ③； 其中系数a ，b ，c ，d 均为常数，我们把形如③的几何变换叫做线性变换。 ③式叫做这个线性变换的坐标变换公式。 (,)P x y '''是(,)P x y 在这个线性变换作用下的像。 像这样，由4个数a ，b ，c ，d 排成的正方形表a b c d ?? ???称为二阶矩阵。数a ，b ，c ，d 称为矩阵的元素 元素全为0的二阶矩阵0000?? ???称为零矩阵，简记为0。 矩阵1001?? ??? 称为二阶单位矩阵，记为E 它是如何在题目中应用的呢？我们通过一道例题来具体说明。 例：在直角坐标系xoy 内，将每个点绕原点O 按逆时针方向旋转30°的变换称为旋转角是30°的旋转变换。求点(1,0)A 在这个旋转变换作用下的像A '。 解析：教师板书。 （3）接着，我们再来看下旋转变换的概念，它的具体内容是： 在直角坐标系xOy 内的每个点绕原点O 按逆时针方向旋转α角的旋转变换（通常记为n R ）的坐标变换公式：cos sin sin cos x x y y x y αααα'=-??'=+?，对应的二阶矩阵为：cos sin sin cos αααα-?? ??? 。 它是如何在题目中应用的呢？我们也通过一道例题来具体说明。 例：例：在直角坐标系xoy 内，将每个点绕原点O 按逆时针方向旋转30°的变换称为旋转角是30°的旋转变换，写出这个旋转变化的表达式。 解析：教师板书。 （4）接着，我们再来看下反射变换内容，它的具体内容是： 一般地，我们把平面上的任意一点P 变成它关于直线l 的对称点P '的线性变换叫做关于l 的反射。 它是如何在题目中应用的呢？我们也通过一道例题来具体说明。 例：在直角坐标系xoy 内，直线l 过原点，倾斜角为α。求关于直线l 的反射变换的坐标变换公式。 学生板书，教师纠正解答。 （5）接着，我们再来看下伸缩变换内容，它的具体内容是： 在直角坐标系xOy 内，将每个点的横坐标变为原来1k 倍，纵坐标变为原来的2k 倍，其中1k ，2k 均为非零常数，我们称这样的几何变换为伸缩变换。 它是如何在题目中应用的呢？我们也通过一道例题来具体说明。 例：直角坐标系xOy 内，将每一点的纵坐标变为原来的2倍，横坐标保持不变。 （1）试确定该伸缩变换的坐标变换公式及其对应的二阶矩阵。 （2）求点A (1,1)-在该伸缩变换作用下的像A ' 教师请同学上讲台解答，并纠正总结。 typedef int ElemType; // 稀疏矩阵的三元组顺序表存储表示 #define MAXSIZE 100 // 非零元个数的最大值 typedef struct { int i,j; // 行下标,列下标 ElemType e; // 非零元素值 }Triple; typedef struct { Triple data[MAXSIZE+1]; // 非零元三元组表,data[0]未用 int mu,nu,tu; // 矩阵的行数、列数和非零元个数 }TSMatrix; // 创建稀疏矩阵M int CreateSMatrix(TSMatrix *M) { int i,m,n; ElemType e; int k; printf("请输入矩阵的行数,列数,非零元素个数：（逗号）\n"); scanf("%d,%d,%d",&(*M).mu,&(*M).nu,&(*M).tu); (*M).data[0].i=0; // 为以下比较顺序做准备 for(i = 1; i <= (*M).tu; i++) { do { printf("请按行序顺序输入第%d个非零元素所在的行(1～%d)," "列(1～%d),元素值：(逗号)\n", i,(*M).mu,(*M).nu); scanf("%d,%d,%d",&m,&n,&e); k=0; // 行或列超出范围 if(m < 1 || m > (*M).mu || n < 1 || n > (*M).nu) k=1; if(m < (*M).data[i-1].i || m == (*M).data[i-1].i && n <= (*M).data[i-1].j) // 行或列的顺序有错 k=1; }while(k); #include 课程设计 题目矩阵乘法 教学院计算机学院 专业09计算机科学与技术 班级 姓名 指导教师 年月日 目录 1 概述 (3) 2 设计目的 (3) 3 设计功能说明 (3) 4 详细设计说明 (3) 5 流程图 (4) 6 调试及结果 (5) 1程序调试 (5) 2运行编译连接过程......................................................... 5-8 7 总结 (9) 附录...........................................................................10-24 参考文献 (25) 成绩评定表 (26) 1 概述 数据结构是一门理论性强、思维抽象、难度较大的课程，是基础课和专业课之间的桥梁只有进行实际操作，将理论应用于实际中，才能确实掌握书中的知识点。通过课程设计，不仅可以加深学生对数据结构基本概念的了解，巩固学习成果，还能够提高实动手力。为学生后继课程的学习打下良好的基础。 2 设计目的 《数据结构》课程设计是在教学实践基础上进行的一次大型实验，也是对该课程所学理论知识的深化和提高。因此，要求学生能综合应用所学知识，设计与制造出具有较复杂功能的应用系统，并且在实验的基本技能方面上进行一次全面的训练。通过程序的编译掌握对程序的调试方法及思想，并且让学生学会使用一些编程技巧。促使学生养成良好的编程习惯。 1.使学生能够较全面地巩固和应用课堂中所学的的基本理论和程序设计方法，能够较熟练地完成程序的设计和调试。 2.培养学生综合运用所学知识独立完成程序课题的能力。 3.培养学生勇于探索、严谨推理、实事求是、有错必改，用实践来检验理论，全方位考虑问题等科学技术人员应具有的素质。 4．提高学生对工作认真负责、一丝不苟，对同学团结友爱，协作攻关的素质。 5.培养学生从资料文献、科学实验中获得知识的能力，提高学生从别人经验中找到解决问题的新途径的悟性，初步培养工程意识和创新能力。 6.对学生掌握知识的深度、运用理论去处理问题的能力、实验能力、课程设计能力、书面及口头表达能力进行考核。 3 设计功能分析 本设计的功能如下： 1、对于用户给定的矩阵相乘可以进行存储，并且用户可以更改 2、根据用户的要求可以选择相应的功能加减乘及转置 3、然后显示用户输入的矩阵进行运算并得到结果后保存到文件 4 详细设计说明 本程序用数据存储的方式建立矩阵。然后用相加，减，乘，转置的方式计算出 数据结构 课程设计实验报告 内容名称：稀疏矩阵的基本操作成员1：09213020-陈东 成员2：09213040-蔡丹 班级：09数31 教师：李晓翠 江苏师范大学 数学科学学院 目录 1.序言 (3) 1.1数据结构背景 (3) 1.2课程设计目的 (3) 1.3 课程名称 (3) 1.4设计要求 (3) 1.5设计说明 (3) 2．课程任务设计说明书 (5) 3.需求分析 (6) 3.1题目名称 (6) 3.2题目内容 (6) 3.3题目分析 (6) 4．概要设计 (7) 4.1稀疏矩阵存储结构 (7) 4.2.稀疏矩阵的基本操作 (7) 4.3各模块设计要求 (8) 4.4总体功能流程图 (9) 4.4.1存储结构流程图 (9) 4.4.2稀疏矩阵基本操作流程图 (10) 5．详细设计 (11) 5.1设计原理 (11) 5.2基本函数实现流程图 (13) 6．主要函数代码 (21) 7．调试与操作说明 (27) 7.1操作说明 (27) 7.2调试结果………………………………………………………………………………. ..28 7.3结果分析 (31) 8.设计体会 (32) 9.参考文献 (32) 10.分工说明 (33) 1.序言 1.1数据结构背景 数据结构是一门理论性强、思维抽象、难度较大的课程，是基础课和专业课之间的桥梁。该课程的先行课程是计算机基础、程序设计语言、离散数学等，后续课程有操作系统、编译原理、数据库原理、软件工程等。通过本门课程的学习，我们应该能透彻地理解各种数据对象的特点，学会数据的组织方法和实现方法，并进一步培养良好的程序设计能力和解决实际问题的能力，而且该课程的研究方法对我们学生在校和离校后的学习和工作，也有着重要的意义。 数据结构是计算机科学与技术专业的一门核心专业基础课程，在该专业的课程体系中起着承上启下的作用，学好数据结构对于提高理论认知水平和实践能力有着极为重要的作用。学习数据结构的最终目的是为了获得求解问题的能力。对于现实世界中的问题，应该能从中抽象出一个适当的数学模型，该数学模型在计算机内部用相应的数据结构来表示，然后设计一个解此数学模型的算法，再进行编程调试，最后获得问题的解答。 基于此原因，我们开设了数据结构课程设计。针对数据结构课程的特点，着眼于培养我们的实践能力。实习课程是为了加强编程能力的培养，鼓励学生使用新兴的编程语言。相信通过数据结构课程实践，无论是理论知识，还是实践动手能力，同学们都会有不同程度上的提高。 1.2课程设计的目的 巩固和深刻理解―数据结构（C语言版）‖课程所讲解的C语言作为数据结构的算法的描述，掌握对数据的存储结构和算法进行描述时，尽量考虑C 语言的特色。培养学生独立工作和创新思维的能力，取得设计与调试的实践经验。提高和加强计算机应用及软件开发能力。通过课程设计题目的练习，强化学生对所学知识的掌握及对问题分析和任务定义的理解，对每到题目作出了相应的逻辑分析和数据结构的选择，通过对任务的分析，为操作对象定义相应的数据结构，以过程化程序设计的思想方法为原则划分各个模块，定 特殊矩阵运算 1.1程序功能简介 对特殊矩阵能够在界面上以人们熟悉的方式显示，可以对特殊矩阵进行加法运算和减法运算，矩阵转置。 按照要求使用了多种数据结构来求解问题，具体为二维数组和类似图的数据结构。 由于题目要求使用多种数据结构，因此分开写了两段程序，均实现了上述要求的功能，以下将分开说明。先说明的是用二维数组实现的程序，后说明的是用图结构实现的程序。 1.2关于输入、输出形式及数据范围 1.2.1使用二维数组实现的程序 输入、输出范围为：-73786976294838206000到73786976294838206000，足以解决绝大多数的矩阵运算问题。 1.2.2输入的格式 进入程序后首先展现的是功能选择界面，如下图： 此时可通过输入对应功能的数字来选择功能。 在此程序中不同功能输入格式不同： 选择功能 1.矩阵转置时需要输入要进行转置操作的矩阵，首先输入矩阵的行数和列数，以逗号隔开，之后依次按矩阵形式输入矩阵即可，各数值之间以空格隔开。 选择功能2.矩阵数乘时需要输入要进行数乘操作的矩阵，此输入格式同上，之后输入一个实数，即要进行数乘的数即可。 功能3.矩阵加法与4.矩阵减法输入格式和5.矩阵乘法相同，按上述操作输入两个矩阵即可，需要注意的是矩阵减法默认顺序为先输入的矩阵减去后输入的 矩阵。 当按照格式输入时可以实现以上功能，但输入错误数据时，例如进行行列数不同的矩阵相加减时则会返回无法操作，请重新输入的提示。具体情况见下文测试部分。 1.3.1使用图结构实现的稀疏矩阵运算器程序 输入、输出范围同上。 1.3.2输入的格式 进入程序后首先展现的是功能选择界面，如下图： 选择功能部分输入同上。 在进行矩阵输入时采取三元组的形式，这是由于稀疏矩阵的多零元性质。 首先输入矩阵的行数、列数、非零元个数，以空格隔开，输入完毕后确认，开始输入各个非零元。 输入非零元时按“所在行下标所在列下标值”的形式输入，需要注意的是输入时只能从所在行小的开始按顺序输入，不能先输入行数大的数据再输入行数小的数据。 2 概要设计 2.1用二维数组实现的程序的概要设计 由于使用二维数组结构实现上述功能较为简单，故全部运算仅由主函数执行，不单写出各个简单的函数。通过switch（）实现对各个功能的选择。具体如下： Switch(1)：进入矩阵转置功能； Switch(2)：进入矩阵数乘功能； Switch(3)：进入矩阵加法功能； Switch(4)：进入矩阵减法功能； Switch(5)：进入矩阵乘法功能； Switch(6)：结束本程序； 各功能中的矩阵都是以二维数组的形式进行存储与运算的，使用完整的存储 韶关学院 学生实验报告册 实验课程名称：数据结构与算法 实验项目名称：实验五数组及其应用 稀疏矩阵运算器 实验类型（打√）：（基础、综合、设计√） 院系：信息工程学院计算机系专业：***** 姓名：*** 学号：***** 指导老师：陈正铭 韶关学院教务处编制 一、实验预习报告内容 二、实验原始（数据）记录 实验时间：2007 年 5 月30日（星期三第7，8 节）实验同组人： 三、实验报告内容 2007年 5 月30 日 注：1、如有个别实验的实验报告内容多，实验报告册页面不够写，或有识图，画图要求的，学生应根据实验指导老师要求另附相同规格的纸张并粘贴在相应的“实验报告册”中。 2、实验报告册属教学运行材料，院系（中心）应按有关规定归档保管。 【源程序】 #include数据结构实验五矩阵的压缩存储与运算学习资料
数据结构稀疏矩阵基本运算实验报告
数据结构课程设计-特殊矩阵计算器
数据结构与算法 特殊矩阵和稀疏矩阵
旋转变换(一)旋转矩阵
高考数学1几种特殊的矩阵变换专题1
稀疏矩阵(算法与数据结构课程设计)
数据结构矩阵的转置
《1.2.3 几类特殊的矩阵变换》教案新部编本1
数据结构课后习题及解
几类特殊线性变换及其二阶矩阵优秀教学设计
数据结构C语言版-稀疏矩阵的三元组顺序表存储表示和实现
数据结构 稀疏矩阵相乘问题
数据结构矩阵相关操作的课程设计
数据结构C语言版-稀疏矩阵三元组的基本操作
数据结构课程设计 特殊矩阵运算
数据结构实验报告(实验五 稀疏矩阵运算器)
相关主题
文本预览