Week 7 Laboratory — Memory Management, Linked Lists

As usual, you can use dry run:

prompt$ ~cs1921/bin/dryrun lab07

prompt$ ~cs1921/bin/dryrun lab07 2

Exercises

1. (Memory management) Write a program called mary.c that concatenates all its command-line arguments, including the name of the executable itself, into a single string on the heap. This string is then printed. Below are some testcases.

   prompt$ ./mary 1 2 3 4 5 6 7 8 9 0 ./mary1234567890

   Notice that there are no spaces.

   prompt$ ./mary had a little lamb, its fleece was white as snow ./maryhadalittlelamb,itsfleecewaswhiteassnow

   If there are no arguments:

   prompt$ ./mary ./mary

   You may use the functions in the string library string.h. You may not use any fixed-length arrays.

2. (Memory management) Write a program called heapsum.c that places all of its numerical command-line arguments on the heap, then sums them, and outputs the result. So for example, we have:

   prompt$ ./heapsum 1 2 3 6

   prompt$ ./heapsum 12 34 56 78 90 270

   prompt$ ./heapsum 100 100

   If there are no arguments, the program does nothing.

   prompt$ ./heapsum prompt$

   Your program should contain:

   • a function to place each of the command-line arguments into the heap, resulting in a heap of numbers
   • another function to sum all the numbers on the heap

   The main() function should call both functions to compute the sum. Note further:

   • you may assume that the command-line arguments are numerical
   • you should store the numbers on the heap only
   • you should not use any fixed-length arrays

3. (Linked Lists) Write a program called llbuild.c that builds a linked list from user input. The only functions that you may call are:

   • NodeT *makeNode(int value): taken from the lecture
   • void freeList(NodeT *head): taken from the lecture
   • void printList(NodeT *head): taken from the lecture but needs modification
   • NodeT *joinList(NodeT *head1, NodeT *head2): joins 2 linked lists head1 and head2. Needs to be implemented.

   The program:

   • starting with an initially NULL linked list called all (say)
   • prompts the user with the message "Enter a number: "
   • makes a linked list node called new from user's response
   • joins all and new
   • asks for more user input and repeats the cycle
   • the cycle is terminated when the user enters any non-numeric character
   • 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"

   A sample interaction is:

   prompt$ ./llbuild Enter an integer: 12 Enter an integer: 34 Enter an integer: 56 Enter an integer: quit Finished: list is 12->34->56

   Note that any non-numeric data 'finishes' the interaction:

   prompt$ ./llbuild Enter an integer: 100 Enter an integer: bye Finished: list is 100

   A longer interaction:

   prompt$ ./llbuild Enter an integer: 421 Enter an integer: 456732 Enter an integer: 321 Enter an integer: 4 Enter an integer: 86 Enter an integer: 89342 Enter an integer: 9 Enter an integer: # Finished: list is 421->456732->321->4->86->89342->9

   If the user provides no data, then no list is output:

   prompt$ ./llbuild Enter an integer: coffee Finished

   Note, please ensure:

   • the linked list all is initially NULL

4. (Linked Lists) 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

5. (Linked Lists) 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.

Submit your work using:

  give  cs1921  lab07  mary.c  heapsum.c  llbuild.c  llsum.c  llord.c