By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,159 Members | 882 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 446,159 IT Pros & Developers. It's quick & easy.

linked list

P: 8
I was doing one of the question but my program was not working properly. Can anyone help me with it pliz........

Here is the question for the program

Question.
Part 1.

Add the function splitAt to split a linked list at a node whose Data is given.

Suppose you have a list with the elements
10 18 34 6 28 92 56 48

and the list is to be split at the node whose Data is 6. You will then have two sublists.
The original one with the elements 10 18 34 and another one with 6 28 92 56 48

a. Add the following function to the structure implementation for doubly linked lists
given in class.

Node* splitAt ( int item);
//splits the list at the node with the Data item into two sublists.
//precondition: The list must exist
//postcondition: pHead still points to the first node of the original list
//the function returns the head pointer for the second list

From your main, print the contents of the original list and the resulting sublists.
Ask the user for a value and insert a new node with that value after the second node on
the second list.

Display the resulting list.

Part 2.

a. Add the following function to the template class List implementation given in class.

void splitAt ( List <Type> &secondList, const Type &item);
//splits the list at the node with the Data item into two sublists.

Note: Notice that the splitAt function receives two parameters by reference. The first
argument is and object of type List. You DONíT need any other modifications to the
class. Just add this new function.

The keyword const just means that the value of item cannot be modified within the
function.

Consider the following statements:

List <int> myList;
List <int> otherList;

they create two objects of type List.
Suppose myList is a list with the elements 34 65 18 39 27 89 12 (in this order). The
Statement

myList.splitAt (otherList, 18);

splits myList into two sublist: myList has the elements 34 65 and otherList has the
elements 18 39 27 89 12.

Write a driver program to print the contents of the original list and the resulting sublists.
Ask the user for a value and insert a new node with that value after the second node on
the second list.

Display the resulting list.

DO NOT VALIDATE ANY KEYBOARD ENTRY UNLESS OTHERWISE SPECIFIED

My program that i have written

#include <iostream.h>
#include <stdlib.h>
#include <string>

struct NODE {
NODE *pNext;
NODE *pPrev;
int nData;
};

NODE *pHead=NULL, *pTail=NULL;


void AppendNode(NODE *pNode);
void InsertNode(NODE *pNode, NODE *pAfter);
void RemoveNode(NODE *pNode);
void DeleteAllNodes( );
NODE *splitAt( int item );

int main( )
{
NODE *pNode;

for (int i=0; i<100; i++){
pNode = new NODE;
pNode->nData = i;
AppendNode ( pNode );
}

cout<<"\nThe contents of the original list are:\n";

for (pNode = pHead; pNode != NULL; pNode = pNode->pNext)
cout << "\t" << pNode->nData<<endl;

system ("pause");
return 0;
}

void AppendNode(NODE *pNode)
{
if (pHead == NULL) {
pHead = pNode;
pNode->pPrev = NULL;
}
else {
pTail->pNext = pNode;
pNode->pPrev = pTail;
}
pTail = pNode;
pNode->pNext = NULL;
}


void InsertNode(NODE *pNode, NODE *pAfter)
{
pNode->pNext = pAfter->pNext;
pNode->pPrev = pAfter;

if (pAfter->pNext != NULL)
pAfter->pNext->pPrev = pNode;
else
pTail = pNode;

pAfter->pNext = pNode;
}


void RemoveNode(NODE *pNode)
{
if (pNode->pPrev == NULL)
pHead = pNode->pNext;

else
pNode->pPrev->pNext = pNode->pNext;

if (pNode->pNext == NULL)
pTail = pNode->pPrev;

else
pNode->pNext->pPrev = pNode->pPrev;

delete pNode;
}


void DeleteAllNodes( )
{
while (pHead != NULL)
RemoveNode(pHead);
}

NODE* splitAt(int item )
{
}
Oct 3 '06 #1
Share this Question
Share on Google+
6 Replies


100+
P: 293
D_C
I assume there is a uniqueness constraint for your lists (i.e. you can't have 2 or 3 copies of 6 in the list, otherwise which one would you split at?).

Find the split element in the list. The previous element's next pointer needs to be nullified, and the split element's previous pointer needs to be nullified. Then return &split_element. You have a special case when you split the head element, but not the tail element (unless the head is the tail).
Oct 4 '06 #2

P: 8
so u mean that the code that i have written is not correct....and i have modify my program more.
Oct 4 '06 #3

P: 2
Write a driver program to print the contents of the original list and the resulting sublists.
Ask the user for a value and insert a new node with that value after the second node on
the second list.

can anyone provide solution to the avove implementation part.
i mean how to insert the :
void InsertNode(NODE *pNode, NODE *pAfter)

how to call this funtion from main(). i have problem solving that part. i have solved the rest.
regards
fanda
Oct 4 '06 #4

P: 2
void List::SplitList(const int iSplitValue)
{
Node *pCurr = NULL;

for(pCurr = pHead; pCurr; pCurr = pCurr->pNext)
if(pCurr->pNext->iValue == iSplitValue)
{
pNewHead = pCurr->pNext;
pCurr->pNext = NULL;
}
}
//hope this helps you in splitting the linked list
Oct 5 '06 #5

100+
P: 293
D_C
so u mean that the code that i have written is not correct....and i have modify my program more.
You didn't write any code for the splitAt method, so it correctly does nothing. Yes, you need more code. After looking at fanda's code above, I think it's missing something.

For example, create a list with one element, say 5. Split it at that element. That should break fanda's code. Look at the head pointer, before and after. Let <- be pPrev, -> be pNext, and <-> be two nodes pointing to each other with pPrev, and pNext respectively.

Before
Expand|Select|Wrap|Line Numbers
  1. NULL <- head <-> 5 -> NULL
After
Expand|Select|Wrap|Line Numbers
  1. NULL <- head -> NULL
  2. NULL <- secondHead <-> 5 -> NULL
Expand|Select|Wrap|Line Numbers
  1. Node* splitAt(const int nodeValue)
  2. {
  3.   Node* pCursor = head;
  4.   while(pCursor != NULL)
  5.   {
  6.     if(pCursor->nData == nodeValue)
  7.     {                         // if we found the split element
  8.       if(pCursor == pHead)    // if we split at the head
  9.         pHead = NULL;         // the head becomes null
  10.       pTail = pCursor->pPrev; // tail is the last node before split
  11.       return pCursor;         // return pointer to new head
  12.     }
  13.     pCursor = pCursor->pNext; // else go to next node
  14.   }
  15.   return NULL;                // did not find element
  16. }
Oct 5 '06 #6

P: 8
I have written the code again. Is this a correct program for the question?

Program modified

Expand|Select|Wrap|Line Numbers
  1. #include <iostream.h>
  2. #include <stdlib.h>
  3. #include <string>
  4.  
  5. struct NODE
  6. {
  7.    NODE *pNext;
  8.    NODE *pPrev;
  9.    int nData;
  10. };
  11.  
  12. NODE *pHead=NULL, *pTail=NULL;
  13. NODE *pNewHead;
  14.  
  15.  
  16. void AppendNode(NODE *pNode);
  17. void InsertNode(NODE *pNode, NODE *pAfter);
  18. void RemoveNode(NODE *pNode);
  19. void DeleteAllNodes( );
  20. NODE *splitAt( int item );
  21.  
  22. int main( )
  23. {
  24.    NODE *pNode;
  25.    int item;
  26.    int num;
  27.   char res;
  28.    cout <<"\n\n\t do u want to insert a value [Y/N]???" ;
  29.    cin >>res;
  30.    while(res =='y'|| res =='Y')
  31.    {
  32.     cout <<"enter the number that u want to append:";
  33.     cin >> num;
  34.       pNode = new NODE;
  35.       pNode->nData = num;
  36.       AppendNode ( pNode );
  37.       cout <<"\n\n\t do u want to insert another value [Y/N]???" ;
  38.       cin >>res;
  39.    }
  40.  
  41.    cout<<"\nThe contents of the original list are:\n";
  42.  
  43.    for (pNode = pHead; pNode != NULL; pNode = pNode->pNext)
  44.        cout << "\t" << pNode->nData<<endl;
  45.  
  46.        cout <<"from which item u wish to split the linked list :";
  47.        cin  >>item;
  48.  
  49.  
  50.        splitAt(item);
  51.           cout<<"\nThe contents of the first splited list are:\n";
  52.        for (pNode = pHead; pNode != NULL; pNode = pNode->pNext)
  53.        cout << "\t" << pNode->nData<<endl;
  54.        cout<<"\nThe contents of the second splited list are:\n";
  55.          for (pNode = pNewHead; pNode != NULL; pNode = pNode->pNext)
  56.           cout <<"\t" << pNode->nData<<endl;
  57.  
  58.  
  59.    system ("pause");
  60.    return 0;
  61. }
  62.  
  63. void AppendNode(NODE *pNode)
  64. {
  65.    if (pHead == NULL)
  66.    {
  67.       pHead = pNode;
  68.       pNode->pPrev = NULL;
  69.    }
  70.    else {
  71.       pTail->pNext = pNode;
  72.       pNode->pPrev = pTail;
  73.    }
  74.    pTail = pNode;
  75.    pNode->pNext = NULL;
  76. }
  77.  
  78. void InsertNode(NODE *pNode, NODE *pAfter)
  79. {
  80.    pNode->pNext = pAfter->pNext;
  81.    pNode->pPrev = pAfter;
  82.  
  83.    if (pAfter->pNext != NULL)
  84.       pAfter->pNext->pPrev = pNode;
  85.    else
  86.       pTail = pNode;
  87.  
  88.    pAfter->pNext = pNode;
  89. }
  90.  
  91. void RemoveNode(NODE *pNode)
  92. {
  93.    if (pNode->pPrev == NULL)
  94.        pHead = pNode->pNext;
  95.  
  96.    else
  97.       pNode->pPrev->pNext = pNode->pNext;
  98.  
  99.    if (pNode->pNext == NULL)
  100.       pTail = pNode->pPrev;
  101.  
  102.    else
  103.       pNode->pNext->pPrev = pNode->pPrev;
  104.  
  105.    delete pNode;
  106. }
  107.  
  108. void DeleteAllNodes( )
  109. {
  110.    while (pHead != NULL)
  111.  
  112.       RemoveNode(pHead);
  113. }
  114.  
  115.  
  116. NODE* splitAt(int item )
  117. {
  118.  NODE *pCurr = NULL;
  119.  
  120. for(pCurr = pHead; pCurr!=NULL; pCurr = pCurr->pNext)
  121. {
  122.   if(pCurr->pNext->nData == item)
  123.   {
  124.    pNewHead = pCurr->pNext;
  125.    pCurr->pNext = NULL;
  126.   }
  127. }
  128. }
  129.  
  130.  
Oct 6 '06 #7

Post your reply

Sign in to post your reply or Sign up for a free account.