Sign in to follow this  
PaladinJohn

Looking for Help/Examples for Linked Lists (C++)

Recommended Posts

PaladinJohn    130
Alright, let me give a little background for those who are interested. Those who are more interested in the code can skip these next two paragraphs. I'm a beginning programmer who just started learning C++ maybe 4 months ago. In my spare time, I run a Table Top game that I designed from the bottom up myself. My friends all love it, but one complaint is that combat is slow and hurts the cinematic feel of the game. I decided that I would kill two birds with one stone and work on my programming while developing aides for my game. As such, I set out to develop the first step in a multi-step project to essentially run the number crunching aspect of combat for my players and leave the cinematic goodness. My problem is, as a novice programmer, I have trouble developing a program if I don't have a good example to work off of. What I'm looking for is a more experienced programmer to either point out the mistake I made with my initial draft and offer some suggestions to fix the problem, or even a good example of what I'm looking to do that I can examine and learn from. The program I have designed is intended to be a Linked List that prompts the user to input a name, and then assign a random number between 1 - 100. As players are added, the linked list sorts the players based on their value until the user chooses to stop adding more players. The linked list then runs through all of the Player objects, displaying the name of the player, and the player's value. Unfortunately, I have never found a good example of a linked list program that has objects that contain two types of member data, and sorts based only on one. I believe I'm close with the current program, but may have made a mistake with a pointer along the way. Also, please note, the current version is not 100% complete. In main() I made it so I could enter in my own value rather than a randomly generated one in order to test and make sure the program was working properly. Since I'm confident in my ability to program that aspect of the program, I am mostly only looking for suggestions in regards to the player class and possibly the linked list itself. Without further ado, here is the source code for my current program:
#include <iostream>
#include <string>

using namespace std;

enum { kIsSmaller, kIsLarger, kIsSame};

class Player
 {
 public:
     int CT;
     string name;
     Player(string name):myCT(CT){};
     ~Player(){}
     int Compare(const Player&);
     void Show() { cout << name << ": " << myCT << endl; }
 private:
     int myCT;
 };

int Player::Compare(const Player & theOtherPlayer)
 {
     if (myCT < theOtherPlayer.myCT)
         return kIsSmaller;
     if (myCT > theOtherPlayer.myCT)
         return kIsLarger;
     else
         return kIsSame;
 }

class Node;
class HeadNode;
class TailNode;
class InternalNode;

class Node
 {
 public:
     Node(){}
     virtual ~Node(){}
     virtual Node * Insert(Player * thePlayer)=0;
     virtual void Show() = 0;
 private:
 };

class InternalNode: public Node
 {
 public:
     InternalNode(Player * thePlayer, Node * next);
     virtual ~InternalNode(){ delete myNext; delete myPlayer; }
     virtual Node * Insert(Player * thePlayer);
     virtual void Show()
         { myPlayer->Show(); myNext->Show(); }

 private:
     Player * myPlayer;
     Node * myNext;
 };

InternalNode::InternalNode(Player * thePlayer, Node * next):
myPlayer(thePlayer),myNext(next)
 {
 }

Node * InternalNode::Insert(Player * thePlayer)
 {

     int result = myPlayer->Compare(*thePlayer);


     switch(result)
     {
     case kIsSame:
     case kIsLarger:
         {
             InternalNode * playerNode =
                 new InternalNode(thePlayer, this);
             return playerNode;
         }

     case kIsSmaller:
         myNext = myNext->Insert(thePlayer);
         return this;
     }
     return this;
 }

class TailNode : public Node
 {
 public:
     TailNode(){}
     virtual ~TailNode(){}
     virtual Node * Insert(Player * thePlayer);
     virtual void Show() { }
 private:
 };

Node * TailNode::Insert(Player * thePlayer)
 {
     InternalNode * playerNode = new InternalNode(thePlayer, this);
     return playerNode;
 }

class HeadNode : public Node
 {
 public:
     HeadNode();
     virtual ~HeadNode() { delete myNext; }
     virtual Node * Insert(Player * thePlayer);
     virtual void Show() { myNext->Show(); }
 private:
     Node * myNext;
 };

HeadNode::HeadNode()
 {
     myNext = new TailNode;
 }

Node * HeadNode::Insert(Player * thePlayer)
 {
     myNext = myNext->Insert(thePlayer);
     return this;
 }

class LinkedList
 {
 public:
     LinkedList();
     ~LinkedList() { delete myHead; }
     void Insert(Player * thePlayer);
     void ShowAll() { myHead->Show(); }
 private:
     HeadNode * myHead;
 };

LinkedList::LinkedList()
 {
     myHead = new HeadNode;
 }

void LinkedList::Insert(Player * pPlayer)
 {
     myHead->Insert(pPlayer);
 }

int main()
 {
     Player * pPlayer;
     int CT;
     string name;
     LinkedList ll;

     for (;;)
     {
         cout << "What Name?: ";
         cin >> name;
         cout << "What CT? (0 to stop): ";
         cin >> CT;
         if (!CT)
             break;
         pPlayer = new Player(name);
         ll.Insert(pPlayer);
     }

     ll.ShowAll();
     return 0;
 }
Thank you for your time, I appreciate and look forward to your input!

Share this post


Link to post
Share on other sites
leeor_net    343
To answer the title of your thread: linked lists. Google is your friend.

To that end, I would highly recommend you use an STL container instead of trying to build a linked list. It's faster, safer and very thouroughly tested.

Depending on what you're specifically trying to do, you're probably looking for std::vector or std::list. STL is somewhat intimidating at first but believe me it will save you a great deal of headaches later on down the line and will actually reduce the amount of code you write. Using an STL solution in your case could reduce your entire code from what it is to just a few lines in your main() function.

In the particular case of using a linked-list type solution, you won't need to bother too much with iterators (a virtual nightmare until you get used to them).

Share this post


Link to post
Share on other sites
nerd_boy    720
[NINJA'D][disturbed]

Hullo.

[Removed]Blech. Got that all wrong. Need sleep...

Also, while I've not used C++ in forever, I think most people suggest using the Standard Template Library(STL) for stuff like this. According to this site, they have a nifty doubly linked list template container thingy. It also seems to have a sort method(you'll hafta scroll down the page a bit) that'll sort the list based on the overloaded < operator. It'd probably be safer/better/easier to use this and just overload the < operator.

Hope I helped!

Share this post


Link to post
Share on other sites
PaladinJohn    130
I remember touching upon STL containers briefly while I was learning C++, but there wasn't a lot of detail given. My original draft for the project actually used a vector instead of Linked List, but the only way I could figure out how to sort it was from smallest to largest. (I made a mistake within my actual program, and it's supposed to display from largest to smallest, but again, that's a fairly easy mix up to remedy.)

I did however take a brief look at the sites both of you linked, and it may be just what I'm looking for. Unfortunately, my brain has just about melted from an overload of work today, so I will check them out tomorrow when I'm refreshed and see if that was just the ticket I needed to solve my problem. Thank you for your quick replies.

Share this post


Link to post
Share on other sites
Zahlman    1682
First off: the "STL" is no more. It's the standard library of C++ now, and to ignore it is no more reasonable than to ignore the standard library of any other language. You wouldn't try to write C code without strlen() et. al. would you? So don't try to use C++ without standard library containers.

Quote:
Original post by PaladinJohn
but the only way I could figure out how to sort it was from smallest to largest.


The standard library separates "algorithms" from containers. Sorting can be done with any container. However, lists need special handling because of how they're constructed (there is no direct random access, which makes some sorting techniques unuseful).

To change the sorting order, you can specify a comparison operation as the third parameter to std::sort(). If your container holds instances of your own class or struct which has a "natural sorting order", you can specify that by implementing operator< for the class or struct. If you want to sort the instance naturally from largest to smallest, then do both: implement operator<, and then use 'std::greater' as the sort order. (std::greater is actually a function. To specify your own comparison operations, you can either write functions, or overload operator() for some other class and pass an instance.)

Also, your class constructor is broken: it uses the uninitialized public 'CT' to initialize the private 'myCT', and ignores the passed in 'name', leaving the instance's 'name' member empty. (And WTF is a "CT", anyway?)


// Don't 'use namespace std;' in headers. The file that #includes the header
// has no way to undo it.
class Player {
std::string name;
int value;

public:
// Pass instances of objects by const reference, in general.
Player(const std::string& name, int value): name(name), value(value) {}
// Don't bother writing and implementing empty destructors, unless they're virtual.

// For the comparison to work naturally with std::sort, you need it to be
// an operator overload. You don't need a 3-way comparison.
boolean operator<(const Player& p) { return value < p.value; }

// Use standard idioms for output.
friend ostream& operator<<(ostream& os, const Player& p) {
return os << p.name << ": " << p.value;
}
};

using namespace std;

int main() {
vector<Player> players;
int value;
string name;

// If you're going to write an infinite loop, do it in a way that's
// more easily recognizable.
while (true) {
// Please note the techniques used here for robust input.
cout << "Give a name and a value, or invalid input to stop: "
if (!(cin >> name >> value)) { break; }
players.push_back(Player(name, value));
std::getline(std::cin, name); // consume the rest of the line.
}
sort(players.begin(), players.end());
// Look what else you can do with <algorithm>:
copy(players.begin(), players.end(), ostream_iterator<Player>(cout, "\n"));
}



Share this post


Link to post
Share on other sites
visitor    643
Quote:
If you want to sort the instance naturally from largest to smallest, then do both: implement operator<, and then use 'std::greater' as the sort order.


A minor correction: std::greater is a wrapper around operator>, which can be implemented in terms of <, but needs to be implemented.

A linked list example:


#include <iostream>
#include <list>
#include <functional>
#include <cstdlib>

using namespace std;

struct Test
{
int n;
Test(int n): n(n) {}
};

bool operator< (const Test& a, const Test& b)
{
return a.n < b.n;
}

bool operator> (const Test& a, const Test& b)
{
return b < a;
}

typedef list<Test> Tests;

void print(const Tests& tests)
{
for (Tests::const_iterator it = tests.begin(); it != tests.end(); ++it) {
std::cout << it->n << ' ';
}
std::cout << '\n';
}

int main()
{
Tests tests;
for (int i = 0; i != 10; ++i) {
tests.push_back(Test(rand() % 128));
}
tests.sort();
print(tests);

tests.sort(greater<Test>());
print(tests);

return 0;
}


Share this post


Link to post
Share on other sites
Zahlman    1682
Quote:
Original post by visitor
which can be implemented in terms of <, but needs to be implemented.


Of course, it's possible to do that for all types via a template. Although I think one of the standard library headers provides such a template anyway. :)

Share this post


Link to post
Share on other sites
PaladinJohn    130
Thank you all for the wealth of information. I took a different approach to the program and I got further than before, but I still have a few bugs to work out. I'm going to attempt to see if I can fix it myself before asking for more help on the subject since I'm one of those people that learns from my mistakes, and then learning how not to make those mistakes again. XD

Quote:
Original post by Zahlman
(And WTF is a "CT", anyway?)


I should have added a note in the code itself, but CT stands for "Charge Time". I had it as CT for clarity's sake for myself, but I can see why it would raise a few eyebrows.

In a more advanced version of the program I will do in the future, I'll include the full basis for taking turns. Essentially, each "Clock Tick" adds a certain number based on each character's speed to their respective "Charge Time". When someone's number reaches 100+, it's their turn. After taking a turn, based on the action(s) they took during their turn they have a certain number subtracted from their current CT, and then the clock ticks back up. Clock Ticks are used to determine persistent effects that affect a character over a span of time.

Of course, while I have this all mapped out in Pseudo-code, I want to take it slow and add to the program bit by bit to make sure that I'm not only learning, but I don't overwhelm myself with too many elements too quickly. Also, I figure it will be easier for me to trouble shoot my program if I know all of the code that came before the new coding is good code.

Share this post


Link to post
Share on other sites
visitor    643
Quote:

Although I think one of the standard library headers provides such a template anyway. :)


Which header?

I have heard that Boost.Operators can be used to synthesize additional operators from a set of base operators. Which should look something like this. Given the presence of overloaded <, operators >, <= and >= are free.


#include <iostream>
#include <list>
#include <functional>
#include <cstdlib>
#include <boost/operators.hpp>

using namespace std;

struct Test: boost::less_than_comparable<Test>
{
int n;
Test(int n): n(n) {}
};

bool operator< (const Test& a, const Test& b)
{
return a.n < b.n;
}

typedef list<Test> Tests;

void print(const Tests& tests)
{
for (Tests::const_iterator it = tests.begin(); it != tests.end(); ++it) {
std::cout << it->n << ' ';
}
std::cout << '\n';
}

int main()
{
Tests tests;
for (int i = 0; i != 10; ++i) {
tests.push_back(Test(rand() % 128));
}
tests.sort();
print(tests);

tests.sort(greater<Test>());
print(tests);

std::cout << (tests.front() <= tests.back()) << ' ' << (tests.front() >= tests.back()) << '\n';

return 0;
}


Share this post


Link to post
Share on other sites
Zahlman    1682
Well, you see, that's the thing. I was sure I remembered seeing something like that, but then I couldn't find it when I tried looking it up. x.x

Share this post


Link to post
Share on other sites
DevFred    840
Quote:
Original post by Zahlman
I was sure I remembered seeing something like that, but then I couldn't find it when I tried looking it up. x.x

It's not easy to find.

#include <utility>
using namespace std::rel_ops;

Share this post


Link to post
Share on other sites
visitor    643
Thanks, I didn't know that.

However, while after replacing boost::less_than_comparable with that the direct comparisons with <= and => in code are alright, std::greater<Test> still fails to compile:


C:/MingW/include/c++/3.4.5/bits/stl_function.h:
In member function `bool std::greater<_Tp>::operator()(const _Tp&, const _Tp&) const
[with _Tp = Test]':
C:/MingW/include/c++/3.4.5/bits/list.tcc:324:
instantiated from `void std::list<_Tp, _Alloc>::merge(std::list<_Tp, _Alloc>&, _StrictWeakOrdering)
[with _StrictWeakOrdering = std::greater<Test>, _Tp = Test, _Alloc = std::allocator<Test>]'
C:/MingW/include/c++/3.4.5/bits/list.tcc:360:
instantiated from `void std::list<_Tp, _Alloc>::sort(_StrictWeakOrdering)
[with _StrictWeakOrdering = std::greater<Test>, _Tp = Test, _Alloc = std::allocator<Test>]'
C:\cprograms\Untitled1.cpp:47: instantiated from here
C:/MingW/include/c++/3.4.5/bits/stl_function.h:218:
error: no match for 'operator>' in '__x > __y'




Or more precisely, it seems it also needs:

using std::rel_ops::operator>;


Is this a problem with library implementation / compiler / C++ namespaces? (I remember vaguely some similar problem with how to get compiler choose user-defined swap method).

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this