This topic is now archived and is closed to further replies.


Recursion Headache

Recommended Posts

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.

Share this post

Link to post
Share on other sites