Posted By

DrPepper on 11/10/11


Tagged


Versions (?)

[CISP 430] Chaining Hash Table (link2.template )


 / Published in: C++
 

  1. // FILE: link2.template
  2. // IMPLEMENTS: The ten template functions of the linked list toolkit
  3. // (see link2.h). Note that this file is not compiled on its own.
  4. // Instead, this file is included with an include directive at the bottom
  5. // of link2.h.
  6.  
  7. #include <assert.h> // Provides assert
  8. #include <stdlib.h> // Provides NULL and size_t
  9.  
  10. template <class Item>
  11. size_t list_length(Node<Item>* head_ptr)
  12. // Library facilities used: stdlib.h
  13. {
  14. Node<Item> *cursor;
  15. size_t answer;
  16.  
  17. answer = 0;
  18. for(cursor = head_ptr; cursor != NULL; cursor = cursor->link)
  19. answer++;
  20.  
  21. return answer;
  22. }
  23.  
  24. template <class Item>
  25. void list_head_insert(Node<Item>*& head_ptr, const Item& new_item)
  26. {
  27. Node<Item> *insert_ptr;
  28.  
  29. insert_ptr = new Node<Item>;
  30. insert_ptr->data = new_item;
  31. insert_ptr->link = head_ptr;
  32. head_ptr = insert_ptr;
  33.  
  34. //cout<<" **list_head_insert** head_ptr->data "<< head_ptr->data<< " \n";
  35. }
  36.  
  37. template <class Item>
  38. void list_insert(Node<Item>* &previous_ptr, const Item& new_item)
  39. {
  40. Node<Item> *insert_ptr;
  41.  
  42. insert_ptr = new Node<Item>;
  43. insert_ptr->data = new_item;
  44. // insert_ptr->link = NULL;
  45. // previous_ptr->link = insert_ptr;
  46. insert_ptr->link = previous_ptr->link;
  47. previous_ptr->link = insert_ptr;
  48.  
  49. // cout<<" $$list_insert$$ previous_ptr->data "<< previous_ptr->data<< " \n";
  50. // cout<<" $$list_insert$$ insert_ptr->data "<< insert_ptr->data<< " \n";
  51. }
  52.  
  53. template <class Item>
  54. Node<Item>* list_search(Node<Item>* head_ptr, const Item& target)
  55. {
  56. Node<Item> *cursor;
  57.  
  58. for (cursor = head_ptr; cursor != NULL; cursor = cursor->link)
  59. if (cursor->data == target)
  60. return cursor;
  61.  
  62. return NULL;
  63. }
  64.  
  65. template <class Item, class SizeType>
  66. Node<Item>* list_locate(Node<Item>* head_ptr, SizeType position)
  67. // Library facilities assert.h, stdlib.h
  68. {
  69. Node<Item> *cursor;
  70. size_t i;
  71.  
  72. assert(position > 0);
  73.  
  74. cursor = head_ptr;
  75. for(i = 1; (i != position) && (cursor != NULL); i++)
  76. cursor = cursor->link;
  77. return cursor;
  78. }
  79.  
  80. template <class Item>
  81. void list_head_remove(Node<Item>*& head_ptr)
  82. {
  83. Node<Item> *remove_ptr;
  84.  
  85. remove_ptr = head_ptr;
  86. head_ptr = head_ptr->link;
  87. delete remove_ptr;
  88. }
  89.  
  90. template <class Item>
  91. void list_remove(Node<Item>* previous_ptr)
  92. {
  93. Node<Item> *remove_ptr;
  94.  
  95. remove_ptr = previous_ptr->link;
  96. previous_ptr->link = remove_ptr->link;
  97. delete remove_ptr;
  98. }
  99.  
  100. template <class Item>
  101. void list_clear(Node<Item>*& head_ptr)
  102. // Library facilities used: stdlib.h
  103. {
  104. while (head_ptr != NULL)
  105. list_head_remove(head_ptr);
  106. }
  107.  
  108. template <class Item>
  109. void list_copy
  110. (Node<Item>* source_ptr, Node<Item>*& head_ptr, Node<Item>*& tail_ptr)
  111. // Library facilities used: stdlib.h
  112. {
  113. head_ptr = NULL;
  114. tail_ptr = NULL;
  115.  
  116. // Handle the case of the empty list
  117. if (source_ptr == NULL)
  118. return;
  119.  
  120. // Make the head node for the newly created list, and put data in it
  121. list_head_insert(head_ptr, source_ptr->data);
  122. tail_ptr = head_ptr;
  123.  
  124. // Copy the rest of the nodes one at a time, adding at the tail of new list
  125. for (source_ptr = source_ptr->link; source_ptr != NULL; source_ptr = source_ptr->link)
  126. {
  127. list_insert(tail_ptr, source_ptr->data);
  128. tail_ptr = tail_ptr->link;
  129. }
  130. }
  131.  
  132. template <class Item>
  133. void list_piece
  134. (Node<Item>* start_ptr, Node<Item>* end_ptr, Node<Item>*& head_ptr, Node<Item>*& tail_ptr)
  135. // Library facilities used: assert.h, stdlib.h
  136. {
  137. head_ptr = NULL;
  138. tail_ptr = NULL;
  139.  
  140. // Handle the case of the empty list
  141. if (start_ptr == NULL)
  142. return;
  143.  
  144. // Make the head node for the newly created list, and put data in it
  145. list_head_insert(head_ptr, start_ptr->data);
  146. tail_ptr = head_ptr;
  147. if (start_ptr == end_ptr)
  148. return;
  149.  
  150. // Copy the rest of the nodes one at a time, adding at the tail of new list
  151. for (start_ptr = start_ptr->link; start_ptr != NULL; start_ptr = start_ptr->link)
  152. {
  153. list_insert(tail_ptr, start_ptr->data);
  154. tail_ptr = tail_ptr->link;
  155. if (start_ptr == end_ptr)
  156. return;
  157. }
  158. }
  159.  
  160. /*template <class Item>
  161. void operator =(const Node<Item>& source)
  162. // Library facilities used: link2.h, stdlib.h
  163. {
  164.   size_t i;
  165.   // Node<Item>* tail_ptr; // Needed for list_copy
  166.  
  167.   if (this == &source)
  168.   return; // Avoid self-assignment
  169. this=&&source;
  170.  
  171.  
  172. }*/

Report this snippet  

You need to login to post a comment.