CIS 212代做、ArrayList ADTs代做、C/C++代写代写、C/C++编程设计调试

日期：2019-05-01 10:00

CIS 212 Project 4

-1-

Use of String and ArrayList ADTs

Due at 11:59pm on Monday, 29 April 2019

In Project 1, we explored the use of pipelines of simple tools in Linux to produce a word

frequency list from a single input file using pipelines of the form

<one or more tr invocations> | sort | uniq -c

In the original version of this pipeline, from the textbook on page 37, the <one or

more tr invocations> was a single tr invocation that simply converted text

read from standard input into one word per line, where words were separated by white

space.

The solution to Part 1 of Project 1 required that you pipe the output of the previous tr

invocation into another tr invocation, this time converting upper-case letters to lowercase

letters.

The solution to Part 3 of Project 1 required that you start the pipeline with a tr

invocation that converted punctuation characters into spaces, piping it into the original

tr invocation to break up into one word per line.

If this summary is a bit too cryptic for you, please refer to the handout for Project 1, as

well as review Exercise 2-4 starting on page 36 of the textbook.

In this project you are going to write a C program that replaces the <one or more

tr invocations> part of the pipeline, converting text from one or more input files

into one word per line on standard output.

1 Requirements

1.1 Synopsis

./wordperline [-lp] [FILE …]

wordperline prints each word in the specified files on a line of its own on standard

output; if no files are specified, it processes standard input.

Words, by default, are separated by white space.

wordperline supports the following options:

-l Convert upper-case characters to lower-case.

-p Punctuation characters also separate words.

You are required to use the String and ArrayList abstract data types described in

chapter 5 of the textbook.

CIS 212 Project 4

-2-

2 Starting files

In Canvas, in Files/Projects, you will find a gzipped tar archive named

project4start.tgz; this file contains the following files:

input – a file that contains text; this is the same file used in Project 1.

input1, input2 – other files containing text; these are the same files used

in Projects 2 and 3.

tscript – a bash script file that performs a number of tests of your

wordperline using input, input1, input2, and test*.out; invoking

./tscript

will execute all of the tests using your executable wordperline.

test*.out – the correct output files for the tests in tscript.

arraylist.[ch] – header and source file for the ArrayList ADT

stringADT.[ch] – header and source file for the String ADT

iterator.[ch] – header and source file for the Iterator ADT, needed by

ArrayList

3 Hints

I suggest that you thoroughly review Chapter 5 of the textbook on Abstract Data Types. I

have included additional information on how to use ArrayList, String , and

Iterator in sections 6-8 below; you are not required to use the Iterator ADT.

4 Checking that your solution works correctly

tscript takes zero or more arguments; if one or more arguments are specified,

tscript will only perform those specific tests; if no arguments are specified, all of the

tests are performed.

The tests that tscript performs are:

a Tests that you detect non-existent file names, log an error on stderr, and

terminate the program

b Tests that it detects illegal flags and terminates the program.

c Tests that it works correctly with no flags and no file names.

d Tests that it works correctly with –l and no file names.

e Tests that it works correctly with –p and no file names.

f Tests that it works correctly with –l –p and no file names.

g Tests that it works correctly with –lp and no file names.

h Tests that it works correctly with no flags and a single file name.

i Tests that it works correctly with –l and a single file name.

CIS 212 Project 4

-3-

j Tests that it works correctly with –p and a single file name.

k Tests that it works correctly with –lp and a single file name.

l Tests that the –l flag works for multiple files.

m Tests that the –p flag works for multiple files.

n Tests that -lp works for multiple files.

For each test, tscript prints out “Starting test <letter>”, where

<letter> is one of {a, b, c, d, e, f, g, h, i, j, k, l, m, n}; it

then prints a 1-line description of what it is testing; it then prints the actual command

line that it is executing; finally, it prints “Stopping test <letter>”.

If there is any output between the actual command line and the Stopping line for any

test but tests a and b, the test has failed.

5 Submission1

You will submit your solutions electronically by uploading a gzipped tar archive2 via

Canvas.

Your TGZ archive should be named <duckid>-project4.tgz, where <duckid> is

your “duckid”. It should contain your files wordperline.c and Makefile; it should

also contain a file named report.txt; this file should contain your name, duckid, the

names of any classmates who helped you and what assistance they provided, and the

current state of your solution. Do not include arraylist.[ch],

stringADT.[ch], or iterator.[ch] in your archive; I will use those provided to

you.

6 Use of the String ADT

This section provides a simple usage guide for the String ADT.

6.1 Creating and using an instance of a String

If you have a C string (i.e., an array of char) named str, you can create a String instance

with a declaration of the following form:

#include "stringADT.h"

const String *st = String_create(str);

1 A 75% penalty will be assessed if you do not follow these submission instructions.

2 See section 7 of Canvas/Files/Projects/P1Handout.pdf for instructions if you do not remember how to

create a gzipped tar archive. Obviously, the filenames used for this project will be different.

CIS 212 Project 4

-4-

The return value from String_create() should be checked to see if it was

successful; if the return value is NULL, String_create() was unable to create the

ADT instance.

As you can see in the next subsection, there are a large number of methods that you can

invoke on your String instance. For example, if we wanted to convert all lower-case

letters to upper-case letters, we would invoke:

st->upper(st);

If you want to obtain the C string equivalent to the contents of your String instance,

you can do the following (shown using printf()):

printf(“My string is: %s\n”, st->convert(st));

If you want to clear the contents of your String instance, you invoke:

st->clear(st);

Finally, if you want to destroy your String instance, you invoke:

st->destroy(st);

6.2 Methods of the String ADT

In each of the following, it is assumed that you have invoked String_create() to

create a pointer to a String instance named st. Invocation of each method is shown

using this pointer prior to a description of what the method does. Where the description

uses an index, this views st as an array of characters with a starting index of 0, and

an ending index of length-1.

const String *nst = st->copy(st);

Creates a copy of the String st in nst.

const String *nst = st->slice(st, begin, end);

Creates a copy of a slice of st corresponding to [begin,end); begin and end are

integers indicating indices of st that define the slice. If end == 0, it indicates that the

slice is [begin, length of the string).

st->destroy(st);

Destroys the String st; returns all heap allocated storage associated with st to the

heap; no return value.

int status = st->append(st, suffix);

Appends the C string suffix to st; returns 1 if successful, 0 if unsuccessful.

int status = st->assign(st, chr, index);

Assigns the C character chr to st at index; returns 1 if successful, in which case the

previous value at index is overwritten, or 0 if the index is out of bounds.

int status = st->clear(st);

Clears st, such that it contains the empty C string, “”; returns 1 if successful, 0 if

unsuccessful.

CIS 212 Project 4

-5-

int status = st->insert(st, substr, index);

Inserts the C string substr into st, starting at index; all current characters from

index to length are shifted up by the length of the substring; returns 0 if illegal

index, 1 otherwise.

st->lower(st);

Converts all upper-case characters in st to lower-case; no return value.

st->lStrip(st);

Remove leading white space from st; all remaining characters are shifted down so that

1st character of the remaining string is at index 0; no return value.

int status = st->remove(st, index);

Removes the character at index; all remaining characters are shifted down; returns 0 if

illegal index; otherwise, returns 1.

int status = st->replace(st, old, new);

Replaces all occurrences of the C string old by the C string new; returns 1 if successful,

0 if unsuccessful.

st->rStrip(st);

Removes trailing white space from st; no return value.

st->strip(st);

Removes leading and trailing white space from st; no return value.

st->upper(st);

Convert all lower-case characters in st to upper-case; no return value.

int value = st->compare(st, ost);

Compares the contents of st with the contents of another String instance, ost; returns

a value less than 0 if st < ost; returns 0 if st == ost; returns a value greater than 0 if

st > ost.

int value = st->endsWith(st, suffix, begin, end);

Checks to see if the [begin,end) slice of st ends with the C string suffix; if end ==

0, it means the length of the string; returns 1 if true, 0 if false.

int ind = st->index(st, substr, begin, end);

Returns the index of the first occurrence of the C string substr in the slice

[begin,end); if end == 0, it means the length of the string; returns the index if

substr is found in the slice, -1 if not.

int value = st->isAlpha(st);

Returns 1 if st has at least one character, and all characters are alphabetic characters;

otherwise, returns 0.

int value = st->isDigit(st);

Returns 1 if st has at least one character, and all characters are digits; otherwise,

returns 0.

CIS 212 Project 4

-6-

int value = st->isLower(st);

Returns 1 if st has at least one character, and all alphabetic characters are lower-case;

otherwise, returns 0.

int value = st->isSpace(st);

Returns 1 if st has at least one character, and all characters are whitespace characters;

otherwise, returns 0.

int value = st->isUpper(st);

Returns 1 if st has at least one character, and all alphabetic characters are upper-cases;

otherwise, returns 0.

int size = st->len(st);

Returns the number of characters currently in st.

int ind = st->rindex(st, substr, begin, end);

Returns the index of the last occurrence of the C string substr in the slice

[begin,end); if end == 0, it means the length of the string; returns the index if

substr is found in the slice, -1 if not.

const ArrayList *al = st->split(st, sepstr);

Splits the contents of st into separate words, returning an ArrayList containing the

words; if the C string sepstr is "", it separates words by whitespace; if it contains a

single character, such as ",", it separates words using that character; if any problems

creating the ArrayList, NULL is returned. After you have finished using al, you

must invoke

al->destroy(al, free);

to return the heap storage associated with al.

int value = st->startsWith(st, prefix, begin, end);

Checks to see if the [begin,end) slice of st starts with the C string prefix; if

end == 0, it means the length of the string; returns 1 if true, 0 if false.

char *sp = st->convert(st);

Returns a pointer to the contents of st as a C string.

7 Use of the ArrayList ADT

This section provides a simple usage guide for the ArrayList ADT.

7.1 Creating and using an instance of an ArrayList

You can create an ArrayList instance with a declaration of the following form:

#include "arraylist.h"

const ArrayList *al = ArrayList_create(capacity);

where capacity is a long integer indicating the number of elements you want al to

hold initially; if capacity == 0L, a default capacity is used. The return value from

CIS 212 Project 4

-7-

ArrayList_create() should be checked to see if it was successful; if the return

value is NULL, ArrayList_create() was unable to create the ADT instance.

In this project, you will receive a pointer to an ArrayList by calling the split()

method on a String instance.

As you can see in the next subsection, there are a large number of methods that you can

invoke on your ArrayList instance. For example, if we wanted to determine the

current number of elements, we would invoke:

long length = al->size(al);

Suppose that we have an ArrayList that contains C strings (such as would be

returned by the split() method for the String ADT). If we want to process each C

string in the ArrayList in order, we would do the following:

long i;

for (i = 0L; i < al->size(al); i++) {

char *sp;

(void) al->get(al, i, (void **)&sp);

/* do something with the string */

}

We place a (void) in front of the get() method invocation since we know there

cannot be an error return; the (void **) cast is needed to avoid warnings from the

compiler.

Finally, if you want to destroy your ArrayList instance, you invoke:

al->destroy(al, freeFxn);

If the elements that were added to the ArrayList were allocated from the heap (as

for the words added by the split() method in the String ADT), you would specify

the free() function defined in <stdlib.h>.

#include <stdlib.h>

al->destroy(al, free);

7.2 Methods of the ArrayList ADT

In each of the following, it is assumed that you have invoked ArrayList_create()

to create a pointer to an String instance named al. Invocation of each method is

shown using this pointer prior to a description of what the method does.

al->destroy(al, freeFxn);

Destroys al; for each occupied index, if freeFxn != NULL, that function is invoked

on the element at that position; the storage associated with al is then returned to the

heap; no return value.

CIS 212 Project 4

-8-

al->clear(al, freeFxn);

Clears all elements from al; for each occupied index, if freeFxn != NULL, that

function is invoked on the element at that position; upon return, al will be empty; no

return value.

int status = al->add(al, element);

Appends element (which is of type void *) to al; if no more room in al, it is

dynamically resized; returns 1 if successful, 0 if unsuccessful.

int status = al->ensureCapacity(al, minCapacity);

Ensures that al can hold at least minCapacity (of type long) elements; returns 1 if

successful, 0 if unsuccessful.

int status = al->get(al, index, elementPtr);

Returns the element at the specified index (of type long) in *elementPtr (of type

void **); returns 1 if successful, 0 if illegal index.

int status = al->insert(al, index, element);

Inserts element (of type void *) at the specified index (of type long) in al; all

elements from index onwards are shifted one position to the right; if no more room in

the list, it is dynamically resized; if the current size of the list is N, legal values of index

are in the interval [0, N]; returns 1 if successful, 0 if unsuccessful.

int value = al->isEmpty(al);

Returns 1 if al is empty, 0 if not.

int status = al->remove(al, index, elementPtr);

Removes the element at index (of type long) from al, returning the value that

occupied that position in elementPtr (of type void **); all elements from

[index + 1, size – 1] are shifted one position to the left; returns 1 if

successful, 0 if illegal index value.

int status = al->set(al, index, element, previousPtr);

Replaces the element at index (of type long) with element (of type void *),

returning the element that was replaced in previousPtr (of type void **); returns

1 if successful, 0 if illegal index value.

length = al->size(al);

Returns the number of elements in al as a long integer.

int status al->trimToSize(al);

Trims the capacity of al to its current size; returns 1 if successful, 0 if failure.

const Iterator *it = al->itCreate(al);

Creates a generic iterator to al; returns pointer to the Iterator instance or NULL if

failure.

CIS 212 Project 4

-9-

8 Use of the Iterator ADT

This section provides a simple usage guide for the Iterator ADT.

8.1 Creating and using an instance of an Iterator

All of the ADTs that we will use that are containers for other data (ArrayList in this

project) support a factory method (named itCreate()) for creating an iterator to

iterate over the contents of the container.

You can create an Iterator instance given an ArrayList instance al with a

declaration of the following form:

const Iterator *it = al->itCreate(al);

With such an iterator, you can then process each of the elements of an ArrayList

with code such as the following (the following assumes that the ArrayList has C

strings in it):

while (it->hasNext(it) {

char *sp;

(void) it->next(al, i, (void **)&sp);

/* do something with the string */

}

it->destroy(it);

We place a (void) in front of the next() method invocation since we know there

cannot be an error return; the (void **) cast is needed to avoid warnings from the

compiler.

Finally, you must destroy your Iterator instance when you are finished with it;

otherwise, you will leak memory from the heap.

8.2 Methods of the Iterator ADT

In each of the following, it is assumed that you have invoked a factory method to create

a pointer to an Iterator instance named it. Invocation of each method is shown

using this pointer prior to a description of what the method does.

it->hasNext(it);

Returns 1 if the iterator has a next element; returns 0 otherwise.

it->next(it, elementPtr);

Returns the next element in the iterator in elementPtr (of type void **); returns 1 if

successful; returns 0 otherwise.

it->destroy(it);

Destroys the iterator, returning all heap storage associated with the iterator.

CIS 212 Project 4

-1-

Grading Rubric

Your submission will be marked on a 50 point scale. Substantial emphasis is placed

upon WORKING submissions, and you will note that a large fraction of the points are

reserved for this aspect. It is to your advantage to ensure that whatever you submit

compiles, links, and runs correctly. The information returned to you will indicate the

number of points awarded for the submission.

You must be sure that your code works correctly on the virtual machine under

VirtualBox, regardless of which platform you use for development and testing. Leave

enough time in your development to fully test on the virtual machine before

submission.

The marking scheme is as follows:

Points Description

5 Your report – honestly describes the state of your submission

Your wordperline passes test a on an unseen set of input files.

Your wordperline passes test b on an unseen set of input files.

Your wordperline passes test c on an unseen set of input files.

Your wordperline passes test d on an unseen set of input files.

Your wordperline passes test e on an unseen set of input files.

Your wordperline passes test f on an unseen set of input files.

Your wordperline passes test g on an unseen set of input files.

Your wordperline passes test h on an unseen set of input files.

Your wordperline passes test i on an unseen set of input files.

Your wordperline passes test j on an unseen set of input files.

Your wordperline passes test k on an unseen set of input files.

Your wordperline passes test l on an unseen set of input files.

Your wordperline passes test m on an unseen set of input files.

Your wordperline passes test n on an unseen set of input files.

wordperline.c successfully compiles

wordperline.c successfully compiles with no warnings

The link phase to create wordperline is successful

The link phase to create wordperline is successful with no warnings

There are no memory leaks in your program

The code could have worked with minor modification to the source.

Note that:

Your report needs to be honest. Stating that everything works and then finding

that it doesn’t is offensive. The 5 points associated with the report are probably

the easiest 5 points you will ever earn as long as you are honest.

CIS 212 Project 4

-2-

The 8 points for “could have worked” is the maximum awarded in this category;

your mark in this category may be lower depending upon how close you were to

a working implementation.