软件综合课程设计
特殊矩阵的压缩存储算法的实现二叉排序树的实现
二〇一四年六月
一、特殊矩阵的压缩存储算法的实现
1.问题陈述
对于特殊矩阵可以通过压缩存储减少存储空间。
基本要求：
1.针对多种特殊矩阵进行压缩存储，并能显示压缩后的相关地址和值；
2.输入在原来特殊矩阵中的地址，要求能从压缩后的矩阵中读出相应的值；
2.程序代码
#include
#include
#include
static shangsanjiao(int n)
{
int i,j,k,z,g;
int L[100][100],SA[100];
cout<<"请输入您要压缩矩阵的行列数"< cin>>n; cout<<"请输入您的矩阵内元素："< for(i=1;i for(j=1;j { cin>>L[i][j]; if(i<=j) k=j*(j-1)/2+i-1; else k=n*(n+1)/2; SA[k]=L[i][j]; } cout<<"您输入的矩阵为："< for(i=1;i {for(j=1;j cout< cout< } cout<<"压缩存储后："< for(k=0;k cout< cout<<"若要读取矩阵的值请输入'100'退出输入'000'。"< cin>>z; for(g=0;g<1000;g++) { while(z==100) { cout<<"请您输入未压缩时所在行数:"< cout<<"请您输入未压缩时所在列数:"< if(i<=j) k=j*(j-1)/2+i-1; else k=n*(n+1)/2; cout<<"该地址的值为："< cout< z=1; cout<<"继续请输入'100'退出输入'000'。"< } break; } } static duichen(int n) { int i,j,k,z,g; int L[100][100],SA[100]; cout<<"请输入您要压缩矩阵的行列数"< cout<<"请输入您的矩阵内元素："< for(i=1;i for(j=1;j { cin>>L[i][j]; if(i>=j) k=i*(i-1)/2+j-1; else k=j*(j-1)/2+i-1; SA[k]=L[i][j]; } cout<<"您输入的矩阵为："< for(i=1;i { for(j=1;j cout< cout< } cout<<"压缩存储后："< for(k=0;k cout< cout<<"若要读取矩阵的值请输入'100'退出输入'000'。"< for(g=0;g<1000;g++) { while(z==100) { cout<<"请您输入未压缩时所在行数:"< cin>>i; cout<<"请您输入未压缩时所在列数:"< cin>>j; if(i>=j) k=i*(i-1)/2+j-1; else k=j*(j-1)/2+i-1; cout<<"该地址的值为："< cout< z=1; cout<<"继续请输入'100'退出输入'000'。"< cin>>z; } break; } } static xiasanjiao(int n) { int i,j,k,z,g; int L[100][100],SA[100]; cout<<"请输入您要压缩矩阵的行列数"< cin>>n; cout<<"请输入您的矩阵内元素： "< for(i=1;i for(j=1;j { cin>>L[i][j]; if(i>=j) k=i*(i-1)/2+j-1; else k=n*(n+1)/2; SA[k]=L[i][j]; } cout<<"您输入的矩阵为："< for(i=1;i { for(j=1;j cout< cout< } cout<<"压缩存储后："< for(k=0;k cout< cout<<"若要读取矩阵的值请输入'100'退出输入'000'。"< for(g=0;g<1000;g++) { while(z==100) { cout<<"请您输入未压缩时所在行数:"< cin>>i; cout<<"请您输入未压缩时所在列数:"< cin>>j; if(i>=j) k=i*(i-1)/2+j-1; else k=n*(n+1)/2; cout<<"该地址的值为："< cout< z=1; cout<<"继续请输入'100'退出输入'000'。"< cin>>z; } break; } } int main() { int n,d; int m; for(d=0;d<100;d++) { cout<<"请选择您要存储的特殊矩阵类型："< cout<<"1:对称矩阵"< cout<<"2:上三角矩阵"< cout<<"3:下三角矩阵"< cout<<"退出请输入0"< cin>>m; if(m==1) {duichen(n);} else if(m==2) {shangsanjiao(n);} else if(m==3) {xiasanjiao(n);} else if(m==0) break; else cout<<"对不起您输入的选号错误"< } } 3.运行结果 1.1运行主窗口 1.2对称矩阵 1.3上三角矩阵 1.4下三角矩阵 二、二叉排序树的实现 1.问题陈述 用顺序和二叉链表作存储结构 (1)以回车('\n')为输入结束标志,输入数列L，生成一棵二叉排序树T； (2)对二叉排序树T作中序遍历，输出结果； (3)输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序 遍历(执行操作2)；否则输出信息“无x”； 2.需求分析 （1）输入一列数L，以回车('\n')为输入结束标志,并将输入的数列生成一棵二叉树T。 （2）调用函数，把生成的二叉树进行中序遍历，并输出最后的结果。 （3）输入一个数，在已有的二叉树排序树中查找，若没有找到，则输出没有这个数，如果有，则输出存在这个数。 （4）如果有这个数，则调用删除函数，删除这个数生成一棵新的二叉树，并以中序遍历输出新的结果。 3.概要设计 要生成一个二叉树T，元素类型是ElemType， 初始化模块：CreateBST() 创建一棵二叉排序树： int BSTInsert 查找元素x：BSTSearch() 中序遍历二叉排序树：inorder() 4.详细设计 （1）主程序模块 #include typedef int KeyType; typedef char ElemType[10]; typedef struct tnode { KeyType key; ElemType data; struct tnode *lchild,*rchild; }BSTNode;定义全局变量、分配储存空间 （2）二叉树初始化 BSTNode *CreatBST(KeyType A[],int n) //由数组中的关键字建立一棵二叉排序树 { BSTNode *bt=NULL; //初始时bt为空树 int i=0; while(i if(InsertBST(bt,A[i])) //将A[i]插入二叉排序树T中 { printf(" 第%d步，插入%d:",i+1,A[i]); DispBST(bt); printf("\n"); i++; } return bt; //返回建立的二叉排序树的根指针} （3）创建二叉树 int BSTInsert(BSTNode *&bt,KeyType k) { BSTNode *f,*p=bt; while (p!=NULL) { if (p->key==k) return(0); f=p; /*f指向*p结点的双亲结点*/ if (p->key>k) p=p->lchild; /*在左子树中查找*/ else p=p->rchild; /*在右子树中查找*/ } p=new BSTNode; /*建立新结点*/ p->key=k; p->lchild=p->rchild=NULL; if (bt==NULL) /*原树为空时,*p作为根结点插入*/ bt=p; else if (k f->lchild=p; /*插入*p作为*f的左孩子*/ else f->rchild=p; /*插入*p作为*f的右孩子*/ return(1); } void CreateBST(BSTNode *&bt,KeyType str[],int n) { bt=NULL; /*初始时bt为空树*/ int i=0; while (i { BSTInsert(bt,str[i]); /*将关键字str[i]插入二叉排序树bt中*/ i++; } } （4）中序遍历模块 void inorder(BSTNode *t)//递归算法 { if(t!=0) { inorder(t->lchild); cout< inorder(t->rchild); } }} （5）查找元素模块 BSTNode *BSTSearch(BSTNode *bt,KeyType k) { BSTNode *p=bt; while (p!=NULL && p->key!=k) { if (k p=p->lchild; /*沿左子树查找*/ else p=p->rchild; /*沿右子树查找*/ } return(p); } （6）删除元素模块 int BSTDelete(BSTNode *&bt,KeyType k) { BSTNode *p=bt,*f,*r,*f1; f=NULL; /*p指向待比较的结点,f指向*p的双亲结点*/ while (p!=NULL && p->key!=k) /*查找值域为x的结点*/ { f=p; if (p->key>k) p=p->lchild; /*在左子树中查找*/ else p=p->rchild; /*在右子树中查找*/ } if (p==NULL) /*未找到key域为k的结点*/ return(0); else if (p->lchild==NULL) /**p为被删结点,若它无左子树*/ { if (f==NULL) /**p是根结点,则用右孩子替换它*/ bt=p->rchild; else if (f->lchild==p) /**p是双亲结点的左孩子,则用其右子替换它*/ { f->lchild=p->rchild; delete p; } else if(f->rchild==p) /**p是双亲结点的右孩子,则用其右孩子替换它*/ { f->rchild=p->rchild; delete p; } } else if (p->rchild==NULL) /**p为被删结点,若它无右子树*/ { if (f==NULL) /**p是根结点,则用左孩子替换它*/ bt=p->lchild; if (f->lchild==p) /**p是双亲结点的左孩子,则用其左孩子替换它*/ { f->lchild=p->lchild; delete p; } else if(f->rchild==p) /**p是双亲结点的右孩子,则用其左孩子替换它*/ { f->rchild=p->lchild; delete p; } } else /**p为被删结点,若它有左子树和右子树*/ { f1=p;r=p->lchild; /*查找*p的左子树中的最右下结点*r*/ while (r->rchild!=NULL) /**r一定是无右子树的结点,*f1作为r的双亲*/ { f1=r; r=r->rchild; } if (f1->lchild==r) /**r是*f1的左孩子,删除*r*/ f1->lchild=r->rchild; else if (f1->rchild==r) /**r是*f1的右孩子,删除*r*/ f1->rchild=r->lchild; r->lchild=p->lchild; /*以下语句是用*r替代*p*/ r->rchild=p->rchild; if (f==NULL) /**f为根结点*/ bt=r; /*被删结点是根结点*/ else if (f->lchild==p) /**p是*f的左孩子*/ f->lchild=r; else /**p是*f的右孩子*/ f->rchild=r; delete p; } return(1); } （7）主函数模块设计 void main() { int n; BSTNode *bt=NULL,*p; KeyType a[200],k; cout <<"请输入元素个数n:"; cin >>n; cout <<"请输入数据:"; for(int i=0;i { cin >>a[i]; } CreateBST(bt,a,n); cout<<"BST:"; BSTdisp(bt);cout< cout<<"中序遍历二叉排序树:"< inorder(bt); cout<<"\n"; // cout<<"先序遍历二叉排序树:"; // preorder(bt); // cout<<"\n"; cout<<"输入要查找的元素x:"; cin >>k; p=BSTSearch(bt,k); if(p!=NULL) { BSTDelete(bt,k); cout <<"已经删除值为"< cout<<"中序遍历二叉排序树:"; inorder(bt); } else cout<<"无"< } 5.程序代码 #include typedef int KeyType; typedef char ElemType[10]; typedef struct tnode { KeyType key; ElemType data; struct tnode *lchild,*rchild; }BSTNode; void BSTdisp(BSTNode *b); BSTNode *BSTSearch(BSTNode *bt,KeyType k) { BSTNode *p=bt; while (p!=NULL && p->key!=k) { if (k p=p->lchild; /*沿左子树查找*/ else p=p->rchild; /*沿右子树查找*/ } return(p); } int BSTInsert(BSTNode *&bt,KeyType k) { BSTNode *f,*p=bt; while (p!=NULL) { if (p->key==k) return(0); f=p; /*f指向*p结点的双亲结点*/ if (p->key>k) p=p->lchild; /*在左子树中查找*/ else p=p->rchild; /*在右子树中查找*/ } p=new BSTNode; /*建立新结点*/ p->key=k; p->lchild=p->rchild=NULL; if (bt==NULL) /*原树为空时,*p作为根结点插入*/ bt=p; else if (k f->lchild=p; /*插入*p作为*f的左孩子*/ else f->rchild=p; /*插入*p作为*f的右孩子*/ return(1); } /*BSTNode *CreatBST(KeyType A[],int n) //由数组中的关键字建立一棵二叉排序树 { BSTNode *bt=NULL; //初始时bt为空树 int i=0; while(i if(BSTInsert(bt,A[i])) //将A[i]插入二叉排序树T中 { count<<" 第"< DispBST(bt); printf("\n"); i++; } return bt; //返回建立的二叉排序树的根指针 }*/ void CreateBST(BSTNode *&bt,KeyType str[],int n) { bt=NULL; /*初始时bt为空树*/ int i=0; while (i { BSTInsert(bt,str[i]); /*将关键字str[i]插入二叉排序树bt中*/ i++; } } int BSTDelete(BSTNode *&bt,KeyType k) { BSTNode *p=bt,*f,*r,*f1; f=NULL; /*p指向待比较的结点,f指向*p的双亲结点*/ while (p!=NULL && p->key!=k)/*查找值域为x的结点*/ { f=p; if (p->key>k) p=p->lchild; /*在左子树中查找*/ else p=p->rchild; /*在右子树中查找*/ } if (p==NULL) /*未找到key域为k的结点*/ return(0); else if (p->lchild==NULL) /**p为被删结点,若它无左子树*/ { if (f==NULL) /**p是根结点,则用右孩子替换它*/ bt=p->rchild; else if (f->lchild==p) /**p是双亲结点的左孩子,则用其右子替换它*/ { f->lchild=p->rchild; delete p; } else if(f->rchild==p) /**p是双亲结点的右孩子,则用其右孩子替换它*/ { f->rchild=p->rchild; delete p; } } else if (p->rchild==NULL) /**p为被删结点,若它无右子树*/ { if (f==NULL) /**p是根结点,则用左孩子替换它*/ bt=p->lchild; if (f->lchild==p) /**p是双亲结点的左孩子,则用其左孩子替换它*/ { f->lchild=p->lchild; delete p; } else if(f->rchild==p) /**p是双亲结点的右孩子,则用其左孩子替换它*/ { f->rchild=p->lchild; delete p; } } else /**p为被删结点,若它有左子树和右子树*/ { f1=p;r=p->lchild; /*查找*p的左子树中的最右下结点*r*/ while (r->rchild!=NULL) /**r一定是无右子树的结点,*f1作为r的双亲*/ { f1=r; r=r->rchild; } if (f1->lchild==r) /**r是*f1的左孩子,删除*r*/ f1->lchild=r->rchild; else if (f1->rchild==r) /**r是*f1的右孩子,删除*r*/ f1->rchild=r->lchild; r->lchild=p->lchild; /*以下语句是用*r替代*p*/ r->rchild=p->rchild; if (f==NULL) /**f为根结点*/ bt=r; /*被删结点是根结点*/ else if (f->lchild==p) /**p是*f的左孩子*/ f->lchild=r; else /**p是*f的右孩子*/ f->rchild=r; delete p; } return(1); } //先序遍历 /*void preorder(BSTNode *t) { if(t!=0) { cout< preorder(t->lchild); preorder(t->rchild); } }*/ //中序遍历 void inorder(BSTNode *t) { if(t!=0) { inorder(t->lchild); cout< inorder(t->rchild); } } void BSTdisp(BSTNode *bt) { if(bt!=NULL) { cout< if(bt->lchild !=NULL||bt->rchild !=NULL) { cout<<"("; BSTdisp(bt->lchild ); if(bt->rchild !=NULL) cout<<","; BSTdisp(bt->rchild ); cout<<")"; } } } void main() { int n; BSTNode *bt=NULL,*p; KeyType a[200],k; cout <<"请输入元素个数n:"; cin >>n; cout <<"请输入数据:"; for(int i=0;i { cin >>a[i]; } CreateBST(bt,a,n); cout<<"BST:"; BSTdisp(bt);cout< cout<<"中序遍历二叉排序树:"< inorder(bt); cout<<"\n"; // cout<<"先序遍历二叉排序树:"; // preorder(bt); // cout<<"\n"; cout<<"输入要查找的元素x:"; cin >>k; p=BSTSearch(bt,k); if(p!=NULL) { BSTDelete(bt,k); cout <<"已经删除值为"< cout<<"删除X后的BST:"; BSTdisp(bt);cout< cout<<"中序遍历二叉排序树:"; inorder(bt); cout< } else cout<<"无"< } 6.运行结果与测试 2.1删除二叉树中的元素 2.2删除不在二叉树中的元素 7.设计体会与总结 通过这两周的课程设计中，又把以前的c++知识又重新过了一遍，主要是因为之前学的c++早已经忘记了，导致现在好多都不会。其次就是让我感受到了在编程过程的那种枯燥，乏味。当然也得到了充足感，而不是整天浪费时间。 课程设计最根本的目的就是培养学生们综合运用之前所学的理论知识，发现提出分析和解决问题，锻炼自身能力的重要课程。在c++方面，最为主要的就是面向对象的学习内容很重要，指针、链表等等。遇到了不少问题，最大的难题就是调试程序了。再想想这两周，又涨了许多知识，同时也让我感到自己的知识的匮乏，只能向同学求助，向网络寻求问题的解决办法。最后，我希望自己能多学一些这方面的知识，让自己脑空白得到一些补给，并且掌握。 数据结构实验五矩阵的压缩存储与运算 第五章矩阵的压缩存储与运算 【实验目的】 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()表示取整，‘%’表示求余。 专业课程设计I报告（2011 / 2012 学年第二学期） 题目稀疏矩阵的转换 专业软件工程 学生姓名张鹏宇 班级学号 09003018 指导教师张卫丰 指导单位计算机学院软件工程系 日期 2012年6月18号 指导教师成绩评定表 附件： 稀疏矩阵的转换 一、课题内容和要求 1．问题描述 设计程序用十字链表实现稀疏矩阵的加、减、乘、转置。 2．需求分析 （1）设计函数建立稀疏矩阵，初始化值。 （2）设计函数输出稀疏矩阵的值。 （3）构造函数进行两个稀疏矩阵相加，输出最终的稀疏矩阵。 （4）构造函数进行两个稀疏矩阵相减，输出最终的稀疏矩阵。 （5）构造函数进行两个稀疏矩阵的相乘，输出最终的稀疏矩阵。 （6）构造函数进行稀疏矩阵的转置，并输出结果。 （7）退出系统。 二、设计思路分析 （1）设计函数建立稀疏矩阵，初始化值。 （2）设计函数输出稀疏矩阵的值。 （3）构造函数进行两个稀疏矩阵相加，输出最终的稀疏矩阵。 （4）构造函数进行两个稀疏矩阵相减，输出最终的稀疏矩阵。 （5）构造函数进行两个稀疏矩阵的相乘，输出最终的稀疏矩阵。 （6）构造函数进行稀疏矩阵的转置，并输出结果。 （7）退出系统。 三、概要设计 为了实现以上功能，可以从3个方面着手设计。 1．主界面设计 为了实现对稀疏矩阵的多种算法功能的管理，首先设计一个含有多个菜单项的主 控菜单子程序以链接系统的各项子功能，方便用户交互式使用本系统。本系统主控菜单运行界面如图所示。 2．存储结构设计 本系统采用单链表结构存储稀疏矩阵的具体信息。其中：全部结点的信息用头结点为指针数组的单链表存储。 3．系统功能设计 本系统除了要完成稀疏矩阵的初始化功能外还设置了4个子功能菜单。稀疏矩阵的初始化由函数i typedef int ElemType 实现。建立稀疏矩阵用void Creat()实现，依据读入的行数和列数以及非零元素的个数，分别设定每个非零元素的信息。4个子功能的设计描述如下。 （1）稀疏矩阵的加法： 此功能由函数void Xiangjia( )实现，当用户选择该功能，系统即提示用户初始化要进行加法的两个矩阵的信息。然后进行加法，最后输出结果。 （2）稀疏矩阵的乘法： 此功能由函数void Xiangcheng( )实现。当用户选择该功能，系统提示输 第五章矩阵的压缩存储与运算 【实验目的】 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. 三对角矩阵 #include 稀疏矩阵及其压缩存储方法 1.基本概念 稀疏矩阵(SparseMatrix)：是矩阵中的一种特殊情况，其非零元素的个数远小于零元素的个数。 设m行n列的矩阵含t个非零元素，则称 以二维数组表示高阶的稀疏矩阵时，会产生零值元素占的空间很大且进行了很多和零值的运算的问题。 特殊矩阵：值相同的元素或0元素在矩阵中的分布有一定的规律。如下三角阵、三对角阵、稀疏矩阵。 压缩存储：为多个值相同的元素只分配一个存储空间；对0元素不分配空间。目的是节省大量存储空间。 n x n的矩阵一般需要n2个存储单元，当为对称矩阵时需要n(1+n)/2个单元。 2.三元组顺序表——压缩存储稀疏矩阵方法之一（顺序存储结构） 三元组顺序表又称有序的双下标法，对矩阵中的每个非零元素用三个域分别表示其所在的行号、列号和元素值。它的特点是，非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。当矩阵中的非0元素少于1/3时即可节省存储空间。 （1）稀疏矩阵的三元组顺序表存储表示方法 #define MAXSIZE 12500 // 假设非零元个数的最大值为12500 typedef struct { int i, j; // 该非零元的行下标和列下标 ElemType e; //非零元素的值 } Triple; // 三元组类型 typedef union { //共用体 Triple data[MAXSIZE + 1]; // 非零元三元组表，data[0]未用 int mu, nu, tu; // 矩阵的行数、列数和非零元个数 } TSMatrix; // 稀疏矩阵类型 （2）求转置矩阵的操作 ◆用常规的二维数组表示时的算法 for (col=1; col<=nu; ++col) for (row=1; row<=mu; ++row) T[col][row] = M[row][col]; 其时间复杂度为: O(mu×nu) ◆用三元组顺序表表示时的快速转置算法 Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T) { // 采用三元组顺序表存储表示，求稀疏矩阵M的转置矩阵T T.mu = M.nu; T.nu = M.mu; T.tu = M.tu; if (T.tu) { for (col=1; col<=M.nu; ++col) num[col] = 0; for (t=1; t<=M.tu; ++t) ++num[M.data[t].j];// 求M 中每一列所含非零元的个数 为了节省存储空间并且加快处理速度，需要对这类矩阵进行压缩存储，压缩存储的原则是：不重复存储相同元素；不存储零值元素。 一、相关概念 ㈠特殊矩阵：矩阵中存在大多数值相同的元,或非0元，且在矩阵中的分布有一定规律。 ⒈对称矩阵：矩阵中的元素满足 a ij=a ji 1≤i,j≤n ⒉三角矩阵：上（下）三角矩阵指矩阵的下（上）三角（不包括对角线）中的元素均为常数c或0的n阶矩阵。 ⒊对角矩阵（带状矩阵）：矩阵中所有非0元素集中在主对角线为中心的区域中。 ㈡稀疏矩阵：非0元素很少（≤ 5%）且分布无规律。 二、存储结构及算法思想 1、对称矩阵 存储分配策略：每一对对称元只分配一个存储单元,即只存储下三角（包括对角线）的元, 所需空间数为: n(n+1)/2。 存储分配方法：用一维数组sa[n(n+1)/2]作为存储结构。 sa[k]与a ij之间的对应关系为: 2、三角矩阵 也是一个n阶方阵，有上三角和下三角矩阵。下(上)三角矩阵是主对角线以上（下）元素均为零的n阶矩阵。设以一维数组sb[0..n(n+1)/2]作为n阶三角矩阵B的存储结构，仍采用按行存储方案，则B中任一元素b i,j和sb[k]之间仍然有如上的对应关系，只是还需要再加一个存储常数c的存储空间即可。如在下三角矩阵中，用n(n+1)/2的位置来存储常数。 对特殊矩阵的压缩存储实质上就是将二维矩阵中的部分元素按照某种方案排列到一维数组中，不同的排列方案也就对应不同的存储方案 2、稀疏矩阵 常见的有三元组表示法、带辅助行向量的二元组表示法（也即行逻辑链表的顺序表），十字链表表示法等。 1）、三元组表示法 三元组表示法就是在存储非零元的同时，存储该元素所对应的行下标和列下标。稀疏矩阵中的每一个非零元素由一个三元组(i,j,a ij)唯一确定。矩阵中所有非零元素存放在由三元组组成的数组中。 传递闭包Warshall方法计算可达矩阵简要介绍 ①在集合X上的二元关系R的传递闭包是包含R的X上的最小的传递关系。R的传递闭包在数字图像处理的图像和视觉基础、图的连通性描述等方面都是基本概念。一般用B表示定义在具有n个元素的集合X上关系R的n×n二值矩阵，则传递闭包的矩阵B+可如下计算： B+ = B + B2 + B3 + ……+ (B)n ②式中矩阵运算时所有乘法都用逻辑与代替，所有加法都用逻辑或代替。上式中的操作次序为B，B(B)，B(BB)，B(BBB)，……，所以在运算的每一步我们只需简单地把现有结果乘以B，完成矩阵的n次乘法即可。 https://www.doczj.com/doc/9716273192.html, /ism/cal_warshall_get_r_mat_detail.php Warshall在1962年提出了一个求关系的传递闭包的有效算法。 其具体过程如下，设在n个元素的有限集上关系R的关系矩阵为M：（1）置新矩阵A=M; （2）置k=1; （3）对所有i如果A[i,k]=1，则对j=1..n执行： A[i,j]←A[i,j]∨A[k,j]; （4）k增1; （5）如果k≤n，则转到步骤（3），否则停止。 所得的矩阵A即为关系R的传递闭包t(R)的关系矩阵。 在《离散数学》中都提及了该算法。 Warshall算法映射到有向图中 设关系R的关系图为G，设图G的所有顶点为u1,u2,…,un，则t(R)的关系图可用该方法得到：若G中任意两顶点ui和uj之间有一条路径且没有ui到uj的弧，则在图G中增加一条从ui到uj的弧，将这样改造后的图记为G’，则G’即为t(R)的关系图。G’的邻接矩阵A应满足：若图G中存在从ui到uj路径，即ui与uj连通，则A[i,j]=1，否则 A[i,j]=0。 这样，求t(R)的问题就变为求图G中每一对顶点间是否连通的问题。 相乘矩阵，就为所有节点的关系图，也就是当前条件下的关系矩阵。 对于相乘矩阵，进行叠代，叠代的过程为，行取值，然后计算值中对应的每一行的值取并集，得到当前行的关系集合。 取完所有行，得到了一个新的转移矩阵再对转移矩阵进行进行求解。 稀疏矩阵基本操作实验报告 一、实验内容 稀疏矩阵的压缩储存结构，以及稀疏矩阵的三元组表表示方法下的转置、相加、相乘等算法 二、实验目的 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报告（ 2011 / 2012 学年第二学期） 题目稀疏矩阵的转换 专业软件工程 学生姓名鹏宇 班级学号 09003018 指导教师卫丰 指导单位计算机学院软件工程系 日期 2012年6月18号 指导教师成绩评定表 附件： 稀疏矩阵的转换 一、课题容和要求 1．问题描述 设计程序用十字链表实现稀疏矩阵的加、减、乘、转置。 2．需求分析 （1）设计函数建立稀疏矩阵，初始化值。 （2）设计函数输出稀疏矩阵的值。 （3）构造函数进行两个稀疏矩阵相加，输出最终的稀疏矩阵。 （4）构造函数进行两个稀疏矩阵相减，输出最终的稀疏矩阵。 （5）构造函数进行两个稀疏矩阵的相乘，输出最终的稀疏矩阵。 （6）构造函数进行稀疏矩阵的转置，并输出结果。 （7）退出系统。 二、设计思路分析 （1）设计函数建立稀疏矩阵，初始化值。 （2）设计函数输出稀疏矩阵的值。 （3）构造函数进行两个稀疏矩阵相加，输出最终的稀疏矩阵。 （4）构造函数进行两个稀疏矩阵相减，输出最终的稀疏矩阵。 （5）构造函数进行两个稀疏矩阵的相乘，输出最终的稀疏矩阵。 （6）构造函数进行稀疏矩阵的转置，并输出结果。 （7）退出系统。 三、概要设计 为了实现以上功能，可以从3个方面着手设计。 1．主界面设计 为了实现对稀疏矩阵的多种算法功能的管理，首先设计一个含有多个菜单项的主控菜单子程序以系统的各项子功能，方便用户交互式使用本系统。本系统主控菜单运行界面如图所示。 2．存储结构设计 本系统采用单链表结构存储稀疏矩阵的具体信息。其中：全部结点的信息用头结点为指针数组的单链表存储。 3．系统功能设计 本系统除了要完成稀疏矩阵的初始化功能外还设置了4个子功能菜单。稀疏矩阵的初始化由函数i typedef int ElemType 实现。建立稀疏矩阵用void Creat()实现，依据读入的行数和列数以及非零元素的个数，分别设定每个非零元素的信息。4个子功能的设计描述如下。 （1）稀疏矩阵的加法： 此功能由函数void Xiangjia( )实现，当用户选择该功能，系统即提示用户初始化要进行加法的两个矩阵的信息。然后进行加法，最后输出结果。 （2）稀疏矩阵的乘法： 此功能由函数void Xiangcheng( )实现。当用户选择该功能，系统提示输入要进行相乘的两个矩阵的详细信息。然后进行相乘，最后得到结果。 （3）稀疏矩阵的转置： 此功能由函数void Zhuanzhi( )实现。当用户选择该功能，系统提示用户初始 实验四数组的运算 实验目的： 掌握稀疏矩阵的压缩存储方法及主要运算的实现。 实验内容与要求： 设计一个稀疏矩阵计算器，要求能够：⑴输入并建立稀疏矩阵；⑵输出稀疏矩阵；⑶执行两个矩阵相加；⑷执行两个矩阵相乘；⑸求一个矩阵的转置矩阵；⑹求一个矩阵的逆矩阵（选做）。 实验代码： Rect.h #define MAXSIZE100 typedef struct { int h_num; int v_num; int elem; }Triple; typedef struct { Triple *arry; int h_i; int v_j; int elem_num; }TSMatrix; void Init_TS(TSMatrix *T ); void creat(TSMatrix *T); void Print_TS(TSMatrix *); void sum_TS(TSMatrix *T1,TSMatrix *T2,TSMatrix *T); void mul_TS(TSMatrix *T1,TSMatrix *T2,TSMatrix *T); void transpose_TS(TSMatrix *T); void equal_Triple(Triple *t1,Triple *t2); Rect.cpp #include void Init_TS(TSMatrix *T) { T->arry=(Triple *)malloc(MAXSIZE*sizeof(Triple)); if(!T->arry) printf("error\n") ; T->elem_num=0; T->h_i=0; T->v_j=0; } void Init_Tr(Triple *t) { t->elem=0; t->h_num=0; t->v_num=0; } void creat(TSMatrix *T) { printf("要输入的数组的行数和列数\n"); scanf("%d,%d",&T->h_i,&T->v_j); printf("要输入稀疏数组的元素个数\n"); scanf("%d",&T->elem_num); printf("输入要输入的稀疏数组的信息\n"); printf("行值列值元素值\n"); for(int i=0;i 数据结构课程设计稀疏矩阵的运算 学生姓名： 学号： 指导教师： 完成日期： 目录： 1、分析问题和确定解决方案 (3) 1.1问题描述 (3) 1.2 输入的形式和输入值的范围 (3) 1.3 输出的形式 (3) 1.4 程序所能达到的功能 (3) 1.5 测试数据 (3) 1.6 确定解决方案 (4) 1.7所有抽象数据类型的定义 (4) 2、详细设计 (5) 2.1稀疏矩阵加法运算思路 (5) 2.2稀疏矩阵减法运算思路 (7) 2.3稀疏矩阵转置运算思路 (9) 2.4创建稀疏矩阵 (11) 3、系统调试与测试 (12) 3.1程序的菜单界面 (12) 3.2 实现加法运算 (12) 3.3 实现减法运算 (13) 3.4实现转置运算 (14) 4、结果分析 (15) 4.1、算法的时空分析 (15) 4.2、经验和体会 (15) 5、参考文献 (15) 1、分析问题和确定解决方案 1.1问题描述 稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计 算可以大大节省存储空间，提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。用三元组实现稀疏矩阵的相加、相减，转置； 1.2输入的形式和输入值的范围 以三元组的形式输入，首先应输入矩阵的行数和列数，并判别给出的两个 矩阵的行、列数对于所要求作的运算是否相匹配。可设矩阵的行数和列数均不超过20； 例如：输入的三元组为：((1,1,10),(2,3,9),(3,1,-1))其对应的稀疏矩阵为： ???? ??????-0019000010 1.3 输出的形式 运算结果的矩阵以通常的阵列形式输出； 1.4程序所能达到的功能 该程序可以实现以三元组形式输入两个矩阵，求出两个矩阵的和、差、转置； 并可根据输入的矩阵的行列数不同判别是否可以进行相加、减、转置，并重新输 入正确的矩阵； 1.5测试数据 测试的数据及其结果如下： 矩阵M 矩阵N 矩阵Q 加法： ???? ??????-0019000010 + ????? ?????--301100000 = ????? ?????-3008000010 减法： ???? ? ?????-0190010 - ???? ? ?????--311000 = ???? ??????-32100010 转置： 第3讲 稀疏矩阵压缩存储上——教学讲义 稀疏矩阵是指矩阵中大多数元素为零的矩阵。从直观上讲，当非零元素个数低于总元素的30 %时,这样的矩阵为稀疏矩阵。如下图所示的矩阵M 、 N 中,非零元素个数均为8个,矩阵元素总数均为6 ×7 =42 ,显然8 /42 <30 %,所以M 、 N 都是稀疏矩阵。 1 稀疏矩阵的三元组表表示法 ( 1 ) 稀疏矩阵的三元组存储表示 对于稀疏矩阵的压缩存储,采取只存储非零元素的方法。由于稀疏矩阵中非零元素aij 的分布没有规律 ,因此,要求在存储非零元素值的同时还必须存储该非零元素在矩阵中所处的行号和列号的位置信息,这就是稀疏矩阵的三元组表表示法。 每个非零元素在一维数组中的表示形式如下图所示。 说明:为处理方便,将稀疏矩阵中非零元素对应的三元组按“行序为主序”用一维结构体数组进行存放,将矩阵的每一行(行由小到大)的全部非零元素的三元组按列号递增存放。由此得到矩阵M 、 N 的三元组表A 和B 。如下图所示。 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 M= 6×7 0 0 -3 0 0 15 12 0 0 0 18 0 9 0 0 24 0 0 0 0 0 0 0 -7 0 0 0 0 0 0 0 0 14 0 0 0 0 0 0 0 0 0 7×6 N= 稀疏矩阵M 和N 三元组的结构 ( 2 )稀疏矩阵三元组表的类型定义 稀疏矩阵三元组表类型定义如下: #define MAXSIZE 1000 /*设非零元素的个数最多为1000*/ typedef struct { int row, col; /*该非零元素的行下标和列下标*/ ElementType e ； /*该非零元素的值*/ }Triple; typedef struct { Triple data[MAXSIZE+1]; /* 非零元素的三元组表。data[0]未用*/ int m, n, len; /*矩阵的行数、列数和非零元素的个数*/ }TSMatrix ； 在稀疏矩阵情况下，采用三元组表表示法大量节约了存储空间,以图5.10中的M 6*7矩阵为例，需要6*7=42个存储单元，但M 采用三元组表A 存放，共有8个非零元素,每个非零元按占3个单元计算，需要3*8=24个单元，显然比矩阵常规存储来讲还是大大节省存储。 ( 3 )三元组表实现稀疏矩阵的转置运算 需要强调的是，矩阵常规存储是二维的，而三元组存储是一维的，由于矩阵存储结构的变化也带来了运算方法的不同，必需认真分析。下面给出稀疏矩阵的转置运算问题，希望从中体会实现算法的处理思路和改进算法的技术。 矩阵转置指变换元素的位置,把位于( row,col)位置上的元素换到( col,row)位置上,把元素的行列互换。如图5 .10的6 ×7矩阵M,它的转置矩阵就是7×6的矩阵N,并且N( row,col)= M( col,row),其中,1 ≤ row ≤ 7 ,1 ≤ col ≤ 6 。 ①矩阵转置的经典算法 采用矩阵的正常存储方式(二维数组)实现矩阵转置。 稀疏矩阵转置经典算法 void TransMatrix （ElementType source[m][n], ElementType dest[n][m]） {/*source 和dest 分别为被转置的矩阵和转置以后的矩阵（用二维数组表示）*/ int i, j; for(i=0;i 1.课程设计的目的 (1) 熟练使用 C ++语言编写程序，解决实际问题; (2) 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和 设计能力; (3) 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试 等基本方法和技能; (4) 提高综合运用所学的理论知识和方法独立分析和解决问题的能 力; 2.需求分析 问题描述：对于特殊矩阵可以通过压缩存储减少存储空间。 基本要求： 1.针对多种特殊矩阵进行压缩存储，并能显示压缩后的相关地址和值。 2.输入在原来特殊矩阵中的地址，要求能从压缩后的矩阵中读出相应的值。 特殊矩阵：具有许多相同矩阵元素或零元素，并且这些相同矩阵元素或零元素的分布有一定规律性的矩阵。最常见的特殊矩阵有对称矩阵、上(下)三角矩阵、对角矩阵等。 特殊矩阵的压缩存储方法：找出特殊矩阵中值相同的矩阵元素的 分布规律，把那些呈现规律性分布的值相同的多个矩阵元素压缩存储到一个存储空间中。 3.矩阵的压缩与解压缩问题的设计 图1-1 4.调试分析 图1-2程序运行界面 图1-3 程序运行界面 5.小结 经过矩阵的压缩与解压缩的实验，让我了解到计算机是怎么为了减少承储空间的，存储矩阵的。以及特殊矩阵式在计算机中存储，以及把这些矩阵的压缩后怎么解压出来，恢复原来的样子！我觉得像这样的课程设计，一定要先想好有哪些板块，以及那些板块之间的关系这么样！谁调谁！ 6、参考文献 [1] 严蔚敏，吴伟民编著. 数据结构(C 语言版)--北京: 清华大学出版社，2007.2 [2]严蔚敏，吴伟民米宁编著. 数据结构题集(C 语言版)--北京: 清华大学出版社，2007.3 [3]网上搜索相关程序作为参考 1.实验目的： 掌握稀疏矩阵的压缩存储方法及主要运算的实现。 2.实验内容与要求： 设计一个稀疏矩阵计算器，要求能够：⑴输入并建立稀疏矩阵；⑵输出稀疏矩阵；⑶执行两个矩阵相加；⑷执行两个矩阵相乘；⑸求一个矩阵的转置矩阵。 3.数据结构设计 逻辑结构：线性结构 存储结构：顺序存储结构 4.算法设计 #include 特殊矩阵的压缩存储 对称矩阵中的元素关于主对角线对称，因此，让每一对对称元素a ij和a ji(i≠j)分配一个存储空间，则n2个元素压缩存储到n(n+1)/2个存储空间，能节约近一半的存储空间。 不失一般性，假设按“行优先顺序”存储下三角形(包括对角线)中的元素。 设用一维数组(向量)sa[0…n(n+1)/2]存储n阶对称矩阵，如图5-4所示。为了便于访问，必须找出矩阵A中的元素的下标值（i,j）和向量sa[k]的下标值k之间的对应关系。 若i≧j：a i j在下三角形中，直接保存在sa中。a i j之前的i-1行共有元素个数：1+2+…+(i-1)=i?(i-1)/2 而在第i行上，a i j之前恰有j-1个元素，因此，元素a i j保存在向量sa中时的下标值k之间的对应关系是： k=i?(i-1)/2+j-1 i≧j 若i 以主对角线划分，三角矩阵有上三角和下三角两种。 上三角矩阵的下三角（不包括主对角线）中的元素均为常数c(一般为0)。下三角矩阵正好相反，它的主对角线上方均为常数，如图5-5所示。 三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n(n+1)/2个，因此，三角矩阵可压缩存储到向量sa[0…n(n+1)/2]中，其中c存放在向量的第1个分量中。 上三角矩阵元素a i j保存在向量sa中时的下标值k与（i,j）之间的对应关系是：下三角矩阵元素a i j保存在向量sa中时的下标值k与（i,j）之间的对应关系是： 3 对角矩阵 矩阵中，除了主对角线和主对角线上或下方若干条对角线上的元素之外，其余元素皆为零。即所有的非零元素集中在以主对角线为了中心的带状区域中，如图5-6所示。 如上图三对角矩阵，非零元素仅出现在主对角(a i i,1≦i≦n)上、主对角线上的那条对角线(a i i+1,1≦i≦n-1) 、主对角线下的那条对角线上(a i+1 i,1≦i≦n-1)。显然，当| i-j |>1时，元素a ij=0。 第五章习题 1.填空题 ⑴ 数组通常只有两种运算：和，这决定了数组通常采 用结构来实现存储。 存取，修改，顺序存储 ⑵ 二维数组A中行下标从10到20，列下标从5到10，按行优先存储，每 个元素占4个存储单元，A[10][5]的存储地址是1000，则元素A[15][10]的存储地址是。 数组A中每行共有6个元素，元素A[15][10]的前面共存储了(15-10)×6+5个元素，每个元素占4个存储单元，所以，其存储地址是1000+140=1140。 ⑶ 设有一个10阶的对称矩阵A采用压缩存储，A[0][0]为第一个元素，其 存储地址为d，每个元素占1个存储单元，则元素A[8][5]的存储地址 为。d+41 ⑷ 稀疏矩阵一般压缩存储方法有两种，分别是和。 三元组顺序表，十字链表 ⑸ 广义表((a), (((b),c)),(d))的长度是，深度是， 表头是，表尾是。 3，4，(a)，((((b),c)),(d)) ⑹ 已知广义表LS=(a，(b，c，d)，e)，用Head和Tail函数取出LS中原 子b的运算是。 Head(Head(Tail(LS))) 2. 选择题 ⑴ 二维数组A的每个元素是由6个字符组成的串，行下标的范围从0~8，列下标的 范围是从0~9，则存放A至少需要（）个字节，A的第8列和第5行共占（）个字节，若A按行优先方式存储，元素A[8][5]的起始地址与当A按列优先方式存储时的（）元素的起始地址一致。 A 90 B 180 C 240 D 540 E 108 F 114 G 54 H A[8][5] I A[3][10] J A[5][8] K A[4][9] D，E，K ⑵ 将数组称为随机存取结构是因为（） A 数组元素是随机的 B 对数组任一元素的存取时间是相等的 C 随时可以对数组进行访问 D 数组的存储结构是不定 B 中国矿业大学 软件开发基础实践报告 姓名： xxs 学号： bbaa0edf 专业：计算机科学与技术 指导教师： sjc 职称： js (仅供徐海计算机参考哈哈哈哈) 2012 年 6 月 20 徐州 目录 第一章实验概述 (3) 1.1实验目的 (3) 1.2实验内容 (3) 1.3实验环境 (3) 第二章实验原理和实现过程 (4) 2.1实验原理 (4) 2.1.1建立图的邻接矩阵，判断图是否连通 (4) 2.1.2 计算任意两个结点间的距离 (4) 2.1.3对不连通的图输出其各个连通支 (5) 2.2实验过程（算法描述） (5) 2.2.1 程序整体思路 (5) 2.2.2具体算法流程 (5) 第三章实验数据及结果分析 (7) 3.1建立图的邻接矩阵并判断图是否连通的功能测试及结果分析 (7) 3.1.1输入无向图的边 (7) 3.1.2建立图的连接矩阵 (8) 3.2其他功能的功能测试和结果分析 (9) 3.2.1计算节点间的距离 (9) 3.2.2判断图的连通性 (9) 3.2.3输出图的连通支 (10) 3.2.4退出系统 (10) 第四章实验收获和心得体会 (11) 4.1实验收获 (11) 4.2心得体会 (12) 第五章实验源程序清单 (13) 5.1程序代码 (13) 第一章实验概述 1.1 实验目的 理解图论的基本概念，图的矩阵表示，图的连通性，图的遍历，以及求图的连通支方法。 通过实验，帮助学生更好地掌握计算机科学技术常用的离散数学中的概念、性质和运算，培养逻辑思维；通过实验提高学生编写实验报告、总结实验结果的能力，提高理论联系实际的能力；使学生具备程序设计的思想，能够独立完成简单的算法设计和分析。 1.2 实验内容 以偶对的形式输入一个无向简单图的边，建立该图的邻接矩阵，判断图是否连通（A），并计算任意两个结点间的距离（B），对不连通的图输出其各个连通支（C）。 注意：题目类型分为A，B，C三类，其中A为基本题，完成A类题目可达到设计的基本要求，其他均为加分题，并按字母顺序分数增加越高。 基本要求如下：程序需具有基本的容错控制，在输入错误时有处理手段；程序界面友好，需要输入的地方有输入说明，说明输入的内容和格式要求等；实验原理和实现过程应该详细分析问题，给出解决思路，描述算法思想，不能用源程序代替算法；测试数据应全面，包括非法输入的处理结果等都应包含在内。 1.3 实验环境 C或C＋＋语言编程环境实现。 软件综合课程设计 特殊矩阵的压缩存储算法的实现二叉排序树的实现 二〇一四年六月 一、特殊矩阵的压缩存储算法的实现 1.问题陈述 对于特殊矩阵可以通过压缩存储减少存储空间。 基本要求： 1.针对多种特殊矩阵进行压缩存储，并能显示压缩后的相关地址和值； 2.输入在原来特殊矩阵中的地址，要求能从压缩后的矩阵中读出相应的值； 2.程序代码 #include数据结构实验五矩阵的压缩存储与运算学习资料
稀疏矩阵的运算(完美版)
数据结构实验五矩阵的压缩存储与运算
三角矩阵在压缩存储下的转置矩阵源代码
稀疏矩阵及其压缩存储方法
矩阵压缩1
可达矩阵快速算法
稀疏矩阵基本操作 实验报告
稀疏矩阵的运算(完美版)
压缩矩阵的运算
稀疏矩阵的运算
稀疏矩阵的压缩存储上
数据结构压缩矩阵
稀疏矩阵的压缩存储方法及主要运算的实现
矩阵
第五章习题 数据结构
离散数学课程设计.图的矩阵表示及基本运算
特殊矩阵的压缩存储算法的实现
相关主题
文本预览