From:	"Graham Reeds" <grahamr AT ntlworld DOT com>
Newsgroups:	comp.os.msdos.djgpp
Subject:	Problem with allocating memory for linked lists.
Lines:	60
X-Priority:	3
X-MSMail-Priority:	Normal
X-Newsreader:	Microsoft Outlook Express 5.50.4133.2400
X-MimeOLE:	Produced By Microsoft MimeOLE V5.50.4133.2400
Message-ID:	<AKUr6.3065$y47.695473@news2-win.server.ntlworld.com>
Date:	Thu, 15 Mar 2001 01:11:03 -0000
NNTP-Posting-Host:	62.254.80.63
X-Complaints-To:	abuse AT ntlworld DOT com
X-Trace:	news2-win.server.ntlworld.com 984619040 62.254.80.63 (Thu, 15 Mar 2001 01:17:20 GMT)
NNTP-Posting-Date:	Thu, 15 Mar 2001 01:17:20 GMT
Organization:	ntlworld News Service
To:	djgpp AT delorie DOT com
DJ-Gateway:	from newsgroup comp.os.msdos.djgpp
Reply-To:	djgpp AT delorie DOT com

Okay.  I have a problem involving memory and linkedlists.  I've been hacking
at this for the past few weeks off and on, and keep getting the same
problem:

I'm coding a MergeSort on linkedlists.  The linkedlist starts off as a
sentinal and two pointers are initially set to point to itself.  All records
after that are tagged onto the end, thus keeping list maintenance simple.
(Yes I know I could use STL and yes I know I could use C++ to create
templates which would be a lot more efficient.)

In the Merge Sort I'll create a second list and after each comparison remove
the smaller record from one list and drop it straight into a secondary
temporary list thus making it more sorted.  Then when all the records are
moved, I'll switch pointers to the two lists and so on and so forth until
the lists are merged.

That is the plan.  However it doesn't work like that.  The function is
called via:
void  mergesort(linkedlist_t *linkedlist)

linkedlist_t is simply:

typedef struct linkedlist_s
  {
  record_t    *sentinal;
  }linkedlist_t;

where record_t is a collection of data with a sortkey (a float in this case)
and two pointers called *next and *prev.

The problem is I create the second linked list via a command called
createlinkedlist() which returns a pointer to memory it allocates and sets
the pointers to point at itself (awaiting records to be added).  The
linkedlist that is passed is created elsewhere in the code.

I then have two other pointers pointing to the linkedlists ('linkedlist',
and 'templist') called 'currlist' for the current list from which the
records are being removed and 'targetlist' which the records are being moved
to.  If I use createlinkedlist() to allocate the memory and initilise
'templist', for some inexplicable reason the following line: currlist =
linkedlist; fails.  Neither moving before the code or any point after will
make it work.  It just points to some (seemingly) random bit of memory
instead (long random numbers instead of the values that are supposed to be
stored).  However if I leave the line out it works fine (the numbers are the
correct numbers), but the moving of the records fails because there is
nowhere for them to be moved to (I know it doesn't actually 'move' but it
best describes them disappearing)..  I could post more code if required.

Also the initialisation code works since I have created insertion sort,
shell sort and even the god-awful bubblesort, and they all work 100% fine.
This has been dragging on for far too long now and is getting really
annoying.

--

Stay Lucky, Graham "Mournblade" Reeds,
ICQ: 30514803
http://homepage.dtn.ntl.com/grahamr

- Raw text -