Linked List Problem

Please support our C++ advertiser: Intel Parallel Studio Home
Reply

Join Date: Nov 2007
Posts: 22
Reputation: d0ugg is an unknown quantity at this point 
Solved Threads: 0
d0ugg d0ugg is offline Offline
Newbie Poster

Linked List Problem

 
0
  #1
Nov 4th, 2007
Hello everyone,

I need to load a multi-word strings from a file to a linked list in one of my programs, and i'm not sure how to do that.

my text file looks like this- (the name of the text file is: names.txt)

Linda
Martinho
Marla
Jose
Mary
Luka
Joseph
Thiago
Ruba

here is some of my code so far...
  1.  
  2.  
  3.  
  4. #include <iostream>
  5. #include <cassert>
  6. #include <String>
  7. #include <stdio.h>
  8. #include <stdlib.h>
  9. using namespace std;
  10.  
  11. template <class TYPE>
  12. struct NODE
  13. {
  14. TYPE data; //Data Item
  15. NODE<TYPE> *next;
  16. };
  17.  
  18. template<class TYPE>
  19. class multiword
  20. {
  21. protected:
  22. int count; //Variable to store the values of the numbers
  23. NODE<TYPE> *first; //pointer to the first NODE
  24. public:
  25. class NotFound {};
  26. void Initialize(); //Initialize the list with no values
  27. bool Empty(); //Check if the list is empty
  28. void Destroy();
  29. void fillNames(ifstream& inFile, multiword<TYPE>& cList); //Delete every value of the list
  30. int binarysearch(const TYPE& item); //Binary search
  31. void additem(const TYPE& add); //Add a value
  32. void Insertion(); //Insertion
  33. void display(); //Display
  34. multiword(); //Constructor(no-arg)
  35. ~multiword(); //Destructor
  36. };
  37.  
  38. template<class TYPE>
  39. void multiword<TYPE>::fillNames(ifstream& inFile, multiword<TYPE>& cList)
  40. {
  41. string firstN;
  42. int i;
  43.  
  44. TYPE temp;
  45. const int number = 10
  46.  
  47. for(i = 0; i < number; i++)
  48. {
  49. inFile>>firstN;
  50. temp.setName(firstN);
  51. cList.insertAt(i, temp);
  52. }
  53. }
  54.  
  55. template<class TYPE> //Check if the list is empty
  56. bool multiword<TYPE>::Empty()
  57. {
  58. return(first == NULL);
  59. }
  60.  
  61. template<class TYPE> //Constructor
  62. multiword<TYPE>::multiword()
  63. {
  64. first = NULL;
  65. count = 0;
  66. }
  67.  
  68. template<class TYPE> //Destructor
  69. multiword<TYPE>::~multiword()
  70. {
  71. Destroy();
  72. }
  73.  
  74. template<class TYPE>
  75. void multiword<TYPE>::Insertion()
  76. {
  77. nodeType<TYPE> *lastInOrder;
  78. nodeType<TYPE> *firstOutOfOrder;
  79. nodeType<TYPE> *current;
  80. nodeType<TYPE> *trailCurrent;
  81.  
  82. lastInOrder = first;
  83.  
  84. if(first = NULL)
  85. cerr << "Cannot sort an empty list." << endl;
  86. else
  87. if(first->link == NULL)
  88. cout << "The list of length1, it is already in order." << endl;
  89. else
  90. while(lastInOrder->link !=NULL)
  91. {
  92. firstOutOfOrder = lastInOrder->link;
  93. if(firstOutOfOrder->info < first->info)
  94. {
  95. lastInOrder->link = firstOutOfOrder->link;
  96. firstOutOfOrder->link = first;
  97. first = firstOutOfOrder;
  98. }
  99. else
  100. {
  101. trailCurrent = first;
  102. current = first->link;
  103. while(current->info < firstOutOfOrder->info)
  104. {
  105. trailCurrent = current;
  106. current = current ->link;
  107. }
  108.  
  109. if(current != firstOutOfOrder)
  110. {
  111. lastInOrder->link = firstOutOfOrder->link;
  112. firstOutOfOrder->link = current;
  113. trailCurrent->link = firstOufOfOrder;
  114. }
  115. else
  116. lastInOrder = lastInOrder->link
  117. }
  118. }
  119. }
  120.  
  121.  
  122. template<class TYPE>
  123. int multiword<TYPE>::binarysearch(const TYPE& item)
  124. {
  125. int first = 0;
  126. int last = length -1;
  127. int mid;
  128.  
  129. bool found = false;
  130.  
  131. while(first <= last && !found)
  132. {
  133. mid = (first + last) / 2;
  134.  
  135. if(list[mid] == item)
  136. found = true;
  137. else
  138. if(list[mid] > item)
  139. last = mid -1;
  140. else
  141. first = mid + 1;
  142. }
  143. if(found)
  144. return mid;
  145. else
  146. return -1;
  147. }
  148.  
  149. template<class TYPE> //Destroy every element on the list
  150. void multiword<TYPE>::Destroy()
  151. {
  152. NODE<TYPE> *temp; //deallocates memory
  153. while(first != NULL) //while there are value in the list
  154. {
  155. temp = first; //set temp to the first value in the list
  156. first = first->next; //put first to the next value
  157. delete temp; //delete memory
  158. }
  159. count = 0;
  160. }
  161.  
  162. template<class TYPE> //Initialize the list
  163. void multiword<TYPE>::Initialize()
  164. {
  165. Destroy(); //If any values are found, remove them.
  166. }

Thank you very much in advance,

Doug
Last edited by d0ugg; Nov 4th, 2007 at 6:42 pm.
Reply With Quote Quick reply to this message  
Join Date: Oct 2007
Posts: 1,951
Reputation: Duoas has much to be proud of Duoas has much to be proud of Duoas has much to be proud of Duoas has much to be proud of Duoas has much to be proud of Duoas has much to be proud of Duoas has much to be proud of Duoas has much to be proud of 
Solved Threads: 214
Featured Poster
Duoas's Avatar
Duoas Duoas is offline Offline
Posting Virtuoso

Re: Linked List Problem

 
0
  #2
Nov 4th, 2007
You need to be just a little more careful with names
Insertion() is a bad name because it is not obvious that it sorts the list. InsertionSort() is a good name.

Destroy() is not a good name because it doesn't destroy your object; it only deletes every item in the list. Name it something like Clear() or MakeEmpty(). By the way, Initialize() has the same logical functionality: both clear the list if not already emtpy. I would get rid of Initialize() and just use Clear() or whatever you name it. Actual initialization already occurs properly in the constructor.

Be careful with your types
In general, you should not assume that TYPE has a member function setName(). If you are just making a linked list of strings, there is no real reason to create a new class just to hold it. Just use std::string. Also, in template declarations, use the word typename instead of class. (Yes, yes, I know... semantics. Even so...)

More on fillNames()
You are trying to do two things here: initialize *this from file and initialize some that (which you named cList). If you need two copies of the multiword list, make a copy constructor and copy it that way; Don't force your user to fill two multiword lists just to load from file.

Also, you are using a member function named insertAt() which you have not defined to exist in the multiword class.

I recommend that you get rid of the cList argument and just load words from file into *this's list.

Lastly, you should not hardcode the number of lines in your file. What if you later want to load a list of names 100 names long? Or two? Just read names and append them to the end of the list as long as there are lines in the file.


Oy, that's enough for now. I haven't looked over your sort or search algorithms... but you seem to have a pretty good start. Work on straightening up those things I mentioned and then come back with compiler errors or what is not working right when you use the class.

Good luck.
Last edited by Duoas; Nov 4th, 2007 at 9:13 pm.
Reply With Quote Quick reply to this message  
Join Date: Nov 2007
Posts: 22
Reputation: d0ugg is an unknown quantity at this point 
Solved Threads: 0
d0ugg d0ugg is offline Offline
Newbie Poster

Re: Linked List Problem

 
0
  #3
Nov 4th, 2007
Hey,
Thank you for the help...
I will work on those ideas that you gave me.
Doug
Reply With Quote Quick reply to this message  
Join Date: Nov 2007
Posts: 22
Reputation: d0ugg is an unknown quantity at this point 
Solved Threads: 0
d0ugg d0ugg is offline Offline
Newbie Poster

Re: Linked List Problem

 
0
  #4
Nov 4th, 2007
Hey,

So I changed a couple things that you told me already, but I have no idea how to do what you told me on the fillname();

Right now it looks like this:
  1. template<typename TYPE>
  2. void multiword<TYPE>::fillNames(ifstream& inFile, multiword<TYPE>& cList)
  3. {
  4. string firstN;
  5. int i;
  6.  
  7. TYPE temp;
  8. const int number = 10
  9.  
  10. for(i = 0; i < number; i++)
  11. {
  12. inFile>>firstN;
  13. temp.setName(firstN);
  14. cList.insertAt(i, temp);
  15. }
  16. }

I'm not sure why I added setName and insertAt. Is there any other way to add the text file without calling other classes such as setname and insertat?

Thank you,

Doug
Reply With Quote Quick reply to this message  
Join Date: Oct 2007
Posts: 1,951
Reputation: Duoas has much to be proud of Duoas has much to be proud of Duoas has much to be proud of Duoas has much to be proud of Duoas has much to be proud of Duoas has much to be proud of Duoas has much to be proud of Duoas has much to be proud of 
Solved Threads: 214
Featured Poster
Duoas's Avatar
Duoas Duoas is offline Offline
Posting Virtuoso

Re: Linked List Problem

 
0
  #5
Nov 4th, 2007
Think about the types of things you have.

You have a NODE class, which is used by the multiword class to store a list of some unspecified TYPE.

The fillNames() function shouldn't know or care what type of thing TYPE is. Just read it from file and store it.

Give it some thought...


Now, when it is time to use your linked list class, what type of thing are you storing in a list? Does it matter if the multiword class has any idea what type that is? Should I be able to say:
multiword<int> my_int_list;
or:
multiword<bool> my_bool_list;
or:
multiword<Employee> my_employee_list; (where Employee is some class defined elsewhere with the >> and << I/O operators properly overloaded)

Think about it.
Last edited by Duoas; Nov 4th, 2007 at 11:57 pm.
Reply With Quote Quick reply to this message  
Reply

This thread is more than three months old.
Perhaps start a new thread instead?
Message:


Thread Tools Search this Thread



About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC