5.3稀疏矩阵的十字链表存储
发布日期:2021-06-30 10:49:13
浏览次数:2
分类:技术文章
本文共 2108 字,大约阅读时间需要 7 分钟。
十字链表产生原因:当矩阵的非零元个数和位置在操作过程中变化较大时,就不宜采用顺序存储结构来表示三元组的线性表。
十字链表特点:
每一个非零元开用含5个域的结点表示,其中i、j和e这3个域分别表示该非零元所在行、列和非零元的值,向右域用以链接同一行中下一个非零元,向下域down用以链接用列中的下一个非零元。
如下稀疏矩阵的十字链表表
下面这图是M的非零元:
下面是稀疏矩阵的十字链表存储
下面是代码(此代码和书上不同,书上的有几个地方错误,下面的代码是修改后的代码)
typedef struct{ int i, j; //该非零元的行和列下标 ElemType e; struct OLNode *right, *down;}OLNode,*OLink;typedef struct{ OLink rhead, chead; //行和列链表头指针向量基址由CreateSMatrix分配 int mu, nu, tu; //稀疏矩阵的行数、列数和非零元个数}CrossList;下面是创建稀疏矩阵M,采用十字链表存储
算法5.4:
代码如下:
Status CreateSMatrix_OL(CrossList &M) { // 创建稀疏矩阵M。采用十字链表存储表示。 // if (M) free(M); // scanf(&m, &n, &t ); // 输入M的行数、列数和非零元个数 OLNode *p, *q; int i, j, e; int m = random(4, 6), n = random(4, 6), t = random(4, 5); M.mu = m; M.nu = n; M.tu = t; if (!(M.rhead = (OLink *)malloc((m + 1)*sizeof(OLink)))) return ERROR; if (!(M.chead = (OLink *)malloc((n + 1)*sizeof(OLink)))) return ERROR; for (int a = 1; a <= m; a++) // 初始化行列头指针向量;各行列链表为空链表 M.rhead[a] = NULL; for (int b = 1; b <= n; b++) M.chead[b] = NULL; for (int c = 1; c <= t; c++) { // 按任意次序输入非零元 scanf(&i, &j, &e); if (!(p = (OLNode *)malloc(sizeof(OLNode)))) return ERROR; p->i = i; p->j = j; p->e = e; p->down = NULL; p->right = NULL; // 新结点 if (M.rhead[i] == NULL || M.rhead[i]->j > j) { p->right = M.rhead[i]; M.rhead[i] = p; } else { // 寻查在行表中的插入位置 for (q = M.rhead[i]; (q->right) && (q->right->j下面来分析下这个代码:right); p->right = q->right; q->right = p; } // 完成行插入 if (M.chead[j] == NULL || M.chead[j]->i > i) { p->down = M.chead[j]; M.chead[j] = p; } else { // 寻查在列表中的插入位置 for (q = M.chead[j]; (q->down) && q->down->i < i; q = q->down); p->down = q->down; q->down = p; } // 完成列插入 } // for return OK;} // CreateSMatrix_OL
此代码最好的理解方法是结合上面的那个图5.6。
那么现在就带大家了解下这个函数的思路,这个函数调用了random这是产生随机数,在stdlib.h中,它把行和列和非零元随机化,然后行和列链表,开辟空间,这里要注意的是,行指针开辟的个数是和列有关,列指针开辟的个数和行有关,大家在那两个if语句中就能明显的看到。
随后紧跟的那两个for循环是对链表的初始化为NULL。
接下来是参数了输入非零元,这里的思路其实就是把非零元结构体初始化了后看看他应该插到什么位置,举个例子,大家看图5.6,第一行,第一列,值为3,那个非零元,就是把M.chead[1]->down指向了他,M.rhead[1]->right指向了它,如果是第三行,第一列,值为2的那个呢?就要把,第一行,第一列,值为3的非零元的down指向他,下面那个for循环就是这个思路。
转载地址:https://it1995.blog.csdn.net/article/details/54980946 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
不错!
[***.144.177.141]2024年04月07日 04时51分26秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
DbUtil异步更新AsyncQueryRunner
2019-04-30
java判断中文汉字工具类
2019-04-30
DbUtils里的ResultSetHandler处理器应用
2019-04-30
Apache WEB服务器启用了OPTIONS方法
2019-04-30
配置文件中的数据库密码加密
2019-04-30
tailf报错limit of inotify watches was reached
2019-04-30
Solr控制台索引维护-删除索引
2019-04-30
ping结果的相关知识点,tracert命令验证
2019-04-30
ARP欺骗原理与模拟
2019-04-30
网络运维相关知识点
2019-04-30
GNS3软件简介
2019-04-30
csdn搜索博主的文章
2019-04-30
ORA-12552: TNS:operation was interrupted
2021-07-03
MyISAM表修复
2019-04-30
GNS3中关联使用SecureCRT
2019-04-30
oracle日期的相关有用统计SQL
2019-04-30
oracle数据库LOB管理
2019-04-30
oracle数据库BFILE的应用demo
2019-04-30
Oracle数据库自定义类型--对象类型
2019-04-30