Original Post
This is driving me cazy, i''m sure it''s not that difficult but i just can''t get my head round it, any pointers would be great. Right this is my problem, I have a tree structure that denotes all posible sequences of takes in a game of draughts, here is an example of one (these are the board positions)
(3,5)
/ \
(1,3) (5,3)
| / \
(3,1) (3,1) (7,5)
x x x
The above tree translates into these 3 moves,
1. (3,5) (1,3) (3,1)
2. (3,5) (5,3) (3,1)
3. (3,5) (5,3) (7,5)
Each move needs to be sored as a list and then added to a list of lists! These are my list classes
// The ListObject Class
// This is an base class Used to create lists of any items
// derived from it.
class ListObject
{
protected:
ListObject *next;
public:
ListObject() {next = NULL;}
ListObject *GetNextObject() {return next;}
void SetNextObject(ListObject *nNext) {next = nNext;}
};
// This class holds board positions
class BoardPosList : public ListObject
{
// the x and y pos
int x, y;
public:
BoardPosList(int nx, int ny) {x=nx; y=ny; next=NULL;}
// gets the x & y positions
int GetX() {return x;}
int GetY() {return y;}
// sets em
void SetX(int nx) {x = nx;}
void SetY(int ny) {y = ny;}
};
// The List Class
// Basic list operations
class List : public ListObject
{
public:
List() {next = NULL;}
~List() {Destroy();}
void Destroy();
// Adds and item to the end of the list
void Add(ListObject *newItem);
// Adds and item to the start of the list
void AddStart(ListObject *newItem);
// removes the first object
ListObject *PopFirst();
// removes last object
ListObject *PopLast();
// Gets a pointer to the first object
ListObject *GetFirst() {return first;}
// Gets a pointer to the last object in the list
ListObject *GetLast();
};
The first tree I showed you is stored as a list where the first item is a BoardPosList(containing the postition)and the second item is a List which points to the next nodes, and so forth.
Here is an example of what the tree I showed u earlier looks like,
[] = list
- = list item divider
() = BoardPos
[(3,5) - [(5,3) - [(3,1) - [] -
(7,5) - []
] -
(1,3) - [(3,1) - []
]
]
And the move tree needs to be coverted into the following moves list,
[ [(3,5) - (1,3) - (3,1)]
[(3,5) - (5,3) - (3,1)]
[(3,5) - (5,3) - (7,5)]
]
I hope all this makes sense :-)
Now I was gonna put the code i''ve already written to do this up but it dosen''t work and is very messy.
I don''t expect anyone to write the function for me but i''m having trouble comming up with the basics of an algorithem to do this so if any one has any ideas or pointers, i''d be eternaly greatful.
also let me knoe if you need anymore info.