Sorted Linked List

Discussion in 'C++' started by massimo, May 24, 2004.

  1. massimo

    massimo Guest

    Hey,

    I wrote this program which should take the numbers entered and sort them
    out. It doesn¹t matter what order, if decreasing or increasing.

    I guess I'm confused in the sorting part. Anyone has any advices??

    #include <iostream>
    using namespace std;

    struct link
    {
    int data;
    link *pNext;
    link *pHead;
    link *current;
    };

    class linkList
    {
    private:
    link *pHead;
    public:
    linkList()
    { pHead = NULL;}
    void add_Item(int d);
    void display();
    };

    void linkList::add_Item(int d)
    {
    link *pPrev;
    link *pSucc;

    pPrev = pHead;
    while(true)
    {
    pPrev = pSucc;
    pSucc = pSucc -> pNext;

    if(pSucc == NULL)
    break;

    if(d >= pSucc -> data)
    break;
    }

    link *newLink = new link;
    newLink -> data = d;
    pPrev -> pNext = newLink;
    newLink -> pNext = pSucc;
    }

    void linkList::display()
    {
    link *current = pHead;
    while (current != NULL)
    {
    cout << current -> data << endl;
    current = current -> pNext;
    }
    }

    int main ()
    {
    int input;

    linkList numbers;

    cin >> input;
    while(input >= 0)
    {
    cout << "Enter any numbers" << endl;
    cin >> input;
    numbers.add_Item(input);
    }

    numbers.display();

    return 0;
    }
     
    massimo, May 24, 2004
    #1
    1. Advertising

  2. massimo

    osmium Guest

    massimo writes:

    > I wrote this program which should take the numbers entered and sort them
    > out. It doesn¹t matter what order, if decreasing or increasing.
    >
    > I guess I'm confused in the sorting part. Anyone has any advices??
    >
    > #include <iostream>
    > using namespace std;
    >
    > struct link
    > {
    > int data;
    > link *pNext;
    > link *pHead;
    > link *current;
    > };
    >
    > class linkList
    > {
    > private:
    > link *pHead;
    > public:
    > linkList()
    > { pHead = NULL;}
    > void add_Item(int d);
    > void display();
    > };
    >
    > void linkList::add_Item(int d)
    > {
    > link *pPrev;
    > link *pSucc;
    >
    > pPrev = pHead;
    > while(true)
    > {
    > pPrev = pSucc;
    > pSucc = pSucc -> pNext;
    >
    > if(pSucc == NULL)
    > break;
    >
    > if(d >= pSucc -> data)
    > break;
    > }
    >
    > link *newLink = new link;
    > newLink -> data = d;
    > pPrev -> pNext = newLink;
    > newLink -> pNext = pSucc;
    > }
    >
    > void linkList::display()
    > {
    > link *current = pHead;
    > while (current != NULL)
    > {
    > cout << current -> data << endl;
    > current = current -> pNext;
    > }
    > }
    >
    > int main ()
    > {
    > int input;
    >
    > linkList numbers;
    >
    > cin >> input;
    > while(input >= 0)
    > {
    > cout << "Enter any numbers" << endl;
    > cin >> input;
    > numbers.add_Item(input);
    > }
    >
    > numbers.display();
    >
    > return 0;
    > }


    The "right" way to do it is to write a merge sort. I am sure there are tons
    of tutorials on the web, probably even Java applets to demonstrate the
    process.

    The quick and dirty way out is to traverse the list, put everything into an
    array, use qsort to sort the array, and write a new list from the sorted
    array. I doubt if an instructor would care for that approach.

    Note also that there are sort aids in the STL.
     
    osmium, May 24, 2004
    #2
    1. Advertising

  3. "massimo" <> wrote in message
    news:BCD7984D.193D%...
    > Hey,
    >
    > I wrote this program which should take the numbers entered and sort them
    > out. It doesn¹t matter what order, if decreasing or increasing.
    >
    > I guess I'm confused in the sorting part. Anyone has any advices??


    I would say to throw away the code and start again, but comments below.

    >
    > #include <iostream>
    > using namespace std;
    >
    > struct link
    > {
    > int data;
    > link *pNext;
    > link *pHead;
    > link *current;


    Why do you need a pointer back to head? What is current?

    > };
    >
    > class linkList
    > {
    > private:
    > link *pHead;
    > public:
    > linkList()
    > { pHead = NULL;}
    > void add_Item(int d);
    > void display();
    > };


    It's good that you have two seperate classes, one for the links and one for
    the list.

    >
    > void linkList::add_Item(int d)
    > {
    > link *pPrev;
    > link *pSucc;


    pSucc is uninitialised.

    >
    > pPrev = pHead;
    > while(true)
    > {
    > pPrev = pSucc;


    pSucc is still uninitialised.

    > pSucc = pSucc -> pNext;
    >

    pSucc is still uninitialised, program crashes here.

    OK, here how to do it properly. Here's some suitable classes

    struct Link
    {
    int data;
    Link* next;
    };

    class List
    {
    public:
    List() { head = NULL; }
    void add_item(int d);
    void display();
    private
    Link* head;
    };

    Now the thing is to think carefully about the add_item algorithm. Lets say
    we are going to add items in ascending order, smallest first, largest last.
    Clearly you are going to have to loop though the list looking for the place
    to add the new data. When will that loop end? One reason for the loop to end
    is when we find data in the list that is larger than the one we are adding,
    then we stop looping and add the item before the larger data. The other
    reason the loop might end is that we hit the end of the list, then we add an
    item at the end of the list. Now an important simplification is that both
    these cases are actually the same. In both cases we add a new link after the
    previous link. In the case when we hit the end of the list the previous link
    is the last link in the list so adding after that link is adding to the end
    of the list.

    Now special case is adding to an empty list or adding a number that is
    smaller than all the numbers in the list. In that case we add to the
    beginning of the list.

    Here's the code

    void List::add_item(int d)
    {
    // test for empty list or data smaller than first item in list
    if (head == NULL || d <= head->data)
    {
    // add to beginning of list
    Link* temp = new Link;
    temp->data = d;
    temp->next = head;
    head = temp;
    }
    else
    {
    // we don't need to add to beginning of list
    // so loop though list looking for where to add
    Link* prev = head;
    Link* curr = head->next;
    // keep looping while not end of list and data bigger than current
    item
    while (curr != NULL && d > curr->data)
    {
    prev = prev->next;
    curr = curr->next;
    }
    // found place to add, add after previous item
    Link* temp = new Link;
    temp->data = d;
    temp->next = curr;
    prev->next = temp;
    }
    }

    This is untested code so it might have bugs, but the main thing is you
    understand the algorithm.

    john
     
    John Harrison, May 24, 2004
    #3
  4. massimo

    massimo Guest

    Hey john,

    Thank you very much. I totally understand the checking/sorting algorithm.

    I debugged the program and it compiles fine. I still believe I have some
    problem with the display() and main(); I'm doing something wrong and I don't
    see it!!
    When it compiles it doesn't prompt me and if I enter the numbers, it just
    return "Enter a number" for as many numbers I entered.
    How do I space the number??
    Let's say I want to enter:
    12 34 56 23 45 33 and the on enter I want the program to spit out the sorted
    list.

    void List::display() // display links
    {
    Link *curr = head; // set pointer to first link
    while (curr != NULL) // on last link stop
    {
    cout << curr -> data << endl; // print data
    curr = curr -> next; // move to next
    }
    }

    int main ()
    {
    int input;

    List numbers; // make linked list

    cin >> input;
    while(input >= 0)
    {
    cout << "Enter any numbers" << endl;
    cin >> input;
    numbers.add_item(input);
    }

    numbers.display();

    return 0;
    }

    Thanks,mass


    On 5/24/04 2:28 PM, in article , "John Harrison"
    <> wrote:

    >
    > "massimo" <> wrote in message
    > news:BCD7984D.193D%...
    >> Hey,
    >>
    >> I wrote this program which should take the numbers entered and sort them
    >> out. It doesn¹t matter what order, if decreasing or increasing.
    >>
    >> I guess I'm confused in the sorting part. Anyone has any advices??

    >
    > I would say to throw away the code and start again, but comments below.
    >
    >>
    >> #include <iostream>
    >> using namespace std;
    >>
    >> struct link
    >> {
    >> int data;
    >> link *pNext;
    >> link *pHead;
    >> link *current;

    >
    > Why do you need a pointer back to head? What is current?
    >
    >> };
    >>
    >> class linkList
    >> {
    >> private:
    >> link *pHead;
    >> public:
    >> linkList()
    >> { pHead = NULL;}
    >> void add_Item(int d);
    >> void display();
    >> };

    >
    > It's good that you have two seperate classes, one for the links and one for
    > the list.
    >
    >>
    >> void linkList::add_Item(int d)
    >> {
    >> link *pPrev;
    >> link *pSucc;

    >
    > pSucc is uninitialised.
    >
    >>
    >> pPrev = pHead;
    >> while(true)
    >> {
    >> pPrev = pSucc;

    >
    > pSucc is still uninitialised.
    >
    >> pSucc = pSucc -> pNext;
    >>

    > pSucc is still uninitialised, program crashes here.
    >
    > OK, here how to do it properly. Here's some suitable classes
    >
    > struct Link
    > {
    > int data;
    > Link* next;
    > };
    >
    > class List
    > {
    > public:
    > List() { head = NULL; }
    > void add_item(int d);
    > void display();
    > private
    > Link* head;
    > };
    >
    > Now the thing is to think carefully about the add_item algorithm. Lets say
    > we are going to add items in ascending order, smallest first, largest last.
    > Clearly you are going to have to loop though the list looking for the place
    > to add the new data. When will that loop end? One reason for the loop to end
    > is when we find data in the list that is larger than the one we are adding,
    > then we stop looping and add the item before the larger data. The other
    > reason the loop might end is that we hit the end of the list, then we add an
    > item at the end of the list. Now an important simplification is that both
    > these cases are actually the same. In both cases we add a new link after the
    > previous link. In the case when we hit the end of the list the previous link
    > is the last link in the list so adding after that link is adding to the end
    > of the list.
    >
    > Now special case is adding to an empty list or adding a number that is
    > smaller than all the numbers in the list. In that case we add to the
    > beginning of the list.
    >
    > Here's the code
    >
    > void List::add_item(int d)
    > {
    > // test for empty list or data smaller than first item in list
    > if (head == NULL || d <= head->data)
    > {
    > // add to beginning of list
    > Link* temp = new Link;
    > temp->data = d;
    > temp->next = head;
    > head = temp;
    > }
    > else
    > {
    > // we don't need to add to beginning of list
    > // so loop though list looking for where to add
    > Link* prev = head;
    > Link* curr = head->next;
    > // keep looping while not end of list and data bigger than current
    > item
    > while (curr != NULL && d > curr->data)
    > {
    > prev = prev->next;
    > curr = curr->next;
    > }
    > // found place to add, add after previous item
    > Link* temp = new Link;
    > temp->data = d;
    > temp->next = curr;
    > prev->next = temp;
    > }
    > }
    >
    > This is untested code so it might have bugs, but the main thing is you
    > understand the algorithm.
    >
    > john
    >
    >
     
    massimo, May 24, 2004
    #4
  5. massimo

    massimo Guest

    Well,

    I guess if I use space between numbers the compiler assumes that are
    different numbers. Ok that¹s good.

    Example_
    if I enter these 4 numbers:
    12 34 52 24 26

    This is the cout:
    Enter any numbers
    Enter any numbers
    Enter any numbers
    Enter any numbers
    Enter any numbers

    Obviously if I enter:
    1265
    This is the cout:
    Enter any numbers

    So it's definitely something wrong with my prompt and the main();

    Thanks,mass

    On 5/24/04 3:21 PM, in article BCD7C37F.19A1%, "massimo"
    <> wrote:

    > Hey john,
    >
    > Thank you very much. I totally understand the checking/sorting algorithm.
    >
    > I debugged the program and it compiles fine. I still believe I have some
    > problem with the display() and main(); I'm doing something wrong and I don't
    > see it!!
    > When it compiles it doesn't prompt me and if I enter the numbers, it just
    > return "Enter a number" for as many numbers I entered.
    > How do I space the number??
    > Let's say I want to enter:
    > 12 34 56 23 45 33 and the on enter I want the program to spit out the sorted
    > list.
    >
    > void List::display() // display links
    > {
    > Link *curr = head; // set pointer to first link
    > while (curr != NULL) // on last link stop
    > {
    > cout << curr -> data << endl; // print data
    > curr = curr -> next; // move to next
    > }
    > }
    >
    > int main ()
    > {
    > int input;
    >
    > List numbers; // make linked list
    >
    > cin >> input;
    > while(input >= 0)
    > {
    > cout << "Enter any numbers" << endl;
    > cin >> input;
    > numbers.add_item(input);
    > }
    >
    > numbers.display();
    >
    > return 0;
    > }
    >
    > Thanks,mass
    >
    >
    > On 5/24/04 2:28 PM, in article , "John Harrison"
    > <> wrote:
    >
    >>
    >> "massimo" <> wrote in message
    >> news:BCD7984D.193D%...
    >>> Hey,
    >>>
    >>> I wrote this program which should take the numbers entered and sort them
    >>> out. It doesn¹t matter what order, if decreasing or increasing.
    >>>
    >>> I guess I'm confused in the sorting part. Anyone has any advices??

    >>
    >> I would say to throw away the code and start again, but comments below.
    >>
    >>>
    >>> #include <iostream>
    >>> using namespace std;
    >>>
    >>> struct link
    >>> {
    >>> int data;
    >>> link *pNext;
    >>> link *pHead;
    >>> link *current;

    >>
    >> Why do you need a pointer back to head? What is current?
    >>
    >>> };
    >>>
    >>> class linkList
    >>> {
    >>> private:
    >>> link *pHead;
    >>> public:
    >>> linkList()
    >>> { pHead = NULL;}
    >>> void add_Item(int d);
    >>> void display();
    >>> };

    >>
    >> It's good that you have two seperate classes, one for the links and one for
    >> the list.
    >>
    >>>
    >>> void linkList::add_Item(int d)
    >>> {
    >>> link *pPrev;
    >>> link *pSucc;

    >>
    >> pSucc is uninitialised.
    >>
    >>>
    >>> pPrev = pHead;
    >>> while(true)
    >>> {
    >>> pPrev = pSucc;

    >>
    >> pSucc is still uninitialised.
    >>
    >>> pSucc = pSucc -> pNext;
    >>>

    >> pSucc is still uninitialised, program crashes here.
    >>
    >> OK, here how to do it properly. Here's some suitable classes
    >>
    >> struct Link
    >> {
    >> int data;
    >> Link* next;
    >> };
    >>
    >> class List
    >> {
    >> public:
    >> List() { head = NULL; }
    >> void add_item(int d);
    >> void display();
    >> private
    >> Link* head;
    >> };
    >>
    >> Now the thing is to think carefully about the add_item algorithm. Lets say
    >> we are going to add items in ascending order, smallest first, largest last.
    >> Clearly you are going to have to loop though the list looking for the place
    >> to add the new data. When will that loop end? One reason for the loop to end
    >> is when we find data in the list that is larger than the one we are adding,
    >> then we stop looping and add the item before the larger data. The other
    >> reason the loop might end is that we hit the end of the list, then we add an
    >> item at the end of the list. Now an important simplification is that both
    >> these cases are actually the same. In both cases we add a new link after the
    >> previous link. In the case when we hit the end of the list the previous link
    >> is the last link in the list so adding after that link is adding to the end
    >> of the list.
    >>
    >> Now special case is adding to an empty list or adding a number that is
    >> smaller than all the numbers in the list. In that case we add to the
    >> beginning of the list.
    >>
    >> Here's the code
    >>
    >> void List::add_item(int d)
    >> {
    >> // test for empty list or data smaller than first item in list
    >> if (head == NULL || d <= head->data)
    >> {
    >> // add to beginning of list
    >> Link* temp = new Link;
    >> temp->data = d;
    >> temp->next = head;
    >> head = temp;
    >> }
    >> else
    >> {
    >> // we don't need to add to beginning of list
    >> // so loop though list looking for where to add
    >> Link* prev = head;
    >> Link* curr = head->next;
    >> // keep looping while not end of list and data bigger than current
    >> item
    >> while (curr != NULL && d > curr->data)
    >> {
    >> prev = prev->next;
    >> curr = curr->next;
    >> }
    >> // found place to add, add after previous item
    >> Link* temp = new Link;
    >> temp->data = d;
    >> temp->next = curr;
    >> prev->next = temp;
    >> }
    >> }
    >>
    >> This is untested code so it might have bugs, but the main thing is you
    >> understand the algorithm.
    >>
    >> john
    >>
    >>

    >
     
    massimo, May 24, 2004
    #5
  6. massimo wrote:
    > Hey john,
    >
    > Thank you very much. I totally understand the checking/sorting algorithm.
    >
    > I debugged the program and it compiles fine. I still believe I have some
    > problem with the display() and main(); I'm doing something wrong and I don't
    > see it!!
    > When it compiles it doesn't prompt me and if I enter the numbers, it just
    > return "Enter a number" for as many numbers I entered.
    > How do I space the number??
    > Let's say I want to enter:
    > 12 34 56 23 45 33 and the on enter I want the program to spit out the sorted
    > list.

    [snip]

    My suggestion is to write a small main() function that reads in the
    numbers then spits them out:

    #include <iostream>
    #include <vector>
    #include <cstdlib>
    #include <algorithm>

    using namespace std;

    typedef vector<int> Vector_Of_Ints;

    int main(void)
    {
    // Create a container for the numbers.
    Vector_Of_Ints numbers;

    int users_number;

    // Read in the numbers until EOF or error:
    while (cin >> users_number)
    {
    numbers.push_back(users_number);
    }

    // Now to sort them:
    sort(numbers.begin(), numbers.end());

    // After sorting, spit them out.
    for (unsigned int i = 0; i < numbers.size(); ++i)
    {
    cout << " " << numbers;
    }
    cout << endl;

    return EXIT_SUCCESS;
    }

    The purpose of this program is to work out how you want to
    enter the numbers. Once you have that working, add in calls
    to your linked list system.

    My understanding is that when you enter a lot of numbers on
    one line:
    12 34 56 23 45 33
    They will be placed into a buffer until you press Enter.
    At that point, whenever a "cin >> number" is performed,
    the next number in the buffer is given to the program.

    When I ran the program, I had to supply my operating
    system with an EOF character (like CTRL-D). It read
    every number on the line.

    --
    Thomas Matthews

    C++ newsgroup welcome message:
    http://www.slack.net/~shiva/welcome.txt
    C++ Faq: http://www.parashift.com/c -faq-lite
    C Faq: http://www.eskimo.com/~scs/c-faq/top.html
    alt.comp.lang.learn.c-c++ faq:
    http://www.raos.demon.uk/acllc-c /faq.html
    Other sites:
    http://www.josuttis.com -- C++ STL Library book
     
    Thomas Matthews, May 24, 2004
    #6
  7. massimo

    massimo Guest

    Re: Sorted Linked List - Final working version

    [Fully functional]. Thanks


    #include <iostream>
    using namespace std;


    struct Link
    {
    int data;
    Link* next;
    };

    class List
    {
    public:
    List() { head = NULL; }
    void add_item(int d);
    void display();
    private:
    Link* head;
    };

    void List::add_item(int d)
    {
    // test for empty list or data smaller than first item in list
    if (head == NULL || d <= head->data)
    {
    // add to beginning of list
    Link* temp = new Link;
    temp->data = d;
    temp->next = head;
    head = temp;
    }
    else
    {
    // Don't need to add to beginning of list
    // so loop though list looking for where to add
    Link* prev = head;
    Link* curr = head->next;
    // keep looping while not end of list and data bigger than
    currentitem
    while (curr != NULL && d > curr->data)
    {
    prev = prev->next;
    curr = curr->next;
    }
    // found place to add, add after previous item
    Link* temp = new Link;
    temp->data = d;
    temp->next = curr;
    prev->next = temp;
    }
    }

    void List::display() // display links
    {
    Link* curr = head; // set pointer to first link
    while (curr != NULL) // on last link stop
    {
    cout << curr -> data << endl; // print data
    curr = curr -> next; // move to next
    }
    }

    int main ()
    {
    int input = 1;

    List numbers; // make linked list

    cout << "Enter any numbers" << endl;
    while(input != 0)
    {
    cin >> input;
    numbers.add_item(input);
    }

    numbers.display();
    return 0;
    }

    //=========================================================================


    On 5/24/04 3:21 PM, in article BCD7C37F.19A1%, "massimo"
    <> wrote:

    > Hey john,
    >
    > Thank you very much. I totally understand the checking/sorting algorithm.
    >
    > I debugged the program and it compiles fine. I still believe I have some
    > problem with the display() and main(); I'm doing something wrong and I don't
    > see it!!
    > When it compiles it doesn't prompt me and if I enter the numbers, it just
    > return "Enter a number" for as many numbers I entered.
    > How do I space the number??
    > Let's say I want to enter:
    > 12 34 56 23 45 33 and the on enter I want the program to spit out the sorted
    > list.
    >
    > void List::display() // display links
    > {
    > Link *curr = head; // set pointer to first link
    > while (curr != NULL) // on last link stop
    > {
    > cout << curr -> data << endl; // print data
    > curr = curr -> next; // move to next
    > }
    > }
    >
    > int main ()
    > {
    > int input;
    >
    > List numbers; // make linked list
    >
    > cin >> input;
    > while(input >= 0)
    > {
    > cout << "Enter any numbers" << endl;
    > cin >> input;
    > numbers.add_item(input);
    > }
    >
    > numbers.display();
    >
    > return 0;
    > }
    >
    > Thanks,mass
    >
    >
    > On 5/24/04 2:28 PM, in article , "John Harrison"
    > <> wrote:
    >
    >>
    >> "massimo" <> wrote in message
    >> news:BCD7984D.193D%...
    >>> Hey,
    >>>
    >>> I wrote this program which should take the numbers entered and sort them
    >>> out. It doesn¹t matter what order, if decreasing or increasing.
    >>>
    >>> I guess I'm confused in the sorting part. Anyone has any advices??

    >>
    >> I would say to throw away the code and start again, but comments below.
    >>
    >>>
    >>> #include <iostream>
    >>> using namespace std;
    >>>
    >>> struct link
    >>> {
    >>> int data;
    >>> link *pNext;
    >>> link *pHead;
    >>> link *current;

    >>
    >> Why do you need a pointer back to head? What is current?
    >>
    >>> };
    >>>
    >>> class linkList
    >>> {
    >>> private:
    >>> link *pHead;
    >>> public:
    >>> linkList()
    >>> { pHead = NULL;}
    >>> void add_Item(int d);
    >>> void display();
    >>> };

    >>
    >> It's good that you have two seperate classes, one for the links and one for
    >> the list.
    >>
    >>>
    >>> void linkList::add_Item(int d)
    >>> {
    >>> link *pPrev;
    >>> link *pSucc;

    >>
    >> pSucc is uninitialised.
    >>
    >>>
    >>> pPrev = pHead;
    >>> while(true)
    >>> {
    >>> pPrev = pSucc;

    >>
    >> pSucc is still uninitialised.
    >>
    >>> pSucc = pSucc -> pNext;
    >>>

    >> pSucc is still uninitialised, program crashes here.
    >>
    >> OK, here how to do it properly. Here's some suitable classes
    >>
    >> struct Link
    >> {
    >> int data;
    >> Link* next;
    >> };
    >>
    >> class List
    >> {
    >> public:
    >> List() { head = NULL; }
    >> void add_item(int d);
    >> void display();
    >> private
    >> Link* head;
    >> };
    >>
    >> Now the thing is to think carefully about the add_item algorithm. Lets say
    >> we are going to add items in ascending order, smallest first, largest last.
    >> Clearly you are going to have to loop though the list looking for the place
    >> to add the new data. When will that loop end? One reason for the loop to end
    >> is when we find data in the list that is larger than the one we are adding,
    >> then we stop looping and add the item before the larger data. The other
    >> reason the loop might end is that we hit the end of the list, then we add an
    >> item at the end of the list. Now an important simplification is that both
    >> these cases are actually the same. In both cases we add a new link after the
    >> previous link. In the case when we hit the end of the list the previous link
    >> is the last link in the list so adding after that link is adding to the end
    >> of the list.
    >>
    >> Now special case is adding to an empty list or adding a number that is
    >> smaller than all the numbers in the list. In that case we add to the
    >> beginning of the list.
    >>
    >> Here's the code
    >>
    >> void List::add_item(int d)
    >> {
    >> // test for empty list or data smaller than first item in list
    >> if (head == NULL || d <= head->data)
    >> {
    >> // add to beginning of list
    >> Link* temp = new Link;
    >> temp->data = d;
    >> temp->next = head;
    >> head = temp;
    >> }
    >> else
    >> {
    >> // we don't need to add to beginning of list
    >> // so loop though list looking for where to add
    >> Link* prev = head;
    >> Link* curr = head->next;
    >> // keep looping while not end of list and data bigger than current
    >> item
    >> while (curr != NULL && d > curr->data)
    >> {
    >> prev = prev->next;
    >> curr = curr->next;
    >> }
    >> // found place to add, add after previous item
    >> Link* temp = new Link;
    >> temp->data = d;
    >> temp->next = curr;
    >> prev->next = temp;
    >> }
    >> }
    >>
    >> This is untested code so it might have bugs, but the main thing is you
    >> understand the algorithm.
    >>
    >> john
    >>
    >>

    >
     
    massimo, May 24, 2004
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Chris Ritchey
    Replies:
    7
    Views:
    489
    emerth
    Jul 10, 2003
  2. Andrew Clark

    linked list sorted insert

    Andrew Clark, Jul 10, 2003, in forum: C Programming
    Replies:
    3
    Views:
    12,466
    Stig Brautaset
    Jul 11, 2003
  3. CR
    Replies:
    5
    Views:
    3,184
    Brian MacBride
    Dec 24, 2003
  4. fool
    Replies:
    14
    Views:
    519
    Barry Schwarz
    Jul 3, 2006
  5. joshd
    Replies:
    12
    Views:
    679
    John Carson
    Oct 2, 2006
Loading...

Share This Page