Thread: Ok this is long, but you don't need to read the whole thing.........

  1. #1
    left crog... back when? incognito's Avatar
    Join Date
    Oct 2001
    Posts
    1,427

    Ok this is long, but you don't need to read the whole thing.........

    just look at the bold letters......I've been trying to figure this one out for a really long time now....I've just about pulled all the hair out of my head and still can't seem to understand it, please I need help.......
    // ***********************************************
    // FILE: Listing 13.13
    //
    // PURPOSE: Demonstrate ilinked list
    // NOTES:
    //
    // COPYRIGHT: Copyright (C) 1998 Liberty Associates, Inc.
    // All Rights Reserved
    //
    // Demonstrates an object-oriented approach to
    // linked lists. The list delegates to the node.
    // The node is an abstract data type. Three types of
    // nodes are used, head nodes, tail nodes and internal
    // nodes. Only the internal nodes hold data.
    //
    // The Data class is created to serve as an object to
    // hold in the linked list.
    //
    // ***********************************************


    #include <iostream>
    using namespace std;

    enum { kIsSmaller, kIsLarger, kIsSame};

    // Data class to put into the linked list
    // Any class in this linked list must support two methods:
    // Show (displays the value) and
    // Compare (returns relative position)
    class Data
    {
    public:
    Data(int val):myValue(val){}
    ~Data(){}
    int Compare(const Data &);
    void Show() { cout << myValue << endl; }
    private:
    int myValue;
    };

    // Compare is used to decide where in the list
    // a particular object belongs.
    int Data::Compare(const Data & theOtherData)
    {
    if (myValue < theOtherData.myValue)
    return kIsSmaller;
    if (myValue > theOtherData.myValue)
    return kIsLarger;
    else
    return kIsSame;
    }

    // forward declarations
    class Node;
    class HeadNode;
    class TailNode;
    class InternalNode;

    // ADT representing the node object in the list
    // Every derived class must override Insert and Show
    class Node
    {
    public:
    Node(){}
    virtual ~Node(){}
    virtual Node * Insert(Data * theData)=0;
    virtual void Show() = 0;
    private:
    };

    // This is the node which holds the actual object
    // In this case the object is of type Data
    // We'll see how to make this more general when
    // we cover templates
    class InternalNode: public Node
    {
    public:
    InternalNode(Data * theData, Node * next);
    ~InternalNode(){ delete myNext; delete myData; }
    virtual Node * Insert(Data * theData);
    // delegate!
    virtual void Show() { myData->Show(); myNext->Show(); }

    private:
    Data * myData; // the data itself
    Node * myNext; // points to next node in the linked list
    };

    // All the constructor does is to initialize
    InternalNode::InternalNode(Data * theData, Node * next):
    myData(theData),myNext(next)
    {
    }

    // the meat of the list
    // When you put a new object into the list
    // it is passed ot the node which figures out
    // where it goes and inserts it into the list
    Node * InternalNode::Insert(Data * theData)
    {

    // is the new guy bigger or smaller than me?
    int result = myData->Compare(*theData);


    switch(result)
    {
    // by convention if it is the same as me it comes first
    case kIsSame: // fall through
    case kIsLarger: // new data comes before me
    {
    InternalNode * dataNode = new InternalNode(theData, this);
    return dataNode;
    }

    // it is bigger than I am so pass it on to the next
    // node and let HIM handle it.
    case kIsSmaller:
    myNext = myNext->Insert(theData);
    return this;
    }
    return this; // appease MSC
    }


    // Tail node is just a sentinel

    class TailNode : public Node
    {
    public:
    TailNode(){}
    ~TailNode(){}
    virtual Node * Insert(Data * theData);
    virtual void Show() { }

    private:

    };

    // If data comes to me, it must be inserted before me
    // as I am the tail and NOTHING comes after me
    Node * TailNode::Insert(Data * theData)
    {
    InternalNode * dataNode = new InternalNode(theData, this);
    return dataNode;
    }

    // Head node has no data, it just points
    // to the very beginning of the list
    class HeadNode : public Node
    {
    public:
    HeadNode();
    ~HeadNode() { delete myNext; }
    virtual Node * Insert(Data * theData);
    virtual void Show() { myNext->Show(); }
    private:
    Node * myNext;
    };

    // As soon as the head is created
    // it creates the tail
    HeadNode::HeadNode()
    {
    myNext = new TailNode;
    }

    // Nothing comes before the head so just
    // pass the data on to the next node
    Node * HeadNode::Insert(Data * theData)
    {
    myNext = myNext->Insert(theData); I don't understand this here because the other one only had this.....myHead->Insert(pData); but this one has an extra "=" sign in it.
    return this;
    }

    // I get all the credit and do none of the work
    class LinkedList
    {
    public:
    LinkedList();
    ~LinkedList() { delete myHead; }
    void Insert(Data * theData);
    void ShowAll() { myHead->Show(); }
    private:
    HeadNode * myHead;
    };

    // At birth, i create the head node
    // It creates the tail node
    // So an empty list points to the head which
    // points to the tail and has nothing between
    LinkedList::LinkedList()
    {
    myHead = new HeadNode;
    }

    // Delegate, delegate, delegate
    void LinkedList::Insert(Data * pData)
    {
    myHead->Insert(pData);
    }

    // test driver program
    int main()
    {
    Data * pData;
    int val;
    LinkedList ll;

    // ask the user to produce some values
    // put them in the list
    for (;;)
    {
    cout << "What value? (0 to stop): ";
    cin >> val;
    if (!val)
    break;
    pData = new Data(val);
    ll.Insert(pData);
    }

    // now walk the list and show the data
    ll.ShowAll();
    int x;
    cin>>x;
    return 0; // ll falls out of scope and is destroyed!
    }
    There are some real morons in this world please do not become one of them, do not become a victim of moronitis. PROGRAMMING IS THE FUTURE...THE FUTURE IS NOW!!!!!!!!!

    "...The only real game I thank in the world is baseball..." --Babe Ruth

    "Life is beautiful"-Don Corleone right before he died.

    "The expert on anything was once a beginner" -Baseball poster I own.


    Left cprog on 1-3-2005. Don't know when I am coming back. Thanks to those who helped me over the years.

  2. #2
    left crog... back when? incognito's Avatar
    Join Date
    Oct 2001
    Posts
    1,427
    Never mind I am too discouraged to keep working on this example.......I'm just skipping it all together and looking at other examples of linked lists that I have.......it's using Structs though and it doesn't have inheritance but I'll just maybe come back to it later.
    There are some real morons in this world please do not become one of them, do not become a victim of moronitis. PROGRAMMING IS THE FUTURE...THE FUTURE IS NOW!!!!!!!!!

    "...The only real game I thank in the world is baseball..." --Babe Ruth

    "Life is beautiful"-Don Corleone right before he died.

    "The expert on anything was once a beginner" -Baseball poster I own.


    Left cprog on 1-3-2005. Don't know when I am coming back. Thanks to those who helped me over the years.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Undefined Reference Compiling Error
    By AlakaAlaki in forum C++ Programming
    Replies: 1
    Last Post: 06-27-2008, 11:45 AM
  2. hton long long
    By carrotcake1029 in forum C Programming
    Replies: 1
    Last Post: 06-01-2008, 08:26 PM
  3. confused with read()
    By _EAX in forum Linux Programming
    Replies: 2
    Last Post: 03-17-2008, 04:14 PM
  4. Replies: 8
    Last Post: 03-10-2008, 11:57 AM
  5. "sorting news" assignment
    By prljavibluzer in forum C Programming
    Replies: 7
    Last Post: 02-06-2008, 06:45 AM