CSCI 2110 - Data Structures and Algorithms - Assignment No.3

• 作业标题：CSCI 2110 - Data Structures and Algorithms - Assignment No.3
• 课程名称：Dalhouse University CSCI 2110 Data Structures and Algorithms
• 完成周期：1天

描述

This assignment on the Ordered List Data Structure. You will write a program to implement the two-finger
walking algorithm discussed in the lectures, and small extensions on the algorithm to perform various
merging operations on ordered lists.

You will need the following files to complete your work:

OrderedList.java (Generic Ordered List Class)
list1.txt (first sample input text file)
list2.txt (second sample input text file)
Exercise: Write a program called OrderedListDemo.java that does the following:

1. Prompt the user to enter two text files, each consisting of words (names) and create two ordered lists.
   For example, if one of the input text files contains:

   Shai
   Tom
   Jim
   Aaron
   Barbara
   Beth
   Fred
   Jack
   Jarred
   Jill
   Amar
   Ralph
   Jill
   Hillary

your program should create the following ordered list:

[Aaron, Amar, Barbara, Beth, Fred, Hillary, Jack, Jarred, Jill, Jim,
Ralph, Shai, Tom]

Note: Although Jill is repeated in the input list, the ordered list does not have repeated items.

2. Write a method called merge that accepts two ordered lists, list1 and list2, as input parameters and creates
   and returns a third list that is a merger of the two ordered lists. Use the two-finger walking algorithm discussed
   in class.
   Your method’s header should be written as follows:

   public static <T extends Comparable<T>> OrderedList<T> merge(OrderedList<T> list1, OrderedList<T>
   list2){
   //TODO
   }

For example, if list1 is {Amar, Boris, Charlie, Dan, Fujian, Inder, Travis} and

list2 is {Alex, Ben, Betty, Charlie, Dan, Pei, Travis, Zola, Zulu}

then the method should return the new ordered list

{Alex, Amar, Ben, Betty, Boris, Charlie, Dan, Fujian, Inder, Pei, Travis, Zola, Zulu}

2. Write another method called difference that accepts two ordered lists, list1 and list2, as input parameters
   and creates and returns a third list that is an ordered list with the items in list1 that are not in list2. Make a
   small modification to the two-finger walking algorithm to implement this method.
   Your method’s header should be written as follows:

public static <T extends Comparable<T>> OrderedList<T> difference(OrderedList<T> list1, OrderedList<T>
list2){
//TODO
}

For example, if list1 is {Amar, Boris, Charlie, Dan, Fujian, Inder, Travis} and

list2 is {Alex, Ben, Betty, Charlie, Dan, Pei, Travis, Zola, Zulu}

then the method should return the new ordered list

{Amar, Boris, Fujian, Inder}

3. Write another method called common that accepts two ordered lists, list1 and list2, as input parameters
   and creates and returns a third list that is an ordered list with the items that are common in list1 and list2.
   Make a small modification to the two-finger walking algorithm to implement this method.

Your method’s header should be written as follows:

public static <T extends Comparable<T>> OrderedList<T> common(OrderedList<T> list1, OrderedList<T>
list2){
//TODO
}

For example, if list1 is {Amar, Boris, Charlie, Dan, Fujian, Inder, Travis} and

list2 is {Alex, Ben, Betty, Charlie, Dan, Pei, Travis, Zola, Zulu}

then the method should return the new ordered list

{Charlie, Dan, Travis}

4. Write the newly created ordered lists into three text files, namely, merged.txt, diff.txt and common.txt.
   Here’s the overall structure of your code and input dialog:

public class OrderedListDemo{
public static void main(String[] args){
//TODO
}

。。。