Assignment: Sorted List

Assigned

• September 9, 2024

Due

• September 16, 2024 11:59pm

Collaboration

All assignments in this class should be completed individually. You may ask for assistance from the instructor or mentor, but you may not discuss any aspect of your work on the assignment with other students in the class.

Submitting

To submit this assignment, run make zip in the VSCode terminal to create a zip archive of your work. Log in to Gradescope at https://gradescope.com and upload it to the Sorted List assignment on Gradescope. You can resubmit as many times as you like before the deadline.

Overview

For this assignment, you will implement a sorted list. This data structure behaves like a normal list, except it maintains all of the values in sorted order (lowest to highest). You are free to implement this data structure using either a linked list or an array, but do not impose an upper limit on the number of elements that can appear in the list. The starter code includes a test program that creates a sorted list and then performs operations on that sorted list that it reads from the command line. Your task for this assignment is to implement each of the sorted list operations.

You will need to complete this assignment using the provided starter code, and upload your code to Gradescope. Follow these steps to set up your working copy of this assignment:

1. Log in to a MathLAN computer, or connect remotely at https://remote.cs.grinnell.edu.
2. Open a terminal window.
3. Run the following commands in your terminal to set up a working directory for this class:

   $ mkdir -p ~/csc213/assignments ~/csc213/exercises ~/csc213/labs
   

4. Now use the git command to check out a copy of the starter code for the assignment:

   $ git clone /home/curtsinger/csc213/assignments/sorted-list ~/csc213/assignments/sorted-list
   

5. And now you can use the code command to open the starter code with Visual Studio Code.

   $ code ~/csc213/assignments/sorted-list
   

6. A Visual Studio Code window should appear with the sorted-list directory open in the file browser. You may see a welcome message, which you can close. You can also close any prompts to upgrade to a new version of VSCode.
7. Open a terminal inside of VSCode using the Terminal menu. By default, terminals appear on the bottom of the window. I find it more conveninent to move it to the right side; just right-click somewhere near the top of the panel that appears and choose Move Panel Right.
8. Now you can run make in the terminal to build the starter code, or just type ctrl+shift+b to run the default build task (which just runs make).

We’ll use VSCode as the default editor for this class. You can use other editors if you prefer, but you’ll be missing out on some useful features. The VSCode projects I distribute will automatically format your C code, and will include some default settings that help with syntax highlighting, running build tasks, etc.

At this point you should read through the requirements for the assignment and review the provided code.

Sorted List Starter Code

The assignment starter code has three source files:

main.c

This contains the driver code to read user input. You may not modify anything in this file.

sorted-list.h

You will need to add fields to the sorted_list_t struct in this file. You are welcome to add additional struct definitions here if you need them, but not global variables. You may not change the names or parameters of any functions declared in this file.

sorted-list.c

You should implement all four functions in this file. You are welcome to add additional helper functions if you like, but you should not use any global variables for this assignment.

The sorted list interface is similar to the stack example from class. Read the details below for information on what each function is meant to do.

void sorted_list_init(sorted_list_t* lst)

This function takes a pointer to a memory location that will be used to hold a sorted list. The lst pointer already points to this location when sorted_list_init is called, so you should not assign a new value to lst. Instead, just fill in any fields in lst required to represent an empty sorted list.

void sorted_list_destroy(sorted_list_t* lst)

This function should clean up any memory allocated to a sorted list. The lst pointer is managed by the caller, so do not free it here. If lst holds any pointers to allocated memory you are responsible for freeing those.

void sorted_list_insert(sorted_list_t* lst, int value)

Add a value to a sorted list. That list should have been initialized already. Walk through the list and find the correct place to insert the value to maintain the list’s sorted order. If the value already appears in the list, insert it again; the order of duplicate entries in the list does not matter.

size_t sorted_list_count(sorted_list_t* lst, int value)

Count how many times a specific value appears in a sorted list and return that count. If the value does not appear in the list, return zero. To receive full credit, you must implement this function in a way that takes advantage of the fact that your list is sorted. It should be possible for your implementation to return a count before walking through the entire list in many cases, although some input/list combinations will require a complete traversal.

void sorted_list_print(sorted_list_t* lst)

Print all of the values in a sorted list separated by a single space, and followed by a newline.

Examples

Here are a few example runs of the program that should help you test your implementation.

The order of values when printed should always be sorted, regardless of insertion order:

$ ./sorted-list
insert 5
insert 4
insert 1
print
1 4 5
insert 3
insert 2
print
1 2 3 4 5

Duplicate values should be preserved, and should appear in sorted order:

$ ./sorted-list
insert 9
insert 8
insert 9
insert 7
insert -3
insert 9
print
-3 7 8 9 9 9

The count command should print the number of times a value appears in the list:

$ ./sorted-list
insert 5
insert 4
insert 3
count 1
0
count 3
1
insert 3
count 3
2
print
3 3 4 5