-
2021-11-22 21:22:05
如果理解了我上次发的关于十字链表插入函数函数的话，这个函数的说明会相对简单。
输出可以有两种方式进行输出：
（1）.第一种，按行进行输出，for循环遍历每一行，指针指向该行的第一个元素，如果指针往右走不为空的话，继续往右走，直到为空的时候，继续遍历下一行；
（2）第二种，按列进行输出，思路和第一种情况一样，for循环遍历每一列，指针指向该列的第一个元素，如果指针往下走不为空，继续往下走，直到为空的时候，继续遍历下一列。
具体看代码：
/* 8. 输出矩阵 */ void PrintSMatrix(CrossList M){ //初始条件: 稀疏矩阵M存在 int i, j; for (i = 1; i <= M.rowSum; i++) { // 从第1行到最后1行 OLink p = M.rhead[i]; // p指向该行的第1个非零元素 for (j = 1; j <= M.ColSum; j++) // 从第1列到最后1列 if (!p || p->col != j) // 已到该行表尾或当前结点的列值不等于当前列值 printf("%-5d", 0); // 输出0 else { printf("%-5d", p->elem); p = p->right; } printf("\n"); } } /* ************************************************************************** */更多相关内容 -
十字链表实现稀疏矩阵的乘法
2014-09-03 16:55:28用C++编写的稀疏矩阵乘法运算，稀疏矩阵采用十字链表存储及计算 -
十字链表实现稀疏矩阵的各种功能
2021-11-19 09:43:47十字链表实现稀疏矩阵的加法、减法、乘法、转置、求最值、插入、查看、删除等基本功能，菜单栏采用hash表存储稀疏矩阵，给每个矩阵存储一个名字，hash函数进行寻找。 -
十字链表实现稀疏矩阵，包含十二大功能
2021-11-19 09:38:15十字链表实现稀疏矩阵 1．问题描述 用十字链表存储和表示稀疏矩阵，并实现如下功能 2．基本要求 初始化：创建十字链表并从文件中读取稀疏矩阵数据（文件数据可以是三元组结构）； 在十字链表上设置坐标为（i，j...展开全文
题目：
- 十字链表实现稀疏矩阵
1．问题描述
用十字链表存储和表示稀疏矩阵，并实现如下功能
2．基本要求
- 初始化：创建十字链表并从文件中读取稀疏矩阵数据（文件数据可以是三元组结构）；
- 在十字链表上设置坐标为（i，j）的位置值为value；
- 获取坐标为（i，j）的位置的值；
- 插入一项、删除某项的值；
- 输出十字链表表示的稀疏矩阵；
- 实现两个稀疏矩阵的加法、减法、乘法的功能，结果保存到新的十字链表中；
- 实现把十字链表表示的稀疏矩阵存入文件；
- 可以用菜单选择所有功能，设计良好的操作界面；
- 在需求分析阶段完成未尽功能需求，适当扩充功能（例如矩阵转置、求最值等）。
实现：
技术难点1：uthash存储十字链表矩阵，给每个矩阵进行命名，以名字作为key，十字链表作为value,实现相对自动化的功能；（需要自己在github上找到相关资源）
技术难点2：十字链表矩阵的插入函数是整个代码的核心，需要对十字链表的存储结构比较熟悉
技术难点3：十字链表矩阵的相加函数，针对两个矩阵不同对应的情况进行相加
代码前面的声明：
#include<iostream> #include<cstdlib> #include<iomanip> #include"uthash.h" using namespace std; /* 稀疏矩阵的十字链表存储 */ typedef struct OLNode { int row; //非零元素的行下标 int col; //非零元素的列下标 int elem; //非零元素值 struct OLNode *right; //右节点 struct OLNode *down; //下节点 }OLNode, *OLink; typedef struct { OLink *rhead; //行指针链表 OLink *chead; //列指针链表 int rowSum; //矩阵的行数 int ColSum; //矩阵的列数 int NumSum; //矩阵的非零元素个数 }CrossList; /* uthash哈希表的结构体声明 */ struct HashCross{ //哈希表 char name[10]; //矩阵名称 key CrossList crosslist; //十字链表结构体 value UT_hash_handle hh; }HashCross; /* 全局hash表，存储矩阵 */ struct HashCross *cross = NULL; /* ************************************************************************** */ /* 函数声明 */ void menu(); //主菜单 void menu1(); //初始化部分 void menu2(); //基础操作部分 void menu3(); //进阶操作部分 void InitSMatrix(CrossList &M); //初始化矩阵 void CreateMatrix(CrossList &M); //创建矩阵 void PrintSMatrix(CrossList M); //输出矩阵 void InsertElem(OLink &newnode,CrossList &M); //插入元素到矩阵M中 void changeValue(CrossList &M); //寻找矩阵M中的某个值 void findValue(CrossList &M); //查找矩阵中的某个值 void deleteValue(CrossList &M); //删除矩阵中的某个值 void AddMatrix(CrossList &M,CrossList &N,CrossList &out); //两个矩阵的相加 void SubtractMatrix(CrossList &M,CrossList &N,CrossList &out); //两个矩阵的相减 void MultiplyMatrix(CrossList &M,CrossList &N,CrossList &out); //两个矩阵的相乘 void TransposeSMatrix(CrossList &M, CrossList &out); //矩阵的转置 void findMaxOrMin(CrossList &M); //矩阵求最值 void CopySMatrix(CrossList &M, CrossList &out); //复制矩阵 void ReadFromFile(CrossList &M); //从文件中读取矩阵 void WriteToFile(CrossList &M); //把矩阵写入文件 CrossList HashFind(char *name); //哈希查找函数(没有该矩阵，手动创建) CrossList HashFind2( char *name); //哈希查找函数(没有该矩阵，文件读取创建) CrossList getCrossList(); //控制台获取矩阵名称(没有该矩阵，手动创建) /* ************************************************************************** */具体每个功能的函数：
/* 实现功能的函数 */ /* 1. 主菜单 */ void menu() { int c=0; printf("--------------------------------------------------------------------------------\n"); printf("******************<-----欢迎使用十字链表存储的稀疏矩阵进行操作----->*****************\n\n"); printf("\t\t\t 1.*--<矩阵初始化>--*\n\n"); printf("\t\t\t 2.*--<矩阵基本操作（插入、删除、查找）>--*\n\n"); printf("\t\t\t 3.*--<矩阵进阶操作（四则运算、求逆、求转置、求最值等）>--*\n\n"); printf("\t\t\t 4.*--<退出本程序>--*\n\n"); printf("\n\n********************************************************************************\n"); printf("--------------------------------------------------------------------------------\n"); printf("*请输入相应功能的编号:"); do { cin >> c; if(c<1||c>4) printf("*无该选项!请重新输入:"); }while(c<1||c>4); switch(c) { case 1:menu1();break; case 2:menu2();break; case 3:menu3();break; case 4:exit(0);break; } } /* ************************************************************************** */ /* 2.初始化菜单 */ void menu1() { int c=0; while(c != 1){ printf("--------------------------------------------------------------------------------\n"); printf("******************<-----欢迎来到矩阵初始化菜单----->*****************\n\n"); printf("\t\t\t 1.*--<返回主菜单>--*\n\n"); printf("\t\t\t 2.*--<手动输入矩阵>--*\n\n"); printf("\t\t\t 3.*--<从文件中读取矩阵>--*\n\n"); printf("\t\t\t 4.*--<退出本程序>--*\n\n"); printf("\n\n********************************************************************************\n"); printf("--------------------------------------------------------------------------------\n"); printf("*请输入相应功能的编号:"); do { cin >> c; if(c<1||c>4) printf("*无该选项!请重新输入:"); }while(c<1||c>4); switch(c) { case 1: menu(); break; case 2:{ getCrossList(); break; } case 3:{ CrossList M; printf("请输入需要操作的矩阵名称:（长度小于10）\n"); char name[10]; cin >> name; M = HashFind2(name); break; } case 4:exit(0); break; } } } /* ************************************************************************** */ /* 3. 矩阵基本操作菜单 */ void menu2() { int c=0; while(c != 1){ printf("--------------------------------------------------------------------------------\n"); printf("******************<-----欢迎来到矩阵基本操作菜单----->*****************\n\n"); printf("\t\t\t 1.*--<返回主菜单>--*\n\n"); printf("\t\t\t 2.*--<查看矩阵下标的值>--*\n\n"); printf("\t\t\t 3.*--<删除矩阵下标的值>--*\n\n"); printf("\t\t\t 4.*--<增加矩阵下标的值>--*\n\n"); printf("\t\t\t 5.*--<退出本程序>--*\n\n"); printf("\n\n********************************************************************************\n"); printf("--------------------------------------------------------------------------------\n"); printf("*请输入相应功能的编号:"); do { cin >> c; if(c<1||c>5) printf("*无该选项!请重新输入:"); }while(c<1||c>5); switch(c) { case 1:menu();break; case 2:{ CrossList M; M = getCrossList(); findValue(M); break; } case 3:{ CrossList M; M = getCrossList(); deleteValue(M); break; } case 4:{ CrossList M; M = getCrossList(); changeValue(M); break; } case 5:exit(0);break; } } } /* ************************************************************************** */ /* 4. 矩阵进阶操作菜单 */ void menu3() { int c=0; while(c != 1){ printf("--------------------------------------------------------------------------------\n"); printf("******************<-----欢迎来到矩阵进阶操作菜单----->*****************\n\n"); printf("\t\t\t 1.*--<返回主菜单>--*\n\n"); printf("\t\t\t 2.*--<求稀疏矩阵的加法>--*\n\n"); printf("\t\t\t 3.*--<求稀疏矩阵的减法>--*\n\n"); printf("\t\t\t 4.*--<求稀疏矩阵的乘法>--*\n\n"); printf("\t\t\t 5.*--<求稀疏矩阵的转置>--*\n\n"); printf("\t\t\t 6.*--<输出稀疏矩阵>--*\n\n"); printf("\t\t\t 7.*--<求稀疏矩阵的最值>--*\n\n"); printf("\t\t\t 8.*--<将稀疏矩阵存入文件>--*\n\n"); printf("\t\t\t 9.*--<退出本程序>--*\n\n"); printf("\n\n********************************************************************************\n"); printf("--------------------------------------------------------------------------------\n"); printf("*请输入相应功能的编号:"); do { cin >> c; if(c<1||c>9) printf("无该选项!请重新输入:"); }while(c<1||c>9); switch(c) { case 1: menu(); break; case 2:{ CrossList M,N,out; M = getCrossList(); N = getCrossList(); AddMatrix(M,N,out); break; } case 3:{ CrossList M,N,out; M = getCrossList(); N = getCrossList(); SubtractMatrix(M,N,out); break; } case 4:{ CrossList M,N,out; M = getCrossList(); N = getCrossList(); MultiplyMatrix(M,N,out); break; } case 5:{ CrossList M,out; M = getCrossList(); TransposeSMatrix(M,out); break; } case 6:{ CrossList M; M = getCrossList(); PrintSMatrix(M); break; } case 7:{ CrossList M; M = getCrossList(); findMaxOrMin(M); break; } case 8:{ CrossList M; M = getCrossList(); WriteToFile(M); break; } case 9:exit(0);break; } } } /* ************************************************************************** */ /* 5. 初始化稀疏矩阵 */ void InitSMatrix(CrossList &M){ M.rhead = (OLink *)malloc((M.rowSum+1)*sizeof(OLink)); M.chead = (OLink *)malloc((M.ColSum+1)*sizeof(OLink)); //将所有结点赋为空值 for(int i = 1; i<=M.rowSum; i++) { M.rhead[i]=NULL; } for(int i = 1; i <= M.ColSum; i++) { M.chead[i]=NULL; } } /* ************************************************************************** */ /* 6. 创建稀疏矩阵 */ void CreateMatrix(CrossList &M){ int rowSum,ColSum,NumSum; int row, col, elem; cout << "请输入创建的稀疏矩阵的行数、列数、非0元素个数：\n" << endl; cin >> rowSum >> ColSum >> NumSum; M.rowSum = rowSum; M.ColSum = ColSum; M.NumSum = NumSum; //初始化矩阵 InitSMatrix(M); //对矩阵进行赋值 cout << "请按任意次序输入" << M.NumSum <<"个非零元的行 列 元素值:" << endl; for(int i = 1; i <= NumSum; i++){ cin >> row; cin >> col; cin >> elem; OLink newNode = (OLink)malloc(sizeof(OLNode)); newNode -> row = row; newNode -> col = col; newNode -> elem = elem; InsertElem(newNode,M); } cout << "创建成功！创建的矩阵为：\n" << endl; // printf("创建成功！创建的矩阵为：\n"); PrintSMatrix(M); } /* ************************************************************************** */ /* 7. 插入结点值 */ void InsertElem(OLink &newnode, CrossList &M){ //将非零元素结点插入矩阵中 OLink rowNode = M.rhead[newnode->row]; //行的插入 if (rowNode == NULL || rowNode -> col > newnode -> col) // 插在该行的第一个结点处 { newnode->right = rowNode; M.rhead[newnode->row] = newnode; } else { //寻找插的位置的前一个结点 for (; !(rowNode->col < newnode->col && (rowNode->right == NULL||rowNode -> right -> col > newnode->col)); rowNode = rowNode->right); newnode->right = rowNode->right; //完成行插入 rowNode->right = newnode; } //列的插入 OLink colNode = M.chead[newnode -> col]; if (colNode == NULL || colNode -> row > newnode -> row) // 插在该行的第一个结点处 { newnode->down = colNode; M.chead[newnode->col] = newnode; } else { //寻找插的位置的前一个结点 for (; !(colNode -> row < newnode->row && (colNode -> down == NULL || colNode -> down -> row > newnode->row)); colNode = colNode->down); newnode->down = colNode->down; //完成列插入 colNode->down = newnode; } } /* ************************************************************************** */ /* 8. 输出矩阵 */ void PrintSMatrix(CrossList M){ //初始条件: 稀疏矩阵M存在 int i, j; for (i = 1; i <= M.rowSum; i++) { // 从第1行到最后1行 OLink p = M.rhead[i]; // p指向该行的第1个非零元素 for (j = 1; j <= M.ColSum; j++) // 从第1列到最后1列 if (!p || p->col != j) // 已到该行表尾或当前结点的列值不等于当前列值 printf("%-5d", 0); // 输出0 else { printf("%-5d", p->elem); p = p->right; } printf("\n"); } } /* ************************************************************************** */ /* 9. 修改矩阵中某个元素的值(如果没有就增加） */ void changeValue(CrossList &M){ //如果不存在对应下标的值，则直接插入新的值 int row; int col; int elem; cout << "请输入需要修改的矩阵的行 列 元素值:\n" << endl; cin >> row >> col >> elem; OLink rowNode = M.rhead[row]; OLink newnode = (OLink)malloc(sizeof(OLNode)); newnode->row = row; newnode->col = col; newnode->elem = elem; if(rowNode == NULL || rowNode -> col > col){ //如果行链表的头结点为空或者是当前修改的结点的列值大于头结点的列值，直接插入 cout << "插入新值！\n" << endl; // printf("插入新值！\n"); InsertElem(newnode,M); } else{ OLink nextNode = rowNode; //头结点不为空，进行判断 while(nextNode){ if(nextNode -> col == col){ nextNode -> elem = elem; cout << "修改成功！\n" << endl; // printf("修改成功！\n"); break; } else if(nextNode -> col > col){ cout << "插入新值！\n" << endl; // printf("插入新值！\n"); InsertElem(newnode,M); break; } else{ nextNode = nextNode -> right; } } //头结点为空时，直接插入 if(nextNode == NULL){ cout << "插入新值！\n" << endl; // printf("插入新值！\n"); InsertElem(newnode,M); } } cout << "修改后的矩阵为:\n" << endl; // printf("修改后的矩阵为:\n"); PrintSMatrix(M); } /* ************************************************************************** */ /* 10. 查找矩阵中某个元素的值 */ void findValue(CrossList &M){ int row; int col; cout << "请输入需要查找的矩阵的对应的行 列 下标值（如：10 10）:\n" << endl; cin >> row >> col; OLink rowNode = M.rhead[row]; if(rowNode == NULL || rowNode -> col > col){ //如果行链表的头结点为空或者是当前修改的结点的列值大于头结点的列值，该元素的值为0 cout << "下标为：(" << row << "," << col << ")值elem = 0\n" << endl; } else{ OLink nextNode = rowNode; //头结点不为空，进行判断 while(nextNode){ if(nextNode -> col == col){ int val = nextNode -> elem; cout << "下标为：(" << row << "," << col << ")值elem =" << val << endl; break; } else if(nextNode -> col > col){ cout << "下标为：(" << row << "," << col << ")值elem = 0\n" << endl; break; } else{ nextNode = nextNode -> right; } } //头结点为空时，值为0 if(nextNode == NULL){ cout << "下标为：(" << row << "," << col << ")值elem = 0\n" << endl; } } } /* ************************************************************************** */ /* 11. 删除矩阵中某个元素的值 */ void deleteValue(CrossList &M){ int row; int col; cout << "请输入1需要删除的矩阵的对应的行 列 的下标值（如：10 10）:\n" << endl; scanf("%d %d", &row, &col); //行指针的删除 OLink rowNode = M.rhead[row]; if(rowNode == NULL || rowNode -> col > col){ //如果行链表的头结点为空或者是当前的结点的列值大于头结点的列值，该元素的值为0 cout << "该下标对应的值为0，无需删除\n" << endl; return; } else{ OLink p = NULL, q = NULL; p = rowNode; while(rowNode){ if(rowNode -> col == col){ if(p == rowNode){ M.rhead[row] = p -> right; } else{ q ->right = p -> right; } break; } else if(rowNode -> col > col){ return; } else{ q = p; p = p -> right; } } } //列指针的删除 OLink ColNode = M.chead[col]; if(ColNode == NULL || ColNode -> row > row){ cout << "该下标对应的值为0，无需删除\n" << endl; return; } else{ OLink p = NULL, q = NULL; p = ColNode; while(ColNode){ if(ColNode -> col == col){ if(p == ColNode){ M.chead[col] = p -> down; } else{ q -> down = p -> down; } break; } else if(ColNode -> row > row){ return; } else{ q = p; p = p -> down; } } } cout << "删除成功！\n" << endl; cout << "删除后的矩阵为：\n" << endl; PrintSMatrix(M); } /* ************************************************************************* */ /* 12. 两个矩阵相加 */ void AddMatrix(CrossList &M,CrossList &N, CrossList &out){ //判断矩阵是否满足相加条件 if(M.ColSum != N.ColSum || M.rowSum != N.rowSum){ cout << "两个矩阵不是同类型的,不能相加\n" << endl; return; } //对out矩阵进行初始化 out.ColSum = M.ColSum; out.rowSum = M.rowSum; out.NumSum = 0; InitSMatrix(out); //进行相加 for(int row = 1; row <= M.rowSum; row++){ OLink Node1 = M.rhead[row]; OLink Node2 = N.rhead[row]; for(int col = 1; col <= M.ColSum; col++){ //M,N在相同位置都有值 if(Node1 && Node1 -> col == col && Node2 && Node2 -> col == col){ // //中间变量保存 // OLink Node3 = Node1; // OLink temp = Node1 -> right; // int tmp = Node1 -> elem; // // //插入 // Node3 -> elem = Node1-> elem + Node2 -> elem; // InsertElem(Node3, out); // out.NumSum++; // // //移动指针 // Node1->elem = tmp; // Node1 = temp; // Node2 = Node2 -> right; //赋值 OLink Node3 = (OLink)malloc(sizeof(OLNode)); Node3 -> elem = Node1-> elem + Node2 -> elem; Node3 -> row = Node1 -> row; Node3 -> col = Node1 -> col; cout << Node1 -> elem; cout << Node2 -> elem; cout << Node3 -> elem << Node3 -> row << Node3 -> col << endl; //插入 InsertElem(Node3, out); out.NumSum++; //移动指针 Node1 = Node1 -> right; Node2 = Node2 -> right; } //M位置没有值，N位置有值 if((Node1==NULL||Node1->col!=col)&& Node2 && Node2->col == col) { // //中间变量保存 // OLink Node3 = Node2; // OLink temp = Node2 -> right; // // //插入 // InsertElem(Node3, out); // out.NumSum++; // // //移动指针 // Node2 = temp; //赋值 OLink Node3 = (OLink)malloc(sizeof(OLNode)); Node3 -> elem = Node2 -> elem; Node3 -> row = Node2 -> row; Node3 -> col = Node2 -> col; //插入 InsertElem(Node3,out); out.NumSum++; //移动指针 Node2 = Node2->right; } //M位置有值，N位置没有值 if(Node1 && Node1->col == col && (Node2 == NULL||Node2 ->col != col)) { // //中间变量保存 // OLink Node3 = Node1; // OLink temp = Node1 -> right; // // //插入 // InsertElem(Node3, out); // out.NumSum++; // // //移动指针 // Node1 = temp; //赋值 OLink Node3 = (OLink)malloc(sizeof(OLNode)); Node3 -> elem = Node1 -> elem; Node3 -> row = Node1 -> row; Node3 -> col = Node1 -> col; //插入 InsertElem(Node3,out); out.NumSum++; //移动指针 Node1 = Node1->right; } } } cout << "相加后的矩阵为：\n" << endl; PrintSMatrix(out); } /* ************************************************************************* */ /* 13. 两个矩阵相减 */ void SubtractMatrix(CrossList&M,CrossList &N, CrossList &out){ //判断矩阵是否满足相减 条件 if(M.ColSum != N.ColSum || M.rowSum != N.rowSum){ cout << "两个矩阵不是同类型的,不能相减 \n" << endl; return; } //对out矩阵进行初始化 out.ColSum = M.ColSum; out.rowSum = M.rowSum; out.NumSum = 0; InitSMatrix(out); //进行相减 for(int row = 1; row <= M.rowSum; row++){ OLink Node1 = M.rhead[row]; OLink Node2 = N.rhead[row]; for(int col = 1; col <= M.ColSum; col++){ //M,N在相同位置都有值 if(Node1 && Node1 -> col == col && Node2 && Node2 -> col == col){ // //中间变量保存 // OLink Node3 = Node1; // OLink temp = Node1 -> right; // // //插入 // Node3 -> elem = Node1-> elem - Node2 -> elem; // InsertElem(Node3, out); // out.NumSum++; // // //移动指针 // Node1 = temp; // Node2 = Node2 -> right; //赋值 OLink Node3 = (OLink)malloc(sizeof(OLNode)); Node3 -> elem = Node1-> elem - Node2 -> elem; Node3 -> row = Node1 -> row; Node3 -> col = Node1 -> col; //插入 InsertElem(Node3, out); out.NumSum++; //移动指针 Node1=Node1->right; Node2 = Node2 -> right; } //M位置没有值，N位置有值 if((Node1 == NULL || Node1 -> col != col) && Node2 && Node2 -> col == col) { // //中间变量保存 // OLink Node3 = Node2; // OLink temp = Node2 -> right; // // //插入 // Node3 -> elem = - Node2-> elem; // InsertElem(Node3, out); // out.NumSum++; // // //移动指针 // Node2 = temp; //赋值 OLink Node3 = (OLink)malloc(sizeof(OLNode)); Node3 -> elem = - Node2 -> elem; Node3 -> row = Node2 -> row; Node3 -> col = Node2 -> col; //插入 InsertElem(Node3,out); out.NumSum++; //移动指针 Node2 = Node2->right; } //M位置有值，N位置没有值 if(Node1 && Node1 -> col == col && (Node2 == NULL || Node2 -> col != col)) { // //中间变量保存 // OLink Node3 = Node1; // OLink temp = Node1 -> right; // // //插入 // InsertElem(Node3, out); // out.NumSum++; // // //移动指针 // Node1 = temp; //赋值 OLink Node3 = (OLink)malloc(sizeof(OLNode)); Node3 -> elem = Node1 -> elem; Node3 -> row = Node1 -> row; Node3 -> col = Node1 -> col; //插入 InsertElem(Node3,out); out.NumSum++; //移动指针 Node1 = Node1->right; } } } cout << "相减后的矩阵为：\n" << endl; PrintSMatrix(out); } /* ************************************************************************* */ /* 14. 两个矩阵相乘 */ void MultiplyMatrix(CrossList &M,CrossList &N, CrossList &out){ //判断矩阵是否满足相乘条件 if(M.ColSum != N.rowSum){ cout << "两个矩阵不满足相乘条件 \n" << endl; return; } //对out矩阵进行初始化 out.rowSum = M.rowSum; out.ColSum = N.ColSum; out.NumSum = 0; InitSMatrix(out); //进行相乘 //行列遍历 for(int row = 1; row <= out.rowSum; row++){ for(int col = 1; col <= out.ColSum; col++){ int elem = 0; OLink Node1 = M.rhead[row]; OLink Node2 = N.chead[col]; //对M的行，N的列进行遍历 for(; Node1; Node1 = Node1 -> right){ for(; Node2 && Node2 -> row <= Node1 -> col; Node2 = Node2 -> down){ if(Node2 -> row == Node1 -> col){//执行相乘 elem = elem + Node1-> elem * Node2 -> elem; break; } } } //满足条件插入矩阵 if(elem){ out.NumSum++; OLink newnode = (OLink)malloc(sizeof(OLNode)); newnode -> row = row; newnode -> col = col; newnode -> elem = elem; InsertElem(newnode, out); } } } cout << "相乘后的矩阵为：\n" << endl; PrintSMatrix(out); } /* ************************************************************************* */ /* 15. 矩阵转置 */ void TransposeSMatrix(CrossList &M, CrossList &out){ //out对M进行复制一份 CopySMatrix(M, out); //进行转置 for(int row = 1; row <= out.rowSum; row++){ OLink rowNode = out.rhead[row]; while(rowNode){ //当结点不为空时，进行指针和下标的交换 OLink nextRightNode = rowNode -> right; //下标更换 int row = rowNode -> row; rowNode -> row = rowNode -> col; rowNode -> col = row; //指针交换 OLink down = rowNode -> down; rowNode -> down = rowNode -> right; rowNode -> right = down; //对下一个进行判断 rowNode = nextRightNode; } } //进行转置后的交换 int rowSum = out.rowSum; int ColSum = out.ColSum; OLink* rhead = out.rhead; out.ColSum = rowSum; out.rowSum = ColSum; out.rhead = out.chead; out.chead = rhead; cout << "转置后的矩阵为：\n" << endl; PrintSMatrix(out); } /* ************************************************************************* */ /* 16. 矩阵求最值 */ void findMaxOrMin(CrossList &M){ int min = INT_MAX; int max = INT_MIN; //矩阵最大值 for(int i = 1; i <= M.rowSum; i++){ OLink p = M.rhead[i]; while(p != NULL){ if(max < p -> elem) max = p -> elem; p = p -> right; } } //矩阵最小值 for(int i = 1; i <= M.rowSum; i++){ OLink p = M.rhead[i]; while(p != NULL){ if(min > p -> elem) min = p -> elem; p = p -> right; } } cout << "矩阵的最大值为: \n" << max << endl; cout << "矩阵的最小值为: \n" << min << endl; } /* ************************************************************************* */ /* 17. 复制矩阵 */ void CopySMatrix(CrossList &M, CrossList &out){ //对out进行初始化 out.NumSum = M.NumSum; out.ColSum = M.ColSum; out.rowSum = M.rowSum; InitSMatrix(out); //复制 for (int row = 1; row <= M.rowSum; row++) { OLink rowNode = M.rhead[row]; while(rowNode) { OLink newnode = (OLink)malloc(sizeof(OLNode)); newnode -> row = rowNode -> row; newnode -> col = rowNode -> col; newnode -> elem = rowNode -> elem; InsertElem(newnode, out); rowNode = rowNode -> right; } } // printf("复制得到的矩阵为：\n"); // PrintSMatrix(out); } /* ************************************************************************* */ /* 18. 从文件中读取 */ void ReadFromFile(CrossList &M){ FILE* fpread; char str[100]; int count=0; int num[1000]; cout << "请输入文件名称:\n" << endl; cin >> str; fpread = fopen(str, "r"); if (fpread == NULL) { cout << "不存在该文件！\n" << endl; return ; } //读取数据 while(1) { int ch = fgetc(fpread); if(ch == EOF) break; else fscanf(fpread, "%d", &num[count++]); } fclose(fpread); //初始化矩阵并输出 M.rowSum = num[0]; M.ColSum = num[1]; M.NumSum = num[2]; InitSMatrix(M); cout << num[0] << M.ColSum << M.NumSum << endl; for(int i = 3; i < count; i+=3){ OLink newNode = (OLink)malloc(sizeof(OLNode)); newNode -> row = num[i]; newNode -> col = num[i+1]; newNode -> elem = num[i+2]; InsertElem(newNode,M); } //显示矩阵 cout << "文件中读取的矩阵为：\n" << endl; PrintSMatrix(M); } /* ************************************************************************* */ /* 19. 把矩阵写入文件 */ void WriteToFile(CrossList &M){ char str[1024]; cout << "请输入需要保存到的文件名:\n" << endl; cin >> str; FILE* fid = fopen(str, "wt"); if (fid == NULL) { cout << "文件不存在！\n" << endl; return; } //写入文件 fprintf(fid," "); fprintf(fid,"%d ",M.rowSum); fprintf(fid,"%d ",M.ColSum); fprintf(fid,"%d\n",M.NumSum); for(int i = 1; i <= M.rowSum; i++){ OLink Node = M.rhead[i]; while(Node != NULL){ fprintf(fid,"%d ",Node -> row); fprintf(fid,"%d ",Node -> col); fprintf(fid,"%d\n",Node -> elem); Node = Node -> right; } } fclose(fid); cout << "文件写入成功！\n" << endl; } /* ************************************************************************* */ /* 20. 哈希查找函数(用于手动写入矩阵) */ CrossList HashFind(char name[10]){ struct HashCross *tmp = NULL; HASH_FIND_STR(cross,name,tmp); if(tmp == NULL){ cout << "该矩阵不存在，系统已经自动为您生成该名称的矩阵\n" << endl; CrossList M; tmp = (struct HashCross *)malloc(sizeof(struct HashCross)); strcpy(tmp -> name, name); CreateMatrix(M); tmp -> crosslist = M; HASH_ADD_STR(cross,name,tmp); if(cross == NULL) cout << "hash还是空" << endl; return M; } else{ cout << "该矩阵存在！\n" << endl; return tmp -> crosslist; } } /* ************************************************************************* */ /* 21. 哈希查找函数(用于读文件写入矩阵) */ CrossList HashFind2(char name[10]){ struct HashCross *tmp = NULL; HASH_FIND_STR(cross,name,tmp); if(tmp == NULL){ cout << "该矩阵不存在，系统已经自动为您生成该名称的矩阵\n" << endl; tmp = (struct HashCross *)malloc(sizeof(struct HashCross)); strcpy(tmp -> name, name); CrossList M; ReadFromFile(M); tmp -> crosslist = M; HASH_ADD_STR(cross,name,tmp); return M; } else{ cout << "该矩阵存在！\n" << endl; return tmp -> crosslist; } } /* ************************************************************************* */ /* 21. 获取矩阵名（没有的话，自动创建矩阵） */ CrossList getCrossList(){ CrossList M; cout << "请输入需要操作的矩阵名称:（长度小于10）\n" << endl; char name[10]; cin >> name; M = HashFind(name); return M; } /* ************************************************************************* */ /* 22.主函数调用 */ int main(){ menu(); return 0; } /* ************************************************************************** */
-
十字链表实现稀疏矩阵的加法
2013-12-10 15:18:22十字链表实现稀疏矩阵的加法 -
十字链表实现稀疏矩阵系列1-----插入元素
2021-11-21 15:31:44十字链表实现稀疏矩阵系列1-----插入元素（链表的基本操作）展开全文具体功能介绍：
将一个已经申请好的结点插入到现有的十字链表中。传入的参数为一个结点的地址，和一个十字链表的地址。新的结点是已经申请好的，所以只需要找到具体的新节点的位置即可。
这里插入主要分为两大部分，一个是行的插入、一个是列的插入。行列插入基本一致，所以这里介绍一下行的插入、列的插入自行理解。
将一个结点插入新的十字链表的行头指针中，由于已经知道新节点的横坐标值，所以不需要循环，直接判断即可。插入的位置可以分为两种：
1、在该行的第一个位置直接插入，满足条件为：头结点为空，或者是新节点的纵坐标要比该行的第一个结点值要小。
if (rowNode == NULL || rowNode -> col > newnode -> col) // 插在该行的第一个结点处 { newnode->right = rowNode; M.rhead[newnode->row] = newnode; }2、不在该行的第一个位置插入，这里需要去找到正确的位置（循环不断往纵坐标大的位置靠），判断条件有两个，
第一个是如果发现当前节点的右指针已经是NULL,可以插入
第二个是当前节点的值比新节点的纵坐标要大了，可以插入
如果不满足，继续往右走
这里采用取反 可以理解为：满足插入条件（1）（2）取反
(1)、左边结点的纵坐标要比新结点纵坐标小，右边结点的纵坐标要比新节点的纵坐标大
(2)、左边结点的纵坐标要比新结点纵坐标小，右边结点的右指针已经为空（NULL）
else { //寻找插的位置的前一个结点 for (; !(rowNode->col < newnode->col && (rowNode->right == NULL||rowNode -> right -> col > newnode->col)); rowNode = rowNode->right); newnode->right = rowNode->right; //完成行插入 rowNode->right = newnode; }列的插入判断条件一样，在这里就不具体介绍了。
具体代码如下：
/* 7. 插入结点值 */ void InsertElem(OLink &newnode, CrossList &M){ //将非零元素结点插入矩阵中 OLink rowNode = M.rhead[newnode->row]; //行的插入 if (rowNode == NULL || rowNode -> col > newnode -> col) // 插在该行的第一个结点处 { newnode->right = rowNode; M.rhead[newnode->row] = newnode; } else { //寻找插的位置的前一个结点 for (; !(rowNode->col < newnode->col && (rowNode->right == NULL||rowNode -> right -> col > newnode->col)); rowNode = rowNode->right); newnode->right = rowNode->right; //完成行插入 rowNode->right = newnode; } //列的插入 OLink colNode = M.chead[newnode -> col]; if (colNode == NULL || colNode -> row > newnode -> row) // 插在该行的第一个结点处 { newnode->down = colNode; M.chead[newnode->col] = newnode; } else { //寻找插的位置的前一个结点 for (; !(colNode -> row < newnode->row && (colNode -> down == NULL || colNode -> down -> row > newnode->row)); colNode = colNode->down); newnode->down = colNode->down; //完成列插入 colNode->down = newnode; } } /* ************************************************************************** */
-
数据结构课程设计 报告 (十字链表实现稀疏矩阵的加法)
2020-12-21 21:53:36一、问题描述十字链表实现稀疏矩阵的加法1、功能要求：根据用户输入的矩阵，实现稀疏矩阵的求和运算，并输出结果。2、输入要求：矩阵的数据在程序运行的时候由用户提供，先由用户输入稀疏矩阵的行数、列数和非零元个...展开全文一、问题描述
十字链表实现稀疏矩阵的加法
1
、
功能要求：
根据用户输入的矩阵，实现稀疏矩阵的求和运算，并输出结果。
2
、
输入要求：
矩阵的数据在程序运行的时候由用户提供，
先由用户输入稀疏矩阵的行
数、列数和非零元个数。
再根据非零元个数，
输入这些非零元，还需要用户为这些非零元输
入行、列和非零元的值。这样，一个稀疏矩阵就输入完成。
若输入
4
3
2
则表示这个稀疏矩阵有
4
行
3
列
2
个非零元
然后用户需要为这两个非零元输入行、列、非零元的值
如：
1
2
2
4
1
1
表示第一个非零元行为
1
，列为
2,
，值为
2
；第二个非零元行为
4
，列为
1
，值为
1
。
此过程输入的稀疏矩阵为：
0
2
0
0
0
0
0
0
0
1
0
0
3
、
输出要求：
输出按矩阵输出，按行列依次输出，非零元则输出非零元的值，不是非
零元则输出“
0
”
。各元素之间用空格隔开。最后输出完整的矩阵。
二、概要设计
1
．稀疏矩阵的抽象数据类型定义如下：
ADT SparseMatrix {
数据对象：
D={
a
ij
|i=1,2,3
„„
m,j=1,2,3
„„
n;
a
ij
属于
ElemSet,m
和
n
分别是稀疏矩阵的行数和列数
}
数据关系：
R={ Row, Col }
Row={<
a
ij
,
a
ij+1
>|1<=i<=m,1<=j<=n-1}
Col={<
a
ij
,
a
i+1j
>|1<=i<=m-1,1<=j<=n}
基本操作：
CreateSMatrix(&M);
//
建立稀疏矩阵
M
DestroySMatrix(&M);
//
销毁稀疏矩阵
M
；
TransposeSMatrix(M);
//
求稀疏矩阵的转置矩阵
AddSMatrix(&M,&N);
//
求稀疏矩阵
M
和
N
之和
MulSMatrix(&M,&N);
-
十字链表存储稀疏矩阵
2021-11-23 10:29:03若矩阵中的元素多数为0，只有少数的元素为非0元素时，我们成该矩阵为稀疏矩阵。 我们有矩阵Aij，其中有非0元素m个，若mij≤0.05，则我们称矩阵Aij为稀疏矩阵 我们有矩阵A_{ij}，其中有非0元素m个，若\frac{m}{ij} \... -
十字链表实现稀疏矩阵
2018-05-07 10:12:05代码里row和col的意义搞反了，虽然说答案是正确的。#include <iostream> using namespace std; typedef struct Node { int row; int col; int data; Node* right; Node* down;... col... -
基于十字链表存储的稀疏矩阵的转置
2019-04-28 14:29:32实现了从字符文件读入三个正整数m, n, t以及t个三元组(i, j, e)建立稀疏矩阵的十字链表存储结构（m、n分别表示矩阵行数和列数；i, j为非零元素行号和列号）和十字链表的转置并将转置后的三元组到另一字符文件中 -
【数据结构】稀疏矩阵的链式存储（十字链表）
2022-03-13 16:57:36稀疏矩阵的十字链表表示： 十字链表中结点的结构： 创建稀疏矩阵的十字链表表示： 稀疏矩阵十字链表的查找： 稀疏矩阵的十字链表表示： 每一行的非零元素构成一个带表头的环形链表 每一列的非零元素构成一个... -
数据结构 | 十字链表完成稀疏矩阵相加
2020-12-21 21:53:33十字链表的实现当稀疏矩阵的非零元数量和位置在操作过程中变化较大时(如矩阵相加)，便不再适宜采用顺序存储，此时使用链式存储更为恰当。十字链表的实现typedef struct{int i,j;ElemType e;OLNode *right,*down;//... -
十字链表储存稀疏矩阵及矩阵相乘
2016-11-03 09:28:11在进行矩阵的加法、减法和乘法等运算时，用十字链表表示稀疏矩阵比用三元组表示更灵活，以下为结构图和代码 -
数据结构 - 十字链表之稀疏矩阵的存储
2019-02-19 14:51:33当数组中非零元素非常少时，我们可以称之为稀疏矩阵。为了减少空间的浪费，在存储稀疏矩阵的时候，我们对它进行压缩存储，即指存储非零信息。 一、数组的顺序存储 在存储稀疏矩阵的时候，除了存储非零元素的值，还... -
数据结构实验：基于十字链表的稀疏矩阵转置
2021-11-20 15:30:13基于十字链表的稀疏矩阵转置 -
十字链表稀疏矩阵相加
2018-11-11 16:48:08本课程设计主要实现在十字链表存储结构下输入稀疏矩阵，并对稀疏矩阵进行相加，操作，最后输出运算后的结果。稀疏矩阵采用十字链表表示，并在不同的存储结构下，求两个具有相同行列数的稀疏矩阵A和B的相加矩阵C，并... -
数据结构-十字链表稀疏矩阵基本操作代码实现
2022-01-08 00:46:23#include <iostream> #include <iomanip> using namespace std; typedef int ElemType;...//该十字链表结点的右指针与下指针 }OLNode,*OLink;//十字链表结点 typedef struct { OLin. -
数据结构之十字链表——稀疏矩阵的链式存储及加法运算
2021-01-16 02:33:32该楼层疑似违规已被系统折叠隐藏此楼查看此楼以下简单实现了数据结构中的十字链表(Java实现)：代码为添加(add)方法及求和(sum)方法，其它方法后续有时间再添加，最下面有测试方法CrossList交叉链表实现代码如下：... -
十字链表存储稀疏矩阵算法（乘法）
2010-04-27 16:55:51十字链表存储稀疏矩阵算法，实现两个矩阵的乘法运算 -
【swjtu】数据结构实验5_基于十字链表的稀疏矩阵转置
2021-11-12 00:58:50编写程序，从字符文件读入三个正整数m, n, t以及t个三元组(i, j, e)建立稀疏矩阵的十字链表存储结构。其中，m、n分别表示矩阵行数和列数；i, j为非零元素行号和列号。编写算法，实现矩阵转置，输出转置后的三元组到... -
基于十字链表的稀疏矩阵加法
2021-04-28 15:10:00稀疏矩阵加法（十字链表）问题描述输入输出输入输出样例代码 问题描述 若将稀疏矩阵 \mathbf{A}A 的非零元素以行序为主序的顺序存于一维数组 VV 中，并用二维数组 BB 表示 AA 中的相应元素是否为零元素（以0和1分别... -
c++十字链法实现稀疏矩阵
2021-06-17 16:51:22c++十字链法实现稀疏矩阵 -
稀疏矩阵十字链表
2015-10-05 15:19:53稀疏矩阵十字链表 -
11.十字链表 实现 稀疏矩阵 及 矩阵相加
2014-04-17 23:49:57// 十字链表 实现 稀疏矩阵 及 矩阵相加 #define OK 0 #define ERROR 1 #define OVERFLOW 1 typedef bool Status; typedef char ElemType; typedef struct OLNode//节点信息 { int i, j; struct OLNo -
稀疏矩阵十字链表存储
2012-12-26 20:45:45资源有限，请谅解。原创作品，不喜勿喷。若有类似资源，请君主动共享。 -
用十字链表实现稀疏矩阵的加法、减法以及乘法运算
2011-07-04 20:29:44用十字链表实现稀疏矩阵加法运算、稀疏矩阵减法运算、稀疏矩阵乘法运算 -
（转载）十字链表法，十字链表压缩存储稀疏矩阵详解
2021-02-25 19:05:45对于压缩存储稀疏矩阵，无论是使用三元组顺序表，还是使用行逻辑链接的顺序表，归根结底是使用数组存储稀疏矩阵。介于数组 “不利于插入和删除数据” 的特点，以上两种压缩存储方式都不适合解决类似 “向矩阵中添加... -
十字链表48稀疏矩阵的压缩存储数据结构Java语言描述.PPT
2020-12-21 21:53:29十字链表48稀疏矩阵的压缩存储数据结构Java语言描述1) 尽可能少存或不存零值元素； 解决问题的原则: 2) 尽可能减少没有实际意义的运算； 3) 操作方便。 即：能尽可能快地找到与下标值(i，j) 对应的元素，能尽可能快... -
十字链表实现稀疏矩阵相加【代码】
2016-10-30 21:28:00把p所指向的节点插入到十字链表中 119 { 120 int i,j,e; 121 OLink q,q1; 122 i=p-> i; 123 j=p-> j; 124 e=p-> e; 125 if (i< 1 ||i>M.mu||j< 1 ||j>M.nu|| 0 ==e) cout " 该元素插入错误！ ...
收藏数
3,630
精华内容
1,452