For this problem, you must implement the openHashTableAdd function and openHashT
ID: 3863840 • Letter: F
Question
For this problem, you must implement the openHashTableAdd function and openHashTableContains for an open address hash table with linear probing. Assume you have access to a hash function named _HASH that returns an arbitrary integer value (not necessarily between [0, tablesize-1]!)
/* NOTE the definition of TOMBSTONE here */
#define TOMBSTONE -1
int _HASH ( TYPE newValue);
struct openHashTable {
TYPE ** table; /* array of pointers to TYPE */
int tablesize;
int count;
};
/* Initialize the open addressing hash table. Note the table entries are initialized to NULL pointers to indicate they are empty */
void initOpenHashTable (struct openHashTable * ht, int size) {
int i;
assert (size > 0);
ht->table = (TYPE **) malloc(size * sizeof(TYPE *));
assert(ht->table != 0);
ht->table[0] = 0;
for (i = 0; i < size; i++)
ht->table[i] = 0; /* initialize empty */
ht->tablesize = size;
ht->count = 0;
}
int openHashTableSize (struct openHashTable *ht) { return ht->count; }
/* Double the size of an open addressing hash table */
void _resizeOpenHashTable (struct openHashTable *ht) {
int oldTableSize = ht->tableSize;
if (ht->tableSize == 0)
ht->tableSize = 1;
ht->tableSize = 2* ht->tableSize;
TYPE **oldArray = ht->table;
/* Create a new array */
ht->table = (TYPE **)malloc(ht->tableSize * sizeof(TYPE *));
assert(ht->table != 0);
/* Rehash elements into new array */
for(i=0; i < oldTableSize i++) {
if(oldArray[i] != 0 && oldArray[i] != TOMBSTONE)
openHashTableAdd(ht, oldArray[i]);
}
free(oldArray);
}
void openHashTableDelete(struct openHashTable * ht, TYPE newValue) {
int loc = openHashTableContains(ht, newValue);
if (loc >= 0) {
/* NOTE: delete will free memory for the item. This assumes that this program owns the memory for this hash table item */
free(ht[loc]);
ht[loc] = TOMBSTONE;
ht->count--;
}
}
void openHashTableAdd (struct openHashTable * ht, TYPE newValue) {
/* TODO: Implement this function, remember to consider TOMBSTONES which should not stop the search but can be replaced with a new item. Note that no two identical values should be added to the hash table. Assume that you can use val == newValue or val != newValue to compare between a variable val and the newValue */
}
/* returns the location of the item in the hash table, -1 if it is not present */
int openHashTableContains (struct openHashTable *ht, TYPE testValue) {
/* TODO: Implement this function, remember to consider TOMBSTONES which should not stop the search. Assume that you can use val == testValue or val != testValue to compare between a variable val and the testValue */
}
Problem #3: Fill in the following code for a breadth-first search (BFS) algorithm that returns reachability of every node in an unweighted directed graph from a particular node startVertex, assume that the adjacency list representation of a graph is given as a parameter to your function (12 points).
#include <stdio.h>
#include <stdlib.h>
struct Edge {
int vertex;
struct Edge * next; /* You can assume next = 0 at the end of the list */
};
bool * BreadthFirstReachability(
struct Edge * adjacencyList[],
int num_vertices,
int startVertex
)
{
/* adjacencyList is a given edge-list representation of a graph;
num_vertices is the number of vertices in the graph;
startVertex gives the vertex to start from. */
/* Assume all vertex indices will be integers from 0 to
num_vertices – 1, hence adjacencyList[vertexA] will contain all the
edges originating from vertexA */
/* calloc will allocate and zero the array (set all values to false)*/
bool *reachable = calloc(num_vertices * sizeof(bool));
assert (reachable != 0);
reachable[startVertex] = true;
/* TODO: Implement the rest of the BFS reachability function here (you are allowed to define additional variables below the given code). */
return reachable;
}
Explanation / Answer
#include<stdio.h>
#include<stdlib.h>
struct edge
{
int val;
struct edge *next;
}
struct edge *insert(struct edgen*head,int num)
{
struct edge *=(struct edge * )malloc(sizeof(struct edge));
p->=num;
p->next=head;
return p;
}
void bfs(struct node *list[],int vertices,int parent[],int level[])
{
struct node *temp;
int i,par,lev,flag=1;
lev=0;
level[1]=lev;
while(flag)
{
flag=0;
for(i=1;i<=vertices;++i)
{
if(level[i]==lev)
{
flag=1;
temp=list[i];
par=i;
while(temp!=NULL)
if(level[temp->val]!=-1)
{
temp=temp->next;
continue;
}
level[temp->val]=lev+1;
parent[temp->val]=par;
temp=temp->next;
}
}
}
++lev;
}}
int main()
{
int vertices,edges,i,j,v1,v2;
printf("enteer the no of vertices ");
scanf("%d",&vertices);
printf("Enteer the no of edges ");
scanf("%d",&edges);
struct edge *adjacency_list[vertices + 1];
int parent[vertices +1];
int level[vertices+1];
for(i=0;i<=vertices;++i)
{
adjacency_list[i]=NULL;
parent[i]=0;
level[i]=-1;
}
for(i=1;i<=edges;++i)
{
scanf("%d%d",&v1,&v2);
adjacency_list[v1]=insert(adjacency_list[v1],v2);
adjacency_list[v2]=insert(adjacency_list[v2],v1);
}
for(i=1;i<=vertices;++i)
{
printf("%d->",i);
struct edge *temp=adjacency_list[i];
while(temp!=NULL)
{
printf("%d->",temp->val);
temp=temp->next;
}
printf("NULL ");
bfs(adjacency_list,vertices,parent,level);
printf(" level and parent array- ");
for(i=1;i<=vertices;++i)
{
printf("level of node %is %d,parent is %d ");
i,level[i],parent[i];
}
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.