精华内容
下载资源
问答
  • 2021-05-21 14:14:20

    南昌航空大学实验报告

    课程名称: 数据结构 实验名称: 实验五 稀疏矩阵的存储和快速转置 班 级: 学生姓名: 学号: 指导教师评定: 签 名:

    题目:假设稀疏矩阵A采用三元组表表示,编写程序实现该矩阵的快速转置 要求:输入一个稀疏矩阵A,由程序将其转换成三元组表存储;转置后的三元组

    表,由程序将其转换成矩阵形式后输出。

    一、需求分析

    1. 用户可以根据自己的需求输入任意一个稀疏矩阵,通过程序将其转换成三元组存储方

    式;

    2. 并且能够完成矩阵的转置功能,要求需要使用的方法是快速转置的方法。

    3. 最后要够显示原矩阵和转置后的矩阵让用户能进行比较。

    4. 程序执行的命令包括:

    (1)构造稀疏矩阵M (2)求转转矩阵T (3)显示(打印)矩阵

    二、概要设计

    ⒈ 为实现上述算法,需要线性表的抽象数据类型:

    ADT SparseMatrix {

    数据对象:D={aij:|aij∈TermSet,i=1 m,m≥0,j=1 n,n≥0

    m和n分别成为矩阵的行数和列数 }

    数据关系:R={Row,Col}

    Row ={|1≤i≤m,1≤j≤n-1 }

    Col ={|1≤i≤m-1,1≤j≤n }

    基本操作:

    CreateSMtrix(& M)

    操作结果:创建稀疏矩阵M。

    DestroySMaix(&M)

    初始条件:稀疏矩阵M已存在。

    操作结果:销毁稀疏矩阵M。

    PrintSMatrix(L)

    初始条件:稀疏矩阵M已经存在。

    操作结果:输出稀疏矩阵M。

    CopySMatrix(M,&T)

    初始条件:稀疏矩阵M已经存在。

    操作结果:由稀疏矩阵M复制得到T。

    TransposeSMatrix(M,&T)

    初始条件:稀疏矩阵M已经存在。

    更多相关内容
  • 数据结构第五次作业-数组运算 数据结构第五次作业-----数组的运算 实验目的 掌握稀疏矩阵的压缩存储方法及主要运算的实现 实验内容与要求 设计一个稀疏矩阵计算器要求能够 输入并建立稀疏矩阵 输出稀疏矩阵 执行两个...
  • 数据结构 课程设计》稀疏矩阵实验报告目 录一、概述1二、 系统分析1三、 概要设计1(1)主界面的设计:2(2)系数矩阵的存储2(3)具体实现流程图:3四、详细设计4(2)稀疏矩阵的相加:5五、 运行与测试8六、 总结与心得8...

    《数据结构 课程设计》稀疏矩阵实验报告

    目 录

    一、概述1

    二、 系统分析1

    三、 概要设计1

    (1)主界面的设计:2

    (2)系数矩阵的存储2

    (3)具体实现流程图:3

    四、详细设计4

    (2)稀疏矩阵的相加:5

    五、 运行与测试8

    六、 总结与心得8

    参考文献9

    源代码9

    一、概述

    稀疏矩阵的加法运算,既将稀疏矩阵A和B,他均为m行n列,分别以数组的形式存放在A和B中,实现A+B=C,将所得的结果存放在C数组中。

    系统分析

    稀疏矩阵的保存:以一位数组顺序存放非零元素的行号、列号和数值,行号为-1作为结束符。以三个一维数组存放一个系数矩阵中的一个非零元素,为零额元素则不保存。用一个二重循环来实现判断每个系数矩阵的非零元素是否为零,不为零,就将其行列下标和其值存入一维数组中

    稀疏矩阵的相加:用循环来判断存储A何B稀疏矩阵的两个一维数组中的行列下标是否相等和其大小关系。若相等,则将两个一维数组的第三个元素的值相加存入新的数组C里,行列下标不变的存入进去;若A的列小于B的列,则将A的三个元素直接存入C中;若B的列小于A的列,则将B的三个元素村日C中;若A的行小于B的行,则将A的三个元素存入C中;若A的行大于B的行,则将B存入C中。

    概要设计

    (1)主界面的设计:

    定义两个矩阵a= 0 0 3 0 0 0 0 0 b= 0 2 0 0 0 0 0 0

    0 0 0 0 0 0 5 0 0 0 0 4 0 0 0 0

    0 0 0 0 0 0 0 0 0 0 0 0 0 6 0 0

    0 0 0 0 7 0 0 0 0 0 0 0 8 0 0 0

    0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0

    0 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0

    定义两个数组A和B,用于存储矩阵a和矩阵b的值;定义一个数组C,用于存放数组A和数组B相加后的结果。

    (2)系数矩阵的存储

    用一维数组存放系数矩阵A如下:A[0]=0,A[1]=2, A[2]=3, A[3]=1, A[4]=6, A[5]=5, A[6]=3, A[7]=4, A[8]=7, A[9]=5, A[10]=1, A[11]=9, A[12]=-1。

    用一维数组存放系数矩阵B如下:B[0]=0,B[1]=1,B[2]=2, B[3]=1,B[4]=3, B[5]=4, B[6]=2, B[7]=5, B[8]=6, B[9]=3, B[10]=4, B[11]=8, B[12]=4,B[13]=2,B[14]=1,B[15]=-1。

    (3)具体实现流程图:

    四、详细设计

    (1)稀疏矩阵的转存:

    void CreateMatrix(int A[m][n],int B[50]),这是一个将稀疏矩阵转存的函数,类似于顺序存储三元组表。在这个方法中,只要用一个二重循环来判断每个矩阵元素是否为零,若不为零,则将其行、列下标及其值存入到一维数组B中对应的元素。在定义函数的过程中,我们需要定义一个for循环,以完成行和列的转换及存储。在函数的末尾我们定义一个B[K]=-1,用于结束非零元素的存储。

    算法如下:

    void CreateMatrix(int A[m][n],int B[50])

    {

    int i,j,k=0;

    for(i=0;i

    for(j=0;j

    if(A[i][j]!=0){

    B[k]=i;k++;

    B[k]=j;k++;

    B[k]=A[i][j];k++;

    }

    B[k]=-1;

    }

    (2)稀疏矩阵的相加:

    void MatrixAdd(int A[max],int B[max],int C[max]),这个函数用于实现数组A和数组B的相加,并将其相加的结果存入数组C。这个函数讨论了数组在相加的过程中的几种情况:

    A数组和B数组的行相等且列相等,两者直接相加后存入数组C中。

    if(A[i]==B[j])

    {

    if(A[i+1]==B[j+1])

    {

    C[k]=A[i];

    C[k+1]=A[i+1];

    C[k+2]=A[i+2]+B[j+2];

    k=k+3;

    i=i+3;

    j=j+3;

    }

    }

    b、A的列小于B的列,将A的三个元素直接存入C中

    if(A[i+1]

    展开全文
  • 采用三元组表示稀疏矩阵,并实现基本运算的实验报告。
  • 稀疏矩阵 三元组单链表 结构体(行数、列数、头) 矩阵运算 重载运算符
  • 大学学数据结构一般都会接触到这个!!所以给大家分享下
  • 一、实验目的及要求:掌握稀疏矩阵的三元组表示方法、算法实现。二、实验内容:(1) 基于三元组的稀疏矩阵表示与输入、输出方法(必做);(2) 基于三元组的稀疏矩阵加法(选做);(3) 基于三元组表示的稀疏矩阵转置(选做)...

    一、实验目的及要求:

    掌握稀疏矩阵的三元组表示方法、算法实现。

    二、实验内容:

    (1) 基于三元组的稀疏矩阵表示与输入、输出方法(必做);

    (2) 基于三元组的稀疏矩阵加法(选做);

    (3) 基于三元组表示的稀疏矩阵转置(选做);

    (4) 基于三元组表示的稀疏矩阵的乘法(选做)。

    三、实验准备:

    1) 计算机设备;2) 程序调试环境的准备,如TC环境;3) 实验内容的算法分析与代码设计与分析准备。

    四、实验步骤和实验过程(该部分不够填写.请填写附页)

    1,对实验问题的描述:

    采用矩阵的压缩存储可以减少存储矩阵的空间:即为多个值相同的元只分配一个存储空间;对零元不分配存储空间,只需存储稀疏矩阵的非零元。可以采用一个三元组(i,j,a)确定矩阵的非零元,由此,稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。按照稀疏矩阵的三元组实现矩阵的输入输出,相加,相乘的基本操作。

    2,算法的数据结构

    #define MAXSIZE 1000

    typedef struct {

    int i,j;

    ElemType v;

    }Triple;

    typedef struct {

    Triple

    data[MAXSIZE+1];

    int mu, nu,

    tu;

    } Spmatrix;

    3,算法基本操作的说明及分析

    1,稀疏矩阵的创建

    int CreatTriple(Spmatrix *a)

    {

    int i;

    printf("input the max

    row and col script and the number of unzero

    element(mu,nu,tu)::");

    scanf("%d,%d,%d",&a->mu,&a->nu,&a->tu);

    printf("input the col

    and row script for each Item(i,j,v)::\n");

    for(i=1;i<=a->tu;i++)

    {

    scanf("%d,%d,%d",&a->data[i].i,&a->data[i].j,&a->data[i].v);

    }

    return OK;

    }

    2,两个稀疏矩阵相加

    int TripleAdd( Spmatrix triple_a, Spmatrix

    triple_b, Spmatrix *triple_c)

    {

    int i=1,j=1,k=1;

    if((triple_a.mu!=triple_b.mu)||(triple_a.nu!=triple_b.nu)){

    printf("The Script is different!");

    exit(0);

    }

    else{

    while(i<=triple_a.tu

    &&

    j<=triple_b.tu){

    if(triple_a.data[i].j

    triple_c->data[k].i=triple_a.data[i].i;

    triple_c->data[k].j=triple_a.data[i].j;

    triple_c->data[k].v=triple_a.data[i].v;

    k++;

    i++;

    }

    else

    if(triple_a.data[i].j>triple_b.data[j].j){

    triple_c->data[k].i=triple_b.data[j].i;

    triple_c->data[k].j=triple_a.data[j].j;

    triple_c->data[k].v=triple_a.data[j].v;

    k++;

    j++;

    }

    else{

    triple_c->data[k].i=triple_b.data[j].i;

    triple_c->data[k].j=triple_a.data[j].j;

    triple_c->data[k].v=triple_a.data[i].v+triple_b.data[j].v;

    k++;

    i++;

    j++;

    }

    }

    else

    if(triple_a.data[i].i

    triple_c->data[k].i=triple_a.data[i].i;

    triple_c->data[k].j=triple_a.data[i].j;

    triple_c->data[k].v=triple_a.data[i].v;

    k++;

    i++;

    }

    else{

    triple_c->data[k].i=triple_a.data[j].i;

    triple_c->data[k].j=triple_b.data[j].j;

    triple_c->data[k].v=triple_b.data[j].v;

    k++;

    j++;

    }

    }

    triple_c->mu=triple_a.mu;

    triple_c->nu=triple_a.nu;

    triple_c->tu=k-1;

    }

    return 0;

    }

    3,两个稀疏矩阵相乘

    int TripleValue(Spmatrix *c,int i,int

    j){

    int k=1;

    while(k<=c->tu

    && (c->data[k].i!=i

    ||c->data[k].j!=j ))

    k++;

    if(k<=c->tu) return

    (c->data[k].v);

    else return 0;

    }

    int TripleMul (int m,int n,int k,Spmatrix a,Spmatrix

    b,Spmatrix *c)

    {

    int i,j,h,p=1,s;

    for(i=0;i

    for(j=0;j

    s=0;

    for(h=0;h

    s=s+TripleValue(&a,i,h)*TripleValue(&b,h,j);

    }

    if(s!=0){

    c->data[p].i=i;

    c->data[p].j=j;

    c->data[p].v=s;

    p++;

    }

    }

    }

    c->mu=m;

    c->nu=k;

    c->tu=p-1;

    return 0;

    }

    4,稀疏矩阵的打印

    int Print( Spmatrix *triple_a)

    {

    int i;

    if(triple_a->tu==0){

    printf("Empty Triple\n\n");

    return ERROR;

    }

    printf("i\tj\tdata\n");

    for( i=1;

    i<=triple_a->tu; i++ ){

    printf("%d\t%d\t%d\n",

    triple_a->data[i].i,triple_a->data[i].j,triple_a->data[i].v);

    }

    return 0;

    }

    4,算法描述的程序代码:

    #include

    #include

    #define

    OK 1

    #define

    ERROR 0

    #define MAXSIZE 1000

    #define M 3

    #define N 3

    typedef int ElemType;

    typedef struct {

    int i,j;

    ElemType v;

    }Triple;

    typedef struct {

    Triple

    data[MAXSIZE+1];

    int mu, nu,

    tu;

    } Spmatrix;

    Spmatrix a;

    int CreatTriple(Spmatrix *a)

    {

    int i;

    printf("input the max

    row and col script and the number of unzero

    element(mu,nu,tu)::");

    scanf("%d,%d,%d",&a->mu,&a->nu,&a->tu);

    printf("input the col

    and row script for each Item(i,j,v)::\n");

    for(i=1;i<=a->tu;i++)

    {

    scanf("%d,%d,%d",&a->data[i].i,&a->data[i].j,&a->data[i].v);

    }

    return OK;

    }

    int TripleAdd( Spmatrix triple_a, Spmatrix

    triple_b, Spmatrix *triple_c)

    {

    int i=1,j=1,k=1;

    if((triple_a.mu!=triple_b.mu)||(triple_a.nu!=triple_b.nu)){

    printf("The Script is different!");

    exit(0);

    }

    else{

    while(i<=triple_a.tu

    &&

    j<=triple_b.tu){

    if(triple_a.data[i].i==triple_b.data[j].i){

    if(triple_a.data[i].j

    triple_c->data[k].i=triple_a.data[i].i;

    triple_c->data[k].j=triple_a.data[i].j;

    triple_c->data[k].v=triple_a.data[i].v;

    k++;

    i++;

    }

    else

    if(triple_a.data[i].j>triple_b.data[j].j){

    triple_c->data[k].i=triple_b.data[j].i;

    triple_c->data[k].j=triple_a.data[j].j;

    triple_c->data[k].v=triple_a.data[j].v;

    k++;

    j++;

    }

    else{

    triple_c->data[k].i=triple_b.data[j].i;

    triple_c->data[k].j=triple_a.data[j].j;

    triple_c->data[k].v=triple_a.data[i].v+triple_b.data[j].v;

    k++;

    i++;

    j++;

    }

    }

    else

    if(triple_a.data[i].i

    triple_c->data[k].i=triple_a.data[i].i;

    triple_c->data[k].j=triple_a.data[i].j;

    triple_c->data[k].v=triple_a.data[i].v;

    k++;

    i++;

    }

    else{

    triple_c->data[k].i=triple_a.data[j].i;

    triple_c->data[k].j=triple_b.data[j].j;

    triple_c->data[k].v=triple_b.data[j].v;

    k++;

    j++;

    }

    }

    triple_c->mu=triple_a.mu;

    triple_c->nu=triple_a.nu;

    triple_c->tu=k-1;

    }

    return 0;

    }

    int Print( Spmatrix *triple_a)

    {

    int i;

    if(triple_a->tu==0){

    printf("Empty Triple\n\n");

    return ERROR;

    }

    printf("i\tj\tdata\n");

    for( i=1;

    i<=triple_a->tu; i++ ){

    printf("%d\t%d\t%d\n",

    triple_a->data[i].i,triple_a->data[i].j,triple_a->data[i].v);

    }

    return 0;

    }

    int TripleValue(Spmatrix *c,int i,int

    j){

    int k=1;

    while(k<=c->tu

    && (c->data[k].i!=i

    ||c->data[k].j!=j ))

    k++;

    if(k<=c->tu) return

    (c->data[k].v);

    else return 0;

    }

    int TripleMul (int m,int n,int k,Spmatrix a,Spmatrix

    b,Spmatrix *c)

    {

    int i,j,h,p=1,s;

    for(i=0;i

    for(j=0;j

    s=0;

    for(h=0;h

    s=s+TripleValue(&a,i,h)*TripleValue(&b,h,j);

    }

    if(s!=0){

    c->data[p].i=i;

    c->data[p].j=j;

    c->data[p].v=s;

    p++;

    }

    }

    }

    c->mu=m;

    c->nu=k;

    c->tu=p-1;

    return 0;

    }

    int main(void)

    {

    Spmatrix A1, A2, A3;

    CreatTriple(&A1);

    CreatTriple(&A2);

    printf("output

    A1:\n");

    Print(&A1);

    printf("output

    A2:\n");

    Print(&A2);

    if( A1.mu==A2.mu

    && A1.nu==A2.nu ){

    TripleAdd( A1, A2, &A3);

    printf("The two Matrix plus is::\n");

    Print(&A3);

    }

    else printf("Not to

    plus\n");

    if( A1.nu==A2.mu

    ){

    TripleMul(A1.mu,A2.mu,A1.tu, A1, A2, &A3);

    printf("The two matrix multiplication::\n");

    Print(&A3);

    }

    system("pause");

    return 0;

    }

    5,对程序代码的测试:

    6,实验结果分析与评价

    (该部分不够填写.请填写附页):

    输入两个矩阵:3 0 2 1 1 0

    0 1 4 0 2 3

    2 0 3 0 0 1

    相加后得:4 1 2 相乘后:3 3 2

    0 3 7 0 2 7

    2 0 4 2 2 3

    7、实验方法的拓展:

    #include

    #define MAXSIZE 100

    typedef int ElemType;

    typedef struct{

    int i,j;

    ElemType e;

    }Triple;

    typedef struct{

    Triple

    data[MAXSIZE+1];

    int mu,nu,tu;

    }SMatrix;

    void CreatMatrix(SMatrix *M)

    {

    int a,b,c,x;

    printf("please input mu,nu,tu of the

    matrix:\n");

    printf(" ");

    scanf("%d,%d,%d",&M->mu,&M->nu,&M->tu);

    for(x=1;x<=M->tu;x++)

    {

    printf("Please input the data:");

    printf(" ");

    scanf("%d,%d,%d",&a,&b,&c);

    M->data[x].i=a;

    M->data[x].j=b;

    M->data[x].e=c;

    }

    }

    void Show(SMatrix *M)

    {

    int x;

    printf("the SMatrix

    is:");

    printf(" ");

    for(x=1;x<=M->tu;x++)

    {

    printf("%3d,%3d,%3d",M->data[x].i,M->data[x].j,M->data[x].e);

    printf(" ");

    }

    }

    void Add(SMatrix *M1,SMatrix *M2,SMatrix *M)

    {

    int

    a=1,b=1;

    int

    k=1;

    CreatMatrix(M1);

    Show(M1);

    CreatMatrix(M2);

    Show(M2);

    printf(" ");

    printf(" ");

    if((M1->mu!=M2->mu)||(M1->nu!=M2->nu))

    {

    printf("the two matrix are not mach: ");

    exit(1);

    }

    M->mu=M1->mu;M->nu=M1->nu;

    if((M1->tu==0)&&(M2->tu==0))

    return ;

    while((a<=M1->tu)&&(b<=M2->tu))

    {

    if(M1->data[a].idata[b].i)

    {

    M->data[k]=M1->data[a];

    a++;k++;

    }

    else

    if(M1->data[a].i>M2->data[b].i)

    {

    M->data[k]=M2->data[b];

    b++;k++;

    }

    else{

    if(M1->data[a].jdata[b].j)

    {

    M->data[k]=M1->data[a];

    a++;k++;

    }

    else if(M1->data[a].j>M2->data[b].j)

    {

    M->data[k]=M2->data[b];

    b++;k++;

    }

    else

    {

    if

    (M1->data[a].e+M2->data[b].e!=0)

    {

    M->data[k].i=M1->data[a].i;

    M->data[k].j=M1->data[a].j;

    M->data[k].e=M1->data[a].e+M2->data[b].e;

    k++;

    }

    a++;b++;

    }

    }

    }

    while(a<=M1->tu)

    {

    M->data[k]=M1->data[a];

    a++;k++;

    }

    while(b<=M2->tu)

    {

    M->data[k]=M2->data[b];

    b++;k++;

    }

    M->tu=k-1;

    return;

    }

    int main(void)

    {

    SMatrix M1,M2,M;

    clrscr();

    Add(&M1,&M2,&M);

    Show(&M);

    return 0;

    }

    8,算法的时间复杂度为:

    O(mu*nu*tu)

    9、实验心得体会

    稀疏矩阵的三元组存储,一个稀疏矩阵的转置仍然是稀疏矩阵,但两个稀疏矩阵的乘积不一定是稀疏矩阵。

    展开全文
  • 教育资料 实验报告 题目稀疏矩阵运算器 班级14电子商务平台建设班 完成日期2015.11.2 学号20141103468 姓名 孙少辉 学号20141103421 姓名 杨德龙 学号20141103407 姓名 柴益新 一需求分析 稀疏矩阵是指那些多数元素...
  • 数据结构实验稀疏矩阵计算器.pdf数据结构实验稀疏矩阵计算器.pdf数据结构实验稀疏矩阵计算器.pdf数据结构实验稀疏矩阵计算器.pdf数据结构实验稀疏矩阵计算器.pdf
  • 数据结构实验报告 稀疏矩阵计算器。稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储(只存储非零元)和计算可以大大节省存储空间,提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。以“带行...
  • 数据结构课小实验,简单实现稀疏矩阵转置,终端显示 压缩包包含:xxjz.txt,一个cpp,可直接编译运行
  • 内蒙古科技大学 数据结构课程设计说明书 题 目稀疏矩阵运算器设计 学生姓名 学 号 专 业计算机科学与技术 班 级计 09-1 班 指导教师刘 月 峰 2011 年 6 月 24 日 稀疏矩阵运算器设计 摘 要 摘要设计一稀疏矩阵运算器...
  • 稀疏矩阵是指矩阵中大多数元素为零的矩阵。从直观上讲,当非零元素个数低于总元素的30%时,这样的矩阵为稀疏矩阵

    数据结构–稀疏矩阵转置(列序递增算法)的c语言实现(超详细注释/实验报告)

    知识小回顾

    稀疏矩阵是指矩阵中大多数元素为零的矩阵。从直观上讲,当非零元素个数低于总元素的30%时,这样的矩阵为稀疏矩阵。

    稀疏矩阵的三元组表表示方法

    对于稀疏矩阵的压缩存储,采取只存储非零元素的方法。由于系数矩阵中非零元素 a i j a_{ij} aij的分布没有规律,因此,在存储非零元素值的同时,还必须存储该非零元素在矩阵中所处的行号和列号的位置信息,这就是稀疏矩阵的三元组表表示方法。

    实验题目

    1. 稀疏矩阵采用三元组顺序表的存储结构
    2. 能够实现按列序递增进行转置
    3. 输出矩阵转置前后的三元组

    实验目的

    1. 了解压缩存储的基本原理
    2. 了解稀疏矩阵的三元组表的压缩存储方法
    3. 熟悉三元组表表示的稀疏矩阵运算的实现

    实验要求

    1. 稀疏矩阵的三元组表示法及三元组表示的矩阵的转置的实现
    2. 三元组表示的稀疏矩阵相关运算的实现

    实验内容和实验步骤

    1.需求分析

     实现用户输入一个三元组表,程序将其转置并输出。
    

    2. 概要设计

     设计一个函数实现转置操作,在主函数中让用户输入并输出结果。
    

    3. 详细设计

    导入库并定义三元组和三元组表的基本类型

    #include<stdio.h>
    #define MAXSIZE 20
    typedef struct
    {
        int row,col,val;//非零元素的行下表和列下标以及值
    }TriNode;
    
    typedef struct
    {
        TriNode data[MAXSIZE+1];//非零元素的三元组表。data[0]未用
        int m,n,len;//矩阵的行数、列数及非零元素个数
    }TriTable;
    

    稀疏矩阵列序递增转置的函数

    //稀疏矩阵列序递增转置
    void Transpose(TriTable A,TriTable *B)s
    {
        int i,j,k;
        B->m=A.n;
        B->n=A.m;
        B->len=A.len;//行数、列数交换,长度还都是相等的
    //    printf("%d %d %d\n",B->m,B->n,B->len);
        if(B->len>0)
        {
            j=1;//j为辅助计数器,记录转置后三元组在三元组B中的下标值
            for(k=1;k<=A.n;k++)
            {
                for(i=1;i<=A.len;i++)
                {
                    if(A.data[i].col==k)
                    {
                        B->data[j].col=A.data[i].row;
                        B->data[j].row=A.data[i].col;
                        B->data[j].val=A.data[i].val;
                        j++;
                    }
                }
            }
        }
    }
    

    主函数部分

    • 这里就是让用户输入需要转置的矩阵的相关信息,然后调用矩阵转置的函数,并输出转置后的矩阵。
    int main()
    {
        TriTable s;
        printf("请输入稀疏矩阵的行数、列数和非零元素个数(以空格隔开):");
    //    scanf("%d",&s.m);
    //    scanf("%d",&s.n);
    //    scanf("%d",&s.len);
        scanf("%d%d%d",&s.m,&s.n,&s.len);
    //    printf("%d%d%d",s.m,s.n,s.len);
        if(s.len==0)
            return 0;
        int val;
        val=s.len;
        int i;
        for(i=1;i<=val;i++)
        {
            printf("第%d个元素<行号,列号,值>:",i);
            scanf("%d%d%d",&s.data[i].row,&s.data[i].col,&s.data[i].val);
        }
    //    printf("%d",s.data[2].val);
        printf("转置前的三元组<行号,列号,值>:\n");
        for(i=1;i<=s.len;i++)
        {
            printf("%d ,%d ,%d \n",s.data[i].row,s.data[i].col,s.data[i].val);
        }
        TriTable t;
        Transpose(s,&t);
        printf("转置后的三元组<行号,列号,值>:\n");
        for(i=1;i<=t.len;i++)
        {
            printf("%d ,%d ,%d \n",t.data[i].row,t.data[i].col,t.data[i].val);
        }
        return 0;
    }
    

    4. 调试分析

    遇到的问题及解决方法

    • 一开始发现列数为矩阵最大列数的三元组无法转置,后来发现时条件判断中的<=误写成了<

    算法的时空分析

    算法已经实现了压缩存储,故空间复杂度相比于普通存储节省了不少。
    算法的时间耗费主要是在双重循环中,其时间复杂度为 O ( A . n ∗ A . l e n ) O(A.n*A.len) O(A.nA.len)。最坏情况是当矩阵中全部是非零元素时,这个时候时间复杂度为 O ( A . m ∗ A . n 2 ) O(A.m*A.n^2) O(A.mA.n2)若采用经典算法实现矩阵转置的算法时间复杂度为 O ( A . m ∗ A . n ) O(A.m*A.n) O(A.mA.n)。因此,三元组表表示法

    实验结果

    在这里插入图片描述

    实验指导中没有编写函数,我是结合课本和实验指导,写了一个转置的函数出来,这样使得程序的可移植性更强,并为后面编写一次定位快速转置做准备!

    实验总结

    顺序串需要注意的细节很多,多多重复,百炼成钢!

    最后附上完整的代码

    #include<stdio.h>
    #define MAXSIZE 20
    typedef struct
    {
        int row,col,val;//非零元素的行下表和列下标以及值
    }TriNode;
    
    typedef struct
    {
        TriNode data[MAXSIZE+1];//非零元素的三元组表。data[0]未用
        int m,n,len;//矩阵的行数、列数及非零元素个数
    }TriTable;
    
    //稀疏矩阵列序递增转置
    void Transpose(TriTable A,TriTable *B)s
    {
        int i,j,k;
        B->m=A.n;
        B->n=A.m;
        B->len=A.len;//行数、列数交换,长度还都是相等的
    //    printf("%d %d %d\n",B->m,B->n,B->len);
        if(B->len>0)
        {
            j=1;//j为辅助计数器,记录转置后三元组在三元组B中的下标值
            for(k=1;k<=A.n;k++)
            {
                for(i=1;i<=A.len;i++)
                {
                    if(A.data[i].col==k)
                    {
                        B->data[j].col=A.data[i].row;
                        B->data[j].row=A.data[i].col;
                        B->data[j].val=A.data[i].val;
                        j++;
                    }
                }
            }
        }
    }
    
    int main()
    {
        TriTable s;
        printf("请输入稀疏矩阵的行数、列数和非零元素个数(以空格隔开):");
    //    scanf("%d",&s.m);
    //    scanf("%d",&s.n);
    //    scanf("%d",&s.len);
        scanf("%d%d%d",&s.m,&s.n,&s.len);
    //    printf("%d%d%d",s.m,s.n,s.len);
        if(s.len==0)
            return 0;
        int val;
        val=s.len;
        int i;
        for(i=1;i<=val;i++)
        {
            printf("第%d个元素<行号,列号,值>:",i);
            scanf("%d%d%d",&s.data[i].row,&s.data[i].col,&s.data[i].val);
        }
    //    printf("%d",s.data[2].val);
        printf("转置前的三元组<行号,列号,值>:\n");
        for(i=1;i<=s.len;i++)
        {
            printf("%d ,%d ,%d \n",s.data[i].row,s.data[i].col,s.data[i].val);
        }
        TriTable t;
        Transpose(s,&t);
        printf("转置后的三元组<行号,列号,值>:\n");
        for(i=1;i<=t.len;i++)
        {
            printf("%d ,%d ,%d \n",t.data[i].row,t.data[i].col,t.data[i].val);
        }
        return 0;
    }
    
    展开全文
  • 教学单位计算机科学与技术 学生学号_5 HUBEI ENGINEERING UNIVERSITY 数据结构 课程设计报告书 题 目稀疏矩阵运算器 学生 专业名称 指导教师 实验目的 深入研究数组的存储表示和实现技术熟悉广义表存储结构的特性 ...
  • 资源仅供参考!不用做其他用途 内含:完整实验报告代码,和注释
  • 编写程序,从字符文件读入三个正整数m, n, t以及t个三元组(i, j, e)建立稀疏矩阵的十字链表存储结构。其中,m、n分别表示矩阵行数和列数;i, j为非零元素行号和列号。编写算法,实现矩阵转置,输出转置后的三元组到...
  • 完整的一套数据结构实验稀疏矩阵源码加完整的实验报告,可以供大家参考一下!
  • 西工大NOJ数据结构实验——实验 2.4稀疏矩阵的乘法
  • 本题要求使用三元组进行矩阵转置,方法有两种,列序递增转置以及一次定位快速转置。 第一种方法思路简单,即将行列直接交换再进行排列,但占用空间较多,时间较慢。 第二种方法耗时较短,思路简述为记录每一列元素个...
  • 西工大NOJ数据结构实验——2.1稀疏矩阵转置

    千次阅读 多人点赞 2022-04-01 13:57:27
    西工大NOJ数据结构实验——2.1稀疏矩阵转置
  • 矩阵转置没什么好说的,都在注释里了,上代码: #include<stdio.h> #include <stdlib.h> #define ok 1 #define error 0 #define max 1000 typedef struct { int hang; int lie; int data; }seq; void...
  • 1、掌握各种特殊矩阵如对称矩阵、上、下三角矩阵和对角矩阵的压缩...掌握稀疏矩阵的各种存储结构以及基本运算实现算法。 2、掌握广义表的定义、存储结构和运算。 3、掌握递归算法的设计,递归算法到非递归算法的转换
  • 数据结构稀疏矩阵基本运算实验报告.课 程 设 计课程:数据结构题目:稀疏矩阵4 三元组单链表 结构体(行数、列数、头) 矩阵运算重载运算符 优班级:姓名:学号:设计时间:2010年1月17日——2010年5月XX日成绩:指导...
  • 数据结构 基于三元组表的存储结构实现稀疏矩阵的应用 课程设计 实验报告 数 据 结 构 课 程 设 计设计题目:基于三元组表的存储结构实现稀疏矩阵的应用课题名称 基于三元组表的存储结构实现稀疏矩阵的应用院 系 年级...
  • 数据结构实验报告稀疏矩阵实验报告的模式,稀疏矩阵的运用
  • 数据结构实验稀疏矩阵的表示和运算 题目描述 ​稀疏矩阵中有大量0元素,为了节约存储空间,可以用三元组表示法存储的稀疏矩阵。 又为了加快访问速度,三元组表示法存储的元素,按行列坐标升序排列。 现要求计算一...
  • 按照教科书《数据结构(C语言版)》(严蔚敏等)5.3.2节中描述的方法,以十字链表表示稀疏矩阵。一、需求分析稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进修学校储存和计算可以大大节省储存空间,提高计算...
  • 掌握稀疏矩阵三元组的存储结构形式及其描述。 2. 熟练掌握用三元组存储稀疏矩阵,实现“列递增”转置和“一次定位”快速转置算法。 【实验类型】 验证型实验实验原理】 (1
  • 实验稀疏矩阵 #include <stdio.h> #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define MAXSIZE 100 typedef int Status; typedef float ElemType; typedef struct{ int i,j; //非零元素行下标...
  • 数据结构稀疏矩阵的转置及快速转置操作实现

    千次阅读 多人点赞 2020-12-10 17:24:57
    稀疏矩阵头文件,宏定义,重命名创建矩阵销毁矩阵输出矩阵普通转置快速转置完整源码 头文件,宏定义,重命名 #include <stdio.h> #include <stdlib.h> #define OK 1 #define ERROR -1 #define OVERFLOW...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 15,306
精华内容 6,122
关键字:

数据结构稀疏矩阵实验

数据结构 订阅