This assignment is intended to give you practice writing C code (e.g. allocating and freeing memory, working with pointers, etc.) and also to have you start working with one of the most fundamental data structures we'll see in this course: the dynamic array. There are several parts to the assignment, each described below.

For this assignment, you are provided with some starter code that defines the structures you'll be working with and prototypes the functions you'll be writing. It's important that you don't modify the function prototypes. To help grade your assignment, we will use a set of unit tests that assume these functions exist and have the same prototypes that are defined in the starter code. If you change the prototypes, it will cause the unit tests to break, and your grade for the assignment will likely suffer. Feel free, however, to write any additional functions you need to accomplish the tasks described below.

Within the provided starter code is a dynamic array implementation in dynarray.h and dynarray.c. You should use this implementation to provide the dynamic array functionality needed by several of the functions you'll write for the assignment. We will review this implementation in lecture.

Importantly, your work for this assignment will be limited to the file students.c, where you will implement the functions described below. You should not modify any other file in this repository. In addition to the descriptions below, there is thorough documentation in students.c describing how each function you'll write should behave.

1. Implement a function to allocate and initialize a single struct student

In create_student(), implement a function that initializes the values of a single newly-allocated student structure. In particular, this function will be passed values for name, id, and gpa. You should allocate memory on the heap to store a struct student. You should also allocate memory on the heap to store a copy of name and copy name into that memory. Then, you should assign the copy of name, id, and gpa to the corresponding fields in the student structure you allocated and return a pointer to that structure.

2. Implement a function to free the memory held by a single struct student

In free_student(), implement a function that frees any memory that was allocated by create_student() for a single student. This function will be passed a pointer to the student whose held memory is to be freed. You must free any memory allocated for the fields of that student structure as well as the memory allocated for the structure itself. Importantly, this function must free all relevant memory and cannot result in a memory leak.

3. Implement a function to create a dynamic array of struct students

In create_student_array(), implement a function to allocate and initialize a dynamic array (i.e. struct dynarray), store a collection of students in that newly-created dynamic array, and then return a pointer to the array. This function will be provided with arrays specifying the names, IDs, and GPAs of the students to be stored in the array. You should use your create_student() function to allocate and initialize a student structure for each set of provided values and store each allocated student structure in the new dynamic array. In the returned array, the ith student should have the ith name, the ith ID, and the ith GPA. Make sure to use the provided dynamic array functions (e.g. dynarray_create() and dynarray_insert()) to allocate and modify the dynamic array.

4. Implement a function to free the memory in a dynamic array of struct students

In free_student_array(), implement a function that frees all of the memory allocated by create_student_array(). In particular, you should use your free_student() function to free the memory held by each individual student in the array, and then you should free the memory held by the array itself. Again, make sure to use the provided dynamic array functions to access elements in the dynamic array and to free the array itself. Importantly, this function must free all of the memory associated with a dynamic array of student structures. In other words, it may not result in memory leaks.

5. Implement a function to print a dynamic array of struct students

In print_students(), implement a function that prints the name, ID, and GPA of each student in a dynamic array, one student per line. As before, make sure to use the provided dynamic array functions to access elements in the dynamic array.

6. Implement functions to find the students in an array with the lowest and highest GPA

In find_min_gpa() and find_max_gpa(), implement functions to respectively find the student with the lowest GPA and the one with the highest GPA in an array. These functions should return a pointer to these students. Importantly, you should not make a copy of the student returned by these functions. Instead, you should simply return the pointer to a student structure that's already stored in the array.

7. Implement a function to sort the students in a dynamic array by descending GPA

In sort_by_gpa(), implement a function to order the students in a dynamic array by descending GPA (i.e. with the highest GPAs at the beginning of the array). You may use any sorting algorithm you like. This function should abide by the following constraints:

It should sort the students in place. In other words, you should not allocate memory for a new array in this function.

It should not use built-in functions like qsort(). In other words, you have to implement the sorting yourself. You may implement any in-place sorting algorithm you like. Some possibilities are selection sort, insertion sort, bubble sort, and quicksort.

As with all of the other functions that work with dynamic arrays, make sure to use the provided dynamic array functions (e.g. dynarray_get(), dynarray_set(), etc.) to access and modify the contents of the dynamic array.

student.h

/* * This file contains the definitions of structures you'll use for this * assignment along with prototypes of functions you'll have to write. You * should not modify anything in this file. */

#include "dynarray.h"

/* * This structure represents information about a single university student. */ struct student { char* name; int id; float gpa; };

/* * These are the prototypes of the functions you will write in students.c. * See the documentation in students.c for more information about each * function. */ struct student* create_student(char* name, int id, float gpa); void free_student(struct student* student); struct dynarray* create_student_array(int num_students, char** names, int* ids, float* gpas); void free_student_array(struct dynarray* students); void print_students(struct dynarray* students); struct student* find_max_gpa(struct dynarray* students); struct student* find_min_gpa(struct dynarray* students); void sort_by_gpa(struct dynarray* students);

student.c

/*

* This is the file in which you will implement the functionality required by

* the assignment. Make sure to add your name and @oregonstate.edu email

* address below:

*

* Name:

* Email:

*/

#include

#include "students.h"

#include "dynarray.h"

/*

* This function should allocate and initialize a single student struct with

* name, ID, and GPA data.

*

* Params:

* name - a string containing the student's name. Note that you'll have to

* make a copy of this string to store in the student struct instead of

* storing this string directly.

* id - an integer ID for the student

* gpa - the student's GPA

*

* Return:

* Should return a newly-allocated student structure whose fields are

* initialized with the values provided.

*/

struct student* create_student(char* name, int id, float gpa) {

struct student* s;

s->name = name;

s->id = id;

s->gpa = gpa;

return NULL;

}

/*

* This function should free all memory allocated by create_student() for a

* single student. This function must free all relevant memory and cannot

* result in a memory leak.

*

* Params:

* student - a pointer to the student whose memory should be freed. This

* function must free any memory allocated to the fields of this struct

* as well as memory allocated for the struct itself.

*/

void free_student(struct student* student) {

}

/*

* This function should create a struct student for each student represented

* in the information provided in the function arguments, and it should store

* those students in a dynamic array (i.e. struct dynarray) allocated by this

* function. In particular, you should create a dynamic array and insert new

* student structs into it, such that the i'th student in the array has the

* i'th name, the i'th ID, and the i'th GPA from the arrays provided as

* arguments. You should use your create_student() function to allocate and

* initialize each student struct stored in the array, and you should use the

* provided dynamic array functions to allocate and work with the dynamic

* array. At the end of the function, you should return the dynamic array

* with student structures stored in it.

*

* Params:

* num_students - the number of students to be stored in the newly allocated

* dynamic array

* names - an array of the names of the students to be stored in the dynamic

* array of student structs. This array will have length num_students.

* ids - an array of the IDs of the students to be stored in the dynamic

* array of student structs. This array will have length num_students.

* gpas - an array of the GPAs of the students to be stored in the dynamic

* array of student structs. This array will have length num_students.

*

* Return:

* Should return a pointer to the newly allocated dynamic array containing

* newly-created student structs. The i'th student in this array should have

* the i'th name, the i'th ID, and the i'th GPA from the arrays provided as

* arguments.

*/

struct dynarray* create_student_array(int num_students, char** names, int* ids,

float* gpas) {

return NULL;

}

/*

* This function should free all of the memory allocated to a dynamic array of

* student structs, including the memory allocated to the array itself as

* well as any memory allocated to the individual student structs. You

* should use free_student() to free the memory for each individual student,

* and you should use provided dynamic array functions to free the memory

* associated with the dynamic array itself. This function must free *all*

* memory associated with a dynamic array of students and must not result in

* any memory leaks.

*

* Params:

* students - a pointer to the dynamic array of student structs whose memory

* is to be freed

*/

void free_student_array(struct dynarray* students) {

}

/*

* This function should print the name, ID, and GPA of each student in an

* array, one student per line. You must use provided dynamic array functions

* to access the student data stored in the array.

*

* Params:

* students - the dynamic array of students to be printed

*/

void print_students(struct dynarray* students) {

}

/*

* This function should return a pointer to the student in a given array with

* the highest GPA. You should not make a copy of the student being returned,

* i.e. this function should not allocate any memory. Instead, you should

* simply return the pointer to the student struct that's already stored in

* the array. You must use the provided dynamic array functions to access

* the data stored in the array.

*

* Params:

* students - the array from which to find the student with the highest GPA

*

* Return:

* Should return a pointer to the student in the array with the highest GPA.

* You should not make a copy of the student being returned but should

* instead return the pointer to the student struct that's already stored in

* the array.

*/

struct student* find_max_gpa(struct dynarray* students) {

return NULL;

}

/*

* This function should return a pointer to the student in a given array with

* the lowest GPA. You should not make a copy of the student being returned,

* i.e. this function should not allocate any memory. Instead, you should

* simply return the pointer to the student struct that's already stored in

* the array. You must use the provided dynamic array functions to access

* the data stored in the array.

*

* Params:

* students - the array from which to find the student with the lowest GPA

*

* Return:

* Should return a pointer to the student in the array with the lowest GPA.

* You should not make a copy of the student being returned but should

* instead return the pointer to the student struct that's already stored in

* the array.

*/

struct student* find_min_gpa(struct dynarray* students) {

return NULL;

}

/*

* This function should sort the students stored in a dynamic array by

* descending GPA (i.e. highest GPAs at the beginning of the array). You may

* implement any sorting algorithm you want, with the following constraints:

* - You must sort in place, i.e. you can't allocate additional memory.

* - You may not use built-in sorting functions like qsort(), i.e. you must

* implement the sort yourself. You may implement any in-place sorting

* algorithm you like. Some possibilities are selection sort, insertion

* sort, bubble sort, and quicksort.

* - You must use provided dynamic array functions (e.g. dynarray_get(),

* dynarray_set(), etc.) to access and modify the contents of the dynamic

* array.

*

* Params:

* students - the dynamic array of students to be sorted. When the function

* returns, this array should be sorted by descending GPA.

*/

void sort_by_gpa(struct dynarray* students) {

}

test.c

/* * This file contains executable code for testing your work in this assignment. */

#include #include

#include "students.h" #include "dynarray.h"

/* * This is the total number of students in the testing data set. */ #define NUM_TESTING_STUDENTS 8

/* * These are the names of the students that'll be used for testing. */ char* TESTING_NAMES[] = { "Luke Skywalker", "Princes Leia", "Chewbacca", "Han Solo", "Lando Calrissian", "Darth Vader", "C-3PO", "R2-D2" };

/* * These are the student IDs for the students in the array above that will be * used for testing. */ int TESTING_IDS[] = { 933111111, 933222222, 933333333, 933444444, 933555555, 933666666, 933777777, 933888888 };

/* * These are the GPAs of the students above that will be used for testing. */ float TESTING_GPAS[] = { 3.75, 4.0, 3.0, 2.5, 3.67, 1.33, 3.25, 3.9 };

int main(int argc, char** argv) { struct student* s = NULL;

struct dynarray* students;

int i;

/* * Create a student using create_student() and print the results. */ s = create_student(TESTING_NAMES[0], TESTING_IDS[0], TESTING_GPAS[0]); printf(" == Here are the results of create_student(): "); if (s) { printf(" - name: %s\tid: %d\tgpa: %f ", s->name, s->id, s->gpa); } else { printf(" - NULL "); }

/* * Free the student created above. */ free_student(s);

/* * Create an array of students using create_student_array() and print the * results. */ students = create_student_array(NUM_TESTING_STUDENTS, TESTING_NAMES, TESTING_IDS, TESTING_GPAS); printf(" == Here are the results of create_student_array(): "); print_students(students);

/* * Use find_max_gpa() to find the student with the highest GPA and print * the result. */ s = find_max_gpa(students); printf(" == Here's the student with the highest GPA: "); if (s) { printf(" - name: %s\tid: %d\tgpa: %f ", s->name, s->id, s->gpa); } else { printf(" - NULL "); }

/* * Use find_min_gpa() to find the student with the lowest GPA and print * the result. */ s = find_min_gpa(students); printf(" == Here's the student with the lowest GPA: "); if (s) { printf(" - name: %s\tid: %d\tgpa: %f ", s->name, s->id, s->gpa); } else { printf(" - NULL "); }

/* * Use sort_by_gpa() to order the students by decreasing GPA and print the * results. */ sort_by_gpa(students); printf(" == Here are the students ordered by decreasing GPA: "); print_students(students);

/* * Free the memory we allocated to the array. You should use valgrind to * verify that you don't have memory leaks. */ free_student_array(students); printf("my test "); system("pause"); return 0; }

Importantly, your work for this assignment will be limited to the file students.c, where you will implement the functions described below. You should not modify any other file in this repository. In addition to the descriptions below, there is thorough documentation in students.c describing how each function you'll write should behave.