CSC212 Lab 6 2014

--D. Thiebaut (talk) 10:56, 1 October 2014 (EDT)

---

Linux Redirection

Finding Out How Many Users have Accounts on Beowulf2

• Connect to your beowulf2 account.
• Try this command at the prompt:

ls /Users

You should get a long list of names. Unfortunately there are several names per line. We can get the list in 1 column by using the -1 switch:

ls -1 /Users

• Let's store this list into a text file in your directory:

 ls -1 /Users  > allusers.txt

• Look at it with emacs. Go to the end of the file by typing Control-X ] and see how many lines are in the file. That should be the number of users!
• Another way to get this information is to use the command wc (word-count) and give it your file to process:

wc allusers.txt
607  607 5550 allusers.txt

Which means the file has 607 lines, 607 words, and 5550 characters in it. Here again we get the number of users.

Sorting Words

• Type the following command at the prompt:

 cat  >  words.txt

this command literally means take the contents of the keyboard and dump it into a file called words.txt. So whatever you type at the keyboard will go into the file, until you press Control-D by itself on a new line.

• Go ahead and enter some random words, on several lines.
• Type Control-D on a line by itself when you're done.
• Verify that your file contains the information you entered:

cat words.txt

now the command means dump the contents of the file to the screen.

• Let's sort these words. Linux has a command called sort.

 sort  words.txt

You should get a list of your lines, sorted alphabetically.

• Let's store this new list in another file:

 sort words.txt  > sortedWords.txt

• Look at the new file created and verify that the sorted list is there.

Singly-Linked Lists

Problem 1

Watch the video below first.

• Take the IntSLLNode code from the video and put it in a separate class in your directory. Make sure it's public.
• Create a new file with a class called BasicLinkedList.
• Put the code from the video that creates a list of 3 elements in the main() method of your new class.
• You can printAll your list with this code:

for ( IntSLLNode it = head; it  != null; it = it.next ) {
    System.out.println( it.info );
}

Problem 2: A Better Linked-List

In this problem you build a Linked List from scratch.

Question 1

• Create a new class called MyLinkedList
• Make head and tail two private members of the new class
• Add a constructor that will set head and tail to null
• Add an addToHead( int el ) method that inserts a new integer at the front of the list. Note that the code is different depending whether the list is empty, or not.
• Add an addToTail( int el ) method that inserts a new integer at the end of the list. Note, as well, that the code is different depending on whether the list is empty or not.
• Add a printAll() method that will use a loop to printAll the contents of your list.
• Add this code in the main() method:

public static int main( String[] args ) {
    MyLinkedList L = new MyLinkedList();

    L.addToHead( 5 );
    L.addToHead( 10 );
    L.addToTail( 3 );
    L.printAll();

}

• Verify that you get a list with 10, 5, and 3 listed in that order.

Question 2: Testing!

• Try this code, and verify that it works with your list.

public static int main( String[] args ) {
    MyLinkedList L = new MyLinkedList();

    L.addToTail( 30 );
    L.addToTail( 20 );
    L.addToTail( 10 );

    L.printAll();

}

• Make sure you fix any errors you may get!

Question 3: Add an isEmpty() Method

• Add an isEmpty() method. Make it return true if the list is empty, false otherwise.
• Test your method.

Question 4: Add a length() Method

• Add a new method that will return the length.
• Instead of creating a loop that will go through all the elements of the list and count them (why is it a bad idea?), add new member variable called length, and set it to 0 in the constructor. Then increment it by 1 in every method that inserts an item, and decrement it by 1 in every method that removes an item.
• The new method just has to return the field length.
• Test your new method thoroughly

Question 5: add a deleteFromHead( ) Method

• First, figure out on a piece of paper how to remove the front element of a non-empty list.
• Once you have a diagram ready, code the series of actions that need to take place. We will assume that deleteFromHead() will always be called on a non-empty list. The user will have to use isEmpty() first before trying to remove anything.
• Make your method return the integer in the element just removed.
• Test your new method as follows:

public static int main( String[] args ) {
    MyLinkedList L = new MyLinkedList();

    L.addToTail( 30 );
    L.addToTail( 20 );
    L.addToTail( 10 );

    while ( ! L.isEmpty() ) {
        int el = L.deleteFromHead();
        System.out.println( "--- Just removed: " + el );
        System.out.print( "L = " );
        L.printAll();
    }
}

• Fix any errors that may come up (in particular, make sure you make your list officially empty when you remove the very last element)!

Question 6: Full Test

• Add this new method to your linked-list class:

	public void printStatus( String caption ) {
		System.out.println( "+===========================================\n|" + caption );
		System.out.println( "+===========================================\n| List:");
		System.out.println( isEmpty()? "| is empty": "| is not empty" );
		System.out.println( "| contains " + length + " element" + ((length!=1)? "s":"" ) );
		System.out.print( "| elements: " );
		printAll();
		System.out.println( "+===========================================" );
	}

• Replace your main() with this new version:

        public static void main(String[] args) {
                MyLinkedList L = new MyLinkedList();
                
                L.printStatus( "Brand new list" );
                
                for ( int i=10; i<50; i+= 10 ) 
                        L.addToTail( i );
                
                L.printStatus( "After adding 10, 20, ...  to tail...");
                
                L = new MyLinkedList();
                L.printStatus( "Brand new list" );
                
                for ( int i=5; i<50; i+= 10 ) 
                        L.addToHead( i );
                
                L.printStatus( "After adding 5, 15, ... to head...");
                
                while ( ! L.isEmpty() ) {
                        int el = L.deleteFromHead();
                        L.printStatus( "After removing " + el );
                }
       }

• Test your program and verify that it behaves correctly.
• Here's the output you should get:

+===========================================
|Brand new list
+===========================================
| List:
| is empty
| contains 0 elements
| elements: 
+===========================================
+===========================================
|After adding 10, 20, ...50  to tail...
+===========================================
| List:
| is not empty
| contains 5 elements
| elements: 10 20 30 40 50 
+===========================================
+===========================================
|Brand new list
+===========================================
| List:
| is empty
| contains 0 elements
| elements: 
+===========================================
+===========================================
|After adding 5, 15, ... to head...
+===========================================
| List:
| is not empty
| contains 5 elements
| elements: 45 35 25 15 5 
+===========================================
+===========================================
|After removing 45
+===========================================
| List:
| is not empty
| contains 4 elements
| elements: 35 25 15 5 
+===========================================
+===========================================
|After removing 35
+===========================================
| List:
| is not empty
| contains 3 elements
| elements: 25 15 5 
+===========================================
+===========================================
|After removing 25
+===========================================
| List:
| is not empty
| contains 2 elements
| elements: 15 5 
+===========================================
+===========================================
|After removing 15
+===========================================
| List:
| is not empty
| contains 1 element
| elements: 5 
+===========================================
+===========================================
|After removing 5
+===========================================
| List:
| is empty
| contains 0 elements
| elements: 
+===========================================

Problem 3: A Java Linked-List

Question 1

Java contains a Linked-List data structure. Its name is LinkedList. All you need to do to create and save some elements in such a list is illustrated in the snippet below:

/**
 * declares a linked list, stores some numbers in it, then display the contents
 * @author Thiebaut
 */

import java.util.LinkedList;


/**
  * The main class demonstrating the LinkedList
  */
public class Lab6_3 {

	
        /**
         * main entry point
         */  
	public static void main(String[] args) {
                // create a new linked list
		LinkedList L = new LinkedList();
		
                // add 5 integers to it.
		for ( int i=10; i<=50; i+= 10 ) 
			L.addFirst( i );
		
               // display contents of list
               System.out.println( L );
	}

}

• Create a new class with the code above.
• Run it.
• Verify that it runs correctly.

Question 2

• Search the Web for the Oracle page describing the Java LinkedList data structure.
• Locate the different methods you can use to add and remove elements at the front or at the end. Also figure out what methods will indicate if the list is empty, and how many elements are contained. Their names are not the same as the names used in the previous problem!
• Using the Oracle documentation for this data structure, perform the same tests you performed with your linked list in Question 6 above. In particular you should make your main program:

• Add 5 ints to the front of the list
• Display the list
• Get a new empty list
• Add 5 ints at the end of the list
• Display the list
• Empty the list, one int at a time, until it is empty. At every stop of the loop:

• get the element removed,
• display it
• display the remaining list
• display the length of the remaining list

• Stop when the list is empty.

Note 1:

if you want to iterate over the element of your LinkedList, you can use this code:

                import java.util.Iterator; // at the top of your program

                Iterator it = L.iterator();
		while ( it.hasNext() ) {
			int el = (int) it.next();  // note the typecast to int!
			doSomethingWith( el  );
		}

Note 2:

If you remove an element of your LinkedList, even though you may have stored it as an int, it will come out as an Object, which is the generic type for Java. To store it in an int variable, you will need to typecast it:

          int x = (int) L.removeFirst();

Problem #4

Question 1

• Take the code below and create a new program with it:

/**
 * A word scanner.
 * @author D. Thiebaut
 */
import java.util.Scanner;
import java.util.Stack;

public class Lab6_4 {
		
	/**
	 * main entry point
	 * @param args
	 */
	public static void main( String[] args ) {
                // create a scanner to read the input, one line at a time
		Scanner inputScanner = new Scanner( System.in );
	
                // while there are lines available...
		while ( inputScanner.hasNextLine() ) {
       
                        // get the new line
			String line = inputScanner.nextLine();
			
                        // create a new scanner to scan the line for words...
			Scanner wordScanner = new Scanner( line );
			
                        // while there are words on the line, get the words and print them...
			while ( wordScanner.hasNext() ) {
				String word = wordScanner.next();
				System.out.println( "word = " + word );
			}
		}
	}
}

• Run the program and type random lines of text at the keyboard. For example:

 CHOCOLATE CHIPS, 
 A CHOCOLATE KISS, 
 FROM CHOCOLATE LIPS, 
 A CHOCOLATE BLISS, read more »
 --Katheryn Foley

• Verify that the program runs correctly. Note: you'll have to type Control-D at the keyboard to indicate to the Java program that there are no more lines in the input. Control-D is an end-of-file character for Linux.

Question 2: Redirection

• Use emacs to create a text file in your directory. Call it mypoem.txt or something similar. Store just one line of text in it.
• Once it is saved, and you are back at the prompt, type this command:

 java  Lab6_4 < mypoem.txt

• Verify that the program takes all the words from your file and displays them, one per line, on the screen.

Question 3: Stack

• Create a new program called Lab6_4_3.java.
• Locate the description of Oracle's Stack data structures. Read the page enough to see how to create and use one.
• Modify your program and add a stack to it.
• Make your program push every word found on a line in the stack.
• Once a line of text is read, make your program pop the words from the stack, one at a time, and display them on the screen.
• Make your program display the original line, and the one made of popped words, one above the other. Below is an example of what your program should emulate:

 CHOCOLATE CHIPS, A CHOCOLATE KISS, FROM CHOCOLATE LIPS,      (original line)
 LIPS, CHOCOLATE FROM KISS, CHOCOLATE A CHIPS, CHOCOLATE      (reversed line)

Moodle Submission

• Submit this last program (Lab6_4_3.java) to Moodle.