问题遇到的现象和发生背景
目前就是先解决相加问题
进阶问题 然后就是如果数据倒过来输入的话创建链表会乱,解决输入顺序对创建链表的影响(顺序不对对矩阵相加好像也有影响)
问题相关代码,请勿粘贴截图
//稀疏矩阵相加
#include"stdio.h"
#include"stdlib.h"
#define MAX 100
typedef struct OLNode
{
int row, col; //非零元素的行号和列号
int v; //非零元素的值
struct OLNode* right, * down; //非零元素所在行和列的后继链域
}OLNode, * OLink;
typedef struct
{
OLNode* rhead[MAX], * chead[MAX]; //行、列链表的头指针向量
int m, n, t; //稀疏矩阵的行数、列数和非零元素个数
}CrossList;
//建立十字链表
void CreateCrossList(CrossList* M)
{
int m, n, t, i, r, c, v;
OLNode* p, * q;
printf("请输入矩阵行数、列数和非零元素个数:");
scanf_s("%d%d%d", &m, &n, &t);
M->m = m;
M->n = n;
M->t = t;
for (i = 1; i <= m; i++)
M->rhead[i] = NULL;
for (i = 1; i <= n; i++)
M->chead[i] = NULL;
for (i = 1; i <= t; i++)
{
printf("输入第%d个非零元素的行号、列号和值:", i);
scanf_s("%d%d%d", &r, &c, &v);
p = (OLNode*)malloc((m + 1) * sizeof(OLNode));//这里我觉得可以改成p=(OLNode*)malloc(sizeof(OLNode));
p->row = r; //为新的十字链表结点赋值
p->col = c;
p->v = v;
p->right = NULL;
p->down = NULL;
if (M->rhead[r] == NULL) //行链表的头指针为空
M->rhead[r] = p; //行链表的头指针指向新的结点
else
{
for (q = M->rhead[r]; q && q->col < c; q = q->right)//这里行数据超过三个以上顺序会颠倒
{//将新结点插入行链表
p->right = q->right;
q->right = p;
}
}
if (M->chead[c] == NULL)
M->chead[c] = p;
else
{
for (q = M->chead[c]; q && q->row < r; q = q->down)
{//将新结点插入列链表
p->down = q->down;
q->down = p;
}
}
}
}
//输出十字链表表示的矩阵
void ShowMatrix(CrossList* M)
{
int i, j;
OLNode* p;
int t = 1;
for (i = 1; i <= M->m; i++) //从第一行开始逐行输出
{
p = M->rhead[i];
if (M->rhead[i]) //该行有非零元素
for (j = 1; j <= M->n; j++) //输出所以非零元素
if (p->col == j)
{
printf("%d ", p->v);
if (p->right)
p = p->right;
}
else
printf("0 "); //其他位置输出0
else //该行无非零元素,则输出0
{
for (j = 1; j <= M->n; j++)
printf("0 ");
}
printf("\n");
}
}
//找到非零元素在列链表中的前驱结点
OLNode* colpred(int r, int c, CrossList* M)
{
OLNode* s;
s = M->chead[c];
while (s->down != NULL && s->down->row < r)
s = s->down;
return s;
}
//十字链表表示的结点相加
void AddMatrix(CrossList* M1, CrossList* M2, CrossList* M)
{
OLNode* p, * q, * ra, * rb, * pa, * pb, * qa;
int i, j;
if (M1->m != M2->m || M1->n != M2->n)
printf("两矩阵不能相加!\n");
else
{//使结果矩阵M的列链表的头指针指向矩阵M1的列链表
for (j = 1; j < M1->n; j++)
M->chead[j] = M1->chead[j];
M->m = M1->m;
M->n = M2->n;
for (i = 1; i <= M1->m; i++) //从第一行开始逐行扫描
{
ra = M1->rhead[i]; //ra和rb分别指向两矩阵当前行中的第一个非零元素
rb = M2->rhead[i];
pa = ra; //pa和pb指向两矩阵当前行中的结点
pb = ra;
qa = NULL;
if (M2->rhead[i] == NULL) //M2中的当前行无非零元素
M->rhead[i] = M1->rhead[i]; //M中该行的头指针指向M1中的该行
while (pb) //pb非空时执行循环
{
if (pa && pa->col < pb->col)
{//如果pa非空且M1中非零元素列号小于M2中非零元素列号,将M1中非零元素直接加入M
if (qa == NULL)
M->rhead[i] = pa;
qa = pa;
pa = pa->right;
}
else
if (!pa || pa->col > pb->col)
{//如果pa为空或者M1中非零元素列号大于M2中非零元素列号,将M2中非零元素插入M
p = (OLNode*)malloc(sizeof(OLNode));
*p = *pb; //将pb所指结点的value值赋给p
if (qa == NULL)
M->rhead[i] = p; //p为该行第一个非零元素
else
qa->right = p; //在行链表中插入p
p->right = pa;
qa = p;
if (M->chead[pb->col] == NULL || M->chead[pb->col]->row > p->row)
{//p为该列非零元素,或者在该列行号最小
M->chead[pb->col] = p;
p->down = NULL;
}
else
{//在列链表中插入p
q = colpred(p->row, p->col, M);
p->down = q->down;
q->down = p;
}
pb = pb->right; //指向M2中本行下一个非零元素
}
else
{
pa->v += pb->v; //pb的值加到pa上
if (pa->v == 0)
{
if (qa == NULL)
M->rhead[i] = pa->right;
else //在行链表上删除该结点
qa->right = pa->right;
if (M->chead[pb->col] == pa)
M->chead[pb->col] = pa->down;
else //在列链表上删除该结点
{
q = colpred(pa->row, pa->col, M);
q->down = pa->down;
free(pa);
}
}
else
{
if (qa == NULL)
M->rhead[i] = pa;
qa = pa;
}
pa = pa->right; //指向M1中下一个非零元素
pb = pb->right; //指向M2中下一个非零元素
}
}
}
}
}
void main()
{
CrossList A, B, C;
CreateCrossList(&A); //创建矩阵A的十字链表
printf("第一个矩阵为:\n");
ShowMatrix(&A); //输出矩阵A
CreateCrossList(&B); //创建矩阵B的十字链表
printf("第二个矩阵为:\n");
ShowMatrix(&B); //输出矩阵B
AddMatrix(&A, &B, &C); //计算C=A+B
printf("相加结果为:\n");
ShowMatrix(&C); //输出结果矩阵C
}
运行结果及报错内容
我的解答思路和尝试过的方法
输出行链表代码,检测时用的
void P(CrossList* M)
{
OLNode* p;
int i;
printf("行链表\n");
for (i = 1; i <= M->m; i++)
{
for (p = M->rhead[i]; p; p = p->right)
printf("%d ", p->v);
printf("\n");
}
}
第二个数据开始倒序输入了
画的草图(有点丑)