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:
The data file sum2.dat consisting of 9 111 22 3333 4 5555555 666 7777 88 999999 results in:
The data file sum3.dat consisting of 1 23 results in:
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:
If the first data is not numerical, for example if the data file sum5.dat consists of xx 1, then the result is:
Finally, if the data file sum6.dat is empty, then:
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:
For the input 12 23 35 213 342 444 456 711 865 912 1000 1001 1234 the output is:
For the input 12 23 35 213 342 444 445 611 865 864 1000 1001 1234 the output is:
For the input 1 78 the output is:
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:
For the input 7 13 29 38 39 50 50 50 the output is:
For the input 4 100 100 100 100 the output is:
For the input 2 100 100 the output is:
For the input 10 33 6 6 12 2 2 38 39 50 50 the output is:
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:
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:
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:
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
(note that this will reverse the order of the strings at the head)
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
NodeT *insertHead(NodeT *, char *)
NodeT *insertTail(NodeT *, char *)
NodeT *makeNode (char *)
void printList(NodeT *head)
void freeList(NodeT *head)
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
prompt$ ./llsum < sum1.dat Linked list = 10->20->30->40 Total = 100 |
prompt$ ./llsum < sum2.dat Linked list = 111->22->3333->4->5555555->666->7777->88->999999 Total = 6567555 |
prompt$ ./llsum < sum3.dat Linked list = 23 Total = 23 |
prompt$ ./llsum < sum4.dat Data missing |
prompt$ ./llsum < sum5.dat No data |
prompt$ ./llsum < sum6.dat No data |
Linked list = 10->20->30->40 List is ordered |
Linked list = 23->35->213->342->444->456->711->865->912->1000->1001->1234 List is ordered |
Linked list = 23->35->213->342->444->445->611->865->864->1000->1001->1234 List is unordered |
Linked list = 78 List is ordered |
Linked list = 10->20->30->30->30->40 List contains triplets |
Linked list = 13->29->38->39->50->50->50 List contains triplets |
Linked list = 100->100->100->100 List contains triplets |
Linked list = 100->100 List contains no triplets |
Linked list = 33->6->6->12->2->2->38->39->50->50 List contains no triplets |
Submit your work using: