$1$

CS $1011$

CSE $101$

Introduction to Data Structures and Algorithms

Programmi

Introduction to Data Structures and Algorithms

Programming Assignment $1$

Our goal in this project is to build an Integer List ADT in C and use it to indirectly alphabetize the lines in a file.

This ADT module will also be used $($with some modifications$)$ in future programming assignments, so you should

test it thoroughly, even though not all of its features will be used here. Begin by reading the handout ADT.pdf

posted on the class webpage for a thorough explanation of the programming practices and conventions required

for implementing ADTs in C in this class.

Program Operation

The main program for this project will be called Lex.c$.$ Your List ADT module will be contained in files called

List.h and List.c$,$ and will export its services to the client module Lex.c$.$ The required List operations are specified

in detail below. Lex.c will take two command line arguments giving the names of an input file and an output file,

respectively.

Lex

The input can be any text file. The output file will contain the same lines as the input, but arranged in

lexicographic $($i$.$e$.$ alphabetical$)$ order. For example:

Input file: Output file:

one five

two four

three one

four three

five two

Lex.c will follow the sketch given below.

$1.$ Check that there are two command line arguments $($other than the program name Lex$).$ Quit with a usage

message to stderr if more than or less than two command line arguments are given.

$2.$ Count the number of lines n in the input file. Create a string array of length n and read in the lines of the

file as strings, placing them into the array. $($Allocate this array from heap memory using functions

calloc$()$ or malloc$()$ defined in the header file stdlib.h$.$ Do not use a variable length array. See

the comments here for more on this topic.$)$

$3.$ Create a List whose elements are the indices of the above string array. These indices should be arranged

in an order that indirectly sorts the array. Using the above input file as an example we would have.

Indices: $01234$

Array: one two three four five

List: $43021$

To build the integer List in the correct order, begin with an initially empty List, then insert the indices of

the array one by one into the appropriate positions of the List. Use the Insertion Sort algorithm $($section

$2\mathrm{.}1$ of the text CLRS$)$ as a guide to your thinking on how to accomplish this. $($Please read the preceding

two sentences several times so that you understand what is required. You are not being asked to sort the

input array using Insertion Sort.$)$ You may use only the List ADT operations defined below to manipulate

$2$

the List. Note that the C standard library string.h provides a function called strcmp$()$ that determines

the lexicographic ordering of two Strings. If s$1$ and s$2$ are strings then:

strcmp$($s$1,$ s$2)<0$ is true if and only if s$1$ comes before s$2$

strcmp$($s$1,$ s$2)>0$ is true if and only if s$1$ comes after s$2$

strcmp$($s$1,$ s$2)==0$ is true if and only if s$1$ is identical to s$2$

$4.$ Use the List constructed in $(3)$ to print the array in alphabetical order to the output file. Note that at no

time is the array ever sorted. Instead you are indirectly sorting the array by building a List of indices in a

certain order.

See the example FileIO.c to learn about file input$-$output operations in C if you are not already familiar with them.

I will place a number of matched pairs of input$-$output files in the examples section, along with a python script

that creates random input files, along with their matched output files. You may use these tools to test your

program once it is up and running.

List ADT Specifications

Your list module for this project will be a bi$-$directional queue that includes a "cursor" to be used for iteration.

Think of the cursor as highlighting or underscoring a distinguished element in the list. Note that it is a valid state

for this ADT to have no distinguished element, i$.$e$.$ the cursor may be "undefined" or "off the list", which is in

fact its default state. Thus the set of "mathematical structures" for this ADT consists of all finite sequences of

integers in which at most one element is distinguished. A list has two ends referred to as "front" and "back"

respectively. The cursor will be used by the client to traverse the list in either direction. Each list element is

associated with an index ranging from $0($front$)$ to $1($back$),$ where $$ is the length of the list. Your List

module will export a List type along with the following operations.

$//$ Constructors$-$Destructors $---------------------------------------------------$

List newList$($void$)$; $//$ Creates and returns a new empty List.

void freeList$($List$*$ pL$)$; $//$ Frees all heap memory associated with $*$pL$,$ and sets

$//*$pL to NULL.

$//$ Access functions $-----------------------------------------------------------$

int length$($List L$)$; $//$ Returns the number of elements in L$.$

int index$($List L$)$; $//$ Returns index of cursor element if defined, $-1$ otherwise.

int fro