数据结构第四次作业..docxVIP

数据结构上机实验报告实验目的：稀疏矩阵的压缩存储，以及二叉树的练习。实验内容：一、1. 实验题目：稀疏矩阵快速转置算法的实现。要求：设计算法fasttranspose，用于实现任意稀疏矩阵的转置。2.程序源代码：#include stdio.h#define MAXCOL 100int a[][3]={{7,6,8},{0,0,5},{0,3,2},{0,5,8},{1,1,6},{1,2,9},{2,3,3},{4,0,9},{5,2,2}};//自定义稀疏矩 //阵int b[9][3];void fasttranspose(int a[][3],int b[][3])//重要操作函数{int m,n,tn,i,j;//m,n是稀疏矩阵行，列的最大值，tn是非零元素的个数int S[MAXCOL],T[MAXCOL];m=a[0][0];n=a[0][1];tn=a[0][2];b[0][0]=n;b[0][1]=m;b[0][2]=tn;if(tn=0) return ;for(i=0;in;i++) S[i]=0;for(i=1;i=tn;i++) S[a[i][1]]=S[a[i][1]]+1;T[0]=1;for(i=1;in;i++)T[i]=T[i-1]+S[i-1];for(i=1;i=tn;i++){j=a[i][1];b[T[j]][0]=a[i][1];b[T[j]][1]=a[i][0];b[T[j]][2]=a[i][2];T[j]=T[j]+1;}}void main(){int i,j;fasttranspose(a,b);for(i=0;i9;i++){printf(\n);for(j=0;j3;j++)printf(%d ,b[i][j]);}}3.运行结果：4.算法分析：影响时间复杂性的语句主要是：for语句；时间复杂性分析：void fasttranspose(int a[][3],int b[][3]) O(n+t);5.总结：稀疏矩阵的快速转置操作主要利用了两个一维数组来存放转换元素的位置信息，这样就能减少对稀疏矩阵的扫面次数。二、1.实验题目：已知两个稀疏矩阵a和b，非零元素个数分别为t1和t2，编写一个函数计算稀疏矩阵a和b的和c，并用三元组表示。2.程序源代码：#include stdio.h#define m 7#define n 7void change(int a[][n],int b[][3])//将稀疏矩阵转化为三元组{int i,j,s;s=1;for(i=0;im;i++)for(j=0;jn;j++){if(a[i][j]!=0){b[s][0]=i;b[s][1]=j;b[s][2]=a[i][j];s++;}}b[0][0]=m;b[0][1]=n;b[0][2]=s--;} void plus(int a[][3],int b[][3],int c[][3]) //操作函数{int i=1,sum,t=0;int pa=1,pb=1,pc=1;//pa,pb,pc做指向三元组当前元素的指针c[0][0]=a[0][0];c[0][1]=a[0][1];for(i=0;i=a[0][0];i++)//控制行数的变换 { while(a[pa][0]i) pa++;while(b[pb][0]i) pb++;while(a[pa][0]==ib[pb][0]==i)//当三元组行数相同时 {if(a[pa][1]==b[pb][1]) {sum=a[pa][2]+b[pb][2];//判断列数的关系，分别操作 if(sum){ c[pc][0]=i; c[pc][1]=a[pa][1]; c[pc][2]=sum; pa++;pb++;pc++;t++;//每次操作后将对应 } //指针下移，即加一 } else{if(a[pa][1]b[pb][1]){c[pc][2]=a[pa][2]; c[pc][0]=i; c[pc][1]=a[pa][1]; pa++;pc++;t++;} else { c[pc][2]=b[pb][2]; c[pc][0]=i; c[pc][1]=b[pb][1]; pb++;pc++;t++;} }} while(a[pa][0]==i)//将三元组a和b中的剩余元素加入c中 {c[pc][2]=a[pa][2]; c[pc][0]=i; c[pc][1]=a[pa][1]; pa++;pc++;t++;} while(b[pb][0]==i) {c[pc][2]=b[pb][2]; c[pc][0]=i; c[pc][1]=b[pb][1]; pb++;pc++;t++;} }c[0][2]=t;