PA 2: Integer List Sorter: Array and Linked List Operations

Due date: February 11 23:59

Github Classroom Assignment

Updates and Revisions

[Jan 29 17:20] Added section on valgrind.
[Feb 5 23:20] Updated Grading and Point Distribution and Sample test cases sections.
[Feb 7 11:21] Added fgets in File I/O operations

Learning Goals
Getting Help
Introduction
1. Linked Lists
Getting Started
The Starter Code
Error Handling
Finding Memory Errors [Updated Jan 29 17:20]
Formatting your code
1. The clang-format Tool
2. Running clang-format
Sample Test Cases [Updated Feb 5 23:20]
Submission Instructions
1. Submitting from GitHub
Grading and Point Distribution [Updated Feb 5 23:20]

Learning Goals

In this assignment, we will–

Gain proficiency in implementing and manipulating linked lists and arrays in C,
Practice using pointers with structs to dynamically create and manage linked lists,
Understand file input/output operations and how to handle them in C programs,
Learn to handle user input and output through interactive console operations,
Strengthen debugging and error-handling techniques in C programming,
Learn how to use srand() and rand() to generate random numbers,
Learn how to use a code formatter.

Getting Help

You are always welcome to come to either instructor or TA office hours. Both of which are listed on the course website. In office hours, however, conceptual questions will be prioritized.

If you need help while working on this PA, make sure to attend tutor hours. Tutor hours policy can be found in the syllabus.

You can also post questions on Piazza or collaborate with your peers 👀
Collaboration guide

Introduction

This assignment is designed to provide hands-on experience with fundamental data structures and algorithms in C. Specifically, you will utilize structs and pointers to dynamically create and manipulate linked lists. The program will also demonstrate how to manage and convert data between arrays and linked lists, implement file input/output, and sort data efficiently. You will work with arrays and linked lists to perform a variety of operations, such as searching, sorting, and converting between the two structures. Additionally, you will learn to implement file input/output and manage memory dynamically.

Linked Lists

Linked lists are one of the most fundamental data structures in computer science. Unlike an array, where the elements are stored continuously in memory, elements in a linked list can be anywhere, and the ordering is maintained by a pointer in each element that points to the next element (hence the name linked list).

Here’s an illustration of what a linked list looks like:

Linked List

(Source: GeeksforGeeks: Understanding the basics of Linked List)

In this programming assignment, you will be creating a linked list interface.

Getting Started

All of our programming assignments will be hosted on GitHub Classoom. Use the following link to accept the GitHub Classroom assignment.

Click here to accept this GitHub Classroom assignment. (Right click to open in new tab)

Once the assignment is accepted, you will see a repository generated for you with the started code for this assignment. Click the link to go to the repository.

You should now clone this repository into your ieng6 workspace. Remember the cse29/ directory you created on ieng6? It would be a good idea to clone it there. If you do not remember how to clone a repository, check out Lab 2 again.

You should have set up ssh authentication for your GitHub account during lab. To clone using ssh authentication, click the green “Code” button and select the “SSH” tab. Use the URL there to clone the repo.

Once you have cloned the repository, you can cd into it, where you will find the following files:

generate.c: Code implementation to generate random numbers
list.c: The starter code
.clang-format: A configuration file for formatting the C code according to coding style guidelines
README.md

The Starter Code

Task 1: Generate integers and store it in a file

To begin with, you are given the program generate.c, which generates a random set of integers using srand() and rand() functions and prints out every integer in its own line to the console (stdout). The program takes two command line arguments:

total_nums: The number of integers to be generated

max_num: The upper bound on the highest value

srand() and rand()

The srand() and rand() functions in C are used for generating pseudo-random numbers:

srand(unsigned int seed) initializes the random number generator. It sets the starting point for producing a series of pseudo-random integers. Using the same seed will result in the same sequence of random numbers.

rand() returns a pseudo-random integer between 0 and RAND_MAX (typically 32767). It generates the next number in the sequence initialized by srand().

In the provided generate.c, srand(SEED) is used to ensure reproducible random number generation, while rand() % max_num generates random numbers within the specified range.

To use this program to generate the input file for list.c, do the following:

Compile the program and store the executable in a file named generate.
Run the program using the following command:
```
 ./generate 20 100
```
For the purpose of this program we will keep the number of integers (20 in this case) below 1000, which is defined as a symbolic constant MAX_INTS in list.c.
The program should have printed out a list of integers to stdout, each on its own line.
Alter the shell command such that the output sent to stdout is instead captured in a file. This is called a shell redirect.
```
 ./generate 20 100 > numbers.txt
```
The program should have created a file named numbers.txt, which contains a list of integers written as ASCII characters.
To try to see the results, you might try the shell command:
```
 cat numbers.txt
```
Commit this newly created text file in your repository using the git commit command.

Below is the expected output -

generate-output

Task 2: Read the integers from the file and build a linked list

Now, once we have our input file, we can move on to our actual program implementation. You have been provided with the file list.c which contains skeleton code for the functions that you need to complete to make the program work as expected.

The program takes in a single command line argument input_file, in our case, numbers.txt, which is the name of the file containing the list of integers to sort.

./list numbers.txt

Now, implement the below steps in your main function:

Open the file numbers.txt using the fopen function.
Read the integers one at a time from the file using the fscanf function, and place each integer in an dynamically allocated array of size MAX_INTS.
Print the array using the print_array function.
Create a linked list from the array using the create_list function, and print the list using the print_list function.

File I/O operations [Updated Feb 7, 11:21]

Opening Files

To open a file, use the fopen() function:

FILE *file = fopen("filename.txt", "mode");

Common modes include:

“r” for reading,

“w” for writing (creates a new file or truncates existing file),

“a” for appending,

Always check if the file was opened successfully:

if (file == NULL) {
    printf("Error opening file!\n");
    return 1;
}

Reading from Files

For reading integers, you can use fscanf() or fgets():

int num;
while (fscanf(file, "%d", &num) != EOF) {
    // Process the integer
}

char buffer[256];
while (fgets(buffer, sizeof(buffer), file) != NULL) {
    // Process the line stored in buffer
}

Writing to Files

To write to a file, use fprintf():

fprintf(file, "%d\n", number);

Closing Files Always close files when you’re done:

fclose(file);

To create the list, you will essentially need to complete the following function implementations:

create_list() Function

struct node* create_list(int intarray[], int len)

This function is responsible for transforming an array of integers into a linked list.

It takes two critical parameters: an integer array containing the numbers to be converted and the length of that array. The function will systematically traverse the input array and use the add_item_at_start function to construct a linked list. Each new item is added to the start of the list. Upon completion, it returns a pointer to the head of the newly created linked list.

add_item_at_start() Function

struct node* add_item_at_start(struct node *head, int data)

This function handles the core mechanism of inserting a new node at the beginning of a linked list.

It receives two parameters: a pointer to the current head of the list and the integer data to be added as a new node. The function dynamically allocates memory for a new node using malloc(), sets the node’s data to the provided integer, and updates the node’s next pointer to point to the previous head. This effectively inserts the new node at the start of the list and returns the new head of the list.

The structure of the node

The structure of a node in the linked list is defined in the provided starter file. Here’s how it looks:

struct node {
    int data;
    struct node *next;
};

This structure defines a node in the linked list, consisting of two members:

int data: This integer field stores the actual value or data of the node.
struct node *next: This is a pointer to another node structure, which represents the next node in the list.

This structure allows each node to hold an integer value and a reference to the next node in the sequence, forming the basis of a singly linked list. The last node in the list typically has its next pointer set to NULL, indicating the end of the list.

A pointer to the first node in the list identifies where the list is. It is called the head of the list. If the head has the value NULL, then the list is empty. When implementing the create_list and add_item_at_start functions, you’ll be working with this node structure to build and manipulate the linked list. Each time you add a new item to the list, you’ll create a new instance of this structure, set its data field to the integer value being added, and adjust the next pointer to maintain the list’s structure.

Task 3: Search for integers

Once we have the array and the linked list populated with integers, the next step is to have the user input a number for which it will search both the array and the linked list to confirm its index and position.

Implement the below steps in the main function:

Prompt the user for a number to search (as shown in Sample Output) and read the input from the keyboard (stdin) using scanf.
Search for the number in the array to find its index. This can be done by completing the search_array() function.
```
 int search_array(int integers[], int numints, int element)
```
This function performs a search through an array of integers to locate a specific element.

It takes three parameters: the integer array to search, the total number of integers in the array, and the element to find. The function iterates through the array, comparing each element with the target. If the element is found, it returns the index of that element. If the element is not found, it returns -1 to indicate the element’s absence.
Print the result of the search and the index of the number if it was found in the array. See the Sample Output for the output format.
Search the number in the linked list to find its position. This can be done by completing the search_list() function.
```
 int search_list(struct node *head, int element)
```
Similar to search_array, this function conducts a search through a linked list to find a specific element.

It takes two parameters: the head of the list and the target element. The function traverses the linked list, keeping track of the current position. If the element is found, it returns the one-based position of the element in the list. If the element is not found after traversing the entire list, it returns -1.
Print out the result of the search and the position of the number if it was found in the linked list.
Repeat steps 1-5 until the user enters the character ‘q’; in this case, stop prompting the user for input and move on.

You can assume that the user will only enter a valid integer or the character ‘q’.

Task 4: Sort the linked list and write the output to a file

Now we will sort the numbers by constructing a new linked list.

Be careful not to modify or destroy the original list that we created.

Implement the below steps in the main function:

Create a new sorted list by calling the create_sorted_list() function.
```
 struct node* create_sorted_list(struct node *head)
```
This function creates a new sorted linked list from an existing unsorted list.

It takes the head of the original unsorted list as input and constructs a new list where elements are arranged in ascending order. The function achieves this by iterating through each node of the original list and using the add_item_sorted() function to insert each element into the correct position in the new sorted list.
```
 struct node* add_item_sorted(struct node *sorted_head, int data)
```
This function is crucial for maintaining the sorted order of a linked list.

It takes two parameters: the head of a sorted list and a new data element. The function determines the correct position for the new element within the existing sorted list, ensuring that after insertion, the list remains sorted in ascending order. This is essentially an implementation of the insertion sort algorithm for linked lists.

For example, in the list shown in the Sample Output, when we create the sorted linked list we would insert the first node with value 59 from the original linked list to the sorted linked list. Next, when we try to insert the second node from the original linked list (with a value of 98) into the sorted linked list, we need to make sure that this node with value 98 is inserted after the node with value 59. So, if you try to print the sorted linked list after inserting two nodes in the sorted order it would look like as shown below:
```
 SORTED LINKED LIST: head → |59| → |98| → NULL
```
Once both the functions are implemented, print the sorted list using the print_list function.
Copy the sorted list to a new array using the function copy_list_to_array(struct node *head, int *array) function:
```
int copy_list_to_array(struct node *head, int *array)
```
This function transfers elements from a linked list to an array while preserving their order.

It takes two parameters: the head of a list and a pointer to an array as input. The function traverses the linked list, copying each element to the corresponding index in the array. It returns the number of integers successfully copied to the array, which helps track the list’s length.

Please make sure that you don’t overwrite the contents of your original unsorted array.
Print the sorted array using the print_array function.
Print the original linked list again using the print_list function.
Print the original array again using the print_array function.
Open a new file named sorted_numbers.txt using fopen function in “w” mode.
Write the sorted integers from the sorted array to this file, line by line with each integer on its own line using fprintf function.
Close the file and print out the number of integers written to the file.

It’s important to note that the print_array and print_list functions will be provided in the starter code. Additionally, the main function in the starter code contains comments to guide you step-by-step on what exactly to do for each part of the assignment.

Sample Output

sample_output

sorted_txt

Error Handling

If the user invokes the list program incorrectly (for example, without an argument, or with two or more arguments), the program should print an error message and return 1 as shown below.

usage_error

Be sure to always check the return value of library functions. For example, if a file cannot be opened, then the program should not read input. Instead it should print an error message as shown below.

wrong_file_error

When using dynamic memory allocation functions like malloc(), always check if the allocation was successful.
Before dereferencing pointers, always check if they are NULL.

Always make sure to exit the program by returning 1 when you encounter errors. This ensures proper error handling and program termination in case of unexpected issues.

Finding Memory Errors [Updated Jan 29 17:20]

In this PA, you are very likely to run into various types of memory errors and leaks, valgrind is an excellent tool for finding memory errors.

Memory leaks are especially harmful in long-running programs, where the amount of available memory gradually reduces over a long time, thereby also reducing the overall performance of the program or the computer in general.

In our autograder, we expect your code to run without any memory errors. (Most importantly, it should not have any memory leaks!) To make sure of that, you need to run valgrind yourself on your program:

First, compile the program as usual:

gcc list.c -o list

Then call valgrind with the executable file along with the appropriate command line arguments

valgrind ./list numbers.txt

Once the program is executed completely, you will be able to see a summary of your memory consumption and leaks, if any. Below is the sample output with valgrind:

Formatting your code

Coding style dictates how code is laid out in a file. As you read more and more code throughout your career, you will realize the importance of having a clean and consistent coding style.

It’s what makes this so hard to understand:

#include<stdio.h>
int main(){
int limit;


  printf("Enter a limit: ");


          //scanf("%i", limit);
          scanf("%d", &limit);
        printf("Even numbers between 1 and %d:\n", limit);
    for (int i=1;i<=l; i++) {
    if (i%2 ==0) {
      //printf(i);
        printf(  "%d ",i);
    }
}
printf ("\n");
    return 0;

}

…whereas this is nice, clean and straightforward to read:

#include <stdio.h>

int main() 
{
    int limit;

    printf("Enter a limit: ");
    scanf("%d", &limit);

    printf("Even numbers between 1 and %d:\n", limit);
    for (int i = 1; i <= limit; i++) {
        if (i % 2 == 0) {
            printf("%d ", i);
        }
    }
    printf("\n");

    return 0;
}

The latter is neat, well-indented, readable, commented and split into logical blocks. The former is an unholy mess, which sadly, we say far too often in office hours. While both pieces of code do work perfectly fine in C (unlike Python which strictly enforces indentation), tracing through and debugging the latter example is infinitely easier than the former.

For this reason, we will mandate neat code if you wish to seek help from Tutors/TAs. Even if you don’t plan on going to office hours, it is always good practice to style your code for your own sake ~~unless you prefer the former for some reason~~.

There is empirical evidence that poorly formatted code leads to more bugs!

Who has time to format their code all the time? I hear you ask. And indeed, it would be much easier if this were automated.

The `clang-format` Tool

For this purpose, we have the clang-format tool. While this can be integrated into an IDE such as Visual Studio Code, we will simply run it from the command line. We have created a .clang-format file for you that contains all the right settings to work for your code in particular.

Running `clang-format`

In your directory with your C code, run the following command:

$ clang-format -i *.c

This command runs the clang-format program. The -i flag tells it to modify the source files in place, which means changes will be made directly to the files. *.c tells the program to format all files with the extension .c in the working directory.

Sample Test Cases [Updated Feb 5 23:20]

We will test your code using unit tests - small tests that are designed to individually verify correctness of your functions. Here are the descriptions of test scenarios that you should test your code against:

struct node* create_list(int intarray[], int len)

Empty array: Pass an empty array and verify that the returned list is NULL.

Single element array: Pass an array with one element.

Multiple elements: Pass an array with multiple elements.
struct node* add_item_at_start(struct node *head, int data)

Empty list: Pass null as head to ensure a new node is created.

Non-empty list: Verify that the new node is at the start and correctly points to the previous head.

Repeated elements: Verify the placement of the nodes with repeated elements
int search_array(int integers[], int numints, int element)

Element present: Search for an existing element and check if it returns the correct position.

Element not present: Ensure the function returns -1 if the element is not in the list.

Empty array: Search in an empty array and confirm it returns -1.

Duplicate values: Ensure the function returns the position of the first occurrence.
int search_list(struct node *head, int element)

Element present: Search for an existing element and check if it returns the correct position.

Element not present: Ensure the function returns -1 if the element is not in the list.

Empty list: Search in an empty list and verify it returns -1.

Single-element list: Check if searching for the only element returns position 1.

Duplicate values: Ensure the function returns the position of the first occurrence.
struct node* create_sorted_list(struct node *head)

Empty list: Pass null and verify that the function returns null.

Sorted list: Ensure a sorted list remains unchanged.

Unsorted list: Test with an unsorted list and verify that the returned list is sorted.

Duplicate values: Verify the placement of the nodes with repeated elements
struct node* add_item_sorted(struct node *head, int data)

Empty list: Pass null as head to ensure a new node is created.

Insert at the start: Insert a value smaller than all existing values and verify that it becomes the new head.

Insert in the middle: Insert a value between two nodes.

Insert at the end: Insert a value greater than all existing values and verify that it is at the end of the list.

Duplicate values: Verify the placement of the nodes with repeated elements
int copy_list_to_array(struct node *head, int *array)

Empty list: Copy an empty list and verify that the function returns 0.

Single-element list: Ensure the array contains the correct single value.

Multiple elements: Verify that the array correctly shows the linked list values.

Duplicate values: Verify the placement of the values with repeated elements

Submission Instructions

Submitting from GitHub

Unlike the first assignment, you no longer need to download files from ieng6—this avoids common issues with scp. Instead, you can submit your assignment directly from your GitHub repository.

Steps to Submit:

Push Your Latest Code: Ensure your most recent changes are pushed to GitHub. To verify, visit your repository on GitHub and check for updates.
Submit via Gradescope:
- Navigate to the submission page for this PA using this link.
- When you submit the assignment, you will see the option to submit from a specific GitHub repository.
- Link your GitHub account if you haven’t already.
- Select your pa2 repository and choose the main branch for submission.

This streamlined process eliminates the need for file transfers and makes submissions more efficient.

Your github repo should include the input file numbers.txt and the output file sorted_numbers.txt as well. Your code is going to be tested against different input files.

Grading and Point Distribution [Updated Feb 5 23:20]

1. Unit Tests (28 Points Total)

Each unit test in your functions is worth 1 point.
Note: While the number of tests per function may vary (some functions have 3 tests, others 4, or 5), the total number of unit tests is 28.
Calculation: Total unit tests = 28 → 28 points

2. Integration Tests (10 Points Total)

Your code will be evaluated using 10 different sets of input files.
- Public Test Cases: 5 tests (visible to you)
- Hidden Test Cases: 5 tests (not visible to you)
Calculation: 10 integration tests × 1 point each = 10 points

3. Valgrind Check (1 Point)

Your code must be free of memory leaks and errors as verified by Valgrind.
Award: 1 point

Total Points Available:
28 (Unit Tests) + 10 (Integration Tests) + 1 (Valgrind Check) = 39 Points

Except the 5 hidden integration test cases, everything else will be visible!