Using C, first, complete the dynamic array implementation. To do this, implement
ID: 3829831 • Letter: U
Question
Using C, first, complete the dynamic array implementation. To do this, implement all functions with the // FIXME... comments in dynamicArray.c . Files below.
/* dynArr.h : Dynamic Array implementation. */
#ifndef DYNAMIC_ARRAY_INCLUDED
#define DYNAMIC_ARRAY_INCLUDED 1
# ifndef TYPE
# define TYPE int
# define TYPE_SIZE sizeof(int)
# endif
# ifndef LT
# define LT(A, B) ((A) < (B))
# endif
# ifndef EQ
# define EQ(A, B) ((A) == (B))
# endif
typedef struct DynArr DynArr;
/* Dynamic Array Functions */
DynArr *newDynArr(int cap);
void deleteDynArr(DynArr *v);
int sizeDynArr(DynArr *v);
void addDynArr(DynArr *v, TYPE val);
TYPE getDynArr(DynArr *v, int pos);
void putDynArr(DynArr *v, int pos, TYPE val);
void swapDynArr(DynArr *v, int i, int j);
void removeAtDynArr(DynArr *v, int idx);
/* Stack interface. */
int isEmptyDynArr(DynArr *v);
void pushDynArr(DynArr *v, TYPE val);
TYPE topDynArr(DynArr *v);
void popDynArr(DynArr *v);
/* Bag Interface */
int containsDynArr(DynArr *v, TYPE val);
void removeDynArr(DynArr *v, TYPE val);
#endif
#include "dynArray.h"
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
/*
* VISUAL STUDIO (VS) USERS: COMMENT OUT THE LINE BELOW
* TO EXCLUDE THE MEMORY TEST CODE.
*/
#define MEMORY_TEST_INCLUDED
#ifdef MEMORY_TEST_INCLUDED
// This header is needed for memory usage calculation.
//#include <sys/resource.h>
#include "string.h"
// Function to get current memory usage in KB (Max Resident Set Size)
int parseLine(char* line) {
int i = strlen(line);
while (*line < '0' || *line > '9') line++;
line[i - 3] = '';
i = atoi(line);
return i;
}
int getMemoryUsage() { //Note: this value is in KB!
FILE* file = fopen("/proc/self/status", "r");
int result = -1;
char line[128];
while (fgets(line, 128, file) != NULL) {
if (strncmp(line, "VmRSS:", 6) == 0) {
result = parseLine(line);
break;
}
}
fclose(file);
return result;
}
//long getMemoryUsage()
//{
// int who = RUSAGE_SELF;
// struct rusage usage;
// getrusage(who, &usage);
// return usage.ru_maxrss;
//}
#endif
// Function to get number of milliseconds elapsed since program started execution
double getMilliseconds()
{
return 1000.0 * clock() / CLOCKS_PER_SEC;
}
int main(int argc, char* argv[])
{
#ifdef MEMORY_TEST_INCLUDED
// Memory used BEFORE creating LinkedList
long m1 = getMemoryUsage();
#endif
if (argc != 2)
{
printf("Usage: %s <number of elements to add> ", argv[0]);
return 1;
}
DynArr * a = newDynArr(1024);
int numElements = atoi(argv[1]);
for (int i = 0 ; i < numElements; i++)
{
addDynArr(a, (TYPE)i);
}
#ifdef MEMORY_TEST_INCLUDED
// Memory used AFTER creating LinkedList
long m2 = getMemoryUsage();
printf("Memory used by Dynamic Array : %ld KB ", m2 - m1);
#endif
double t1 = getMilliseconds(); // Time before contains()
for (int i = 0; i < numElements; i++)
{
containsDynArr(a, i);
}
double t2 = getMilliseconds(); // Time after contains()
printf("Time for running contains() on %d elements: %g ms ", numElements, t2 - t1);
deleteDynArr(a);
return 0;
}
/* dynamicArray.c: Dynamic Array implementation. */
#include <assert.h>
#include <stdlib.h>
#include "dynArray.h"
struct DynArr
{
TYPE *data; /* pointer to the data array */
int size; /* Number of elements in the array */
int capacity; /* capacity ofthe array */
};
/* ************************************************************************
Dynamic Array Functions
************************************************************************ */
/* Initialize (including allocation of data array) dynamic array.
param: v pointer to the dynamic array
param: cap capacity of the dynamic array
pre: v is not null
post: internal data array can hold cap elements
post: v->data is not null
*/
void initDynArr(DynArr *v, int capacity)
{
assert(capacity > 0);
assert(v!= 0);
v->data = (TYPE *) malloc(sizeof(TYPE) * capacity);
assert(v->data != 0);
v->size = 0;
v->capacity = capacity;
}
/* Allocate and initialize dynamic array.
param: cap desired capacity for the dyn array
pre: none
post: none
ret: a non-null pointer to a dynArr of cap capacity
and 0 elements in it.
*/
DynArr* newDynArr(int cap)
{
assert(cap > 0);
DynArr *r = (DynArr *)malloc(sizeof( DynArr));
assert(r != 0);
initDynArr(r,cap);
return r;
}
/* Deallocate data array in dynamic array.
param: v pointer to the dynamic array
pre: none
post: d.data points to null
post: size and capacity are 0
post: the memory used by v->data is freed
*/
void freeDynArr(DynArr *v)
{
if(v->data != 0)
{
free(v->data); /* free the space on the heap */
v->data = 0; /* make it point to null */
}
v->size = 0;
v->capacity = 0;
}
/* Deallocate data array and the dynamic array ure.
param: v pointer to the dynamic array
pre: none
post: the memory used by v->data is freed
post: the memory used by d is freed
*/
void deleteDynArr(DynArr *v)
{
freeDynArr(v);
free(v);
}
/* Resizes the underlying array to be the size cap
param: v pointer to the dynamic array
param: cap the new desired capacity
pre: v is not null
post: v has capacity newCap
*/
void _dynArrSetCapacity(DynArr *v, int newCap)
{
/* FIXME: You will write this function */
}
/* Get the size of the dynamic array
param: v pointer to the dynamic array
pre: v is not null
post: none
ret: the size of the dynamic array
*/
int sizeDynArr(DynArr *v)
{
return v->size;
}
/* Adds an element to the end of the dynamic array
param: v pointer to the dynamic array
param: val the value to add to the end of the dynamic array
pre: the dynArry is not null
post: size increases by 1
post: if reached capacity, capacity is doubled
post: val is in the last utilized position in the array
*/
void addDynArr(DynArr *v, TYPE val)
{
/* FIXME: You will write this function */
}
/* Get an element from the dynamic array from a specified position
param: v pointer to the dynamic array
param: pos integer index to get the element from
pre: v is not null
pre: v is not empty
pre: pos < size of the dyn array and >= 0
post: no changes to the dyn Array
ret: value stored at index pos
*/
TYPE getDynArr(DynArr *v, int pos)
{
/* FIXME: You will write this function */
/* FIXME: you must change this return value */
return 1;
}
/* Put an item into the dynamic array at the specified location,
overwriting the element that was there
param: v pointer to the dynamic array
param: pos the index to put the value into
param: val the value to insert
pre: v is not null
pre: v is not empty
pre: pos >= 0 and pos < size of the array
post: index pos contains new value, val
*/
void putDynArr(DynArr *v, int pos, TYPE val)
{
/* FIXME: You will write this function */
}
/* Swap two specified elements in the dynamic array
param: v pointer to the dynamic array
param: i,j the elements to be swapped
pre: v is not null
pre: v is not empty
pre: i, j >= 0 and i,j < size of the dynamic array
post: index i now holds the value at j and index j now holds the value at i
*/
void swapDynArr(DynArr *v, int i, int j)
{
/* FIXME: You will write this function */
}
/* Remove the element at the specified location from the array,
shifts other elements back one to fill the gap
param: v pointer to the dynamic array
param: idx location of element to remove
pre: v is not null
pre: v is not empty
pre: idx < size and idx >= 0
post: the element at idx is removed
post: the elements past idx are moved back one
*/
void removeAtDynArr(DynArr *v, int idx)
{
/* FIXME: You will write this function */
}
/* ************************************************************************
Stack Interface Functions
************************************************************************ */
/* Returns boolean (encoded in an int) demonstrating whether or not the
dynamic array stack has an item on it.
param: v pointer to the dynamic array
pre: the dynArr is not null
post: none
ret: 1 if empty, otherwise 0
*/
int isEmptyDynArr(DynArr *v)
{
/* FIXME: You will write this function */
/* FIXME: You will change this return value*/
return 1;
}
/* Push an element onto the top of the stack
param: v pointer to the dynamic array
param: val the value to push onto the stack
pre: v is not null
post: size increases by 1
if reached capacity, capacity is doubled
val is on the top of the stack
*/
void pushDynArr(DynArr *v, TYPE val)
{
/* FIXME: You will write this function */
}
/* Returns the element at the top of the stack
param: v pointer to the dynamic array
pre: v is not null
pre: v is not empty
post: no changes to the stack
*/
TYPE topDynArr(DynArr *v)
{
/* FIXME: You will write this function */
/* FIXME: You will change this return value*/
return 1;
}
/* Removes the element on top of the stack
param: v pointer to the dynamic array
pre: v is not null
pre: v is not empty
post: size is decremented by 1
the top has been removed
*/
void popDynArr(DynArr *v)
{
/* FIXME: You will write this function */
}
/* ************************************************************************
Bag Interface Functions
************************************************************************ */
/* Returns boolean (encoded as an int) demonstrating whether or not
the specified value is in the collection
true = 1
false = 0
param: v pointer to the dynamic array
param: val the value to look for in the bag
pre: v is not null
pre: v is not empty
post: no changes to the bag
*/
int containsDynArr(DynArr *v, TYPE val)
{
/* FIXME: You will write this function */
/* FIXME: You will change this return value */
return 1;
}
/* Removes the first occurrence of the specified value from the collection
if it occurs
param: v pointer to the dynamic array
param: val the value to remove from the array
pre: v is not null
pre: v is not empty
post: val has been removed
post: size of the bag is reduced by 1
*/
void removeDynArr(DynArr *v, TYPE val)
{
/* FIXME: You will write this function */
}
Explanation / Answer
I modified a few functions for you. Here is the modified code for you:
/* dynamicArray.c: Dynamic Array implementation. */
#include <assert.h>
#include <stdlib.h>
#include "dynArray.h"
struct DynArr
{
TYPE *data; /* pointer to the data array */
int size; /* Number of elements in the array */
int capacity; /* capacity ofthe array */
};
/* ************************************************************************
Dynamic Array Functions
************************************************************************ */
/* Initialize (including allocation of data array) dynamic array.
param: v pointer to the dynamic array
param: cap capacity of the dynamic array
pre: v is not null
post: internal data array can hold cap elements
post: v->data is not null
*/
void initDynArr(DynArr *v, int capacity)
{
assert(capacity > 0);
assert(v!= 0);
v->data = (TYPE *) malloc(sizeof(TYPE) * capacity);
assert(v->data != 0);
v->size = 0;
v->capacity = capacity;
}
/* Allocate and initialize dynamic array.
param: cap desired capacity for the dyn array
pre: none
post: none
ret: a non-null pointer to a dynArr of cap capacity
and 0 elements in it.
*/
DynArr* newDynArr(int cap)
{
assert(cap > 0);
DynArr *r = (DynArr *)malloc(sizeof( DynArr));
assert(r != 0);
initDynArr(r,cap);
return r;
}
/* Deallocate data array in dynamic array.
param: v pointer to the dynamic array
pre: none
post: d.data points to null
post: size and capacity are 0
post: the memory used by v->data is freed
*/
void freeDynArr(DynArr *v)
{
if(v->data != 0)
{
free(v->data); /* free the space on the heap */
v->data = 0; /* make it point to null */
}
v->size = 0;
v->capacity = 0;
}
/* Deallocate data array and the dynamic array ure.
param: v pointer to the dynamic array
pre: none
post: the memory used by v->data is freed
post: the memory used by d is freed
*/
void deleteDynArr(DynArr *v)
{
freeDynArr(v);
free(v);
}
/* Resizes the underlying array to be the size cap
param: v pointer to the dynamic array
param: cap the new desired capacity
pre: v is not null
post: v has capacity newCap
*/
void _dynArrSetCapacity(DynArr *v, int newCap)
{
/* FIXME: You will write this function */
realloc(v->data, sizeof(int) * newCap);
v->capacity = newCap;
}
/* Get the size of the dynamic array
param: v pointer to the dynamic array
pre: v is not null
post: none
ret: the size of the dynamic array
*/
int sizeDynArr(DynArr *v)
{
return v->size;
}
/* Adds an element to the end of the dynamic array
param: v pointer to the dynamic array
param: val the value to add to the end of the dynamic array
pre: the dynArry is not null
post: size increases by 1
post: if reached capacity, capacity is doubled
post: val is in the last utilized position in the array
*/
void addDynArr(DynArr *v, TYPE val)
{
/* FIXME: You will write this function */
if(v->size == v->capacity)
_dynArrSetCapacity(v, v->capacity + 1);
v->data[v->size] = val;
(v->size)++;
}
/* Get an element from the dynamic array from a specified position
param: v pointer to the dynamic array
param: pos integer index to get the element from
pre: v is not null
pre: v is not empty
pre: pos < size of the dyn array and >= 0
post: no changes to the dyn Array
ret: value stored at index pos
*/
TYPE getDynArr(DynArr *v, int pos)
{
/* FIXME: You will write this function */
if(pos >= 0 && pos < v->size)
/* FIXME: you must change this return value */
return v->data[pos];
else
return -1;
}
/* Put an item into the dynamic array at the specified location,
overwriting the element that was there
param: v pointer to the dynamic array
param: pos the index to put the value into
param: val the value to insert
pre: v is not null
pre: v is not empty
pre: pos >= 0 and pos < size of the array
post: index pos contains new value, val
*/
void putDynArr(DynArr *v, int pos, TYPE val)
{
/* FIXME: You will write this function */
if(pos >= 0 && pos < v->size)
v->data[pos] = val;
}
/* Swap two specified elements in the dynamic array
param: v pointer to the dynamic array
param: i,j the elements to be swapped
pre: v is not null
pre: v is not empty
pre: i, j >= 0 and i,j < size of the dynamic array
post: index i now holds the value at j and index j now holds the value at i
*/
void swapDynArr(DynArr *v, int i, int j)
{
/* FIXME: You will write this function */
TYPE temp = v->data[i];
v->data[i] = v->data[j];
v->data[j] = temp;
}
/* Remove the element at the specified location from the array,
shifts other elements back one to fill the gap
param: v pointer to the dynamic array
param: idx location of element to remove
pre: v is not null
pre: v is not empty
pre: idx < size and idx >= 0
post: the element at idx is removed
post: the elements past idx are moved back one
*/
void removeAtDynArr(DynArr *v, int idx)
{
/* FIXME: You will write this function */
for(int i = idx; i < v->size-1; i++)
v->data[i] = v->data[i+1];
v->size--;
}
/* ************************************************************************
Stack Interface Functions
************************************************************************ */
/* Returns boolean (encoded in an int) demonstrating whether or not the
dynamic array stack has an item on it.
param: v pointer to the dynamic array
pre: the dynArr is not null
post: none
ret: 1 if empty, otherwise 0
*/
int isEmptyDynArr(DynArr *v)
{
/* FIXME: You will write this function */
if(v->size == 0)
/* FIXME: You will change this return value*/
return 1;
return 0;
}
/* Push an element onto the top of the stack
param: v pointer to the dynamic array
param: val the value to push onto the stack
pre: v is not null
post: size increases by 1
if reached capacity, capacity is doubled
val is on the top of the stack
*/
void pushDynArr(DynArr *v, TYPE val)
{
/* FIXME: You will write this function */
}
/* Returns the element at the top of the stack
param: v pointer to the dynamic array
pre: v is not null
pre: v is not empty
post: no changes to the stack
*/
TYPE topDynArr(DynArr *v)
{
/* FIXME: You will write this function */
/* FIXME: You will change this return value*/
return 1;
}
/* Removes the element on top of the stack
param: v pointer to the dynamic array
pre: v is not null
pre: v is not empty
post: size is decremented by 1
the top has been removed
*/
void popDynArr(DynArr *v)
{
/* FIXME: You will write this function */
}
/* ************************************************************************
Bag Interface Functions
************************************************************************ */
/* Returns boolean (encoded as an int) demonstrating whether or not
the specified value is in the collection
true = 1
false = 0
param: v pointer to the dynamic array
param: val the value to look for in the bag
pre: v is not null
pre: v is not empty
post: no changes to the bag
*/
int containsDynArr(DynArr *v, TYPE val)
{
/* FIXME: You will write this function */
/* FIXME: You will change this return value */
return 1;
}
/* Removes the first occurrence of the specified value from the collection
if it occurs
param: v pointer to the dynamic array
param: val the value to remove from the array
pre: v is not null
pre: v is not empty
post: val has been removed
post: size of the bag is reduced by 1
*/
void removeDynArr(DynArr *v, TYPE val)
{
/* FIXME: You will write this function */
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.