Abstract In this programming assignment, you will implement smart arrays (arrays that expand automatically whenever they get too full). This is an immensely powerful and awesome data structure, and it will ameliorate several problems we often encounter with arrays in C (see pg. 3 of this PDF). By completing this assignment, you will gain advanced experience working with dynamic memory management and structs in C. You will also gain additional experience managing programs that use multiple source files. In the end, you will have an awesome and useful data structure that you can reuse in the future.

1. Overview A smart array is an array that grows to accommodate new elements whenever it gets too full. As with normal arrays in C, we have direct access to any index of the smart array at any given time. There are four main advantages to using smart arrays, though: 1. We do not need to specify the length of a smart array when it is created. Instead, it will automatically expand when it gets full. This is great when we dont know ahead of time just how much data were going to end up holding in the array. 2. We will use get() and put() functions to access individual elements of the array, and these functions will check to make sure we arent accessing array positions that are out of bounds. (Recall that C doesnt check whether an array index is out of bounds before accessing it during program execution. That can lead to all kinds of whacky trouble!) 3. If our arrays end up having wasted space (i.e., they arent full), we can trim them down to size. 4. In C, if we have to pass an array to a function, we also typically find ourselves passing its length to that function as a second parameter. With smart arrays, the length will get passed automatically with the array, as theyll both be packaged together in a struct. While some languages offer built-in support for smart arrays (such as Javas ArrayList class), C does not. Thats where you come in. You will implement basic smart array functionality in C, including: 1. automatically expanding the smart arrays capacity when it gets full; 2. adding new elements into arbitrary positions in the smart array, or at the end of the smart array; 3. providing safe access to elements at specific positions in the smart array; 4. gracefully signaling to the user (i.e., the programmer (re-)using your code) when he or she attempts to access an index in the smart array that is out of bounds (instead of just segfaulting); In this assignment, your smart array will be designed to hold arrays of strings. A complete list of the functions you must implement, including their functional prototypes, is given below in Section 3, Function Requirements). You will submit a single source file, named SmartArray.c, that contains all required function definitions, as well as any auxiliary functions you deem necessary. In SmartArray.c, you should #include any header files necessary for your functions to work, including SmartArray.h (see Section 2, SmartArray.h). Note that you will not write a main() function in the source file you submit! Rather, we will compile your source file with our own main() function(s) in order to test your code. We have attached example source files that have main() functions, which you can use to test your code.

2. SmartArray.h This header file contains the struct definition and functional prototypes for the smart array functions you will be implementing. You should #include this file from your SmartArray.c file, like so:

#include "SmartArray.h"

The basic struct you will use to implement the smart arrays (defined in SmartArray.h) is as follows: typedef struct SmartArray

{

char **array; // pointer to array of strings

int size; // number of elements in array

int capacity; // length of array (maximum capacity)

} SmartArray;

3. Function Requirements

In the source file you submit, SmartArray.c, you must implement the following functions. You may implement any auxiliary functions you need to make these work, as well. Please be sure the spelling, capitalization, and return types of your functions match these prototypes exactly. In this section, I often refer to malloc(), but youre welcome to use calloc() or realloc() instead, as you see fit.

SmartArray *createSmartArray(int length); Description: Dynamically allocate space for a new SmartArray. Initialize its internal array to be of length length or DEFAULT_INIT_LEN, whichever is greater. (DEFAULT_INIT_LEN is defined in SmartArray.h.) Properly initialize pointers in the array to NULL, and set the size and capacity members of the struct to the appropriate values. Output: -> Created new SmartArray of size . (Output should not include the quotes. Terminate the line with a newline character, . should of course be the length of the new array, without the angled brackets.) Returns: A pointer to the new SmartArray, or NULL if any calls to malloc() failed.

char *put(SmartArray *smarty, char *str); Description: Insert a copy of str into the next unused cell of the array. If the array is already full, call expandSmartArray() to grow the array to length (capacity * 2 + 1) before inserting the new element. When copying str into the array, only allocate the minimum amount of space necessary to store the string. Returns: A pointer to the copy of the new string that was inserted into the array, or NULL if the string could not be added to the array (e.g., malloc() failed, or smarty or str was NULL).

===================================================================================

SmartArray.h

================

#ifndef __SMART_ARRAY_H

#define __SMART_ARRAY_H

// Default capacity for new SmartArrays

#define DEFAULT_INIT_LEN 10

typedef struct SmartArray

{

// We will store an array of strings (i.e., an array of char arrays)

char **array;

// Size of array (i.e., number of elements that have been added to the array)

int size;

// Length of the array (i.e., the array's current maximum capacity)

int capacity;

} SmartArray;

// Functional Prototypes

SmartArray *createSmartArray(int length);

SmartArray *destroySmartArray(SmartArray *smarty);

SmartArray *expandSmartArray(SmartArray *smarty, int length);

SmartArray *trimSmartArray(SmartArray *smarty);

char *put(SmartArray *smarty, char *str);

char *get(SmartArray *smarty, int index);

char *set(SmartArray *smarty, int index, char *str);

char *insertElement(SmartArray *smarty, int index, char *str);

int removeElement(SmartArray *smarty, int index);

int getSize(SmartArray *smarty);

void printSmartArray(SmartArray *smarty);

double difficultyRating(void);

double hoursSpent(void);

#endif

============================================================================