Week 8 Laboratory — Linked Lists (of Characters and Strings)

This lab aims at familiarising you with characters and strings in linked lists as well, and how using insertHead() and insertTail() is a matter of choice.

As usual, you can use dry run:

prompt$ ~cs1921/bin/dryrun lab08

prompt$ ~cs1921/bin/dryrun lab08 2

Exercises

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

   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:
   1. 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
   2. 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

2. (Linked Lists)

   1. (Note: do not use linked lists in the first part of this exercise. It is an exercise in string processing.)

      Write a program called rotate.c that takes a string command-line argument, rotates the characters in the string by a single place, and prints the result. The direction of the rotation should be controlled by the optional switch -r for a right rotation, and -l for a left rotation. The usage syntax is the following:

      ./rotate [-r|-l] string

      where string is the sequence of characters to be rotated.
      • if the switch is omitted, then a right rotation is assumed
      • if there is just one argument, it is assumed to be the string to be rotated
      • if there are no arguments at all on the command line, or too many, then a usage message is printed (see below)

      Examples of its use are:

      prompt$ ./rotate -r cows3 3cows prompt$ ./rotate orangepurplepink korangepurplepin prompt$ ./rotate -r orangepurplepink korangepurplepin prompt$ ./rotate -l orangepurplepink rangepurplepinko prompt$ ./rotate -r 12 21 prompt$ ./rotate -l 12 21 prompt$ ./rotate A A prompt$ ./rotate -q abcdef Usage: ./rotate [-r|-l] string prompt$ ./rotate Usage: ./rotate [-r|-l] string

      If there is a command-line switch but no string (i.e. ./rotate -l or ./rotate -r) then the switch is treated as a string).

   2. Modify the program from the previous exercise and place each character in the string in a node of a linked list and rotate the linked list by re-linking the nodes. Call the new program llrotate1.c.

      You should do the following in this exercise:
      • rotate left and right as in the previous exercise (use the same command-line interface)
      • you must build a linked list containing the characters of the string in the original order before you rotate the string
      • rotate the string by re-linking only
        • you may only change the link but not the data in a node
      • you should create functions that carry out left and right rotations
      • the output format differs slightly from the previous exercise:
      • 'arrows' are placed between characters to emphasise the linked list structure (see examples below)
      • the string should be printed before and after rotation
      • you should free the nodes in the linked list before program termination

      The same testcases apply, but the output will be different if the command-line arguments are correct:

      prompt$ ./llrotate1 -r cows3 c->o->w->s->3 3->c->o->w->s prompt$ ./llrotate1 orangepurplepink o->r->a->n->g->e->p->u->r->p->l->e->p->i->n->k k->o->r->a->n->g->e->p->u->r->p->l->e->p->i->n prompt$ ./llrotate1 -r orangepurplepink o->r->a->n->g->e->p->u->r->p->l->e->p->i->n->k k->o->r->a->n->g->e->p->u->r->p->l->e->p->i->n prompt$ ./llrotate1 -l orangepurplepink o->r->a->n->g->e->p->u->r->p->l->e->p->i->n->k r->a->n->g->e->p->u->r->p->l->e->p->i->n->k->o prompt$ ./llrotate1 -r 12 1->2 2->1 prompt$ ./llrotate1 -l 12 1->2 2->1 prompt$ ./llrotate1 A A A

      Executions resulting in a usage message are the same as in the previous exercise (with the name of the executable different of course).

3. (Linked Lists) Modify the program in the previous exercise to use a data-copy strategy: rotate the string by copying data from node to node: the addresses of the nodes should not change. Call the new program llrotate2.c. You should pay attention to:

   • you should only copy data between list nodes (do not do any re-linking of the list nodes)
   • a function that carries out a rotation should be of type void as it must not change the location of the head
   • do not make any new lists or nodes!

   This program should run identically to the program in the previous exercise, so all the above testcases apply.

Submit your work using:

  give  cs1921  lab08  llinserth.c  rotate.c  llrotate1.c  llrotate2.c