1
CSE 101
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,
espectively.
Lex
The input can be any text file. The output file will contain the same lines as the input, but a
anged 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 stde
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 a
ay of length n and read in the lines of the
file as strings, placing them into the a
ay. (Allocate this a
ay from heap memory using functions
calloc() or malloc() defined in the header file stdlib.h. Do not use a variable length a
ay. See
the comments here for more on this topic.)
3. Create a List whose elements are the indices of the above string a
ay. These indices should be a
anged
in an order that indirectly sorts the a
ay. Using the above input file as an example we would have.
Indices: XXXXXXXXXX XXXXXXXXXX
A
ay: one two three four five
List: XXXXXXXXXX XXXXXXXXXX1
To build the integer List in the co
ect order, begin with an initially empty List, then insert the indices of
the a
ay one by one into the appropriate positions of the List. Use the Insertion Sort algorithm (section
2.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 a
ay using Insertion Sort.) You may use only the List ADT operations defined below to manipulate
https:
stackoverflow.com/questions/6629394/variable-length-vs-malloc-ed-a
ays
2
the List. Note that the C standard li
ary string.h provides a function called strcmp() that determines
the lexicographic ordering of two Strings. If s1 and s2 are strings then:
strcmp(s1, s2)<0 is true if and only if s1 comes before s2
strcmp(s1, s2)>0 is true if and only if s1 comes after s2
strcmp(s1, s2)==0 is true if and only if s1 is identical to s2
4. Use the List constructed in (3) to print the a
ay in alphabetical order to the output file. Note that at no
time is the a
ay ever sorted. Instead you are indirectly sorting the a
ay 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 underscored. A list has two ends refe
ed to as "front" and "back"
espectively. 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 front(List L);
Returns front element of L. Pre: length()>0
int back(List L);
Returns back element of L. Pre: length()>0
int get(List L);
Returns cursor element of L. Pre: length()>0, index()>=0
ool equals(List A, List B);
Returns true iff Lists A and B are in same
state, and returns false otherwise.
Manipulation procedures ----------------------------------------------------
void clear(List L);
Resets L to its original empty state.
void set(List L, int x);
Overwrites the cursor element’s data with x.
Pre: length()>0, index()>=0
void moveFront(List L);
If L is non-empty, sets cursor under the front element,
otherwise does nothing.
void moveBack(List L);
If L is non-empty, sets cursor under the back element,
otherwise does nothing.
void movePrev(List L);
If cursor is defined and not at front, move cursor one
step toward the front of L; if cursor is defined and at
front, cursor becomes undefined; if cursor is undefined
do nothing
void moveNext(List L);
If cursor is defined and not at back, move cursor one
step toward the back of L; if cursor is defined and at
back, cursor becomes undefined; if cursor is undefined
do nothing
3
void prepend(List L, int x);
Insert new element into L. If L is non-empty,
insertion takes place before front element.
void append(List L, int x);
Insert new element into L. If L is non-empty,
insertion takes place after back element.
void insertBefore(List L, int x);
Insert new element before cursor.
Pre: length()>0, index()>=0
void insertAfter(List L, int x);
Insert new element after cursor.
Pre: length()>0, index()>=0
void deleteFront(List L);
Delete the front element. Pre: length()>0
void deleteBack(List L);
Delete the back element. Pre: length()>0
void delete(List L);
Delete cursor element, making cursor undefined.
Pre: length()>0, index()>=0
Other operations -----------------------------------------------------------
void printList(FILE* out, List L);
Prints to the file pointed to by out, a
string representation of L consisting
of a space separated sequence of integers,
with front on left.
List copyList(List L);
Returns a new List representing the same integer
sequence as L. The cursor in the new list is undefined,
regardless of the state of the cursor in L. The state
of L is unchanged.
The above operations are required for full credit, though it is not expected that all will be used by the client module
in this project. The following operation is optional, and may come in handy in some future assignment:
List concatList(List A, List B);
Returns a new List which is the concatenation of
A and B. The cursor in the new List is undefined,
regardless of the states of the cursors in A and B.
The states of A and B are unchanged.
Notice that the above operations offer a standard method for the client to iterate in either direction over the
elements in a