sorting the nodes

Discussion in 'C++' started by jw, Dec 6, 2005.

  1. jw

    jw Guest

    hi all,i have such 2 classes for a linked list,
    class Node{
    private:
    int value;
    Node *next;
    public:
    Node()
    {
    next=NULL;
    }
    friend class List;
    };
    class List{
    private:
    Node *head,*tail,*TOP;
    void append(Node *add);
    public:
    List()
    {
    TOP=new Node;
    head=tail=TOP;
    }
    void sortAll();...
    --------
    for ex i have this 4-15-17-3-5-1 in the list,how can i sort the
    nodes(not the numbers in the nodes),i ll use insertion sort.
    jw, Dec 6, 2005
    #1
    1. Advertising

  2. jw

    Howard Guest

    "jw" <> wrote in message
    news:...
    > hi all,i have such 2 classes for a linked list,
    > class Node{
    > private:
    > int value;
    > Node *next;
    > public:
    > Node()
    > {
    > next=NULL;
    > }
    > friend class List;
    > };
    > class List{
    > private:
    > Node *head,*tail,*TOP;
    > void append(Node *add);
    > public:
    > List()
    > {
    > TOP=new Node;
    > head=tail=TOP;
    > }
    > void sortAll();...
    > --------
    > for ex i have this 4-15-17-3-5-1 in the list,how can i sort the
    > nodes(not the numbers in the nodes),i ll use insertion sort.
    >


    You already said how you would do it: use an insertion sort. Read your
    textbook on how to do an insertion sort. (But note: you generally don't
    call an insertion sort after the list is already built. It's something
    that's usually done as you read in or otherwise enter the data, and insert
    it into the list. Thus the term "insertion".)

    BTW: what is the tail pointer for? If you've got a singly-linked list like
    this (where each node only has a next pointer), then there's no need for a
    tail pointer, since the last (tail) node is identifiable by the fact that
    its next pointer is NULL. And it's pretty useless to have, since you have
    to maintain it, and can't use it for much due to the fact that you don't
    have a previous pointer, so you can't manuipulate the tail without
    traversing the list anyway.

    And what's "TOP"?

    -Howard
    Howard, Dec 6, 2005
    #2
    1. Advertising

  3. jw

    jw Guest

    Howard wrote:
    > "jw" <> wrote in message
    > news:...
    > > hi all,i have such 2 classes for a linked list,
    > > class Node{
    > > private:
    > > int value;
    > > Node *next;
    > > public:
    > > Node()
    > > {
    > > next=NULL;
    > > }
    > > friend class List;
    > > };
    > > class List{
    > > private:
    > > Node *head,*tail,*TOP;
    > > void append(Node *add);
    > > public:
    > > List()
    > > {
    > > TOP=new Node;
    > > head=tail=TOP;
    > > }
    > > void sortAll();...
    > > --------
    > > for ex i have this 4-15-17-3-5-1 in the list,how can i sort the
    > > nodes(not the numbers in the nodes),i ll use insertion sort.
    > >

    >
    > You already said how you would do it: use an insertion sort. Read your
    > textbook on how to do an insertion sort. (But note: you generally don't
    > call an insertion sort after the list is already built. It's something
    > that's usually done as you read in or otherwise enter the data, and insert
    > it into the list. Thus the term "insertion".)
    > i have to first create the list and then sort it by swaping the nodes
    > BTW: what is the tail pointer for? If you've got a singly-linked list like
    > this (where each node only has a next pointer), then there's no need for a
    > tail pointer, since the last (tail) node is identifiable by the fact that
    > its next pointer is NULL. And it's pretty useless to have, since you have
    > to maintain it, and can't use it for much due to the fact that you don't
    > have a previous pointer, so you can't manuipulate the tail without
    > traversing the list anyway.
    >
    > And what's "TOP"?

    TOP is a pointer that is not necessary but i use it as an empty node
    before the head
    >
    > -Howard
    jw, Dec 6, 2005
    #3
  4. jw

    jw Guest

    jw wrote:
    > Howard wrote:
    > > "jw" <> wrote in message
    > > news:...
    > > > hi all,i have such 2 classes for a linked list,
    > > > class Node{
    > > > private:
    > > > int value;
    > > > Node *next;
    > > > public:
    > > > Node()
    > > > {
    > > > next=NULL;
    > > > }
    > > > friend class List;
    > > > };
    > > > class List{
    > > > private:
    > > > Node *head,*tail,*TOP;
    > > > void append(Node *add);
    > > > public:
    > > > List()
    > > > {
    > > > TOP=new Node;
    > > > head=tail=TOP;
    > > > }
    > > > void sortAll();...
    > > > --------
    > > > for ex i have this 4-15-17-3-5-1 in the list,how can i sort the
    > > > nodes(not the numbers in the nodes),i ll use insertion sort.
    > > >

    > >
    > > You already said how you would do it: use an insertion sort. Read your
    > > textbook on how to do an insertion sort. (But note: you generally don't
    > > call an insertion sort after the list is already built. It's something
    > > that's usually done as you read in or otherwise enter the data, and insert
    > > it into the list. Thus the term "insertion".)

    i have to first create the list and then sort it by swaping the nodes
    > > BTW: what is the tail pointer for? If you've got a singly-linked list like
    > > this (where each node only has a next pointer), then there's no need for a
    > > tail pointer, since the last (tail) node is identifiable by the fact that
    > > its next pointer is NULL. And it's pretty useless to have, since you have
    > > to maintain it, and can't use it for much due to the fact that you don't
    > > have a previous pointer, so you can't manuipulate the tail without
    > > traversing the list anyway.
    > >
    > > And what's "TOP"?

    > TOP is a pointer that is not necessary but i use it as an empty node
    > before the head
    > >
    > > -Howard
    jw, Dec 6, 2005
    #4
  5. jw

    Howard Guest

    "jw" <> wrote in message
    news:...

    >> > > for ex i have this 4-15-17-3-5-1 in the list,how can i sort the
    >> > > nodes(not the numbers in the nodes),i ll use insertion sort.


    >> > You already said how you would do it: use an insertion sort. Read your
    >> > textbook on how to do an insertion sort. (But note: you generally
    >> > don't
    >> > call an insertion sort after the list is already built. It's something
    >> > that's usually done as you read in or otherwise enter the data, and
    >> > insert
    >> > it into the list. Thus the term "insertion".)


    > i have to first create the list and then sort it by swaping the nodes


    Then that's not an insertion sort. An insertion sort inserts the data in
    the correct location in the first place.

    Decide which sort you want to use (e.g., bubble sort), then implement that.
    Your textbook (or class notes) should show how to implement each of the most
    common sorts.

    If you have a C++ language problem while implementing your sort, post the
    code here, and explain the problem you're having with it. (But don't expect
    us to simply write the code for you.)

    -Howard
    Howard, Dec 6, 2005
    #5
  6. jw

    jw Guest

    Howard wrote:
    > "jw" <> wrote in message
    > news:...
    >
    > >> > > for ex i have this 4-15-17-3-5-1 in the list,how can i sort the
    > >> > > nodes(not the numbers in the nodes),i ll use insertion sort.

    >
    > >> > You already said how you would do it: use an insertion sort. Read your
    > >> > textbook on how to do an insertion sort. (But note: you generally
    > >> > don't
    > >> > call an insertion sort after the list is already built. It's something
    > >> > that's usually done as you read in or otherwise enter the data, and
    > >> > insert
    > >> > it into the list. Thus the term "insertion".)

    >
    > > i have to first create the list and then sort it by swaping the nodes

    >
    > Then that's not an insertion sort. An insertion sort inserts the data in
    > the correct location in the first place.
    >
    > Decide which sort you want to use (e.g., bubble sort), then implement that.
    > Your textbook (or class notes) should show how to implement each of the most
    > common sorts.

    ok the sort tecnique is not important now,the thing i have to is to
    sort the nodes,and i dont expect a code only a way
    >
    > If you have a C++ language problem while implementing your sort, post the
    > code here, and explain the problem you're having with it. (But don't expect
    > us to simply write the code for you.)
    >
    > -Howard
    jw, Dec 6, 2005
    #6
  7. jw

    Howard Guest

    "jw" <> wrote in message
    news:...
    >
    > Howard wrote:
    >> "jw" <> wrote in message
    >> news:...
    >>
    >> >> > > for ex i have this 4-15-17-3-5-1 in the list,how can i sort the
    >> >> > > nodes(not the numbers in the nodes),i ll use insertion sort.

    >>
    >> >> > You already said how you would do it: use an insertion sort. Read
    >> >> > your
    >> >> > textbook on how to do an insertion sort. (But note: you generally
    >> >> > don't
    >> >> > call an insertion sort after the list is already built. It's
    >> >> > something
    >> >> > that's usually done as you read in or otherwise enter the data, and
    >> >> > insert
    >> >> > it into the list. Thus the term "insertion".)

    >>
    >> > i have to first create the list and then sort it by swaping the nodes

    >>
    >> Then that's not an insertion sort. An insertion sort inserts the data in
    >> the correct location in the first place.
    >>
    >> Decide which sort you want to use (e.g., bubble sort), then implement
    >> that.
    >> Your textbook (or class notes) should show how to implement each of the
    >> most
    >> common sorts.


    > ok the sort tecnique is not important now,the thing i have to is to
    > sort the nodes,and i dont expect a code only a way
    >>


    That's what your textbook and class notes are for. But it involves two
    things: traversing the list somehow, and swapping nodes that are out of
    order.

    For something like a bubble sort, you effectively traverse the list multiple
    times, using nested loops. Something like this:

    for each node I in the last _except_ the last one:
    for each node J _after_ I in the list:
    if the data value in I is greater than the data value in J, then:
    swap nodes I and J

    (For descending sort, change "greater than" to "less than".)

    So you need to know how to swap in a singly linked list. Do you? It
    requires four pointers: one for each node to be swapped, and one for each of
    the nodes _preceding_ the nodes to be swapped (because you need to modify
    their "next" pointers, right?). NOTE that if your node I in the algorithm
    above is the head node, then when you go to swap it, there IS NO preceding
    node! In that case, you'll need to identify that special case and modify
    the "head" pointer instead.

    Work it out on paper, if your textbook or class notes don't contain the
    details. Then turn the design into some real code.

    -Howard
    Howard, Dec 6, 2005
    #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. asd
    Replies:
    3
    Views:
    424
    Arnaud Berger
    May 23, 2005
  2. gavnosis
    Replies:
    0
    Views:
    498
    gavnosis
    Aug 2, 2003
  3. Timo Nentwig

    selecting nodes between other nodes

    Timo Nentwig, Jun 16, 2004, in forum: XML
    Replies:
    1
    Views:
    390
    Patrick TJ McPhee
    Jun 17, 2004
  4. Johnny Ooi

    Looking A Nodes From Within Nodes

    Johnny Ooi, Nov 13, 2004, in forum: XML
    Replies:
    10
    Views:
    642
    Johnny Ooi
    Nov 14, 2004
  5. Replies:
    2
    Views:
    376
Loading...

Share This Page