数据结构5---矩阵和广义表

一、矩阵的压缩存储

特殊矩阵:矩阵中很多值相同的元素并且它们的分布有一定的规律。

稀疏矩阵:矩阵中有很多零元素。压缩存储的基本思想是:

        (1)为多个值相同的元素只分配一个存储空间;

        (2)对零元素不分配存储空间。

1、特殊矩阵的压缩存储

（1）对称矩阵

只存储下三角部分的元素

存储结构

对于下三角的元素aij(i>=j)，在数组中的下标与i,j关系为 k = i*(i-1)/2 + j-1

上三角的元素aij(i<j),因为aij = aji，则访问它的元素aji即可,即：k = j*(j-1)/2+i - 1

 (2)三角矩阵

只存储上三角(或下三角)部分的元素

下三角矩阵

存储：

1.下三角元素        2.对角线上方的常数

矩阵中的任一元素aij在数组中的下标k与i,j的对应关系

当i>=j时        k=i*(i-1)/2+j-1

当i<j              k=n*(n+1)/2

上三角矩阵

存储：

1.上三角元素        2.对角线下方的常数

矩阵中的任一元素aij在数组中的下标k与i,j的对应关系

当i<=j时        k=(i-1)*(2n-i+2)/2+j-1

当i>j              k=n*(n+1)/2

 (3)对角矩阵

对角矩阵:所有非零元素都集中在以主对角线为中心的带状区域中，除了主对角线和它的上下方若干条对角线的元素外，所有其他元素都为零。

 (4)稀疏矩阵

 我们定义了一个三元组

struct Triple
{int row,col;    //行和列DataType item;    //值
};

三元组表:将稀疏矩阵的非零元素对应的三元组所构成的集合,按行优先的顺序排列成一个线性表。

采用顺序存储结构存储三元组表

三元顺序表的存储结构定义

const int MAX = 100;
struct SparseMatrix
{struct Triple data[MAX];    //存储非零元素int mu,nu,num;    //行数，列数，非零元素个数
};

这种存储方法的缺点是:进行矩阵加法、减法等操作时，非零元素的个数和位置都会发生变化，顺序存储法就非常不方便了。

2、十字链表

采用链接存储结构存储三元组表，每个非零元素对应的三元组存储为一个链表结点，结构为:

rowcolitem
downright

row:存储非零元素的行号

col:存储非零元素的列号

item:存储非零元素的值

right:指针域，指向同一行中的下一个三元组

down:指针域，指向同一列中的下一个三元组

定义结构体

#define ElementType inttypedef struct OLNode
{int row;//1~mint col;//1~nElementType value;struct OLNode *right, *down;//非零元素所在行，列后继链域
}OLNode, *OLink;typedef struct CrossList
{OLink* row_head, *col_head;//行，列链表的头指针向量int m;//行数int n;//列数int len;//非零元素个数
}CrossList;

代码实现

//稀疏矩阵的链式存储结构：十字链表
#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define ElementType inttypedef struct OLNode
{int row;//1~mint col;//1~nElementType value;struct OLNode *right, *down;//非零元素所在行，列后继链域
}OLNode, *OLink;typedef struct CrossList
{OLink* row_head, *col_head;//行，列链表的头指针向量int m;//行数int n;//列数int len;//非零元素个数
}CrossList;void CreatCrossList(CrossList* M, int m, int n, int len)
{M->m = m;M->n = n;M->len = len;if(!(M->row_head = (OLink*)malloc((m + 1) * sizeof(OLink)))){perror("row_head");exit(-1);}if(!(M->col_head = (OLink*)malloc((n + 1) * sizeof(OLink)))){perror("col_head");exit(-1);}memset(M->row_head, 0, (m + 1) * sizeof(OLink));memset(M->col_head, 0, (n + 1) * sizeof(OLink));//初始化为空链表int i = 0, j = 0, e = 0;//结点的行，列，值printf("请输入结点的行号,列号,值:\n");while(len){scanf("%d %d %d", &i, &j, &e);if(i < 1||i > m||j < 1||j > n){printf("行列号不合法,请重新输入:\n");continue;}int flag = 0;//检查位置是否重复for(OLNode* k = M->row_head[i]; k != NULL; k = k->right){if(k->col == j)flag = 1;}if(flag){printf("结点位置重复,请重新输入:\n");continue;}OLNode* p = (OLNode*)malloc(sizeof(OLNode));//申请结点if(p == NULL){perror("Node application");exit(-1);}p->row = i; p->col = j; p->value = e;p->right = p->down = NULL;//行链表插入if(M->row_head[i] == NULL)//该行还没有结点{M->row_head[i] = p;}else if(p->col < M->row_head[i]->col)//新建结点列号<该行首结点列号{p->right = M->row_head[i];M->row_head[i] = p;}else//寻找插入位置{OLNode* q;for(q = M->row_head[i]; q->right && q->right->col < j; q = q->right);p->right = q->right;q->right = p;}//列链表插入if(M->col_head[j] == NULL)//该列还没有结点{M->col_head[j] = p;}else if(p->row < M->col_head[j]->row)//新建结点行号<改行首节点行号{p->down = M->col_head[j];M->col_head[j] = p;}else//寻找插入位置{OLNode* q;for(q = M->col_head[j]; q->down && q->down->row < i; q = q->down)p->down = q->down;p->down = p;}len--;printf("插入成功!\n");printf("请输入结点的行号,列号,值:\n");}}void PrintCrossList(CrossList* M)//打印十字链表
{for(int row = 0; row < M->m; row++){OLNode* p = M->row_head[row];while(p != NULL){printf("(%d, %d)=%d ", p->row, p->col, p->value);p = p->right;}printf("\n");}
}int main()
{CrossList M;CreatCrossList(&M, 10, 10, 10);PrintCrossList(&M);return 0;
}

3、快速转置

在顺序结构里转置

(1)简单转置

按矩阵source的列序进行转置

算法实现

SparseMatrix source,dest;
int q = 1;
for(col=1;col<=source.nu;col++)
{for(p=1;p<=source.num;p++){if(source.data[p].col==col){dest.data[q].row = source.data[p].col;dest.data[q].col = source.data[p].row;dest.data[q].e = source.data[p].e;q++;}}}

(2)快速转置

按矩阵source的行序进行转置

方法：增加2个辅助向量

这里的cPos[col]为：1 3 5 7 8 8 9

-3一定是第一个，12一定是第三个....

cPos算法:

cPos[1] = 1;
for(col = 2;col <= source.nu; col++)
{cPos[col] = cPos[col-1]+cNum[col-1];
}

cNum算法：

for(col = 1;col <= source.nu; ++col) cNum[col]=0;    //初始化全为0
for(sPos = 1;sPos <= source.number;++sPos)++cNum[source.data[sPos].col];        //就是按列遍历整个三元组，列号为几，就在对应的cNum上++

就是找位置，找到对应位置后，其相应的cPs+1

二、广义表

1、定义

 广义表又称列表，也是一种线性存储结构，通数组类似，广义表中即可存储不可再分的元素也能存储可在分元素。

        例如：数组中可以存储‘a’、3这样的字符或数字，也能存储数组，比如二维数组、三维数组，数组都是可在分成子元素的。广义表也是如此，但与数组不同的是，在广义表中存储的数据是既可以再分也可以不再分的，形如：{1,{1,2,3}}。

    广义表记作：

LS = (a1,a2,…,an)

2、原子和子表

    广义表中存储的单个元素称为 "原子"，而存储的广义表称为 "子表"。

例如创建一个广义表 LS = {1,{1,2,3}}，我们可以这样解释此广义表的构成：广义表 LS 存储了一个原子 1 和子表 {1,2,3}。

以下是广义表存储数据的一些常用形式：

  • A = ()：A 表示一个广义表，只不过表是空的。
  • B = (e)：广义表 B 中只有一个原子 e。
  • C = (a,(b,c,d)) ：广义表 C 中有两个元素，原子 a 和子表 (b,c,d)。
  • D = (A,B,C)：广义表 D 中存有 3 个子表，分别是A、B和C。这种表示方式等同于 D = ((),(e),(b,c,d)) 。
  • E = (a,E)：广义表 E 中有两个元素，原子 a 和它本身。这是一个递归广义表，等同于：E = (a,(a,(a,…)))。


注意，A = () 和 A = (()) 是不一样的。前者是空表，而后者是包含一个子表的广义表，只不过这个子表是空表。

3、表头和表尾

当广义表不是空表时，称第一个数据（原子或子表）为"表头"，剩下的数据构成的新广义表为"表尾"。

强调一下，除非广义表为空表，否则广义表一定具有表头和表尾，且广义表的表尾一定是一个广义表。

例如在广义表中 LS={1,{1,2,3},5} 中，表头为原子 1，表尾为子表 {1,2,3} 和原子 5 构成的广义表，即 {{1,2,3},5}。

再比如，在广义表 LS = {1} 中，表头为原子 1 ，但由于广义表中无表尾元素，因此该表的表尾是一个空表，用 {} 表示。

4、广义表的存储结构

使用顺序表实现广义表结构，不仅需要操作 n 维数组（例如 {1,{2,{3,4}}} 就需要使用三维数组存储），还会造成存储空间的浪费。

typedef struct GLNode{int tag;//标志域union{char atom;//原子结点的值域struct{struct GLNode * hp,*tp;}ptr;//子表结点的指针域，hp指向表头；tp指向表尾}subNode;
}*Glist;

 这里用到了 union 共用体，因为同一时间此节点不是原子节点就是子表节点，当表示原子节点时，就使用 atom 变量；反之则使用 ptr 结构体。

Glist creatGlist(Glist C) {//广义表CC = (Glist)malloc(sizeof(Glist));C->tag = 1;//表头原子‘a’C->subNode.ptr.hp = (Glist)malloc(sizeof(Glist));C->subNode.ptr.hp->tag = 0;C->subNode.ptr.hp->subNode.atom = 'a';//表尾子表（b,c,d）,是一个整体C->subNode.ptr.tp = (Glist)malloc(sizeof(Glist));C->subNode.ptr.tp->tag = 1;C->subNode.ptr.tp->subNode.ptr.hp = (Glist)malloc(sizeof(Glist));C->subNode.ptr.tp->subNode.ptr.tp = NULL;//开始存放下一个数据元素（b,c,d）,表头为‘b’，表尾为（c,d）C->subNode.ptr.tp->subNode.ptr.hp->tag = 1;C->subNode.ptr.tp->subNode.ptr.hp->subNode.ptr.hp = (Glist)malloc(sizeof(Glist));C->subNode.ptr.tp->subNode.ptr.hp->subNode.ptr.hp->tag = 0;C->subNode.ptr.tp->subNode.ptr.hp->subNode.ptr.hp->subNode.atom = 'b';C->subNode.ptr.tp->subNode.ptr.hp->subNode.ptr.tp = (Glist)malloc(sizeof(Glist));//存放子表(c,d)，表头为c，表尾为dC->subNode.ptr.tp->subNode.ptr.hp->subNode.ptr.tp->tag = 1;C->subNode.ptr.tp->subNode.ptr.hp->subNode.ptr.tp->subNode.ptr.hp = (Glist)malloc(sizeof(Glist));C->subNode.ptr.tp->subNode.ptr.hp->subNode.ptr.tp->subNode.ptr.hp->tag = 0;C->subNode.ptr.tp->subNode.ptr.hp->subNode.ptr.tp->subNode.ptr.hp->subNode.atom = 'c';C->subNode.ptr.tp->subNode.ptr.hp->subNode.ptr.tp->subNode.ptr.tp = (Glist)malloc(sizeof(Glist));//存放表尾dC->subNode.ptr.tp->subNode.ptr.hp->subNode.ptr.tp->subNode.ptr.tp->tag = 1;C->subNode.ptr.tp->subNode.ptr.hp->subNode.ptr.tp->subNode.ptr.tp->subNode.ptr.hp = (Glist)malloc(sizeof(Glist));C->subNode.ptr.tp->subNode.ptr.hp->subNode.ptr.tp->subNode.ptr.tp->subNode.ptr.hp->tag = 0;C->subNode.ptr.tp->subNode.ptr.hp->subNode.ptr.tp->subNode.ptr.tp->subNode.ptr.hp->subNode.atom = 'd';C->subNode.ptr.tp->subNode.ptr.hp->subNode.ptr.tp->subNode.ptr.tp->subNode.ptr.tp = NULL;return C;
}

4、长度 

 广义表的长度，指的是广义表中所包含的数据元素的个数。
由于广义表中可以同时存储原子和子表两种类型的数据，因此在计算广义表的长度时规定，广义表中存储的每个原子算作一个数据，同样每个子表也只算作是一个数据。
例如，在广义表 {a,{b,c,d}} 中，它包含一个原子和一个子表，因此该广义表的长度为 2。
再比如，广义表 {{a,b,c}} 中只有一个子表 {a,b,c}，因此它的长度为 1。
前面我们用 LS={a1,a2,...,an} 来表示一个广义表，其中每个 ai 都可用来表示一个原子或子表，其实它还可以表示广义表 LS 的长度为 n。

广义表规定，空表 {} 的长度为 0。

 5、深度

由于这个不做考试内容，分享一个博客

数据结构-广义表-CSDN博客icon-default.png?t=N7T8https://blog.csdn.net/qq_51701007/article/details/126352030?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522171894059816800211521274%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=171894059816800211521274&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-126352030-null-null.142%5Ev100%5Epc_search_result_base5&utm_term=%E5%B9%BF%E4%B9%89%E8%A1%A8&spm=1018.2226.3001.4187

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/363241.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

数据库自动备份到gitee上，实现数据自动化备份

数据库自动备份到gitee上，实现数据自动化备份

本人有个不太好的习惯&#xff0c;每次项目的数据库都是在线上创建&#xff0c;Navicat 连接线上数据库进行处理&#xff0c;最近有一个项目需要二次升级&#xff0c;发现老项目部署的服务器到期了&#xff0c;完蛋&#xff0c;数据库咩了&#xff01;&#xff01;&#xff01;…
阅读更多...
从 Hadoop 迁移，无需淘汰和替换

从 Hadoop 迁移，无需淘汰和替换

我们仍然惊讶于有如此多的客户来找我们&#xff0c;希望从HDFS迁移到现代对象存储&#xff0c;如MinIO。我们现在以为每个人都已经完成了过渡&#xff0c;但每周&#xff0c;我们都会与一个决定进行过渡的主要、高技术性组织交谈。 很多时候&#xff0c;在这些讨论中&#xff…
阅读更多...
游戏AI的创造思路-技术基础-深度学习（5）

游戏AI的创造思路-技术基础-深度学习（5）

继续深度学习技术的探讨&#xff0c;填坑不断&#xff0c;头秃不断~~~~~ 目录 3.5. 自编码器&#xff08;AE&#xff09; 3.5.1. 定义 3.5.2. 形成过程 3.5.3. 运行原理 3.5.3.1.运行原理及基本框架 3.5.3.2. 示例代码 3.5.4. 优缺点 3.5.5. 存在的问题和解决方法 3.5…
阅读更多...
开源模型应用落地-FastAPI-助力模型交互-WebSocket篇（三）

开源模型应用落地-FastAPI-助力模型交互-WebSocket篇（三）

一、前言 使用 FastAPI 可以帮助我们更简单高效地部署 AI 交互业务。FastAPI 提供了快速构建 API 的能力,开发者可以轻松地定义模型需要的输入和输出格式,并编写好相应的业务逻辑。 FastAPI 的异步高性能架构,可以有效支持大量并发的预测请求,为用户提供流畅的交互体验。此外,F…
阅读更多...
鸿蒙开发 之 健康App案例

鸿蒙开发 之 健康App案例

1.项目介绍 该项目是记录用户日常饮食情况&#xff0c;以及针对不同食物摄入营养不同会有对应的营养摄入情况和日常运动消耗情况&#xff0c;用户可以自己添加食品以及对应的热量。 1.1登陆页 1.2饮食统计页 1.3 食物列表页 2.登陆页 2.1自定义弹框 import preferences from oh…
阅读更多...
使用自定义的shiro密码匹配器CredentialsMatcher完成密码验证

使用自定义的shiro密码匹配器CredentialsMatcher完成密码验证

今天突然想研究一下shiro怎么匹配用户的密码。 我们使用shiro的API登录时&#xff0c;会先创建一个令牌对象&#xff0c;而经常用的令牌对象是UsernamePasswordToken&#xff0c;把用户输入的用户名和密码作为参数构建一个UsernamePasswordToken&#xff0c;然后通过Subject.l…
阅读更多...
十二、Yocto集成ROS2 app程序(package)

十二、Yocto集成ROS2 app程序(package)

文章目录 Yocto集成ROS2 app程序1. 添加一个ros2 package应用程序2. 添加bb文件集成app应用程序 Yocto集成ROS2 app程序 本篇文章为基于raspberrypi 4B单板的yocto实战系列的第十二篇文章&#xff1a; 一、yocto 编译raspberrypi 4B并启动 二、yocto 集成ros2(基于raspberrypi…
阅读更多...
stable diffusion 模型和lora融合

stable diffusion 模型和lora融合

炜哥的AI学习笔记——SuperMerger插件学习 - 哔哩哔哩接下来学习的插件名字叫做 SuperMerger，它的作用正如其名，可以融合大模型或者 LoRA，一般来说会结合之前的插件 LoRA Block Weight 使用，在调整完成 LoRA 模型的权重后使用改插件进行重新打包。除了 LoRA ，Checkpoint 也…
阅读更多...
Kafka入门到精通(三)-Kafka

Kafka入门到精通(三)-Kafka

Kafka简介 Kafka是由Apache软件基金会开发的一个开源流处理平台&#xff0c;由Scala和Java编写。Kafka是一种高吞吐量的分布式发布订阅消息系统&#xff0c;它可以处理消费者在网站中的所有动作流数据。 这种动作&#xff08;网页浏览&#xff0c;搜索和其他用户的行动&#xf…
阅读更多...
pgsql的套接字文件不存在

pgsql的套接字文件不存在

问题&#xff1a;psql: error: connection to server on socket "/tmp/.s.PGSQL.5432" failed: No such file or directory 解决方式&#xff1a; 检查 postgresql.conf 文件中的 unix_socket_directories 设置&#xff0c;确保它包含 /tmp 或者你期望的目录。 重…
阅读更多...
文本分析|小白教程

文本分析|小白教程

在信息爆炸的时代&#xff0c;文本数据无处不在&#xff0c;如何从这些海量的文字中提炼出有价值的信息呢&#xff1f;答案就是——文本分析。文本分析&#xff0c;简单来说&#xff0c;就是对文本数据进行深度的研究和分析。它能够从看似普通的文字中&#xff0c;提取出主题、…
阅读更多...
sheng的学习笔记-AI-高斯混合模型（GMM)

sheng的学习笔记-AI-高斯混合模型（GMM)

AI目录&#xff1a;sheng的学习笔记-AI目录-CSDN博客 需要学习前置知识&#xff1a; 聚类&#xff0c;可参考 sheng的学习笔记-AI-聚类(Clustering)-CSDN博客 EM算法&#xff0c;可参考 sheng的学习笔记-AI-EM算法-CSDN博客 贝叶斯&#xff0c;可参考 sheng的学习笔记-AI-…
阅读更多...
关于使用绿联 USB-A转RJ45 2.5G网卡提速的解决问题

关于使用绿联 USB-A转RJ45 2.5G网卡提速的解决问题

问题 网络下载速率低 网线是七类网线&#xff0c;外接的USB网卡驱动 我的自带网卡是 I219v 在嵌入了2.5G网络后一直无法到达1.5G以上。 平均测速300~500M 解决方案 更新了USB的网卡驱动 禁用了 I219-V的驱动。测速即可 USB驱动下载地址 https://download.csdn.net/downlo…
阅读更多...
分销裂变实战：PLG模式如何助力企业突破增长瓶颈

分销裂变实战：PLG模式如何助力企业突破增长瓶颈

在竞争激烈的商业环境中&#xff0c;企业如何快速、有效地实现增长&#xff0c;一直是业界关注的焦点。近年来&#xff0c;分销裂变作为一种新兴的商业模式&#xff0c;凭借其独特的优势&#xff0c;逐渐受到企业的青睐。而产品驱动增长&#xff08;PLG&#xff09;模式更是为分…
阅读更多...
JAVA：Word2Vec的使用

JAVA：Word2Vec的使用

1、简介 Word2Vec是 Google 在 2013 年年中开源的一款将词表征为实数值向量的高效工具, 其利用深度学习的思想&#xff0c;可以通过训练&#xff0c;把对文本内容的处理简化为 K 维向量空间中的向量运算&#xff0c;而向量空间上的相似度可以用来表示文本语义上的相似度。 Wo…
阅读更多...
Maven deploy上传远程私服失败

Maven deploy上传远程私服失败

Failed to execute goal org.apache.maven.plugins:maven-deploy-plugin:2.8.2:deploy (default-deploy) on project 你的项目: Cannot deploy artifacts when Maven is in offline mode 解决方案&#xff1a; 1.IDEA把这个钩子去掉 2. settings.xml里把 <offline>标…
阅读更多...
聊聊啥项目适合做自动化测试

聊聊啥项目适合做自动化测试

作为测试从业者&#xff0c;你是否遇到过这样的场景&#xff0c;某天公司大Boss找你谈话。 老板&#xff1a;小李&#xff0c;最近工作辛苦了 小李&#xff1a;常感谢您的认可&#xff0c;这不仅是对我个人的鼓励&#xff0c;更是对我们整个团队努力的认可。我们的成果离不开每…
阅读更多...
填完高考志愿后，每天必须要做的三件事！

填完高考志愿后，每天必须要做的三件事！

填完志愿后是等录取通知书吗&#xff1f;错&#xff0c;大错特错&#xff0c;今天老师特别提醒大家&#xff0c;每天要做的3件事非常重要&#xff0c;一定要点赞收藏起来。 第一&#xff0c;每天早上9点登录你们省教育考试院的官网&#xff0c;凭个人的账号和密码查看招生考试…
阅读更多...
PTA—C语言期末复习（选择题）

PTA—C语言期末复习（选择题）

1. 按照标识符的要求&#xff0c;&#xff08;A&#xff09;不能组成标识符。 A.连接符 B.下划线 C.大小写字母 D.数字字符 在大多数编程语言中&#xff0c;标识符通常由字母&#xff08;包括大写和小写&#xff09;、数字和下划线组成&#xff0c;但不能以数字开头&#xff0c…
阅读更多...
[数据集][目标检测]棉花叶子害虫检测数据集VOC+YOLO格式595张1类别

[数据集][目标检测]棉花叶子害虫检测数据集VOC+YOLO格式595张1类别

数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径的txt文件&#xff0c;仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)&#xff1a;595 标注数量(xml文件个数)&#xff1a;595 标注数量(txt文件个数)&#xff1a;595 标注类别…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023