Posted By

DrPepper on 11/10/11


Tagged


Versions (?)

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


 / Published in: C++
 

  1. // FILE: link2.h
  2. // PROVIDES: A toolkit of ten template functions for manipulating linked lists.
  3. // Each node of the list contains a piece of data and a pointer to the next
  4. // node, as shown in this template struct:
  5. //
  6. // template <class Item> Item may be any of the C++ built-in types
  7. // struct Node (int, char, etc.), or a class with a default
  8. // { constructor, an assignment operator,
  9. // Item data; and a test for equality (x == y).
  10. // Node *link;
  11. // };
  12. //
  13. // FUNCTIONS in the linked list toolkit:
  14. // template <class Item>
  15. // size_t list_length(Node<Item>* head_ptr)
  16. // Precondition: head_ptr is the head pointer of a linked list.
  17. // Postcondition: The value returned is the number of nodes in the linked
  18. // list. The list itself is unaltered.
  19. //
  20. // template <class Item>
  21. // void list_head_insert(Node<Item>*& head_ptr, const Item& entry)
  22. // Precondition: head_ptr is the head pointer of a linked list.
  23. // Postcondition: A new node containing the given entry has been added at
  24. // the head of the linked list; head_ptr now points to the head of the new,
  25. // longer linked list.
  26. //
  27. // template <class Item>
  28. // void list_insert(Node<Item>* previous_ptr, const Item& entry)
  29. // Precondition: previous_ptr points to a node in a linked list.
  30. // Postcondition: A new node containing the given entry has been added
  31. // after the node that previous_ptr points to.
  32. //
  33. // template <class Item>
  34. // Node<Item>* list_search(Node<Item>* head_ptr, const Item& target)
  35. // Precondition: head_ptr is the head pointer of a linked list.
  36. // Postcondition: The pointer returned points to the first node containing
  37. // the specified target in its data member. If there is no such node, the
  38. // null pointer is returned. The list itself is unaltered.
  39. //
  40. // template <class Item, class SizeType>
  41. // Node<Item>* list_locate(Node<Item>* head_ptr, SizeType position)
  42. // Precondition: head_ptr is the head pointer of a list, and position > 0.
  43. // Postcondition: The pointer returned points to the node at the specified
  44. // position in the list. (The head node is position 1, the next node is
  45. // position 2, and so on). If there is no such position, then the null
  46. // pointer is returned. The list itself is unaltered.
  47. //
  48. // template <class Item>
  49. // void list_head_remove(Node<Item>*& head_ptr)
  50. // Precondition: head_ptr is the head pointer of a linked list, with at
  51. // least one node.
  52. // Postcondition: The head node has been removed and returned to the heap;
  53. // head_ptr is now the head pointer of the new, shorter linked list.
  54. //
  55. // template <class Item>
  56. // void list_remove(Node<Item>* previous_ptr)
  57. // Precondition: previous_ptr points to a node in a linked list, and this
  58. // is not the tail node of the list.
  59. // Postcondition: The node after previous_ptr has been removed.
  60. //
  61. // template <class Item>
  62. // void list_clear(Node<Item>*& head_ptr)
  63. // Precondition: head_ptr is the head pointer of a linked list.
  64. // Postcondition: All nodes of the list have been returned to the heap,
  65. // and the head_ptr is now NULL.
  66. //
  67. // template <class Item>
  68. // void list_copy
  69. // (Node<Item>* source_ptr, Node<Item>*& head_ptr, Node<Item>*& tail_ptr)
  70. // Precondition: source_ptr is the head pointer of a linked list.
  71. // Postcondition: head_ptr and tail_ptr are the head and tail pointers for
  72. // a new list that that contains the same items as the list pointed to by
  73. // source_ptr.
  74. //
  75. // template <class Item>
  76. // void list_piece
  77. // (Node<Item>* source_ptr, Node<Item>* end_ptr,
  78. // Node<Item>*& head_ptr, Node<Item>*& tail_ptr)
  79. // Precondition: source_ptr and end_ptr are pointers to nodes on the same
  80. // linked list, with the source_ptr node at or before the end_ptr node.
  81. // Postcondition: head_ptr and tail_ptr are the head and tail pointers for
  82. // a new linked list that contains the items from source_ptr to end_ptr.
  83. // The original list is unaltered.
  84.  
  85. #ifndef LINK2_H
  86. #define LINK2_H
  87. #include <stdlib.h> // Provides size_t
  88.  
  89. template <class Item>
  90. struct Node
  91. {
  92. typedef Item data;
  93. Node *link;
  94. };
  95.  
  96. // FUNCTIONS for the linked list toolkit
  97. template <class Item>
  98. size_t list_length(Node<Item>* head_ptr);
  99.  
  100. template <class Item>
  101. void list_head_insert(Node<Item>*& head_ptr, const Item& entry);
  102.  
  103. template <class Item>
  104. void list_insert(Node<Item>*& previous_ptr, const Item& entry);
  105.  
  106. template <class Item>
  107. Node<Item>* list_search(Node<Item>* head_ptr, const Item& target);
  108.  
  109.  
  110.  
  111. template <class Item, class SizeType>
  112.  
  113. Node<Item>* list_locate(Node<Item>* head_ptr, SizeType position);
  114.  
  115. template <class Item>
  116. void list_head_remove(Node<Item>*& head_ptr);
  117.  
  118. template <class Item>
  119. void list_remove(Node<Item>* previous_ptr);
  120.  
  121. template <class Item>
  122. void list_clear(Node<Item>*& head_ptr);
  123.  
  124. template <class Item>
  125. void list_copy
  126. (Node<Item>* source_ptr, Node<Item>*& head_ptr, Node<Item>*& tail_ptr);
  127.  
  128. template <class Item>
  129. void list_piece
  130. (Node<Item>* source_ptr, Node<Item>* end_ptr,
  131. Node<Item>*& head_ptr, Node<Item>*& tail_ptr);
  132.  
  133. #include "link2temp.h" // Include the implementation
  134. #endif

Report this snippet  

You need to login to post a comment.