0

我有一个自定义结构

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;

工具.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;
}
4

2 回答 2

0

这一行在这里：

newList->ppLists=(node**)malloc(numberOfNodes*sizeof(node));

应改为：

newList->ppLists = malloc(numberOfNodes*sizeof(node*));

原因是，你有一个指向节点的指针数组。所以这个数组的真正类型是一个指向节点（node*）的指针。这是您要为其分配内存的类型。分配内存后malloc，它将返回一个指向该类型的指针，因此您将获得一个指向指针 =node**

在 C 中，您不必强制转换为与 c++ 不同的void *返回malloc

于 2013-07-06T12:34:35.300 回答
0

这里：

newList->ppLists=(node**)malloc(numberOfNodes*sizeof(node));

您要求 malloc 返回指向某些节点的指针。但是，由于您有一个指向指针的声明，因此ppLists您希望 malloc 采用以下方式（考虑到 H2CO3 的建议不要转换结果）：

newList->ppLists = malloc(numberOfNodes * sizeof *newList->ppLists);

这是要求 malloc 给你一个指向类型结构的指针数组，node而不是一个所述结构的数组。

于 2013-07-06T12:34:52.863 回答