/* CSC16 Lab 6 Due 10/25/05 This week we again look at linked lists, as they are a very fundamental data structure. Part I. Continuing the program you wrote last week, write the following functions RECURSIVELY. It's recommended that you use the static, constructive style. 1. A function that returns the last cell in a list (it should naturally return null if the list is empty). public static dcell lastcell(dcell A) 2. A function "interleave" that takes two lists as arguments and interleaves them. That is, if A is 1-3-5 and B is 2-4-6, then interleave(A,B) should return the list 1-2-3-4-5-6. It's your choice as to what to do if the lists are not of the same length. You may throw an exception, or interleave them as much as possible - document what you did. Part II. This time our "cells" are going to be bank account objects. Instead of just a "head" representing the data stored in each cell, there will be information pertaining to a bank account (balance and name of owner). We want to implement the typical operations of openning and closing a bank account, which of course are just versions of the insert and delete operations. However, we want our bank account cells to be sorted by the names of the owner. This will make certain operations more efficient. I have written some operations that do not take advantage of a sorted list. You are to modify these operations, and add a few others of your own. To determine if one string comes before another string alphabetically, we can use the "compareTo" function (instructions below). We will also look at the use of class inheritance in a mild way. */ // basic bank account class: class account { protected double balance; // "protected" is explained below protected String owner; // owner of the account public account(double d, String s) { balance = d; owner = s; } public void withdraw(double x) { if (x>0) balance -= x; } public void deposit(double x) { balance += x; } public double inquiry() { return balance; } public String toString() { return owner+"'s balance is $"+balance; } } // class account // The following class adds the tail pointer to account, effectively // making accounts into a linked list. In "extending" the account // class, it "inherits" all the elements already defined in account. // The variables balance and owner are still visible inside the new // class because these variables are declared "protected". "protected" // means they're accessible to classes derived from the current class. Why // do we want to do things this way? Why not just add the tail pointer // to the account class directly? The issue here is object oriented design. // We may want to use the account class in some other context, such // as in an array of account objects, where it doesn't make sense for them // to have a tail pointer. // The axiom to remember about inheritance is that "Every instance of // a subclass contains an instace of the super class". class bankcell extends account { private bankcell tail; // tail now added to bankaccount public bankcell(double d, String s, bankcell b) { super(d,s); // calls the superclass constructor ****** tail = b; } // Remember, the bankcell class still contains everything in the // account class. /* *********** Now for linked-list operations *********** */ // prints info for every account - you don't need to change this. public void printinfo() { bankcell i = this; while (i!=null) { System.out.println(i); i=i.tail; } } // look up an account by name - you need to change this // so that it takes advantage of the list being sorted - that is, // it should return null as soon as it determines that there's // no account that has the given name. public account lookup(String name) { bankcell i = this; while(i!=null && i.owner != name) i= i.tail; return i; // returns null if no such account // there's a subtlety here: i is of type bankcell, so it is // therefore also of type account, so this return is of the correct // type. } // create a new account - add account to the end. You need to // change this so that the account is inserted in alphabetical order. // Be careful: the return type can nolonger be void - why? public void openaccount(String owner, double bal) { bankcell i = this; while (i.tail!=null) i=i.tail; i.tail = new bankcell(bal,owner,null); } // delete an account - may delete "this" account. You need to // again optimize this by taking advantage of the fact that the // list is sorted. public bankcell closeaccount(String name) { if (this.owner==name) return this.tail; // special case bankcell i=this; while (i.tail!=null && i.tail.owner!=name) i=i.tail; if (i.tail!=null) i.tail = i.tail.tail; return this; } } // class bankcell public class bank2 { public static void main(String[] args) { bankcell B = new bankcell(0,"evil professor",null); B.openaccount("mary",100); B.openaccount("larry",200); B.openaccount("bob",300); B = B.closeaccount("mary"); System.out.println("larry has $" + B.lookup("larry").inquiry()); B.printinfo(); // you need to add more here. } } /* ********************** YOUR ASSIGNMENT ************************ 0. Write a method "inthered" that prints out the names of everybody who's balance is below 0. This should be a warmup. 1. Modify my lookup, openaccount and closeaccount operations by taking advantage of having a sorted list. For example, the close account (delete) operation should stop as soon as it detects that the name given doesn't own an account in the list. Also, in the "openaccount" method, DO NOT create accounts that have the same "owner" (throw an exception or something!). Given Strings A and B, A.compareTo(B) returns 0 if A and B are equal, a negative number if A comes before B alphabetically, and a positive number if A follows B alphabetically. 2. Write a method "mergeaccount" that takes two names (string args) and create a merged account. The balance of the new account should naturally be the sum of the two accounts, and the owner variable should be changed to something like "mary and bob". For this operation, you have the option of either deleting both old accounts and create a brand new account object, or just delete one account and modify the other object - please document what you're doing. If there are no accounts of the name(s) specified, you can throw an exception. 3. Write a recursive function that checks if a bankcell list is in fact sorted (it should return true or false). hint: a list is sorted if it's null or a singleton list or if the first element is less than the second element and the rest of the list is also sorted. 4. Modify the main function in the public class to test all your methods. Use a list with at least 8 account cells. *************************************************************** */