Posted By

DrPepper on 11/10/11


Tagged


Versions (?)

[CISP430] Chaining Hash Table (table.h)


 / Published in: C++
 

  1. /*
  2.  
  3. data
  4.   | 1 | -> head of node1 linked list A
  5.   | 2 | -> head of node2 linked list B
  6.  
  7. data[] Node Node
  8. key | table| | key value paire |
  9. | 1 | -> [*link] -> [*link] -> NULL
  10. | 2 | -> NULL;
  11. | 3 | -> [*link] -> NULL
  12.  
  13. */
  14. #include <assert.h> // Provides assert
  15. #include <stdlib.h> // Provides NULL and size_t
  16. #include <iostream>
  17. #include "link2.h"
  18.  
  19. using namespace std;
  20. template <class RecordType> // tamplate parameter is RecodeType
  21. class Table
  22. {
  23. private :
  24. static const size_t CAPACITY = 811;
  25. /**** Node stuff *****/
  26. int key; // Each record requres a unique identifying value
  27. // key is the stock number store in a member function
  28. int var; // varriable for input
  29. Node<RecordType> *data[CAPACITY]; // TABLE_SIZE show me how many capacity of data set in the data then ex. data[1] is the first set of array list
  30. Node<RecordType> *curNote; //to point to the current of node
  31. Node<RecordType> *precursor; //to point to the one before current node
  32. //Node<Item> *curNote; //to point to the current of node
  33. //Node<Item> *precursor; //to point to the one before current node
  34. size_t total_records; // like many_nodes
  35. public:
  36. Table(); //constructor
  37. // Table(const Table& source); // copy constructor
  38. ~Table();// missing
  39. void insert(const RecordType& entry);
  40. void remove(int key);
  41. // void print(int index)const;
  42. // void operator =(const Table& source);
  43. bool is_present(const RecordType& target) const; // THIS LINE HAS ERROR
  44. void find(int key, bool& found, RecordType& result) const;
  45. int getHash(int key){return(key % CAPACITY);} // get table number
  46. size_t size( ) const{ return this.total_recods; }
  47. /*
  48. struct hotKey
  49. { int key; };
  50. */
  51. // EXTRA FUNCTION
  52. // void hashTable(int &var);
  53.  
  54. };
  55. template <class RecordType>
  56. Table<RecordType>::~Table(){ }
  57. template <class RecordType>
  58. //Table<RecordType>::Table()
  59. Table<RecordType>::Table()
  60. //Postcondition: The Table has been initialized as an empty Table.
  61. {
  62. int i =0;
  63. // WORNG DECLEARATION FOR TABLE
  64. // ALL THE CELL OF THE DATA[CAPACITY] POINT TO NULL
  65. for (i; i <CAPACITY;++i)
  66. data[i] = NULL; // DATA IS CONFUSING WITH NODE ITEM DATA
  67. curNote=NULL;
  68. precursor=NULL;
  69. total_records=0;
  70. key = 0;
  71.  
  72.  
  73.  
  74.  
  75. /*
  76. table = new Node<RecordType>*[CAPACITY];
  77. for (int i =0;< i <CAPACITY;++i)
  78. table[i].key = NULL;
  79. */
  80. /*
  81. size_t i;
  82. used = 0;
  83. for(i=0;i<CAPACITY;++i)
  84. { data[i].key = NEVER_USED; }
  85. */
  86. }
  87. /*
  88. template <class RecordType>
  89. Table<RecordType>::Table(const RecordType& result)
  90. {
  91. table = new LinkedHashEntry*[TABLE_SIZE];
  92.   for (int i = 0; i < TABLE_SIZE; i++)
  93. { table[i] = result.data[i]; }
  94. }
  95.  
  96. template <class RecordType>
  97. //void Table<RecordType>::hashTable(RecordType &var)
  98. void Table<RecordType>::hashTable(int &var)
  99. // HASHTABLE PASS DATA TO INSERT AND PRINT
  100. {
  101. RecordType temp;
  102. const RecordType *entry = &temp;
  103.  
  104. temp.key = var;
  105. temp.var = var;
  106. insert(entry);
  107. }
  108. */
  109. template <class RecordType>
  110. void insert(const RecordType& entry)
  111. // Precondition: entry>= 0. Also if entry is not already a key in the table,
  112. // then the Table has space for another record.(i.e., size( ) < CAPACITY).
  113. // Postcondition: If the table already had a record with a key equal to //
  114. // entry, then that record is replaced by entry. Otherwise, the entry will be
  115. // added as a new record of the Table.
  116. // A. DECLEAR EVERYTHING AS 0 // CONSTRUCTOR
  117. // B. AFTER STEP 1 CREATE NEW NODE IF NESSESAY OTHERWISE DATA[INDEX]-> NULL
  118. // 1. FIND TABLE USING KEY
  119. // 2. CHECK IF THERE IS ALREADY ITEM IN THE TABLE OR NOT
  120. // 3-A. IF THERE IS NOT ITEM IN THE TABLE, INSERT NODE
  121. // 3-B. IF THERE IS ITEM INSERT THE ITEM AFTER LAST NODE
  122. //
  123. // ** TABLE[HASH] IS ALREADY POINTER THEREFORE YOU CAN CONNECT TO NEWNDOE IN LINK
  124. // ** BEFORE INSERT, I NEED TO CREATE KEY
  125. // ** INEED TO CREATE NODE BEFORE ASSIGN TO TABLE[]
  126. {
  127. int hash = getHash(entry.key);
  128. /* IF THERE IS NO ITEM CREATE NEW NODE IN THE HASH */
  129. //TABLE IS NOT DETECTED SO I MAY NEED TO CHANGE LATER
  130. if( entry.data[hash].key == NULL ) // THERE IS NO ITEM IN THE HASH AREA -> CREATE NEW NODE IN THE HASH
  131. {
  132. Node<RecordType> ptr = new Node<RecordType>;
  133. entry.data[hash].key = ptr;
  134. }// CREATED NEW NODE IN THE TABLE[HASH] PLACE
  135. /* IF THERE IS (ARE) ITEM(S)*/
  136. else
  137. {
  138. // 1. FIND IF THERE IS MORE THAN 1 ITEM
  139. // 2. IF THERE ARE MROE THAN 1 FIND END OF LINKED LIST
  140. // 3. INSERT ITEM IN THE END OF LINKED LIST AND POINT NULL
  141. // NEED TO RETHINK HERE
  142.  
  143. Node<RecordType>* newNode = entry.data[hash]; // CREATE NEW NODE
  144. while ((newNode != NULL) && (newNode.key != entry.key ))
  145. newNode = newNode->link;
  146. if(newNode.key == entry.key) // entry key and previous key are much
  147. {
  148. list_head_insert(newNode,newNode.key);
  149. ++entry.total_records;
  150. }
  151. else // there is not much key
  152. {
  153. list_insert(newNode,newNode.key);
  154. ++entry.total_records;
  155. }
  156. }
  157. }
  158.  
  159. template <class RecordType>
  160. //void Table<RecordType>::remove(int key)
  161. void remove(int key)
  162. // Postcondition: If a record was in the Table with the specified key, then that record has been removed; otherwise the table is unchanged.
  163. {
  164. int hash = getHash(key);
  165. //IF DATA[HASH] IS NOT NULL FIND WHRE YOU NEED TO ELASE
  166. if(data[hash] != NULL)
  167. {
  168. precursor = NULL;
  169. Node<RecordType>* newNode = data[hash];
  170. while((newNode->link != NULL)&&(newNode.key!= key))
  171. {
  172. precursor = newNode;
  173. newNode = newNode.link;
  174. }
  175. if(newNode.key == key)
  176. {
  177. if(precursor == NULL)
  178. {
  179. // SUPPOSED TO BE NODE<ITEM>
  180. Node<RecordType>* tempNode = newNode.link;
  181. delete newNode;
  182. data[hash] = tempNode;
  183. --total_records;
  184. }
  185. else
  186. {
  187. Node<RecordType>* tempNode2 = newNode.link;
  188. delete newNode;
  189. precursor.link;
  190. --total_records;
  191. }
  192. }
  193. }
  194.  
  195.  
  196.  
  197.  
  198. /*
  199. bool fond;
  200. size_t index;
  201. assert(key >= 0);
  202. find_index(key,found,index);
  203. if(found)
  204. {
  205. // the key was found, so remove this record and reduce used by 1
  206. data[index].key=PREVIOUSLY_USED;
  207. --used;
  208. }*/
  209. }
  210. /*
  211. template <class RecordType>
  212. //void Table<RecordType>::print(int index) const
  213. void Table<RecordType>::print(int index) const
  214. //Postcondition: If the Table with the index has data, then print the index and data in a chining format
  215. //PRINT IS NOT PRINTING HOW MANY YET
  216. {
  217. // INDEX WILL INPORT SO DATA HASH IS ALREADY SELECTED
  218. //curNote = data[index]; //
  219. cout << "data["<<index<<"] = ";
  220. if(data[index]!=NULL)
  221. {
  222. while(curNote != NULL)
  223. {
  224. cout <<"[" << curNote->data <<"] -> ";
  225. }
  226. }
  227. else if ((data[index]==NULL) || (curNote == NULL))
  228. { cout << " NULL "; }
  229. cout << endl;
  230. }
  231.  */
  232. template <class RecordType>
  233. //bool Table<RecordType>::is_present(const Item& target) const
  234. //bool Table<RecordType>::is_present(const RecordType& target) const
  235. bool Table<RecordType>::is_present(const RecordType& target) const
  236. //Postcondition: The return value is true if there is a record in the Table with the specified key.
  237. // Otherwise, the return value is false.
  238. // YOU NEED TO USE FIND FUNCTION TO FIND RESULT
  239. // THIS FUNCTION ASK YOU IF THERE IS NODE OR NOT
  240. // QUOTING FROM TEXT BOOK :
  241. //"HASHING CAN BE FIND IN THE AVERAGE CASE. ADDING AND DELETING ELEMENTS
  242. //IS EASIER IN A CONTAINER THAT PROVIDES HASHING, BECAUSE A BINARY SEARCH REQUIRES THAT THE ITEMS REMAIN SORTED."
  243.  
  244. {
  245. int hash = getHash(target.key);
  246. if(data[hash] == NULL)
  247. { return false; }
  248. else
  249. {
  250. Node<RecordType>* newNode = data[hash];
  251. while((newNode!=NULL) && (newNode.key!=key))
  252. { newNode = newNode.link; }
  253. if (newNode == NULL)
  254. { return false; }
  255. else
  256. { return true; }
  257. }
  258. }
  259.  
  260. template <class RecordType>
  261. //void Table<RecordType>::find(int key, bool& found, RecordType& result) const
  262. void Table<RecordType>:: find(int key, bool& found, RecordType& result) const
  263. //Postcondition: If a record is in the Table with the specified key,
  264. //then found is true and result is set to a copy of the record with that key.
  265. //Otherwise found is false and the result contains garbage.
  266. {
  267. int hash = getHash(key);
  268. if(data[hash]==NULL)
  269. { found = false; }
  270. else
  271. {
  272. Node<RecordType>* newNode = data[hash];
  273. while((newNode!=NULL) && (newNode.key!=key))
  274. { newNode = newNode.link; }
  275. if (newNode == NULL)
  276. { found = false; }
  277. else
  278. {
  279. found = true;
  280. // I NEED TO COPY NEWNODE TO RESULT * RESULT IS EMPTY NOW
  281. result.key = newNode.key;
  282. }
  283. }
  284.  
  285. }

Report this snippet  

You need to login to post a comment.