C :: Make A Hash Table Array Of Linked Lists / Separate Chaining Technique
Jul 5, 2013how to create a hash table array and use linked lists inside the elements.
View 5 Replies
ADVERTISEMENT
C++ :: Separate Chaining Hash Table?
Nov 28, 2014my insert() function
template <class T>
class Node
{
public:
[Code]....
C++ :: Insert Numbers Into A Hash Table Of Size 10 - Using Linear Probing And Chaining
May 28, 2014How to approach this? Not very clear on how hashing works..
Insert the following numbers into a hash table of size 10 (ie an array with 0…9 index position) using a hash function h(k)=(k*71+94)%10 and using Linear Probing.
75, 98, 43,1,-56,93,101,34,23
Insert the following numbers into a hash table of size 10 (ie an array with 0…9 index position) using a hash function h(k)=(k*71+94)%10 and using Chaining.
75, 98, 43,1,-56,93,101,34,23
C++ :: Splitting Linked List Into Two Separate Lists
Feb 14, 2013I've been given a ton of code (5 files worth) that does various things with a linked list. I'm supposed to add a function to split this list into two separate lists by testing whether or not each number is <,=, or > a certain element. I am completely lost and don't understand linked lists at all. I'm also a bit lost on pointers since it's been almost a year since I've looked at programming, but I could probably figure that out if I could just get this linked list thing down.
Here's my SplitLists function so far:
void UnsortedType::SplitLists () {
// Pointers for each new list
NodeType* list1Ptr;
NodeType* list2Ptr;
[Code] ....
In other places in the code, I have GetNextItem, ComparedTo, PutItem, and ResetList that were already given to me.
C :: Linked List Or Hash Table For Matrix Operations And Representation
Jul 21, 2014I have matrix in C with size m x n. Size n isn't known. I want to have operations on matrix such as : delete first element and find i-th element. (where size m woudn't be too big , from 10 to 50 columns).
What is more efficient to use, linked list or hash table? How can I map each column of matrix to different element of linked list or hash table; depends what I choose to use?
C++ :: Hash Table Program - Sorting Pointer Table After All Of Values Entered
Nov 19, 2013I am having an issue with my sort function. This is one part of the Hash table program. The main issue is that I am trying to sort the pointer table after all of the values have been entered. The ptr_sort function is not a class function and so I am therefore unable to use the class variables psize and pTable. Is there another way I should be trying this? it is a Vector should I use the sort() function from the vector class in STL?
#include "/home/onyuksel/courses/340/progs/13f/p9/util9.h"
#include "/home/onyuksel/courses/340/progs/13f/p9/hTable.h"
#ifndef H_TABLE1
#define H_TABLE1
void ptr_sort ( );
[Code] ....
C :: 3D Array Of Pointers To Linked Lists
Aug 8, 2013I am having some trouble getting a 3d array of pointers to link up with a linked list for each of the array elements. the 3d array of pointers is declared like this:
Code:
struct particle *cell[MAXCELLS][MAXCELLS][MAXCELLS]; and there are linked lists declared like this:
Code: struct particle { /* structure for particles */
double sw[3]; /* square well components */
double hs[3]; /* hard sphere components */
double u[3]; /* unit vector for rotations */
struct particle *link;
};
I want to get the array pointers 'cell[x][y][z]' to point to the first observed particle in a function next to main, something like this:
Code:
void generate_list(){
int i,j,k,l;
/* determine the number of cells to decompose the simulation box in each of x, y and z directions*/
int(cells_x) = floor(boxX/cell_size);
int(cells_y) = floor(boxY/cell_size);
int(cells_z) = floor(boxZ/cell_size);
/* initialise the array of pointers to NULL */
for (j=0;j<cells_x;j++){
[Code]...
I am getting a pointer type cast error when I compile "assignment from incompatible pointer type",
C++ :: Array Based Implementation Of Linked Lists
Jul 19, 2014I first want to say that i am trying to solve my code without Pointers.
My goal is to..
1. Construct an empty 2D array with a capacity of 25. (list[25][2];)
2. Empty(): test if the stack is empty
3. Push(): add a value to the stack in the (list[i][0] = value;) position and (list[i][1] = previous list[i][0] position)
4. Top(); read the value(list[i][0]) at the top(count) of the stack
5. Pop(); remove the value at the top of the stack (list[i]= 0;)
6. Display(); displays all the elements in the stack going from the top to bottom order. (shows array index, data value, and next array index)
I have hit a road block and don't know what to fix or where to go from here.
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
char name[5];
srand(time(0));
//Protoypes
void construction(int table[25][2]);
[Code]...
C :: How To Add New Value To Hash Table
Apr 18, 2013I have a problem with this function that adds a new value to the hash table or updates its data if the value already exists:
Code:
int tab_add(tab_disp *td, const object *value) the function should return:
TABDISP_OK if the value is correctly added, or TABDISP_ERROR if memory error, or TABDISP_INVALID if pointer td = NULL
The type of structure I am using is the following:
Code:
typedef struct {
char key[25];
char value[100];
} object;
[code]....
C++ :: Implementing Double Linked Lists As Array Of Pointers
Dec 27, 2012I am studying/writing/ code for a future Advanced Data Structure class in C++; however I am not suppose to use STL, Templates and etc (the way I just code "kinda" of resembles what I have to use).
My application is suppose to read/analyze all integers contained in a text file of 5-digit integers (10000 - 99999).
For simplicity I am using the following input (or check the attached):
20007 20008 20009
20010 20010
20012 20012
20013
20014 20010
20015
20016 ....
So far, my code is not displaying/printing the lists separated by the first digit of these 5-digits integers. I am expecting it to display/print logically/similar to the following:
Output:
Results for input file numbers.txt:
27 total integers read from file
The 3 unique integers beginning with digit 1 were
18399 17342 19948
The 6 unique integers beginning with digit 3 were
39485 34710 31298 38221 35893 32791
The 4 unique integers beginning with digit 4 were
43928 49238 45678 43210
The 6 unique integers beginning with digit 6 were
64545 62987 66221 61777 66666 65432
The 2 unique integers beginning with digit 8 were
88888 86861
The 1 unique integer beginning with digit 9 was
98765
There were 22 unique 5-digit integers in the file.
The highest unique count in one list was 6 integers.
My code that will follow soon displays/prints only the LAST 5-digits "group" of integers (in this case the 5-digits starting with 3). I am not sure what's wrong with my code; perhaps I am not designing it correctly. May be my calls in it are on the wrong place or I have to write all integers and then traverse it and output it (if that's the case, I am not sure how).
My code follows:
#include <iostream>
#include <fstream>
#include <iomanip>
using namespace std;
const int MAX_CELLS = 10;
const int UNIQUE_FIVE_DIGIT = 5;
[Code] .....
C :: How To Generate Hash Table
Jul 29, 2013Code: I have these two columns.
ID Group
0 2
1 2
2 3
3 4
4 4
5 4
6 4
7 4 Code: I want to store ID values on the bases of same Group, like we do in Hash table (key, value) .
Group ID
2 0,1
3 2
4 3,4,5,6,7
so when i said key 2 it will give me 0,1. how can i do it. As first i thought that i can use array of array but then how i can store the value of key. Now I am thinking of hash but i don't know how I will store and retrieve these values.
C++ :: Duplicates In Hash Table
Feb 24, 2013I am having problems with this function:
bool HashTable::insert(char const * const key, const Player& aPlayer) {
//calculate the insertion position (the index of the array)
size_t index = calculateIndex(key);
for(int i=0; i < capacity; i++) {
[Code] ....
The inserting part works just fine, but the checking for duplicates where I compare the two values is crashing my program.
C/C++ :: PJW Algorithm Of Hash Table
Jul 28, 2012I have a doubt in the PJW algorithm of the Hash Table.
What is the logic in shifting the bytes by this specified number as specified in the pjw algorithm.
C++ :: Retrieve Object From Hash Table
Feb 25, 2013I'm trying to retrieve the Player object from my hash table so I can edit the content of that object. Here is what I have.
Player* HashTable::retrieve(char * key, Player& aPlayer) {
//calculate the retrieval position (the index of the array)
size_t index = calculateIndex(key);
//search for the data in the chain (linked list)
node * curr = table[index];
char id[100];
[Code] .....
Here I'm calling the retrieve and I need to return a pointer of that object.
Player* PlayerDB::FetchPlayer(char* name) {
Player* info = new Player();
out << "Fetching player " << """ << name << "" -- ";
if(h.retrieve(name, *info)) {
out << "Success!" << endl;
[Code] .....
And here is my call in main.
Player* outPlayer = NULL;
outPlayer = pdb.FetchPlayer("Sappho");
if (outPlayer != NULL) {
outPlayer->LevelUp();
}
I'm just trying to change the actual level of the player using the LevelUp function, but right now it is not making that change. I've been told I need to return a reference of the object in my retrieve function, but I thought that was what I was doing already.
C++ :: Runtime Error In Hash Table
Apr 25, 2013I am getting a strange runtime error when trying to run my hash table program. I have it separated in 3 separate files. I believe I have narrowed down where the error is occurring. It is either happening in insert(const &string s) or in the implementation of vector<list<string>> ht. I would appreciate some input. This is the implementation of insert():
void HTable::insert(const string &s) {
int h = hash(s);
cout<<h<<endl;
list<string> &tempList = ht[h];
[Code] .....
And it is giving me some sort of compilation error saying I cannot convert a type string to type list.
C++ :: Hash Table Remove Function
Apr 11, 2013I am working on creating a program using HashTables. This is for homework. This is the first time I am using and creating HashTables, so forgive me in advance as to I don't know entirely what I am doing. The main problem I am having right now is incorporating my remove() function. I can get the code to compile, but when I run test the program out, it crashes. The error that I am receiving is list iterator is not decrementable Here is my hashtable class as well as my remove() function. Also need to incorporate a print method.
class HTable
{
public:
HTable(int size);
[Code]....
C++ :: Hash Table Of Function Pointers?
Dec 15, 2014Is it possible to create a hash table of function pointers so that functions can be referenced by their name (using a string?)
View 2 Replies View RelatedC :: Free Memory From A Dynamically Allocated Array Of Pointers To Linked Lists
Feb 26, 2013Having some frustrating issues trying to free memory from a dynamically allocated array of pointers to linked lists. I think the problem is in how I initialize the pointers to NULL. Is there a more elegant way to have the program recognize that the list is empty so it knows to create a head node for the linked list in the function 'add_end_stub_to_array'?
I ran the code through Valgrind and it says that memory is definitely lost from this array.
This is the structure definition.
Code: struct stub_edge {
int loc_id;
int anim_type;
int mkt;
struct stub_edge *next_node;
};
Here is the code snippet from main allocating and deallocating memory to the array.
Code:
struct stub_edge **stub_list = (struct stub_edge **)malloc( sizeof(struct stub_edge *) * 12);
for (i = 0; i < 12; i++)
{
stub_list[i] = (struct stub_edge *)malloc(sizeof(struct stub_edge));
stub_list[i] = NULL;
}
stub_list = add_end_stub_to_array(end_stubs, stub_list);
destroy_end_stub_array(stub_list);
Here the function for adding nodes to the lists by reading through a dynamically allocated 2D array. (The end_stubs array is ordered by month and each linked list represents events occuring within the month).
Code:
struct stub_edge **add_end_stub_to_array(int **end_stubs, struct stub_edge **list)
{
long int i = 0;
int mon = 0;
struct stub_edge *current_node1;
struct stub_edge *new_node1;
int break1 = 0;
while(i < num_edges && break1 == 0 && mon < 12)
[Code]...
Here is the function for freeing memory from the list.
Code:
void destroy_end_stub_array(struct stub_edge **list)
{
if(list != NULL)
{
int mon = 0;
struct stub_edge *current_node1;
struct stub_edge *new_node1;
for(mon = 0; mon < 12; mon++)
[Code]...
C :: Setting Hash-table Entries To NULL?
Apr 21, 2013Here is my code so far:
Code:
//LINEAR CHAINING OR SEPERATE CHAINING...
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define MAX_USERNAME_LEN 15
#define MAX_PASSWORD_LEN 20
[Code] ....
When I compile I get this error:
Code:
simpleauth.c: In function ‘initialize_table’:
simpleauth.c:179:30: error: incompatible types when assigning to type ‘DBEntry’ from type ‘void *’
I am sure its a simple error but I cannot seem to figure out how to set all the entries in the database to NULL. My plan is this:
1. Set all entries to NULL.
2. Check if entry is empty, if empty insert into hash-location, if not increment until empty...
Part 2 seems easy to me, but I cannot set them to empty....
C/C++ :: Hash Table - Interpreting Valgrind Output
Nov 22, 2014I have a large hash table, where each index has a container that has a doubly linked list. Things work up until releasing the memory. Each record is created with malloc, and each record->data is also created with malloc and the associated string is copied in using strcpy(). The table itself is released in another part of the program and doesn't produce and error.
/**
* valgrind --track-origins=yes
*/
==16898== Conditional jump or move depends on uninitialised value(s)
==16898== at 0x8049685: shFree (SpellHash.c:110)
==16898== by 0x8049352: unload (dictionary.c:115)
==16898== by 0x8048E64: main (speller.c:158)
==16898== Uninitialised value was created by a heap allocation
[Code] .....
How to interpret valgrind. Error resolved on a small problem. Now running into issues on large (>10000 words to check) problems. It appears the virtual machine just can't keep up for some reason. Running the code on my local computer produces no errors, memory usage is minuscule, and profile tools don't report any issues.
C++ :: Dynamically Allocating Hash Table Using Data From File
Nov 5, 2013I have an abstract based class and three derived classes. I also have a templated hash table class(using chaining as my collision resolution method, an array of stl lists), and a class to parse commands from a file, this also holds the instantiation of the hash table. My question is that since my command parsing class's constructor instantiates the hash table in the main driver(unable to modify) how can I make this dynamically allocated using data from the file?
template<class T>
class hashTable{
public:
hashTable(int size);
~hashTable();
[Code] .....
C++ :: Create A Map Based Hash Table For A Sparse Matrix?
Jul 24, 2014I have this assignment where I have to create a map based hash table for a sparse matrix. The professor has provided some code and I'm supposed to fill in parts of it to make it work.
He has given us a class sparseMatrix which we need to provide a hash function for. This hash function is to be defined in a Class TupleHash which is inside sparseMatrix. I think I got that part down. What is really confusing me is what he has done with some typedefs.
For one of them I had to declare an unorderd_map that maps a struct Tuple on to the class template argument Object. I did that like so:
typedef unordered_map<Object,Tuple,TupleHash> HashTable;
The next typedef was given to me like so:
typedef typename HashTable::value_type valueType;
This is giving me a world of unintelligible error messages. This is how it starts.
In instantiation of 'struct std::__detail::__is_noexcept_hash<int, sparseMatrix<int>::TupleHash>':|
recursively required from 'struct std::__and_<std::is_default_constructible<sparseMatrix<int>::TupleHash>, std::is_copy_assignable<sparseMatrix<int>::TupleHash>, std::__detail::__is_noexcept_hash<int, sparseMatrix<int>::TupleHash> >'|
C++ :: Implementing Hash Table - STL List Compiler Error
Jun 5, 2013I have been implementing a Hash Table class made, and ran into a bit of a problem in my Delete function. I have the hash table made up as
vector<list<HashNode<T,X>>> m_Table
My problem is when I iterate through the vector, and then the list in that current element to try and find the Node I want to delete, the STL list class gives me the error:
Error1error C2678: binary '==' : no operator found which takes a left-hand operand of type 'HashNode<T,X>' (or there is no acceptable conversion)
Here's the Delete function:
template <typename T, typename X>
void HashTable<T,X>::Delete(T key) {
HashNode<T,X> Node;
HashNode<T,X> NodeTemp;
list<HashNode<T,X>> temp;
list<HashNode<T,X>>::iterator it;
vector<list<HashNode<T,X>>>::iterator iter;
[Code] ....
Why it's not letting me do the .Remove() function?
Visual C++ :: Hash Table - How To Setup Static Variable
Apr 22, 2014I am having trouble getting the cout statements that I commented out to work properly. And I can't figure out why the first movie in the movies.txt file displays at the end of the list in my output screen when it should only display once as the first item. I am also having trouble figuring out where and how to set up the static variable.
Purpose : This assignment requires that you to develop a program using the classes listed above. Specifically you will build a hash table containing movie data. The collision strategy will be to build linked lists as the array elements.
Program Specifications : Your program will read the data from the file named Movies.txt located in the StudentFiles1.zip file on the Connections Portal. Each record contains 2 fields separated by a space. They are:
FieldsData Type
Motion Picture Association Code (MPAC)Integer
Movie NameString
Your application program will read each record, create a Movie structure instance and place that structure instance into the hash table.
You will need to modify the appropriate code to provide for an audit trail of the hash table construction. To accomplish this, you will use cout statements in the above class member functions. You will need to modify them to include couts, but the modifications will be relatively small. If not, you are doing it wrong. The hashing algorithm to use is:
Index = int ( 0.618033 * MPAC) % size
Make the array size a constant and set it to 10.
Include a counter for the number of collisions that occurred in building the hash table. Including a static variable in the LinkedList or List class is the best method for doing that.
See the sample audit trail below for the first 5 records on Movies.txt and the size of the hash table set to 3. This is shown for illustration only. The full file will have different locations calculated.
1101-Casablanca is being added
The hashed location is 2
There was no collision loading 1101-Casablanca
------------------------------------------------
1200-Duck Soup is being added
The hashed location is 0
There was no collision loading 1200-Duck Soup
------------------------------------------------
[Code] ....
After the above is displayed, prompt the user to enter the MPAC of a movie to locate. Produce an audit trail when locating the requested movie as shown below: Make sure you list all movies that have collided at the hashed location. That may also cause you to modify one of the existing ADTs a little.
Will search for 6601
at the hashed location is 2
There was a collision here with 6601-Wizard of Oz
There was a collision here with 1101-Casablanca
retrieved from hash table: 6601-Wizard of Oz
[Code] ....
C++ :: Creating A Linked List Of Common Elements From Two Other Linked Lists
Apr 29, 2013I'm trying to write a function that takes two linked lists and creates a third one with only the common elements.
It assumes the first list (the caller) has no dups, but it doesn't seem to be working. The program doesn't crash, it just hangs when it is supposed to display L3 (the third list)..everything else runs and is displayed fine.
template <typename T>
LList <T> LList <T>:: common (LList <T> &B)//common fct
{
Node <T> *hunter1 = Head;
[Code]......
C :: Make A Separate Function
May 6, 2013I will post the entire code at the bottom. Its running fine right now but This part in the menu function I need to make as a separate function. My problem is when I make it into a function by itself I have to declare and initialize the grades A,B,C,D,F how can I do that when I can't make them equal 0 because it has to keep track of how many of each letter grade.
Code:
//Count letter grade
if(ave >= 90)
++A;
else if (ave >= 80)
++B;
else if (ave >= 70)
++C;
else if (ave >= 60)
++D;
}
[code]....