CS2023 Assignment 8

Winter 2004

Due Wednesday, April 7, 10:30 AM, in the assignment bin on E-Level, and electronically (see "Deliverables" below).
This assignment will be marked out of 75 points. Marks will be deducted if you do not follow the C Language Coding Standard.

Ordered Lists of Strings

In class you have seen how to construct a simple ordered list. In this assignment you will build a module which will provide some basic functions for manipulating ordered lists of strings. To test the module you will write a program that reads in a text file of university-country pairs and sorts them into lists according to country, using your ordered list module. You will also use RCS version control during the writing/debugging/testing process, and submit logs of all files.

Requirements

Module

Using the following structure:

typedef struct node{
char *string;
struct node *next;
} StringNodeT, *StringNodeTP;

build a module which implements the following functions:

int oslist_put(const char *string, StringNodeTP *oslist);

string

oslist

void oslist_print(const StringNodeTP oslist)

oslist

stdout

StringNodeTP oslist_merge(const StringNodeTP oslist1, StringNodeTP *oslist2);

oslist1

oslist2

StringNodeTP oslist1, oslist2

if(oslist_merge(oslist1, &oslist2) == NULL) ...oslist2

void oslist_free(StringNodeTP *oslist);

oslist

NULL

Program

Write a program which makes use of the above module to read a file of university-country pairs from stdin, sort them according to country, and then alphabetically overall. Using the above module, do the following:

Create an ordered list of universities for each country
Print the list for each country (the order of countries does not matter)
Merge all the lists into one sorted list
Print the merged list

You may assume a reasonable maximum number of countries, so that you can create a fixed-size array to store the pointers to your lists.
The input format consists of a university-country pair per line, with the two members of the pair separated by a tab character. For example, the following input:

UPEI    Canada
MIT    USA
Ecole des Mines    France
UNB    Canada
Princeton    USA
Dalhousie    Canada

produces the following output:

Canada
--------
Dalhousie
UNB
UPEI

USA
--------
MIT
Princeton
France
--------
Ecole des Mines
Dalhousie
Ecole des Mines
MIT
Princeton
UNB
UPEI

Version Control

Place all files (program and module implementation files and header file) under source control using RCS. When you are ready to submit your assignment, print out RCS logs of these files.

Marking Scheme

(20 marks) Your module correctly implements the functions specified above.
(15 marks) Your program for sorting universities meets the requirements specified above.
(15 marks) Your program produces correct output, as in the above example.
(5) Header file, including comments for each function.
(8) Formatting and style: your source code must be readable, and your logic must be clear.
(5) Makefile: correctly builds executable.
(7) RCS logs for all .c and .h files.

Deliverables

A hardcopy of your assignment in the bin on E-level, which must include source code and header files, RCS logs of .c and .h files, and electronic submission of your program, which includes your two C files, header file, a makefile which produces an executable file which must be called universities, to the "Submit your assignment" link on the CS2023 home page.

Eric Aubanel, Mar. 25, 2004