| |||||||||
![]() |
|
|
«
Previous Thread
|
Next Thread
»
|
Thread Tools | Search this Thread | Display Modes |
|
#1
|
|||
|
|||
|
Hey, I am stuck with something that i don't usually get stuck with. So i am thinking that either i have stumbled across some gotcha quality with the operator delete that i did not know about before, or that the problem is staring me in the face and i just can't see it!!!!!
this is the problem: I have an array which i allocated. Each item in the array has a linked list tied to it. So to delete I iterate through the array, and at each index i deallocate the linked list. and at the end of that, i delete the array with delete [] array I have done this very same thing many times before. So i would think i know what I am doing, but apprently i don't because this is the message i get on the very first index while deallocating its linked list: *** glibc detected *** free(): invalid pointer: 0x0804ee70 *** Aborted Also, if i skip the deallocation of the linked lists, and just try deallocating the array with delete [] array, i get almost the same message (with a different pointer value): *** glibc detected *** double free or corruption (!prev): 0x0804fa70 *** Aborted here is the entire code ,the functions that pertain are: void Mygraph::deletelist() void file_createlist(const char* filename); void string_createedges(int v, string* str_edges); thank you very much to whoever figures it out!!!! Code:
/////////////.h////////////////////////
#include <ostream>
#include <fstream>
#include <iostream>
//#include "Mystack.h"
using namespace std;
struct EdgeData
{
int weight;
struct Node* dest;
};
struct Edge
{
struct EdgeData data;
Edge* nextedge;
};
struct NodeData
{
int nodenumber;
};
struct Node
{
NodeData data;//container holding node data
struct Edge* edges;//list of directed edges connecting vertex (node) to other vertices
};
class Mygraph
{
private:
Node* vlist;
int size;
public:
Mygraph();
~Mygraph();
int getsize();
void printlist(ostream& out);
void deletelist();
bool inorderpath(int source, int dest, bool *visited ,ostream& out);
//breadthprint(ostream& out);
void file_createlist(const char* filename);
void string_createedges(int v, string* str_edges);
};
/////////////.cpp//////////
Mygraph::Mygraph()
{
vlist = 0;
size = 0;
}
Mygraph::~Mygraph()
{
deletelist();
}
void Mygraph::printlist(ostream& out)
{
Edge* edge = 0;
out<<"Adjacency List has "<<size<<" vertices"<<endl;
for(int i = 0; i < size; i++)
{
out<<vlist[i].data.nodenumber<<"\t";
edge = vlist[i].edges;
while(edge)
{
out<<edge->data.dest->data.nodenumber<<" ";
edge = edge->nextedge;
}
out<<endl;
}
}
int Mygraph::getsize()
{
return size;
}
void Mygraph::deletelist()
{
Edge *nextedge;
Edge *doomed;
for(int i = 0; i < size; i++)
{
doomed = vlist[i].edges;
while(doomed)
{ cout<<"deleting..."<<endl;
nextedge = doomed->nextedge;
//delete doomed;
doomed = nextedge;
}
}
delete [] vlist;
}
bool Mygraph::inorderpath(int source, int dest, bool *visited ,ostream& out)
{
Edge* edge = 0;
bool found = false;
//check to see if this node has been visited
if( !visited[source] )
{
//check to see if the this node is the destination node
if(vlist[source].data.nodenumber == dest)
{
found = true;
cout<<"Cool..we found a path to "<<dest<<endl;
//stack.push(source);
}
//mark it as visited
visited[source] = true;
//go through all nodes connected to this one
edge = vlist[source].edges;
while(edge && !found)
{
found = inorderpath(edge->data.dest->data.nodenumber,dest, visited,out);
if(found)//last node visited was the destination node
{
//stack.push(source);
cout<<"Currently visiting "<<vlist[source].data.nodenumber<<" on path back from "<<dest<<endl;
}
edge = edge->nextedge;
}
}
return found;
}
//void Mygraph::breadthprint(ostream& out);
void Mygraph::file_createlist(const char* filename)
{
string stringbuf;
fstream file;
int vindex = 0;
file.open(filename,ios::in);
if(file.fail())
{
vlist = 0;
return;
}
//matrix is n by n so find number
//of vertices to make array.
getline(file,stringbuf);
size = stringbuf.length() - 31;
vlist = new Node[size];
string_createedges(vindex,&stringbuf);
for(vindex = 1; !file.eof(); vindex++)
{
getline(file,stringbuf);
if(file.eof())
break;
vlist[vindex].data.nodenumber = vindex;
string_createedges(vindex,&stringbuf);
}
file.close();
return;
}
void Mygraph::string_createedges(int v, string* str_edges)
{
Edge** stitch = &(vlist[v].edges);
*stitch = 0;
int strlength = str_edges->length();
for(int i = 0; i < strlength; i+=2)
{
if( (*str_edges)[i] == '1')
{
*stitch = new Edge;
(**stitch).data.dest = &(vlist[i/2]);
stitch = &((**stitch).nextedge);
*stitch = 0;//tie up end
}
}
}
|
|
#2
|
|||
|
|||
|
Some comments would help as it's next to impossible to understand what you are trying to do. You're doing some wierd stuff with the pointers and I can't conceptualize what you are trying to build. However this looks mighty suspect to me:
Code:
void Mygraph::string_createedges(int v, string* str_edges)
{
Edge** stitch = &(vlist[v].edges);
*stitch = 0;
int strlength = str_edges->length();
for(int i = 0; i < strlength; i+=2)
{
if( (*str_edges)[i] == '1')
{
*stitch = new Edge; <- you allocate a new Edge here
(**stitch).data.dest = &(vlist[i/2]);
stitch = &((**stitch).nextedge);
*stitch = 0;//tie up end <- and here you blow away the pointer to it.
}
}
}
This looks suspect as well: Code:
for(vindex = 1; !file.eof(); vindex++) <- why are you starting at index 1 and not index 0?
{
getline(file,stringbuf)
if(file.eof())
break;
vlist[vindex].data.nodenumber = vindex;
string_createedges(vindex,&stringbuf);
}
Also just a coding style question but your struct NodeData only has one element and it's a simple type of int. Why make this a struct at all? Also, this seems kind of convoluted: your Node points to an Edge, but then your Edge points at a Node through the EdgeData. I can't picture what you are trying to build, or what goes where. |
|
#3
|
|||
|
|||
|
Well basically its a graph. The structures are are only in place in case that more data is added to the nodes and /or edges.
As for the pointer stuff, I am using a double pointer to build the list as it doesn't need special cases for the root pointer and the end pointer in case of a doubly linked list. I did actually figure out my problem. I was passing my graph to a function by value, so when the function was done the graph was destroyed, but since the freed memory did not have much time to get currupted, only a bit of would be and it wasn't readily apparent. Yes I acknowledge the program is bloated beyond the point of ridiculous....but i was trying stuff out! thanks for the reply! |
![]() |
| Viewing: Dev Articles Community Forums > Programming > C/C++ Help > deallocation problem, never been so stuck before. |
| Thread Tools | Search this Thread |
| Display Modes | Rate This Thread |
|
|
|
|
|