CS 107 – Introduction to Computing and Programming – Spring 2013 Homework Assignment 7 ( Draft 3.0 – Hopefully Final )
Fun with Linked Lists
Due: Monday 29 April at 8:00 A.M. Optional hard copy may be turned in to TA during lab.
Overall Assignment
For this assignment, you are to write a program that reads in sentences character-by-character, creates a linked list out of the character stream, and then performs various operations on the resulting list(s).
Node Structure
The linked list node that you create for this assignment shall be named “node”, and shall have at a minimum the following fields:
struct node { char c; int sequence, totalSequence; struct node * next; };
where:
The char c is a character read in from the keyboard. sequence is the original position of this character within the sentence, starting from 1. I.e. the
first character in the sentence will have sequence 1, the second 2, etc. totalSequence is the same idea as sequence, but the numbers are since the program started. So
for example, if the first sentence read contains 20 characters, ( not counting the newline character ), then the first character of the second sentence would have a sequence number of 1, but a totalSequence number of 21.
Program Operation
After reporting your name and explaining to the user what the program does, your program should do the following:
1. Ask the user to enter a sentence. 2. Read the characters one-by-one, until the newline character ( ‘\n’ ) is read in.
For each character read in: A. Create a new node, using dynamic allocation ( malloc ), and fill in the node fields. B. Add the node to the beginning of a linked list for this sentence.
3. Once the sentence is stored in a linked list, give the user a list of operations supported, ( see below ) and allow them to choose which one(s) to perform. Based upon their choice, use a switch to perform the operation requested and print out the results.
4. Two choices on the list must be to quit the program and to read in the next sentence. In the latter case the current sentence must be either deleted or added to a linked list of past sentences.
5. Repeat from step 1 until the user enters “done”. Note that this test should be case-insensitive. 6. Print overall summary statistics, such as number of characters and sentences processed.
Required Functions
void print( struct node *head ); o This function prints out the characters of the linked list, in the order of the list. o Note: Printing the sentence as the linked list is originally created will print backwards from
what the user entered, because of the way that the linked list is created.
o Alternate: For all functions, if you use typedef to create a type “node”, then you can use that defined type instead of “struct node”.
o Skills: Traversing a linked list. Also, printing is always needed. void printReversed( struct node *head );
o This function prints out the characters of the linked list, in the reverse order of the list. o This function must work recursively, by first calling itself to recursively print the
remainder of the list ( i.e. the following nodes ),and then print the character in the current node.
o Alternate: Instead of writing a separate function, the print function listed above can be modified to accept a second argument indicating whether to print the list forwards or backwards.
o Skills: Recursion. void delete( struct node *head );
o This function deletes the node pointed to by head, and all nodes after it in the list. o The required algorithm is to remove nodes one-by-one from the beginning of the list,
deleting each one as it is removed from the list.
o This function will be needed to delete the old linked list whenever a user asks to enter a new sentence. ( It may also be needed for other tasks. )
o Skills: Removing nodes from the beginning of a list. Deleting ( freeing ) a node. struct node *find( struct node *head, char c );
o This function searches the list pointed to by head, and returns a pointer to the first node found that contains the character c.
o The function returns NULL if the character is not found. o When the user chooses this option from the switch menu, the program should report ALL
the information in the node found, including sequence and totalSequence.
o Skills: Searching a list for a key value. ( Map lookup. ) void removeDuplicates( struct node *head );
o This function removes all duplicate characters from the list, retaining only the first occurrence of each letter. For example, “I really like apples” would become “I realyikps”.
o Note that the test for duplicates is case sensitive, and non-alphabetic characters are treated the same as any other character.
o Skills: Removing arbitrary nodes from the list, but never the first node.
void removeIfEqual( struct node *head, char target ); o This function removes all nodes from the list having the value of target. o Skills: remove nodes from arbitrary positions, either the beginning or elsewhere.
struct node *copy( struct node *source ); o This function creates a copy of a linked list, allocating new nodes to make the copy. The
copy should be in the same order as the original list.
o Skills: Copying nodes. ( Don’t forget sequence and totalSequence. )
Optional Enhancements
void reverseInPlace( struct node **head ); o This function reverses the order of the linked list, and changes the pointer to the head of the
list to point to the new head of the reversed list.
o The reversal must be done by manipulating the next pointers, not by changing the data in the nodes. More specifically, the algorithm is to remove nodes from the original list one- by-one, from the beginning of the list, and add them to a new list, also at the beginning.
o This function does not create or destroy any nodes. It merely rearranges the existing nodes. o Note that the source variable is a pointer to a pointer, i.e. a pointer passed by reference.
This allows the function to change source, so that it points to the new head of the list when the function is completed.
o Skills: Pointers to pointers. struct node *createSortedCopy( struct node *head );
o This function creates a sorted copy of a list, by copying nodes from the list one by one and inserting the copies into a new sorted list.
o This function uses findPrevious( ) and insertAfter( ) – See below. o Skills: Needed to create a sorted list.
struct node *findPrevious( struct node *head, char c ); o This function searches the list pointed to by head, and returns a pointer to the node that
would precede c if the list were sorted by character value.
o The function returns NULL if c belongs at the beginning of the list. o Skills: Dealing with a sorted list.
void insertAfter( struct node *previous, char c ); o This function adds a new node following the node pointed to by previous. o Skills: Needed to create a sorted list.
void applyFunction( struct node *head, char (*fp)( char ) ); o Applies the function pointed to by fp to each of the
characters in the list, and stores the return value in place of the original character value.
o The function pointed to by fp must take a char argument and return a char.
o Typical functions might change the case or do a substitution. o Skills: Function pointers o Suggested functions to use with the function pointer:
char toUpper( char ); – If the input is in the range from ‘a’ to ‘z’, then add ‘A’ – ‘a’ to convert it from lower to upper case. Otherwise just return the input.
char toLower( char ); – Convert from upper to lower case. char toggleCase( char ); – Change case of all alphabetic
characters. char rot13( char ); – A very simple substitution cipher
that “rotates” all alphabetic characters 13 positions through the alphabet. If the input is in the range from ‘a’ to ‘m’ or ‘A’ to ‘M’ inclusive, add 13. Otherwise if the input is in the range ‘n’ to ‘z’ or ‘N’ to ‘Z’, subtract 13. Applying this operation twice should return the original string.
struct node * select( struct node *head, bool (*fp)( char ) ); o This function creates a new list containing copies of only
those nodes from the original list that satisfy a given criterion, as determined by the Boolean function pointed to by the function pointer.
o e.g. bool isAlphabetic( char );, bool isLowerCase( char );, etc.
o Note that the bool data type requires C99 and #include stdbool.h ( The former can be set in Dev C++ by selecting Project->Project Options from the menu bar, then selecting Parameters and entering “-std=c99” in the Compiler section. ) Otherwise replace all references to “bool” with “int”, and use 0 for false and 1 for true.
o Skills: Function pointers, selectively copying part of a list.
bool isPalindrome( struct node * head ); bool isPurePalindrome( struct node *head );
o If you choose to implement these functions, they should be done with doubly linked lists. Alternatively you can create a reversed copy and compare them, but it won’t be as impressive or worth as much credit.
Others that you might think of. Check with your TA.
Incremental Development
For any large programming task, it is best to develop and test the code in small incremental steps, rather than trying to do it all at once. For this assignment, it is recommended that you develop your program by developing and testing functions one-by-one, ( not necessarily in the order listed here ), making sure each function works before continuing on to the next function. Main( ) can grow as functions are added, by adding new options to the switch.
What to Hand In: 1. Your code, including a readme file and a project file if requested by the TA, should be
handed in electronically using Blackboard.
2. The purpose of the readme file is to make it as easy as possible for the grader to understand your program. If the readme file is too terse, then (s)he can’t understand your code; If it is overly verbose, then it is extra work to read the readme file. It is up to you to provide the most effective level of documentation.
3. If there are problems that you know your program cannot handle, it is best to document them in the readme file, rather than have the TA wonder what is wrong with your program. In particular, if your program does not complete all of the steps outlined above, then you should document just exactly which portions of the project your program does accomplish.
4. A printed copy of your program, along with your readme file and any supporting documents you wish to provide, ( such as hand-drawn sketches or diagrams ) may be handed in in lab.
5. Make sure that your name and your CS account name appear at the beginning of each of your files. Your program should also print this information when it runs.
Optional Enhancements: It is course policy that students may go above and beyond what is called for in the base assignment if they wish. These optional enhancements will not raise any student’s score above 100 for any given assignment, but they may make up for points lost due to other reasons.
Some of the functions listed here are optional. You may think of others.
Other enhancements that you think of – Check with TA for acceptability.