数据结构实践——稀疏矩阵相加

本文针对数据结构基础系列网络课程(5)：数组与广义表的实践项目。

【项目 - 稀疏矩阵相加】
　　采用三元组存储稀疏矩阵，设计两个稀疏矩阵相加的运算算法
提示1：两个行数、列数相同的矩阵可以相加
提示2：充分利用已经建立好的算法库解决问题

[参考解答1]（程序中使用的头文件”tup.h”见稀疏矩阵的三元组表示算法库）　

#include <stdio.h>
#include "tup.h"
bool MatAdd(TSMatrix a,TSMatrix b,TSMatrix &c)
{
    int i,j;
    ElemType va,vb,vc;
    if (a.rows!=b.rows || a.cols!=b.cols)
        return false;                        //行数或列数不等时不能进行相加运算
    c.rows=a.rows;
    c.cols=a.cols;       //c的行列数与a的相同
    c.nums=0;
    for(i=0; i<M; i++)
        for(j=0; j<N; j++)
        {
            Assign(a,va,i,j);
            Assign(b,vb,i,j);
            vc=va+vb;
            if(vc)
                Value(c,vc,i,j);
        }
    return true;
}

int main()
{
    TSMatrix ta,tb,tc;
    int A[M][N]=
    {
        {0,0,1,0,0,0,0},
        {0,2,0,0,0,0,0},
        {3,0,0,0,0,0,0},
        {0,0,0,5,0,0,0},
        {0,0,0,0,6,0,0},
        {0,0,0,0,0,7,4}
    };
    int B[M][N]=
    {
        {0,0,10,0,0,0,0},
        {0,0,0,20,0,0,0},
        {0,0,0,0,0,0,0},
        {0,0,0,50,0,0,0},
        {0,0,20,0,0,0,0},
        {0,0,0,10,0,0,4}
    };
    CreatMat(ta,A);
    CreatMat(tb,B);
    printf("A:\n");
    DispMat(ta);
    printf("B:\n");
    DispMat(tb);
    if(MatAdd(ta, tb, tc))
    {
        printf("A+B:\n");
        DispMat(tc);
    }
    else
    {
        printf("相加失败\n");
    }
    return 0;
}

[参考解答2]
　　下面给出的解答，没有利用算法库中已经实现的Assign和Value两个基本运算，而是直接e采取了更为直接的方法去完成。用i和j两个变量扫描三元组a和b，按行序优先的原则进行处理，将结果存放于c中。当a的当前元素和b的当前元素的行号和列号均相等时，将它们的值相加，只有在相加值不为0时，才在c中添加一个新的元素。

#include <stdio.h>
#include "tup.h"
bool MatAdd(TSMatrix a,TSMatrix b,TSMatrix &c)
{
    int i=0,j=0,k=0;
    ElemType v;
    if (a.rows!=b.rows || a.cols!=b.cols)
        return 0;        //行数或列数不等时不能进行相加运算
    c.rows=a.rows;
    c.cols=a.cols;       //c的行列数与a的相同
    while (i<a.nums && j<b.nums)         //处理a和b中的每个元素
    {
        if (a.data[i].r==b.data[j].r)    //行号相等时
        {
            if(a.data[i].c<b.data[j].c)  //a元素的列号小于b元素的列号
            {
                c.data[k].r=a.data[i].r;//将a元素添加到c中
                c.data[k].c=a.data[i].c;
                c.data[k].d=a.data[i].d;
                k++;
                i++;
            }
            else if (a.data[i].c>b.data[j].c)//a元素的列号大于b元素的列号
            {
                c.data[k].r=b.data[j].r;      //将b元素添加到c中
                c.data[k].c=b.data[j].c;
                c.data[k].d=b.data[j].d;
                k++;
                j++;
            }
            else                    //a元素的列号等于b元素的列号
            {
                v=a.data[i].d+b.data[j].d;
                if (v!=0)           //只将不为0的结果添加到c中
                {
                    c.data[k].r=a.data[i].r;
                    c.data[k].c=a.data[i].c;
                    c.data[k].d=v;
                    k++;
                }
                i++;
                j++;
            }
        }
        else if (a.data[i].r<b.data[j].r) //a元素的行号小于b元素的行号
        {
            c.data[k].r=a.data[i].r;      //将a元素添加到c中
            c.data[k].c=a.data[i].c;
            c.data[k].d=a.data[i].d;
            k++;
            i++;
        }
        else                              //a元素的行号大于b元素的行号
        {
            c.data[k].r=b.data[j].r;      //将b元素添加到c中
            c.data[k].c=b.data[j].c;
            c.data[k].d=b.data[j].d;
            k++;
            j++;
        }
    }
    while (i<a.nums)         //a中尚有元素时
    {
        c.data[k].r=a.data[i].r;//将a元素添加到c中
        c.data[k].c=a.data[i].c;
        c.data[k].d=a.data[i].d;
        k++;
        i++;
    }
    while (j<b.nums)         //b中尚有元素时
    {
        c.data[k].r=b.data[j].r;      //将b元素添加到c中
        c.data[k].c=b.data[j].c;
        c.data[k].d=b.data[j].d;
        k++;
        j++;
    }
    c.nums=k;
    return true;
}

int main()
{
    TSMatrix ta,tb,tc;
    int A[M][N]=
    {
        {0,1,0,0,0,0,0},
        {0,2,0,0,0,0,0},
        {3,0,0,0,0,0,0},
        {0,0,0,5,0,0,0},
        {0,0,0,0,6,0,0},
        {0,0,0,0,0,7,4}
    };
    int B[M][N]=
    {
        {0,0,10,0,0,0,0},
        {0,0,0,20,0,0,0},
        {0,0,0,0,0,0,0},
        {0,0,0,50,0,0,0},
        {0,0,20,0,0,0,0},
        {0,0,0,10,0,0,4}
    };
    CreatMat(ta,A);
    CreatMat(tb,B);
    printf("A:\n");
    DispMat(ta);
    printf("B:\n");
    DispMat(tb);
    if(MatAdd(ta, tb, tc))
    {
        printf("A+B:\n");
        DispMat(tc);
    }
    else
    {
        printf("相加失败\n");
    }
    return 0;
}

　　对比两种方案，“参考解答1”利用Assign和Value两个基本运算的方案，可以在只知道“矩阵加法是对应位置的元素相加”的基础上就可以求解；而“参考解答2”则不得不关注在数据存储层面的细节，以致于矩阵加法的规则都不容易看出来了。“参考解答2”中繁杂的代码，违反了程序设计中诸多的原则（例如模块化），相对“参考解答1”的简洁中透出的优雅，该不是学习者效仿的思维。

附：1楼评论中带bug的解答，原参考解答2。重点观察少了while (i<a.nums)、while (j<b.nums)两个循环，当a和b的最后一个元素不在同一行同一列时，会丢数据的。这个bug的漏网，和main函数中采用的测试数据不够好有关，让两个矩阵非0元素在同一行同一列，忽略了“边界”数据的重要性。
　　与此同时，再次体会参考解答1的好处，缺少了一层抽象，对应的就是处处要考虑细节。智者千虑，必有一失，还是要运用上工程中的原则为好。

#include <stdio.h>
#include "tup.h"
bool MatAdd(TSMatrix a,TSMatrix b,TSMatrix &c)
{
    int i=0,j=0,k=0;
    ElemType v;
    if (a.rows!=b.rows || a.cols!=b.cols)
        return 0;        //行数或列数不等时不能进行相加运算
    c.rows=a.rows;
    c.cols=a.cols;       //c的行列数与a的相同
    while (i<a.nums && j<b.nums)         //处理a和b中的每个元素
    {
        if (a.data[i].r==b.data[j].r)    //行号相等时
        {
            if(a.data[i].c<b.data[j].c)  //a元素的列号小于b元素的列号
            {
                c.data[k].r=a.data[i].r;//将a元素添加到c中
                c.data[k].c=a.data[i].c;
                c.data[k].d=a.data[i].d;
                k++;
                i++;
            }
            else if (a.data[i].c>b.data[j].c)//a元素的列号大于b元素的列号
            {
                c.data[k].r=b.data[j].r;      //将b元素添加到c中
                c.data[k].c=b.data[j].c;
                c.data[k].d=b.data[j].d;
                k++;
                j++;
            }
            else                    //a元素的列号等于b元素的列号
            {
                v=a.data[i].d+b.data[j].d;
                if (v!=0)           //只将不为0的结果添加到c中
                {
                    c.data[k].r=a.data[i].r;
                    c.data[k].c=a.data[i].c;
                    c.data[k].d=v;
                    k++;
                }
                i++;
                j++;
            }
        }
        else if (a.data[i].r<b.data[j].r) //a元素的行号小于b元素的行号
        {
            c.data[k].r=a.data[i].r;      //将a元素添加到c中
            c.data[k].c=a.data[i].c;
            c.data[k].d=a.data[i].d;
            k++;
            i++;
        }
        else                              //a元素的行号大于b元素的行号
        {
            c.data[k].r=b.data[j].r;      //将b元素添加到c中
            c.data[k].c=b.data[j].c;
            c.data[k].d=b.data[j].d;
            k++;
            j++;
        }
        c.nums=k;
    }
    return true;
}

int main()
{
    TSMatrix ta,tb,tc;
    int A[M][N]=
    {
        {0,0,1,0,0,0,0},
        {0,2,0,0,0,0,0},
        {3,0,0,0,0,0,0},
        {0,0,0,5,0,0,0},
        {0,0,0,0,6,0,0},
        {0,0,0,0,0,7,4}
    };
    int B[M][N]=
    {
        {0,0,10,0,0,0,0},
        {0,0,0,20,0,0,0},
        {0,0,0,0,0,0,0},
        {0,0,0,50,0,0,0},
        {0,0,20,0,0,0,0},
        {0,0,0,10,0,0,4}
    };
    CreatMat(ta,A);
    CreatMat(tb,B);
    printf("A:\n");
    DispMat(ta);
    printf("B:\n");
    DispMat(tb);
    if(MatAdd(ta, tb, tc))
    {
        printf("A+B:\n");
        DispMat(tc);
    }
    else
    {
        printf("相加失败\n");
    }
    return 0;
}
时间： 2024-09-19 04:57:44

数据结构实践——稀疏矩阵相加的相关文章

数据结构实践项目——数组和广义表

本文针对 [数据结构基础系列网络课程(5):数组和广义表] 1. 数组的基本概念与存储结构 2. 特殊矩阵的压缩存储 3. 稀疏矩阵的三元组表示 4. 稀疏矩阵的十字链表表示 5. 广义表 6. 广义表的存储结构及基本运算的实现 [项目1 - 猴子选大王(数组版)] 一群猴子,编号是1,2,3 -m,这群猴子(m个)按照1-m的顺序围坐一圈.从第1只开始数,每数到第n个,该猴子就要离开此圈,这样依次下来,最后一只出圈的猴子为大王.输入m和n,输出猴子离开圈子的顺序,从中也可以看出最后为大王是几号

数据结构实践——停车场模拟(栈和队列综合)

本文是针对数据结构基础系列网络课程(3):栈和队列的实践项目. 设停车场是一个可停放n辆汽车的狭长死胡同,南边封口,汽车只能从北边进出(这样的停车场世间少有).汽车在停车场内按车辆到达时间的先后顺序,最先到达的第一辆车停放在车场的最南端,依次向北排开.若车场内已停满n辆汽车,则后来的汽车只能在门外的候车场上等候,一旦有车开走,则排在候车场上的第一辆车即可开入.当停车场内某辆车要离开时,在它之后进入的车辆必须先退出车场为它让路(假定停车场内设有供车辆进出的便道,所有的司机也必须在车内随时待命),待

数据结构实践项目——最短路径和拓扑序列

本文是针对[数据结构基础系列(7):图]的第2组实践例程. (程序中graph.h是图存储结构的"算法库"中的头文件,详情请单击链接-) 0710 生成树的概念 0711 最小生成树的普里姆算法 0712 最小生成树的克鲁斯卡尔算法 0713 从一个顶点到其余各顶点的最短路径 0714 每对顶点之间的最短路径 0715 拓扑排序 0716 AOE网与关键路径 纸上谈兵:"知原理"检验题目 1.针对下面的图1: (图1) (1)写出图的邻接矩阵: (2)按照Prim算

数据结构实践项目——排序

本文是[数据结构基础系列(9):排序]课程的实践项目. 本文针对: 1. 排序问题及导学 2. 插入排序之直接插入排序 3. 插入排序之希尔排序 4. 交换排序之冒泡排序 5. 交换排序之快速排序 6. 选择排序之直接选择排序 7. 选择排序之堆排序 8. 归并排序 9. 简单的计数排序 10. 基数排序 11. 各种排序的比较 纸上谈兵:"知原理"检验题目 1．给定序列{57, 40, 38, 11, 13, 34, 48, 75, 6, 19, 9, 7},采用下面的算法,分别描述

数据结构实践——单链表：逆置、连接与递增判断

本文针对数据结构基础系列网络课程(2):线性表的实践项目. [项目 - 单链表算法](程序中利用了已经实现的单链表算法,头文件LinkList.h及其中函数的实现见单链表算法库) 1.设计一个算法,将一个带头结点的数据域依次为a1,a2,-,an(n≥3)的单链表的所有结点逆置,即第一个结点的数据域变为an,-,最后一个结点的数据域为a1.实现这个算法,并完成测试. [参考解答] (程序中利用了已经实现的单链表算法,头文件LinkList.h及其中函数的实现见单链表算法库) #include <

数据结构例程——稀疏矩阵的十字链表表示

本文针对数据结构基础系列网络课程(5):数组与广义表中第4课时稀疏矩阵的十字链表表示. 下面的程序中,实现了创建并显示十字链表的算法. #include <stdio.h> #include <malloc.h> #define M 3 //矩阵行 #define N 3 //矩阵列 #define Max ((M)>(N)?(M):(N)) //矩阵行列较大者 typedef int ElemType; typedef struct mtxn { int row; //行号

数据结构实践项目——图的基本运算及遍历操作

本文是针对[数据结构基础系列(7):图]中第1-9课时的实践项目. 0701 图结构导学 0702 图的定义 0703 图的基本术语 0704 图的邻接矩阵存储结构及算法 0705 图的邻接表存储结构及算法 0706 图的遍历 0707 非连通图的遍历 0708 DFS的应用 0709 BFS的应用 [项目1 - 图基本算法库] 定义图的邻接矩阵和邻接表存储结构,实现其基本运算,并完成测试. 要求: 1.头文件graph.h中定义相关的数据结构并声明用于完成基本运算的函数.对应基本运算的函数包括

数据结构实践项目——查找（一）

本文是[数据结构基础系列(8):查找]课程的第一组实践项目. 本文针对: 0801 查找问题导学 0802 线性表的顺序查找 0803 线性表的折半查找 0804 索引存储结构 0805 分块查找 0806 二叉排序树 0807 二叉排序树(续) 0808 平衡二叉树 纸上谈兵:"知原理"检验题目 [参考(部分)] [参考(1)] 1.对于A[0..10]有序表{12,18,24,35,47,50,62,83,90,115,134} (1)用二分查找法查找 90时,需进行多少次查找可确

数据结构实践——猴子选大王

本文针对数据结构基础系列网络课程(2):线性表的实践项目. [项目 - 猴子选大王] 一群猴子,编号是1,2,3 -m,这群猴子(m个)按照1-m的顺序围坐一圈.从第1只开始数,每数到第n个,该猴子就要离开此圈,这样依次下来,直到圈中只剩下最后一只猴子,则该猴子为大王.输入m和n,输出为大王的猴子是几号. 提示: (1)链表解法:可以用一个循环单链表来表示这一群猴子.表示结点的结构体中有两个成员:一个保存猴子的编号,一个为指向下一个人的指针,编号为m的结点再指向编号为1的结点,以此构成环形的链.