COP-4338: Systems Programming
Programming Assignment 4
PART II
In this assignment, you are asked to write a program that gets a series of string chars
followed by EOF from user through console, alphabetically sorts them using bucket sort,
and prints the sorted strings using printf function.
1 Bucket Sort
Bucket sort, or bin sort, is a sorting algorithm that works by distributing the elements of a
list into a number of buckets. Each bucket is then sorted individually and then the sorted
list is obtained by merging all the sorted buckets together. To sort each bucket in this
assignment, you need to use any algorithm that you want. If you have no preference, you
can use bu
le sort algorithm which is fairly easy to implement. Also, to compare strings
with one another, you need to use function strcmp.
→
Figure 1: Example of bucket sort for sorting numbers 29, 25, 3, 49, 9, 37, 21, 43. Numbers
are distributed among bins (left image). Then, elements are sorted within each bin (right
image).
1
2 Buckets of Your Algorithm
In order to implement bucket sort algorithm for strings, you need to have an a
ay of buckets
such that bucket is a C structure defined in the following way:
struct bucket{
int minInitial;
int maxInitial;
int numWords;
struct node* chainHead;
};
and node is another C structure defined in the following way:
struct node{
char* string;
struct node* next;
};
The a
ay of buckets must be defined and initialized in the following way:
struct bucket list[NUMBUCKS] = {
’a’, ’b’, 0, NULL,
’c’, ’c’, 0, NULL,
’d’, ’f’, 0, NULL,
’g’, ’k’, 0, NULL,
’l’, ’o’, 0, NULL,
’p’, ’r’, 0, NULL,
’s’, ’s’, 0, NULL,
’t’, ’z’, 0, NULL
};
where NUMBUCKS represents 8. Therefore, you have eight buckets in your program. Each
ucket contains four variables:
ˆ int minInitial: determines the minimum ASCII code of the initial letter which the
strings in the bucket can start with.
ˆ int maxInitial: determines the maximum ASCII code of the initial letter which the
strings in the bucket can start with.
ˆ int numWords: determines the number of strings placed in the bucket.
ˆ struct node* chainHead: points to a singly linked list which is a chain of nodes con-
taining the strings in the bucket.
2
3 Program Input
Assume that user enters a series of string chars followed by an EOF. Also, assume that every
input string only contains letters of English Alphabet in lowercase format. Every string of
chars that user passes to the program must be stored in the format of a char string. To
allocate memory for storing a char string in memory, you can use expression char* aWord =
(char *)malloc(strlen(inputString)+1); in which inputString is a char * pointing to the a
ay
of letters given by the user, strlen and malloc are functions defined in stdlib.h li
ary (note
that +1 in the mentioned expression allocates an extra memory cell for \0 that specifies the
end of a char string).
After allocating enough memory cells for each input string and copying the string into
them, you need to allocate memory for storing a variable of type struct node containing a
char * (pointing to the string) and a struct node * pointing to the next node in the linked
list of appropriate bucket.
4 Program Output
Your program must print out the sorted list of strings in an alphabetical order using printf
function.
5 Submissions
You need to submit a .zip file compressing the C source file(s) related to the assignment (.c
files) along with a readme.txt file explaining which sorting algorithm you used for sorting
each bucket and listing parts of the assignment has been implemented completely/partially.
3
COP-4338 Systems Programming
Programming Assignment 5:
PART II
Due Date: June 16 at 11:55 PM
In this assignment, you are asked to write a program that converts a file format to
another. It should support the following formats:
ˆ .csv (comma separated values) file: stores tabular data in plain text. Each line of the
file represents a table row containing one or more cells separated by commas.
ˆ .tl5 file: stores tabular data in plain text. Each line of the file represents a table row
containing one or more cells separated by ’|’ character. Each cell is 5-characters long
and contains a left-aligned string. If the string stored in a cell has n < 5 characters,
the rest of it will be filled with spaces; i.e. there will be 5−n extra space characters in
the field after the string. However, if a string with more than 5 characters is supposed
to be placed in a cell, only its first 5 characters is stored in the cell.
1 50% Bonus Part
As the bonus part, the program must support the following formats specified below:
ˆ .tr9 file: stores tabular data in plain text. Each line of the file represents a table row
containing one or more cells separated by ’|’ character. Each cell is 9-characters long
and contains a right-aligned string. If the string stored in a cell has n < 9 characters,
the rest of it will be filled with spaces; i.e. there will be 9−n extra space characters in
the cell before the string. However, if a string with more than 9 characters is supposed
to be placed in a cell, only its last 9 characters is stored in the cell.
ˆ .tc9 file: stores tabular data in plain text. Each line of the file represents a table row
containing one or more cells separated by ’|’ character. Each cell is 9-characters long
and contains a center-aligned string. If the string stored in a cell has n < 9 characters,
the rest of it will be filled with spaces; i.e. there will be b9−n
2
c extra space characters in
the cell before the string and d9−n
2
e extra space characters in the field after it. However,
if a string with more than 9 characters and odd length is supposed to be placed in a
cell, only its middle 9 characters is stored in the cell. In the case that the length of
original string is even and greater than 9, its middle 8 characters must be stored in the
cell (plus an extra space character).
1
2 Program Input
Assume that user first enters the name and address of a file which he/she wants to convert.
Then, the program gets the name and address of the file in which the user wants to store
the result of format conversion.
3 Program Output
Your program must print out a message showing whether the file conversion is successful.
It also must halt with an e
or message if the file format is not consistent with the filename
extension.
4 Submissions
You need to submit a .zip file compressing the C source file(s) related to the assignment (.c
files) and a readme file specifying which of the following conversions are supported by you
program:
from/to csv tl5 tr9 tc9
csv Y/N Y/N Y/N Y/N
tl5 Y/N Y/N Y/N Y/N
tr9 Y/N Y/N Y/N Y/N
tc9 Y/N Y/N Y/N Y/N
2