Linked list question....again

**dP munky** · 04-02-2003

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

**Stoned_Coder** · 04-02-2003

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.

**dP munky** · 04-03-2003

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;
        }
    }

}

**elad** · 04-03-2003

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.

Thread: Linked list question....again

Thread Tools

Search Thread

Display

Linked list question....again

Similar Threads

Linked List Not Saving Value as Int

linked list question

singly linked circular list

singly linked list