Week 7 Laboratory
We have created some scripts that can automatically run your program against some tests. To run these tests you can execute the dry run program with an argument that corresponds to the lab and week, i.e. lab07 for this week. It expects to find all the programs to be submitted as part of this lab in the current directory. You can use dry run as follows:
prompt$ ~cs1921/bin/dryrun lab07
or specific tests (e.g. test #2) as follows:
prompt$ ~cs1921/bin/dryrun lab07 2
Exercises
Write a program called llsum.c that uses a linked list to sum a stream of data on stdin. Your program should call functions to build the linked list, to print the list, to add the data stored in the list and finally to free the list.
Numbers stored in the linked list should be summed with a function of prototype:
int sumList(NodeT *head);
which returns the sum of the nodes in the list
Below is shown a number of testcases:
If a data file sum1.dat contains the numbers 4 10 20 30 40 (notice that the first number is the size of the data) then execution results in:
prompt$ ./llsum < sum1.dat
Linked list = 10->20->30->40
Total = 100
The data file sum2.dat consisting of 9 111 22 3333 4 5555555 666 7777 88 999999 results in:
prompt$ ./llsum < sum2.dat
Linked list = 111->22->3333->4->5555555->666->7777->88->999999
Total = 6567555
The data file sum3.dat consisting of 1 23 results in:
prompt$ ./llsum < sum3.dat
Linked list = 23
Total = 23
If there are not enough numbers on stdin, for example if the data file sum4.dat consists of 3 1 2, then the result is:
prompt$ ./llsum < sum4.dat
Data missing
If the first data is not numerical, for example if the data file sum5.dat consists of xx 1, then the result is:
prompt$ ./llsum < sum5.dat
No data
Finally, if the data file sum6.dat is empty, then:
prompt$ ./llsum < sum6.dat
No data
Using the program from the previous exercise as starting point, write a program called llord.c that creates a linked list from a stream of data on stdin and indicates whether the linked list is in ascending order or not.
The order of the data in the linked list should be checked with a function of prototype:
int isOrderedList(NodeT *head);
which returns 1 if the linked list is ordered, otherwise 0
You may assume that the data is numerical. Nodes that have the same value are considered to be ordered. Examples of use are shown below.
For the input 4 10 20 30 40 the output is:
Linked list = 10->20->30->40
List is ordered
For the input 12 23 35 213 342 444 456 711 865 912 1000 1001 1234 the output is:
Linked list = 23->35->213->342->444->456->711->865->912->1000->1001->1234
List is ordered
For the input 12 23 35 213 342 444 445 611 865 864 1000 1001 1234 the output is:
Linked list = 23->35->213->342->444->445->611->865->864->1000->1001->1234
List is unordered
For the input 1 78 the output is:
Linked list = 78
List is ordered
The final testcase is, if there is no input data then there should be no output.
Using either of the programs from the two previous exercises as starting point, write a program called lltrip.c that indicates whether a stream of data on stdin contains a triplet. A triplet is a consecutive group of 3 nodes that all contain the same data.
The linked list should be checked for triplets with a function of prototype:
int hasTripList(NodeT *head);
which returns 1 if the linked list contains a triplet, otherwise 0
You may assume that the data is numerical. Examples of use are shown below.
For the input 6 10 20 30 30 30 40 the output is:
Linked list = 10->20->30->30->30->40
List contains triplets
For the input 7 13 29 38 39 50 50 50 the output is:
Linked list = 13->29->38->39->50->50->50
List contains triplets
For the input 4 100 100 100 100 the output is:
Linked list = 100->100->100->100
List contains triplets
For the input 2 100 100 the output is:
Linked list = 100->100
List contains no triplets
For the input 10 33 6 6 12 2 2 38 39 50 50 the output is:
Linked list = 33->6->6->12->2->2->38->39->50->50
List contains no triplets
Finally, if there is no input data then there should be no output.
Write a program called llinserth.c that uses the insert at the tail and head functions to build a linked list of strings from user input. You should call only the functions:
NodeT *insertHead(NodeT *, char *)
NodeT *insertTail(NodeT *, char *)
NodeT *makeNode (char *)
void printList(NodeT *head)
void freeList(NodeT *head)
Further, a linked-list node should have the following structure:
typedef struct _Node {
char *data; // a pointer to data
struct _Node *next;
} NodeT;
The program builds a linked list consisting of character strings from user input. The user is prompted to enter a string with the message "Enter a string: ". Each string that the user enters is inserted into the linked list, but in a special way:
if the first character of the string is a lower or upper case alphabetic character, then the string is inserted at the head of the list
all other strings are inserted at the tail of the list
The user terminates the session with a full stop (which is stored at the very end of the list, unless no other data was input). On termination the program generates the message "Finished: list is " followed by the contents of the linked list. If the user has entered no data, then the message is simply "Finished".
Note:
you may use a fixed-length array to read the user-entered string
you may assume there are no blanks in the string
the strings may be inserted at the head or the tail in the order they are entered
(note that this will reverse the order of the strings at the head)
Some sample testcases are shown below:
prompt$ ./llinserth
Enter a string: 1234
Enter a string: abcd
Enter a string: .
Finished: list is abcd->1234->.
prompt$ ./llinserth
Enter a string: 12
Enter a string: O'CLOCK
Enter a string: .
Finished: list is O'CLOCK->12->.
prompt$ ./llinserth
Enter a string: 1dog
Enter a string: $500
Enter a string: #1
Enter a string: A987
Enter a string: a654
Enter a string: .
Finished: list is a654->A987->1dog->$500->#1->.
prompt$ ./llinserth
Enter a string: 7
Enter a string: parrots
Enter a string: and
Enter a string: 3
Enter a string: kangaroos
Enter a string: eating
Enter a string: 12
Enter a string: biscuits
Enter a string: .
Finished: list is biscuits->eating->kangaroos->and->parrots->7->3->12->.
prompt$ ./llinserth
Enter a string: 123456789012345678901234567890123456789012345678901234567890
Enter a string: .
Finished: list is 123456789012345678901234567890123456789012345678901234567890->.
If the user provides no data, then no list is output:
prompt$ ./llinserth
Enter a string: .
Finished
Submit your work using:
give cs1921 lab07 llsum.c llord.c lltrip.c llinserth.c