Linked list question....again

This is a discussion on Linked list question....again within the C++ Programming forums, part of the General Programming Boards category; im working on a linked list assignment....AGAIN (god i hate my teacher) anyway, he said we had to write these ...

  1. #1
    cereal killer dP munky's Avatar
    Join Date
    Nov 2002
    Posts
    655

    Linked list question....again

    im working on a linked list assignment....AGAIN (god i hate my teacher) anyway, he said we had to write these two new functions...

    Code:
    //function reverses phone book, cannot be altered
    const PhoneBook* ReversePhoneBook(const PhoneBook *headP)
    {
    	//take phone book, traverse through and reverse the order
    }
    
    
    //function combines 2 phone books.
    void CombinePhoneBook(PhoneBook **headPP1, const PhoneBook *headP2)
    {	//take phone book 2 and add it to phone book 1
    	//if anything matches, throw it out
    }
    the linked list im dealing with is a singlely linked, meaning there is only one pointer pointing to the next node, none pointing to the previous, can anyone help get me going on these functions, like usual im kinda confused where to start
    guns dont kill people, abortion clinics kill people.

  2. #2
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    how would you do it on paper. Ignore the code for a minute and think about the problem. Try to write a pseudocode algorithm that can solve the problem on paper. If you get stuck then read this but i urge you to try and figure it out yourself first. Reversing is particularly simple. Merging not much harder.
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

  3. #3
    cereal killer dP munky's Avatar
    Join Date
    Nov 2002
    Posts
    655
    this is what i have so far......am i heading in the right direction

    Code:
    const PhoneBook* ReversePhoneBook(const PhoneBook *headP)
    {
        PhoneBook *first = (PhoneBook*) headP;
        PhoneBook *temp = new PhoneBook;
        PhoneBook *newlist = temp;
        PhoneBook *last = 0;
    
        while(headP->next != 0)
        {
            headP = headP->next;
        }
    
        StringCopy(temp->data.name, headP->data.name);
        temp = temp->next;
        
        while(last != first)
        {
            while(last->next != first)
            {
                temp = temp->next;
            }
        }
    
    }
    guns dont kill people, abortion clinics kill people.

  4. #4
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    Here's a possible approach to the reversal problem.

    Step 1
    using a loop with a pointer called current find the last entry in original phonebook and assign current to a pointer called last

    Step 2
    declare a new node. Give the new node the data in current and assign the new node to the head of new PhoneBook called reversePhonebook

    Step 3
    use a loop starting at head of original phonebook and search original phonebook until current->next == last.

    Step 4
    assign values in current to a new node and add the new node to the end of reversePhoneBook

    Step 5
    assign current to last

    Step 6
    repeat Step 3, 4, 5 until head->next = last.


    and for merging two phone books into a third you could try something like this:

    Assumption: pb1 and pb2 will be merged into pb3 in sequence based on member x avoiding duplicate values of x. c1, c2, c3 are node pointers for pb1 pb2, pb3 respectively and start out at head

    Step 1
    if c1x == c2x assign values in c1 to new node and then assign c1-> next to c1

    Step 2
    else if c1x < c2x assign values in c1 to new node and then assign c1 next to c1

    Step 3
    else if c1x > c2x assign values in c2 to new and then assign c2 next to c2

    Step 4
    assign new node to c3 next if c3 not NULL and then assign c3 next to c3. if c3 == NULL assign new node to c3

    Step 5
    repeat step 1, 2, 3, 4 as long as c1 and c2 not NULL then just dump the rest of the pb that isn't empty into the new phone book in current order using simple loop.

    and for merging one phone book into another:

    Assumptions: add pb2 to pb1 sequentially based on member x without destroying pb2. Neither pb2 nor pb1 are empty to begin with. c1 and c2 are node pointers that start at head of each phonebook. prev is node pointer starting at pb1 head

    Scenario 1
    if c2x == c1x
    assign c2 next to c2
    assign prev next to prev if c1 != head
    and then assign c1 next to c1

    Scenario 2
    if c2x > c1x
    assign prev next to prev if c1 != head
    and then c1 next to c1

    Scenario 3
    if c2x < c1x and
    if c1 == c1 head
    assign values in c2 to new node
    assign new node to c1 head
    assign c1 to head next
    assign head to c1
    then c2 next to c2
    else if c1 != c1 head
    assign c2 values to a new node
    assign c2 next to c2
    assign new node to prev next
    assign c1 to new node next
    assign prev next to prev

    Scenario 4
    if c2 == NULL
    stop

    Scenario 5
    if c1 next == NULL and and c2 != NULL
    assign values in c2 to new node
    add new node c1 next
    assign c1 next to c1
    assign c2 next to c2
    repeat Scenario 5 until c2 == NULL


    I haven't had time to review all this or to try writing code myself, but it should give you an idea of how to get started.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Linked List Not Saving Value as Int
    By bar338 in forum C Programming
    Replies: 4
    Last Post: 05-04-2009, 07:53 PM
  2. linked list question
    By brb9412 in forum C Programming
    Replies: 16
    Last Post: 01-04-2009, 03:05 PM
  3. singly linked circular list
    By DarkDot in forum C++ Programming
    Replies: 0
    Last Post: 04-24-2007, 08:55 PM
  4. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21