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

简介: 本文针对数据结构基础系列网络课程(5):数组与广义表的实践项目。【项目 - 稀疏矩阵相加】   采用三元组存储稀疏矩阵,设计两个稀疏矩阵相加的运算算法 提示1:两个行数、列数相同的矩阵可以相加 提示2:充分利用已经建立好的算法库解决问题[参考解答1](程序中使用的头文件”tup.h”见稀疏矩阵的三元组表示算法库) #include <stdio.

本文针对数据结构基础系列网络课程(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;
}
目录
相关文章
|
1月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
141 77
|
1月前
|
存储 C++
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
【数据结构——树】哈夫曼树(头歌实践教学平台习题)【合集】目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:任务描述 本关任务:编写一个程序构建哈夫曼树和生成哈夫曼编码。 相关知识 为了完成本关任务,你需要掌握: 1.如何构建哈夫曼树, 2.如何生成哈夫曼编码。 测试说明 平台会对你编写的代码进行测试: 测试输入: 1192677541518462450242195190181174157138124123 (用户分别输入所列单词的频度) 预
58 14
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
|
1月前
|
存储 C++ 索引
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
42 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
|
1月前
|
算法 C++
【C++数据结构——查找】二叉排序树(头歌实践教学平台习题)【合集】
【数据结构——查找】二叉排序树(头歌实践教学平台习题)【合集】 目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果: 任务描述 本关任务:实现二叉排序树的基本算法。 相关知识 为了完成本关任务,你需要掌握:二叉树的创建、查找和删除算法。具体如下: (1)由关键字序列(4,9,0,1,8,6,3,5,2,7)创建一棵二叉排序树bt并以括号表示法输出。 (2)判断bt是否为一棵二叉排序树。 (3)采用递归方法查找关键字为6的结点,并输出其查找路径。 (4)分别删除bt中关键
51 11
【C++数据结构——查找】二叉排序树(头歌实践教学平台习题)【合集】
|
1月前
|
Java C++
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
47 12
|
1月前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
43 10
|
1月前
|
算法 C++
【C++数据结构——图】最小生成树(头歌实践教学平台习题) 【合集】
【数据结构——图】最小生成树(头歌实践教学平台习题)目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:【合集】任务描述 本关任务:编写一个程序求图的最小生成树。相关知识 为了完成本关任务,你需要掌握:1.建立邻接矩阵,2.Prim算法。建立邻接矩阵 上述带权无向图对应的二维数组,根据它建立邻接矩阵,如图1建立下列邻接矩阵。注意:INF表示无穷大,表示整数:32767 intA[MAXV][MAXV];Prim算法 普里姆(Prim)算法是一种构造性算法,从候选边中挑
43 10
|
1月前
|
存储 算法 C++
【C++数据结构——图】图的邻接矩阵和邻接表的存储(头歌实践教学平台习题)【合集】
本任务要求编写程序实现图的邻接矩阵和邻接表的存储。需掌握带权有向图、图的邻接矩阵及邻接表的概念。邻接矩阵用于表示顶点间的连接关系,邻接表则通过链表结构存储图信息。测试输入为图的顶点数、边数及邻接矩阵,预期输出为Prim算法求解结果。通关代码提供了完整的C++实现,包括输入、构建和打印邻接矩阵与邻接表的功能。
46 10
|
1月前
|
存储 算法 C++
【C++数据结构——查找】顺序查找(头歌实践教学平台习题)【合集】
若查找的关键字k=5,则SeqSearch函数输出是3,6,2,10,1,8,5,并返回值7。若查找的关键字为k=15,则函数输出是3,6,2,10,1,8,5,7,4,9,并返回值0。假设顺序表中R的关键字依次是3,6,2,10,1,8,5,7,4,9,(第一行是输入的一组原始关键字数据,第二行是要查找的关键字)顺序查找算法中要依次输出与k所比较的关键字,用空格分隔开。本关任务:实现顺序查找的算法。开始你的任务吧,祝你成功!
35 8
|
1月前
|
C++
【C++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
37 7

热门文章

最新文章