Hey, I am stuck with something that i don't usually get stuck with. So i am thinking that either i have stumbled across something 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
}
}
}
Linear Mode
