Posted By

DrPepper on 09/22/11


Tagged


Versions (?)

[CISP430] node template


 / Published in: C++
 

  1. // FILE: node2.template
  2. // IMPLEMENTS: The functions of the node template class and the
  3. // linked list toolkit (see node2.h for documentation).
  4. //
  5. // NOTE:
  6. // Since node is a template class, this file is included in node2.h.
  7. // Therefore, we should not put any using directives in this file.
  8. //
  9. // INVARIANT for the node class:
  10. // The data of a node is stored in data_field, and the link in link_field.
  11.  
  12. #include <cassert> // Provides assert
  13. #include <cstdlib> // Provides NULL and size_t
  14.  
  15. namespace CISP430_A3
  16. {
  17. template <class Item>
  18. void list_clear(node<Item>*& head_ptr)
  19. // Library facilities used: cstdlib
  20. {
  21. while (head_ptr != NULL)
  22. list_head_remove(head_ptr);
  23. }
  24.  
  25. template <class Item>
  26. void list_copy(
  27. const node<Item>* source_ptr,
  28. node<Item>*& head_ptr,
  29. node<Item>*& tail_ptr
  30. )
  31. // Library facilities used: cstdlib
  32. {
  33. head_ptr = NULL;
  34. tail_ptr = NULL;
  35.  
  36. // Handle the case of the empty list
  37. if (source_ptr == NULL)
  38. return;
  39.  
  40. // Make the head node for the newly created list, and put data in it
  41. list_head_insert(head_ptr, source_ptr->data( ));
  42. tail_ptr = head_ptr;
  43.  
  44. // Copy rest of the nodes one at a time, adding at the tail of new list
  45. source_ptr = source_ptr->link( );
  46. while (source_ptr != NULL)
  47. {
  48. list_insert(tail_ptr, source_ptr->data( ));
  49. tail_ptr = tail_ptr->link( );
  50. source_ptr = source_ptr->link( );
  51. }
  52. }
  53.  
  54. template <class Item>
  55. void list_head_insert(node<Item>*& head_ptr, const Item& entry)
  56. {
  57. head_ptr = new node<Item>(entry, head_ptr);
  58. }
  59.  
  60. template <class Item>
  61. void list_head_remove(node<Item>*& head_ptr)
  62. {
  63. node<Item> *remove_ptr;
  64.  
  65. remove_ptr = head_ptr;
  66. head_ptr = head_ptr->link( );
  67. delete remove_ptr;
  68. }
  69.  
  70. template <class Item>
  71. void list_insert(node<Item>* previous_ptr, const Item& entry)
  72. {
  73. node<Item> *insert_ptr;
  74.  
  75. insert_ptr = new node<Item>(entry, previous_ptr->link( ));
  76. previous_ptr->set_link(insert_ptr);
  77. }
  78.  
  79. template <class Item>
  80. size_t list_length(const node<Item>* head_ptr)
  81. // Library facilities used: cstdlib
  82. {
  83. const node<Item> *cursor;
  84. std::size_t answer;
  85.  
  86. answer = 0;
  87. for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( ))
  88. ++answer;
  89.  
  90. return answer;
  91. }
  92.  
  93. template <class NodePtr, class SizeType>
  94. NodePtr list_locate(NodePtr head_ptr, SizeType position)
  95. // Library facilities used: cassert, cstdlib
  96. {
  97. NodePtr cursor;
  98. SizeType i;
  99.  
  100. assert(0 < position);
  101. cursor = head_ptr;
  102. for (i = 1; (i < position) && (cursor != NULL); ++i)
  103. cursor = cursor->link( );
  104. return cursor;
  105. }
  106.  
  107. template <class Item>
  108. void list_remove(node<Item>* previous_ptr)
  109. {
  110. node<Item> *remove_ptr;
  111.  
  112. remove_ptr = previous_ptr->link( );
  113. previous_ptr->set_link(remove_ptr->link( ));
  114. delete remove_ptr;
  115. }
  116.  
  117. template <class NodePtr, class Item>
  118. NodePtr list_search(NodePtr head_ptr, const Item& target)
  119. // Library facilities used: cstdlib
  120. {
  121. NodePtr cursor;
  122.  
  123. for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( ))
  124. if (target == cursor->data( ))
  125. return cursor;
  126. return NULL;
  127. }
  128. }

Report this snippet  

You need to login to post a comment.