程式扎記: [ Data Structures with Java ] Section 10.4 : LinkedList Applications

標籤

2011年2月8日 星期二

[ Data Structures with Java ] Section 10.4 : LinkedList Applications


Preface :
Let us look at two applications that use a LinkedList collection to store the elements. The first example simulate a professional football term building its draft list with players ranked in the order of their "desirability". The program makes extensive use of the index-based list operations. A second example checks whether a string is a palindrome; that is, whether it reads the same forward and backward. You will see effective use of the special list operations that access and update the ends of the list.

Application: The Draft List
A professional football team participates in an annual draft of college players. In preparation for the draft, the team gathers scouting reports and creates an initial list of players with their names given in a rank order. The first name identifies the player the team most desires and so forth. As the draft nears, the team may want to modify the list by adding or removing names or by adjusting the relative ranking of the players.
The application simulates managing a draft list. The data structure is the LinkedList object draftList consisting of a list of strings. Four variables supply information for an update to the list. The variable updateAction of type char indicates the type of update.
The options are add('a') or remove('r') a name for the list or shift('s') a name from its current position to a different position indicating a change in rank. A fourth option ('q') terminates the simulation. The variable playerName of type String identifies a player's name, and the integer values fromIndex and toIndexare used by the shift update to move a player from position fromIndex to the new position at index toIndex.
The program runs in a loop. For each iteration, the user is prompted to input a character representing an update or quit action. A switch statement distinguishes how updates are performed. For instance, with a shift ('s'), the user inputs integers fromIndex and toIndex. The element (playerName) is removed by calling remove(fromIndex) and then reinserted in the list using add(toIndexplayName).
The design of the application takes into account how the football coaches view the list. They think of the first name as their #1 choice, the second name as the #2 choice, and so forth. A linked list stores the names starting at index 0. When a user inputs a position, we simply subtract 1 to make the coach's position correspond to the list's position :
- DraftList.java 代碼 :
  1. package DSwJ.S10;  
  2.   
  3. import java.util.LinkedList;  
  4. import java.util.Scanner;  
  5.   
  6. public class DraftList {  
  7.     public static void main(String args[]) {  
  8.         String[] initialList = {"Jones""Hardy""Donovan""Bundy"};  
  9.         LinkedList draftList = new LinkedList();  
  10.         for(int i=0; i
  11.             draftList.add(initialList[i]);  
  12.         }  
  13.         Scanner keyIn = new Scanner(System.in);  
  14.         String playName;  
  15.         int fromIndex, toIndex;  
  16.         System.out.println("Add player: Input 'a' ");  
  17.         System.out.println("Shift player: Input 's' ");  
  18.         System.out.println("Delete player: Input 'r' \n");  
  19.         System.out.println(draftList);  
  20.         while(true) {  
  21.             System.out.println("\tUpdate: ");  
  22.             char updateAction = keyIn.next().charAt(0);  
  23.             if(updateAction == 'q')  
  24.                 break;  
  25.             switch(updateAction) {  
  26.             case 'a':  
  27.                 playName = keyIn.next();  
  28.                 draftList.add(playName);  
  29.                 break;  
  30.             case 'r':  
  31.                 playName = keyIn.next();  
  32.                 draftList.remove(playName);  
  33.                 break;  
  34.             case 's':  
  35.                 fromIndex = keyIn.nextInt();  
  36.                 fromIndex--;  
  37.                 toIndex = keyIn.nextInt();  
  38.                 toIndex--;  
  39.                 String obj = draftList.remove(fromIndex);  
  40.                 draftList.add(toIndex, obj);  
  41.                 break;  
  42.             }  
  43.             System.out.println("List: "+draftList);  
  44.         }  
  45.     }  
  46. }  

Applications: A List Palindrome
A palindrome is sequence of values that reads the same forward and backward. For instance, the characters in the string "level" from a palindrome, as do the digits in the integer "1991". The method isPalindrome() takes a LinkesList object as an argument and returns the boolean value true if the sequence of elements is a palindrome and false otherwise. The object in the linked-list implement the equals() method. The algorithm compares the elements on opposite ends of the list using getFirst() and getLast(). If they match, delete the elements, and repeat the comparison on the list, which now has two fewer elements. If the comparison fails, immediately exit with a return value false. Otherwise, continue until the size of the list is less than 2. This occurs when the list is a palindrome, and the return value is true :
- PalindromeCheck.java 代碼 :
  1. package DSwJ.S10;  
  2.   
  3. import java.util.LinkedList;  
  4. import java.util.Scanner;  
  5.   
  6. public class PalindromeCheck {  
  7.     public static boolean isPalindrome(LinkedList aList){  
  8.         while(aList.size()>1){  
  9.             if(!aList.getFirst().equals(aList.getLast()))return false;  
  10.             aList.removeFirst();  
  11.             aList.removeLast();  
  12.         }  
  13.         return true;  
  14.     }  
  15.     public static void main(String args[]) {  
  16.         LinkedList charList = new LinkedList();  
  17.         Character c;  
  18.         Scanner keyIn = new Scanner(System.in);  
  19.         System.out.println("Enter the string: ");  
  20.         String line = keyIn.nextLine();  
  21.         for(int i=0; i
  22.             c = line.charAt(i);  
  23.             if(Character.isLetter(c)){  
  24.                 charList.add(c);  
  25.             }  
  26.         }  
  27.         if(isPalindrome(charList)) {  
  28.             System.out.println("'"+line+"' is a palindrome!");  
  29.         } else {  
  30.             System.out.println("'"+line+"' isn't a palindrome!");  
  31.         }  
  32.     }  
  33. }  
This message was edited 1 time. Last update was at 01/10/2010 11:46:49

沒有留言:

張貼留言

網誌存檔

關於我自己

我的相片
Where there is a will, there is a way!