In C programming language I have to write a program using Vector Abstract Data T
ID: 664183 • Letter: I
Question
In C programming language I have to write a program using Vector Abstract Data Type. I have a node.h and a node.c files and I also have a vector.h and have to create a vector.c file. I have almost everything done except for a void vadd(VectorT *vector, NodeItemT item) function. I am suppose to use this function to append a new element to the end of the vector. If the capacity of the vector is reached, the vector is supposed to dynamically grow by a fixed rate. *this is all supposed to happen in side the void vadd(VectorT *vector, NodeItemT item) function. all the files are listed below:
vector.h:
#ifndef _NODE_H
#define _NODE_H
// -----------------------------------------
// Definition of an item stored with a Node.
// -----------------------------------------
typedef char NodeItemT;
// ----------------------
// Definition of a Node
// ----------------------
typedef struct NodeT
{
NodeItemT info;
} NodeT;
// ----------------------
// Interface to Node ADT
// ----------------------
/**
* Creates a new node and stores the specified item in it.
*
* @param item the item to be stored in the node.
*/
NodeT *newNode(NodeItemT item);
/**
* Returns the item of a node.
*
* @return the item stored in this node
*/
NodeItemT* getInfo(NodeT *node);
/**
* Sets the item in a node.
*
* @param node a node whose item must be set
* @param item the item of the node
*/
void setInfo(NodeT* node, NodeItemT item);
/**
* Frees up the item of a node.
*
* @param node the node to be deallocated from memory
*/
void freeNode(NodeT * node);
/**
* Returns the item that indicates that the node is empty.
*
* @return an item indicating that the node is empty
*/
NodeItemT getEmtpyNodeItem();
#endif
node.h:
#ifndef _NODE_H
#define _NODE_H
// -----------------------------------------
// Definition of an item stored with a Node.
// -----------------------------------------
typedef char NodeItemT;
// ----------------------
// Definition of a Node
// ----------------------
typedef struct NodeT
{
NodeItemT info;
} NodeT;
// ----------------------
// Interface to Node ADT
// ----------------------
/**
* Creates a new node and stores the specified item in it.
*
* @param item the item to be stored in the node.
*/
NodeT *newNode(NodeItemT item);
/**
* Returns the item of a node.
*
* @return the item stored in this node
*/
NodeItemT* getInfo(NodeT *node);
/**
* Sets the item in a node.
*
* @param node a node whose item must be set
* @param item the item of the node
*/
void setInfo(NodeT* node, NodeItemT item);
/**
* Frees up the item of a node.
*
* @param node the node to be deallocated from memory
*/
void freeNode(NodeT * node);
/**
* Returns the item that indicates that the node is empty.
*
* @return an item indicating that the node is empty
*/
NodeItemT getEmtpyNodeItem();
#endif
node.c:
#include "node.h"
#include <stdlib.h>
// -----------------------------------------
// Definition of an empty item.
// -----------------------------------------
const NodeItemT EmptyNodeItem = '';
NodeT *newNode(NodeItemT item)
{
NodeT* node;
// allocate memory for new node
node = (NodeT*) malloc (sizeof(NodeT));
// set item in new node
node->info = item;
return node;
}
NodeItemT* getInfo(NodeT* node)
{
if (node == NULL)
return NULL;
return &(node->info);
}
void setInfo(NodeT* node, NodeItemT item)
{
node->info = item;
}
void freeNode(NodeT * node)
{
free (node);
}
NodeItemT getEmtpyNodeItem()
{
return EmptyNodeItem;
}
vector.c:
#include <stdlib.h>
#include <stdio.h>
#include <malloc.h>
#include "node.h"
#include "vector.h"
/**
* Creates a new and empty vector with an initial capacity.
*
* @param capacity the initial capacity of the Vector.
*/
VectorT* newVector(int capacity)
{
VectorT *vector = malloc(sizeof(VectorT));
vector->list = malloc(capacity * sizeof(NodeT*));
vector->capacity = capacity;
vector->size = 0;
return vector;
}
/**
* Appends a new element to the end of the vector. If the capacity of the vector is reached, the vector
* dynamically grows by a fixed size.
*
* @param vector the vector to be modified
* @param item the item to be appended to the vector
*/
void vadd(VectorT *vector, NodeItemT item)
{
if(vector->size <= vector->capacity)
{
vector->list[vector->size] = newNode(item);
vector->size = vector->size + 1;
}
else
{
VectorT *tempVector = newVector(vector->capacity + GROWTH_RATE);
int i;
for(i=0; i < vector->capacity; i++)
{
tempVector->list[i] = vector->list[i];
}
vdelete(vector);
for(i=0; i < tempVector->capacity; i++)
{
vector->list[i] = tempVector->list[i];
}
}
}
/**
* Returns an element from the vector given a location.
*
* @param vector the vector to be accessed for an element
* @param index the location of the element to be returned
*
* @return the item in the vector at the location or NULL if the location is out of the valid range
* of the vector
*/
NodeItemT* vget(const VectorT *vector, int index)
{
if(index > (vector->capacity))
{
return NULL;
}else
return vector->list[index]->info;
}
/**
* Sets an item in a vector.
*
* @param vector the vector to be modified
* @param item the item to be set
* @param index the location where the item needs to be set
*
* @return the location where the item was set or -1, if the item was not set because the location is
* out of the vector's range
*/
int vset(VectorT *vector, NodeItemT item, int index)
{
if(index <(vector->capacity))
{
(*vector).list[index]->info = item;
return index;
}
else
return -1;
}
/**
* Removes an item in a vector at the specified location and shifts any subsequent elements to the left
* by subtracting one from their indices.
*
* @param vector the vector to be modified
* @param index the location where the item needs to be removed
*/
void vremove(VectorT *vector, int index)
{
int i;
vector->list[index]->info='';
if(index>(vector->size)||index<0)
printf("ERROR INVALID INPUT ");
else if((vector->list[index]->info)=='')
{
for(i=index;i<(vector->size);i++)
{
vector->list[i]=vector->list[i+1];
}
vector->list[vector->size]->info='';
vector->size=(vector->size)-1;
}
}
/**
* Returns the number of elements in the vector.
*
* @param vector the vector whose size is to be determined
*
* @return the total number of elements stored in the vector
*/
int vsize(const VectorT *vector)
{
return vector->size;
}
/**
* Returns the capacity of the vector.
*
* @param vector the vector whose capacity is to be determined
*
* @return the total number of elements that the vector may be able to store
*/
int vcapacity(const VectorT *vector)
{
return vector->capacity;
}
/**
* Tests if the vector contains a specified element.
*
* @param vector the vector to be tested for containment of a specific element
* @param item the item to be tested
*
* @return 1 if the vector contains the element; 0 otherwise
*/
int vcontains(const VectorT *vector, NodeItemT item)
{
int i;
for(i=0; i <= vector->capacity; i++)
{
if(vector->list[i]->info == item)
{
return 1;
}else
return 0;
}
}
/**
* Returns the index for a specified item in the vector.
*
* @param vector the vector to be checked for an element
* @param item the item whose location in the vector needs to be checked
*
* @return the index of the location of the item in the vector or -1 if the item cannot be found
*/
int vindexOf(const VectorT *vector, NodeItemT item)
{
int i;
for(i=0;i<(*vector).size;i++)
if(vector->list[i]->info==item)
return i;
}
/**
* Removes all elements from the specified vector. The capacity remains unchanged but the size changes to 0.
*
* @param vector the vector to be cleared
*/
void vclear(VectorT *vector)
{
int i;
for(i=vector->size;i>=0;i--)
vector->list[i]->info='';
vector->size=0;
}
/**
* Deletes the vector. Memory for storing elements will be deallocated.
*
* @param vector the vector to be deleted
*/
void vdelete(VectorT *vector)
{
int i = 0;
for(i; i<vector->capacity; i++)
{
free(vector->list[i]);
}
free(vector);
}
vector.c vadd function above is what I have so far but I am getting a segmentation fault, like my vector is not dynamically growing. anyhelp would be greatly appreciated.
Explanation / Answer
void add1(VectorT *vector, NodeItemT item)
{
NodeT *tempList;
int i;
if((vector->size)>=(vector->capacity))
{
tempList=(NodeT*)malloc(((vector->capacity)*2)*sizeof(NodeT*));
for(i=0;i<vector->capacity;i++)
tempList[i]=vector->list[i];
for(i=vector->capacity;i<((vector->capacity)*2);i++);
tempList[i].info='';
vector->list=tempList;
vector->capacity=((vector->capacity)*2);
}
vector->list[vector->size].info=item;
vector->size=(vector->size)+1;
}