我有一个自定义结构
typedef struct node
{
struct node *next;
int vertex;
}node;
typedef struct {
int numberOfNodes;
int *visited;
int numberOfEdges ;
node **ppLists;
} adjacencyList;
我正在尝试使用带有numberOfNodes为1000的以下代码为邻接列表分配内存。
adjacencyList *createAdjList(int numberOfNodes)
{
int i;
adjacencyList *newList;
//Allocate memory for list and the array of nodes
newList=(adjacencyList *)malloc(sizeof(adjacencyList));
newList->numberOfNodes=numberOfNodes;
newList->ppLists=(node**)malloc(numberOfNodes*sizeof(node));
for (i = 0; i < newList->numberOfNodes; i++) {
newList->ppLists[i] = (node*)malloc(sizeof(node)*newList->numberOfNodes);
}
return newList;
}
该代码可以成功执行，但是在运行时出现了段错误。我使用了gdb，这是追溯信息。
#0 0x00007ffff7a51425 in __GI_raise (sig=<optimized out>) at ../nptl/sysdeps/unix/sysv/linux/raise.c:64
#1 0x00007ffff7a54b8b in __GI_abort () at abort.c:91
#2 0x00007ffff7a9915d in __malloc_assert (assertion=<optimized out>, file=<optimized out>, line=<optimized out>, function=<optimized out>) at malloc.c:300
#3 0x00007ffff7a9c674 in sYSMALLOc (av=0x7ffff7dd3720, nb=16016) at malloc.c:2448
#4 _int_malloc (av=0x7ffff7dd3720, bytes=16000) at malloc.c:3903
#5 0x00007ffff7a9dfc5 in __GI___libc_malloc (bytes=16000) at malloc.c:2924
#6 0x0000000000401c08 in createAdjList (numberOfNodes=1000) at /home/merlyn/projects/soft/AdjacencyList.c:25
#7 0x0000000000401155 in createAdjListFromMatrix (pAdjMatrix=0x605010) at /home/merlyn/projects/soft/tools.c:86
#8 0x0000000000401017 in main (argc=2, argv=0x7fffffffdf18) at /home/merlyn/projects/soft/main.c:22
瓦尔格朗德
==6328== Memcheck, a memory error detector
==6328== Copyright (C) 2002-2011, and GNU GPL'd, by Julian Seward et al.
==6328== Using Valgrind-3.7.0 and LibVEX; rerun with -h for copyright info
==6328== Command: ./exercise
==6328==
==6328== Invalid write of size 4
==6328== at 0x4E8892D: _IO_vfscanf (vfscanf.c:1857)
==6328== by 0x4E903EA: __isoc99_fscanf (isoc99_fscanf.c:35)
==6328== by 0x401A15: readAdjMatrixFromFile (AdjacencyMatrix.c:138)
==6328== by 0x400FF5: main (main.c:14)
==6328== Address 0x51f3675 is 997 bytes inside a block of size 1,000 alloc'd
==6328== at 0x4C2B6CD: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==6328== by 0x4019AA: readAdjMatrixFromFile (AdjacencyMatrix.c:126)
==6328== by 0x400FF5: main (main.c:14)
==6328==
1000
==6328== Conditional jump or move depends on uninitialised value(s)
==6328== at 0x401D68: addEdgeToAdjList (AdjacencyList.c:75)
==6328== by 0x4011A5: createAdjListFromMatrix (tools.c:77)
==6328== by 0x401016: main (main.c:22)
==6328==
==6328==
==6328== HEAP SUMMARY:
==6328== in use at exit: 17,098,448 bytes in 7,154 blocks
==6328== total heap usage: 7,156 allocs, 2 frees, 17,099,584 bytes allocated
==6328==
==6328== LEAK SUMMARY:
==6328== definitely lost: 48 bytes in 2 blocks
==6328== indirectly lost: 17,098,400 bytes in 7,152 blocks
==6328== possibly lost: 0 bytes in 0 blocks
==6328== still reachable: 0 bytes in 0 blocks
==6328== suppressed: 0 bytes in 0 blocks
==6328== Rerun with --leak-check=full to see details of leaked memory
==6328==
==6328== For counts of detected and suppressed errors, rerun with: -v
==6328== Use --track-origins=yes to see where uninitialised values come from
==6328== ERROR SUMMARY: 3994 errors from 2 contexts (suppressed: 2 from 2
主.c
#include "AdjacencyList.h"
#include "AdjacencyMatrix.h"
#include "tools.h"
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char* argv[])
{
// load the matrix
adjacencyMatrix *newAdjMatrix=readAdjMatrixFromFile(argv[1]) ;
// A test to check if the matrix has actually been loaded
writeAdjMatrixToFile(newAdjMatrix, "123.txt");
// covert matrix to list
adjacencyList *newAdjList = createAdjListFromMatrix(newAdjMatrix);
// perform reachablity for matrix
//checkReachabilityMatrix(newAdjMatrix,0) ;
// perform reachability for list
return 0;
}
adjacencyMatrix *readAdjMatrixFromFile(char *pFilename)
{
adjacencyMatrix *newAdjMatrix;
newAdjMatrix = (adjacencyMatrix *) malloc(sizeof(adjacencyMatrix));
FILE *pFile;
pFile = fopen("/home/merlyn/projects/soft/Graph.txt", "r");
char ch;
if(pFile==NULL)
{
printf("Cannot open File");
}
//First Character will have number of nodes
int i,j;
//fgetc(
fscanf(pFile, "%d",&i);
//newAdjMatrix->numberOfNodes=((int)fgetc(pFile));
newAdjMatrix->numberOfNodes = i;
newAdjMatrix->ppMatrix = (bool**) malloc(sizeof(bool*)*newAdjMatrix->numberOfNodes);
int idx;
for (idx = 0; idx < newAdjMatrix->numberOfNodes; idx++)
newAdjMatrix->ppMatrix[idx] = (bool*) malloc(sizeof(bool)*newAdjMatrix->numberOfNodes);
i=0;//rows
j=0;//columns
//iterate over entire file
for(i=0;i<newAdjMatrix->numberOfNodes;i++)
{
for(j=0;j<newAdjMatrix->numberOfNodes;j++)
//keep adding elements to the column for ith row
fscanf(pFile, "%d",&newAdjMatrix->ppMatrix[i][j]);
}
fclose(pFile);
return newAdjMatrix;
}
typedef struct
{
int numberOfNodes;
bool **ppMatrix;
} adjacencyMatrix;
tools.c
adjacencyList *createAdjListFromMatrix(adjacencyMatrix *pAdjMatrix)
{
//create a adjacencyList with the same number of nodes as adjacencyMatrix
adjacencyList *pNewadjacencyList=createAdjList(pAdjMatrix->numberOfNodes);
// now we move from row to row and create a list for every 1
int i,j;
for( i=0;i<pAdjMatrix->numberOfNodes;i++)
{
for( j=0;j<pAdjMatrix->numberOfNodes;j++)
{
//If an edge is found then create a node
if(pAdjMatrix->ppMatrix[i][j]==1)
{
addEdgeToAdjList(pNewadjacencyList, i, j);
}
}
}
return pNewadjacencyList;
}
最佳答案
这行在这里：
newList->ppLists=(node**)malloc(numberOfNodes*sizeof(node));
应更改为：
newList->ppLists = malloc(numberOfNodes*sizeof(node*));
原因是，您有一个指向节点的指针数组。因此，此数组的实际类型是指向节点（
node*）的指针。这是您要为其分配内存的类型。 malloc分配内存后，它将返回一个指向该类型的指针，因此您将获得一个指针= node**与C ++不同，在C语言中不必强制转换
void *返回的malloc