Loading [MathJax]/jax/output/CommonHTML/config.js
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
社区首页 >问答首页 >当我将图中的节点数从4增加到大于5的任何值时,malloc得到内存损坏

当我将图中的节点数从4增加到大于5的任何值时,malloc得到内存损坏
EN

Stack Overflow用户
提问于 2019-08-22 08:36:21
回答 1查看 147关注 0票数 1

我已经写了一个简单的代码来打印给定的边的图形,我使用结构来存储图形中的数据,当节点的数量小于5但任何大于5的节点都会带来malloc错误时,它工作得很好,我不知道为什么会发生这种情况,有人能指出我做错了什么吗?

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
#include <stdio.h>
#include <stdlib.h>

// Define maximum number of vertices in the graph

#define N 5
//#define N 4 //use this when the nodes are less than 5 

// Data structure to store graph
struct Graph {
    // An array of pointers to Node to represent adjacency list
    struct Node *head[N];
};

// A data structure to store adjacency list nodes of the graph
struct Node {
    int dest;
    struct Node *next;
};

// data structure to store graph edges
struct Edge {
    int src, dest;
};

// Function to create an adjacency list from specified edges
struct Graph *createGraph(struct Edge edges[], int n) {
    unsigned i;

    // allocate memory for graph data structure
    struct Graph *graph = (struct Graph *)malloc(sizeof(struct Graph));

    // initialize head pointer for all vertices
    for (i = 0; i < n; i++)
        graph->head[i] = NULL;

    // add edges to the directed graph one by one
    for (i = 0; i < n; i++) {
        // get source and destination vertex
        int src = edges[i].src;
        int dest = edges[i].dest;

        // allocate new node of Adjacency List from src to dest
        // error occurs over here and does not move forward when the number of nodes are greater than 5
        struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
        newNode->dest = src;

        // point new node to current head
        newNode->next = graph->head[dest];

        // point head pointer to new node
        graph->head[dest] = newNode;
    }
    return graph;
}

// Function to print adjacency list representation of graph
void printGraph(struct Graph *graph) {
    int i;
    for (i = 0; i < N; i++) {
        // print current vertex and all ts neighbors
        printf("for node %d\n", i);
        struct Node *ptr = graph->head[i];
        while (ptr != NULL) {
            printf("(%d -> %d)\t", i, ptr->dest);
            ptr = ptr->next;
        }
        printf("\n");
    }
}

// Directed Graph Implementation in C
int main(void) {
    // input array containing edges of the graph (as per above diagram)
    // (x, y) pair in the array represents an edge from x to y
    // when the nodes are 5 or more use this 
    struct Edge edges[] = {
        { 3, 0 }, { 3, 1 }, { 3, 2 }, { 1, 0 },
        { 1, 2 }, { 4, 1 }, { 4, 3 }
    };

    //when the nodes are 4 use this below
    // struct Edge edges[] = {
    //     { 3, 0 }, { 3, 1 }, { 3, 2 }, { 1, 0 },
    //     { 1, 2 }
    // };

    // calculate number of edges
    int n = sizeof(edges) / sizeof(edges[0]);
    printf("%d\n",n );
    // construct graph from given edges
    struct Graph *graph = createGraph(edges, n);

    // print adjacency list representation of graph
    printGraph(graph);

    return 0;
} 

我在以下位置使用大于4的节点时遇到的错误:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));

如下所示:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
malloc(): memory corruption aborted (core dumped)
EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2019-08-22 09:09:52

在您的代码中,您在Graph中分配了一个由4个节点指针组成的数组,称为head。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
// Data structure to store graph
struct Graph {
    // An array of pointers to Node to represent adjacency list
    struct Node* head[N];
};

稍后,你会因为初始化越界而接触到不属于你的内存:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
   // initialize head pointer for all vertices
for (i = 0; i < n; i++)
    graph->head[i] = NULL;

使用valgrind:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
=16498== Invalid write of size 8
==16498==    at 0x400653: createGraph (a.c:37)
==16498==    by 0x400815: main (a.c:103)
==16498==  Address 0x52044a0 is 0 bytes after a block of size 32 alloc'd
==16498==    at 0x4C2DB8F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==16498==    by 0x40063E: createGraph (a.c:33)
==16498==    by 0x400815: main (a.c:103)
票数 5
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/57605262

复制
相关文章
MySQL -- 全表扫描
-- db1.t有200GB mysql -h$host -P$port -u$user -p$pwd -e "select * from db1.t" > $target_file 查询数据 Inn
猿哥
2019/03/19
2.9K0
MySQL -- 全表扫描
MYSQL 查询优化之路-之DISTINCT全表扫描
背景:今天对一个20w的表做关联查询,创建各种索引,没有提高执行的效率,使用EXPLAIN检查,总是提示“Using temporary”全表扫描,这不是我想的。通过度娘,各种百度,是因为DISTINCT使用了全表扫描,现在特别记录下来。以背查验。
用户5640963
2019/07/25
4.3K1
MySQL中的全表扫描案例
这两天看到了两种可能会导致全表扫描的sql,这里给大家看一下,希望可以避免踩坑:
AsiaYe
2019/11/06
2.7K0
MySQL 全表扫描成本计算
全表扫描成本作为参照物,用于和表的其它访问方式的成本做对比。任何一种访问方式,只要成本超过了全表扫描成本,就不会被使用。
csch
2022/12/20
8970
索引 vs 全表扫描
索引是数据库的重要技术,本质是用空间换时间,或者放慢写入加速查询。通常我们会将索引和全表扫描来对比,并且一般都会觉得全表扫描很 low,真的是这样吗?
Apache IoTDB
2020/09/27
1.2K0
索引 vs 全表扫描
高水位线和全表扫描
   高水位线好比水库中储水的水位线,用于描述数据库中段的扩展方式。高水位线对全表扫描方式有着至关重要的影响。当使用delete 操作 表记录时,高水位线并不会下降,随之导致的是全表扫描的实际开销并没有任何减少。本文给出高水位线的描述,如何降低高水位线,以及高水 位线对全表扫描的影响。
Leshami
2018/08/14
5140
mysql中创建表实例全析及查询基本操作
create table cats( id int not null auto_increment, pid int not null default '0', name varchar(60) not null default '', desn text not null default '', primary key(id), index name(name, pid) )engine=InnoDB default character set=utf8;
闵开慧
2018/03/30
1.5K0
MySQL 分表查询
分表是一种数据库分割技术,用于将大表拆分成多个小表,以提高数据库的性能和可管理性。在MySQL中,可以使用多种方法进行分表,例如基于范围、哈希或列表等。下面将详细介绍MySQL如何分表以及分表后如何进行数据查询。
孟斯特
2023/10/19
1.1K0
MySQL 分表查询
MySQL单表查询
3.将取出的一条条记录进行分组group by,如果没有group by,则整体作为一组
changxin7
2019/09/10
17.9K0
mysql 查询表结构
use information_schema; select * from columns where table_name='NODES';
大数据工程师-公子
2019/03/14
9.1K0
使用索引快速全扫描(Index FFS)避免全表扫描的若干场景
2. Index FFS只能通过CBO(Index hint强制使用CBO)获得。
bisal
2022/12/01
7250
MySQL跨表查询
    跨表查询适用于两个及两个以上的表中关联信息的数据,通过联系查询到表的联系!
十月梦想
2018/10/11
9.3K0
MySQL跨表查询
MySQL单表查询
MySQL之单表查询 创建表 # 创建表 mysql> create table company.employee5( id int primary key AUTO_INCREMENT not null, name varchar(30) not null, sex enum('male','female') default 'male' not null, hire_date date not null, post varchar(50) not null,
星哥玩云
2022/08/18
6.3K0
MongoDB 定位 oplog 必须全表扫描吗?
MongoDB oplog 记录数据库的所有修改操作,除了用于主备同步;oplog 还能玩出很多花样,比如
MongoDB中文社区
2019/08/20
1.6K0
MongoDB 定位 oplog 必须全表扫描吗?
MySQL之单表查询、多表查询
having的语法格式与where一致,只不过having是在分组之后进行的过滤,即where虽然不能用聚合函数,但是having可以!
py3study
2020/01/16
22K0
Mysql避免全表update
在测试的时候忘记写where条件导致全表更新的话,可以收拾包袱走人了 下面这条语句可以开启检查,当没有加where时拦截下来 set sql_safe_updates=1; 关闭: set sql_safe_updates=0;
DH镔
2019/12/20
2.7K0
mysql-单表查询
mysql> create table employee(id int primary key auto_increment,name  varchar(20) not null,sex enum('male','female') not null default 'male',age int(3) unsigned not null default 28,hire_date date not null,post varchar(50),post_comment varchar(100),salary  double(15,2),office int,depart_id int);
py3study
2018/08/03
4.3K0
MySQL子查询,联结表
子查询:嵌套在其他查询中;执行顺序由里到外。子查询数目没有限制,如果要使用多层查询,注意写好缩进格式,不要出错。
小末快跑
2019/07/03
4.5K0
mysql分表+分页查询
我们都知道,数据量大了,都要对数据库进行分库分表。奈何一直对分表及分表查询没什么概念,这里先不讲那么多概念,先直接演示一个demo。我们直接上车,请坐稳扶好。
用户10002156
2023/08/07
4820
mysql分表+分页查询
点击加载更多

相似问题

MySql - JOIN查询的全表扫描

28

MySQL全表扫描

12

禁止MySQL对查询使用全表扫描

23

Mysql子句全表扫描

12

如何避免对MySQL查询进行全表扫描

12
添加站长 进交流群

领取专属 10元无门槛券

AI混元助手 在线答疑

扫码加入开发者社群
关注 腾讯云开发者公众号

洞察 腾讯核心技术

剖析业界实践案例

扫码关注腾讯云开发者公众号
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
查看详情【社区公告】 技术创作特训营有奖征文