Functions and Strings in C

Due 11:55pm on Wednesday, February 5, 2020.

In this lab, we will focus on functions and strings in C by implementing bubble sort of character strings.

Relevant readings:

• Perry and Miller: Chapters 6, 19, 21-22 (arrays), 23 (sorting) and 30-32 (functions).
• Note: The bubble sort algorithm in Perry/Miller is somewhat different from the most commonly used version. We will use the version specified below.
• C string library functions: http://www.cplusplus.com/reference/cstring/.
• Please review Lab 3 for how strings are declared and manipulated in C.

Bubble Sort

We will use the bubble sort algorithm for sorting. This algorithm repeatedly scans a list or array of values, from left to right, comparing two neighboring values at a time, and swaps them if they are out of order. For more details, please see this Wikipedia article. You will use the algorithm described in the first pseudocode (under "Implementation"), or the optimized version that appears immediately thereafter (or any other largely similar version). While bubble sort is one of the simplest sorting algorithms, it is not the most efficient one. (Here's an interesting video clip from popular culture.)

In this assignment, you will extend the bubble sort algorithm for sorting integers into your own algorithm for sorting strings.

Exercise 1

For the first version of sorting strings, you will implement the primary data structure as a 2-dimensional array Strings[NUM][LEN], where NUM is the number of strings, and LEN is the maximum length allowed for the string: the first index i gives you the i-th string, and the second index j gives you the j-th character within that string. Use the starter file ex1.c. Your code must strictly follow these specifications:

• Use fgets() to read each string from the input, one string per line. Use LEN as an argument to fgets() to ensure that an input line that is too long does not exceed the bounds imposed by the string's length. The function fgets() will make sure that it will not put more than LEN characters into the string variable (including the newline and NULL characters).
• The comparison of two strings must be done by checking them one character at a time, without using any C string library functions for string comparison. That is, write your own loop to do this. Put this code inside a function called my_compare_strings().
• The swap of two strings must be done by swapping one character at a time (using a char temp variable of your choice), without using any C string library functions for copying strings. That is, write your own loop to do this. Put this code inside a function called my_swap_strings().
• You are allowed to use C library functions for printing strings, e.g., fputs(), puts(), printf(), etc.
• You are allowed to use the C library function strlen() to calculate the length of a string.

Alphabetical Order: The alphabetical order of strings is defined by reading them left-to-right, until you reach a character position in which the two strings are different, or until one or both strings terminate. If a position is reached where the strings are different, then their order is determined by the ordering of those respective characters. For example, consider two strings: A="Apple" and B="Aptitude". The first index where they are different is 2: A[2]='p' and B[2]='t'. Since A[2] < B[2], we conclude that the string A < B, i.e., A comes before B in alphabetical order. There are no special checks needed for upper-case vs. lower-case vs. punctuation etc.; simply check if A[i] < B[i] where i is the first character position where the strings are different. If one string terminates before any differences are found, then the shorter string appears first in alphabetical order. If both strings terminate before any difference is found, then they are equal.

Exercise 2

• Add "#include <string.h>" near the top of the C file to tell the compiler that you will be using the C string library functions.
• Remove your my_compare_strings() function from the code. Instead, use the C function strcmp() to perform the comparison of two strings. Study this function carefully (see readings above). You may choose to use a similar function called strncmp() instead of strcmp() because the former also allows you to specify the maximum number of characters to check (e.g., for extra safety, or if only a first few characters are significant, etc.).
• Remove your my_swap_strings() function from the code. Instead, use the C function strcpy() to perform the copy of one string to another, in order to perform the swap of two strings (see readings above). Thus, you may use a temporary string variable (char tempstring[LEN]), and three calls to strcpy() to swap two strings. There is also a variant strncpy() which copies only a specified maximum number of characters.

Test Inputs, Due Date and Submission Procedure

Your assignment must be submitted electronically via Sakai by 11:55pm on Wednesday, February 5, 2020. You will submit your work on Exercises 1-2, specifically, the files ex1.c and ex2.c.

Sample Inputs/Outputs: Sample inputs and corresponding outputs are provided on the server under /home/montek/comp411/samples/lab4. The sequence of steps to run your program and verify its output is as follows. First, copy all the sample input and output files to your lab4 folder:

% cd ~/comp411lab/lab4
% cp /home/montek/comp411/samples/lab4/* .

(Note the dot at the end of the cp command above.)

Then do the following to compile and run your programs:

% gcc ex1.c -o ex1
% ./ex1 < ex1in1 > ex1result1
% diff -qs ex1result1 ex1out1

... and so on. If diff reports the files are different, carefully inspect them to identify the differences. You can run diff with some of the other options, as explained in Lab 2, to highlight the differences, and also use pico or hexdump -c to inspect the files.

Before submitting your work, be sure that each of your compiled programs runs correctly on all of the sample inputs provided exactly. You may receive zero credit if your program's output does not exactly match the sample outputs provided.

Final check before submitting: Navigate to the folder where these files are stored, and run the following command for running a self-checking script:

% cd ~/comp411lab/lab4
% selfchecklab4

How to submit: First transfer your work back to your laptop by either using WinSCP (for Windows), or Cyberduck/FileZilla/Macfusion or terminal/shell (for Mac/Linux), as explained in Lab 1. Next, log in to Sakai in a browser window, and look for the lab under "Assignments" in the left panel. Attach the requested files and submit.

Resubmissions: You are allowed to submit a lab assignment as many times as you would like to, but only the latest submission will be considered for grading.

In case of any problems, please contact the instructor or the TAs.