Thread: data structure assignment .. help me : |

Hi all .
I have home work in data structure and I understood a little part of it
so I need your experience

this is the idea and the question


Program Description

Consider a program that manages the payroll of some organization. The three simplest operations performed by this program include:
(i) adding a new employee to the payroll,
(ii) searching for an employee, given some information about her, and
(iii) deleting an employee who has left the organization.

To keep things simple, let us assume that each employee record consists of three fields:
(i) name,
(ii) social security number (ssn), and
(iii) salary.

The three operations mentioned above, can be stated more precisely as follows: INSERT(record): to insert the given employee record into the collection of employee records.
 DELETE(ssn): to delete the employee whose ssn is given, from the collection.
 SEARCH(ssn): to search the collection for the employee whose ssn is given.

Program Specifications

We need to decide how the collection of records is actually stored in memory and how the above operations will be implemented. This kind of specification defines an abstract data type (ADT). Typically, an ADT can be implemented using one of several different data structures. A useful first step in deciding what data structure to use in a program is to specify an ADT for the program.

Now we consider two alternate data structures for the above ADT:
(i) Unordered array of records: the employee records are stored in an array, in no particular order. There is a variable, say n, that keeps track of the number of employees currently on the payroll.
(ii) Ordered array of records: the employee records are stored in an array, in increasing order of ssn. Again, there is a variable, say n, that keeps track of the number of employees currently on the payroll.

Tasks

Referring to the provided Java code segments (pages 3-5) complete the following tasks (Whenever you see TO DO: add your code):

(i) Task1: Complete the code, so your program will support insert, delete, and search. After you finish, make another copy of this program using unordered array to insert a new record at the end, sequential search.

(ii) Task2: Implement a function called payRangeQuery that takes two double parameters low and high and print all records of employees whose pay is between low and high. The payRangeQuery function should be implemented as a public method in the RecordDB class.

(iii) Task3: Write a search function that is similar to the currently implemented search function, except that the new search function returns an integer. If the given ssn is found, then the function returns a non-negative integer that is the index of the slot in which the ssn was found. If the given ssn is not found, then the function should return a negative integer, whose magnitude (absolute value) is the index of the slot in which the ssn would have been found, had it been in the array. For example, if the social security numbers in the array are: 10, 20, 30, 40 and we were looking for 22, and then the function should return -2 because if 22 were present in the array it would be in slot 2.

(iv) Task4: Re-implement the “insert” and “delete” functions so that they call the new search function. You would have noticed that both insert and delete currently perform a linear scan of the array; insert does it in order to find a slot to insert the new record in and delete does it in order to find the record with the given ssn. Having implemented the new search function, it is possible to simplify and speed-up both insert and delete by making appropriate calls to the new “search” function.

Record.java
public class Record {
	// data members
	public int ssn;	// Primary Key
	public String name;
	public double pay;
	// The constructor for this class
	Record (int newSSN, String newName, double newPay) {
		ssn = newSSN;
		name = newName;
		pay = newPay;
	} // end of constructor
} // end of class
 
//--------------------------------------------------------------------------------
RecordDB.java
/*********************************************************
 * A class containing list of records with insert/delete *
 * and search functionality. 					   *
 *********************************************************/
public class RecordDB {
	private static int maxRecords = 200;
	private int numRecords = 0;
	private Record recordList[] = new Record[maxRecords];	
//--------------------------------------------------------------------------------
	//Inserts a record into the ordered array in a sorted fashion.
//Parameter rec:  The record to be inserted.
	public void insert (Record rec) {
 
		// Check for overflow; if overflow, then don't insert
		if (numRecords == maxRecords-1) {
			return;	
		}
 
		// TO DO: 
	// Find the position to insert in, by scanning the array left-to-right
	// until a large ssn is located
		// Then, Shift all records one space down
		// Then, Insert the new record
		// Finally, Increment current number of employees in the list	
		// Print All records
		printAll();
	}
//--------------------------------------------------------------------------------	//Deletes a record from the list based on the key (ssn).
       // Performs a linear scan of the array of records until
       //a record is found with the given ssn
	//Parameter ssn
	public void delete (int newSSN) {
 
		// TO DO:
		//Check for underflow; if underflow, then don't delete
 
 
		// TO DO:
		// Scan the array searching for the record containing newSSN
		// Then, Shift all records that are beyond slot i to the left by one slot
		// Finally, Decrement current number of employees in the list	
 
 
	// Print All records
		printAll();
 
	}
//--------------------------------------------------------------------------------
	//Search for the record with the given SSN, Parameter newSSN
	public Record search (int newSSN) {
		// Print All records
		printAll();
 
		// TO DO:
		// Complete this Binary Search algorithm
		int first=0, last=numRecords-1;
 
	} // end of search function
//-------------------------------------------------------------------------------
	//Prints the list of records to the standard output;
	private void printAll() {
 
		System.out.println("---------------------------------");
		for (int i=0; i<numRecords; i++) {
			System.out.println(""+i+" "+recordList[i].ssn+
			"  "+recordList[i].name+" " +recordList[i].pay);
		}
	}
//--------------------------------------------------------------------------------
 
// Main method - adds and deletes records and searches for some.
	public static void main(String[] args) {
		RecordDB recDB = new RecordDB();
 
		recDB.insert(new Record(3, "John", 500));
		recDB.insert(new Record(22, "Mike", 2500));
		recDB.insert(new Record(13, "Mark", 1760));
		recDB.insert(new Record(19, "Bob", 500));
		recDB.insert(new Record(7, "Cathy", 500));
 
		Record r  = recDB.search(22);
		if(r == null)
			System.out.println("Not found");
		else 
			System.out.println("Found");
 
		r = recDB.search(34);
		if(r == null)
			System.out.println("Not found");
		else 
			System.out.println("Found");
 
		recDB.delete(19);
		recDB.delete(7);
		recDB.delete(3);
		recDB.delete(13);
		recDB.delete(21);
		recDB.delete(22);
		recDB.delete(3);
	}
}

please help me in code writing

where are you ..? I am really need you

Everyone that contributes to the forums does so without pay...expecting something within a few hours of your post from contributors who are not paid and spend their free time doing so is asking quite a lot, and quite often might turn them away. Especially it the post is quite lengthy and has no defined question. Recommended reading:
How To Ask Questions The Smart Way
Short, Self Contained, Correct Example

Where specifically in the code writing do you need help with, and what is it that you don't quite understand?