Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

C# We want our structure to hold a group of Patients. We don't need to sort them, but we do need to look them up.

C#

We want our structure to hold a group of Patients. We don't need to sort them, but we do need to look them up. In our little program, we will have a way to assign ids to our patients based on their name. (In real life, this could be problematic since our names may end up generating the same id. The list of names you will be working with do not have such a problem.) Our patient information will consist of first and last names, patient id and the cost of their most recent procedure.

As was mentioned above, we will be using two different data structures. The first of these is simply an array. (The old-fashioned kind with a fixed length, no automatic update of a counter, etc.) The second will be the linked-list we have been working on. The array will be an array of these linked-lists; the linked lists will hold patients. Not all of the entries in the array will have a linked list. This will depend on the size of the array, the number of patients among other things. Here is a diagram of what the lists will resemble.

Your program needs to be able to add entries into this rather odd data structure in the following way:

The top row is the array. Some of the elements are empty (i.e. have a null reference), others have a linked list. The linked lists are represented by the grey sentinel element and the blue data-containing elements. Note that these can be different lengths depending on how many patient ids map to a given slot in the array. Some may be empty. In fact, initially all will be empty.

When a patient is added, the code will retrieve the id from the Patient object. It will then mod (%) the patient id by the length of the array. Because of the way mod works, this will give you a number between zero and the length of the array; for example, if the array has a length of 500, mod will give some number from zero up to, but not including, 500. Hopefully you can see that this number can be used as an index into the array. If the entry at that index is null, create a new linked list and place it in the array at that index. At this point, you simply need to add the patient to the linked-list. You do this whether there was already a list or not.

Once the list has been built, the PatientData class will need the ability to retrieve a given Patient from the list. The FindPatientByName method will be passed a patient name. Just as before, this id should be used to determine which slot in the array is used. (You can use the static method in the Patient class or you can instantiate a Patient object using the name passed to the method. The latter approach may be easier since you can then use this dummy object when you call Find. Since CompareTo in the Patient class doesnt use the ProcedureCost, it can be any value. Once the slot is found, the code should use the SimpleLinkedList class at that location to find the given patient. Make certain there is a list there; you should not crash if a non-existent patient id is entered. In addition to returning the Patient object, if found, the code will also keep track of the number of times the CompareTo method is called in the Patient class. This code is already built into the Patient class; you might want to check that code to make certain you understand how it works. We may find a need to keep track of this type of information in future assignments.

An existing project is attached to this assignment. This project has a SimpleLinkedList class and a Patient class. The beginning of the PatientData class is also included. Most of the work that you do will need to be in this class. You will also need to add code to the Main method. For a grade of C or B you will not need to modify the SimpleLinkedList; for an A, you will since there is no method that removes entries from the linked-list. You will find that there is a loadPatients method that reads in the patients and adds them to the PatientData object. The method that actually adds the patient is a stub since this is part of what you will be implementing.

For a starting grade of C:

Implement the above structure. Modify the loop in Main so that it will retrieve the patient from the PatientData object. If the patient does not exist, the user should be informed. If the patient does exist, the user should be shown the patient's name, id and procedure cost. The user should be able to continue entering patients names until typing 'quit'. For our purposes, the program should also indicate how many compares were made to find a given patient. (This means you need to reset the count before calling your find method.)

For a starting grade of B:

Modify the loop in Main to present the user with a menu showing (F)ind, (S)tatistics, (Q)uit. The Statistics menu item should report four values (appropriately labeled): The number of slots in the array, the percentage of used slots in the array (be careful of integer division), the maximum length of the linked lists of your PatientData, and the average length of your linked lists (again, be careful of integer division; also, do not count empty slots when calculating the average, only slots that have a list). The average length can be calculated easily or somewhat more complexly. Think about it.

For a starting grade of A:

Add the ability to remove a patient. Add a (R)emove option to your menu. If a user is removed, Find should report that the user does not exist. As mentioned above, this will involve adding code to the SimpleLinkedList class. Your book can help you with an algorithm to remove items. Make certain you keep the first pointer in your list up-to-date. The remove method does not need to remove a linked-list from the array if it becomes empty, though you may do so if you like.

Questions:

Answer these in a separate document that you submit along with your program.

Run the program several times, using the following values for the size of the array: 3, 200, 1000, 1500. Pick three names that are in the list. Search for them and not how many comparisons each search takes. Make a chart similar to the following:

Name/Size

3

200

1000

1500

name 1

name 2

name 3

What do you notice about the number of comparisons it takes as the size of the array increases? Why is this true?

For a small array size, what is the Big-O for finding an element in this data structure? What about for large array sizes?

If you did work for a B or above:

Add three more entries to the above array capturing the maximum and average lengths of the linked lists and the percent full.

What do you observe about the average lengths? the percentage of slots that are used? Comments on why this is so?

What would the size of the array need to be so that no list had a length greater than one?

Here is the code for the starter program:

Program.cs:

using System; using System.Collections.Generic; using System.IO; using System.Linq; using System.Text; using System.Threading.Tasks;

namespace PatentData { class Program { private const int LIST_SIZE = 3;

static void showPatient(Patient p) { // TODO put code to display the patient's name, id and procedure cost here. }

static void Main(string[] args) { PatientData data = new PatientData(LIST_SIZE); data.LoadPatients("c:/CPT244/patientList.csv");

Console.WriteLine("Enter first and last name:"); string name = Console.ReadLine(); while (!name.ToLower().StartsWith("quit")) { String[] names = name.Split(); if (names.Length != 2) { // TODO -- you may need to modify where you put the end brace // You may also want to change the sense of the boolean expression in the 'if' above // There are multiple ways to handle bad input, // but you shouldn't let bad input crash your program }

Patient.Comparisons = 0; Patient pat = data.FindPatientByName(names[0], names[1]); if (pat != null) { showPatient(pat); } else { Console.WriteLine("Patient not found"); } Console.WriteLine("Comparisions: {0}", Patient.Comparisons); Console.WriteLine("Enter a name:"); name = Console.ReadLine(); }

Console.ReadLine(); } } }

PatientData.cs:

using SimpleLinkedList; using System; using System.IO;

namespace PatentData { class PatientData { private SimpleLinkedList[] list;

public PatientData(int size) { list = new SimpleLinkedList[size]; }

public void LoadPatients(string filename) { FileStream fs = new FileStream(filename, FileMode.Open); StreamReader input = new StreamReader(fs);

while (!input.EndOfStream) { string line = input.ReadLine(); string[] fields = line.Split(",".ToCharArray()); // TODO create the new patient // TODO add the patatient to the list } }

///

/// Adds a patient to the data structure. /// /// The patient to be added. public void AddPatient(Patient patient) { // TODO add code needed to add a patient // Find the correct index // Add the patient to the linked list // Create a new list if there isn't one at this index }

public Patient FindPatientByName(string first, string last) { Patient pat = null; // TODO // create a patient using the names; the cost can be zero since it isn't used in the comparison // use the patient you created to get the id, slot in the array and finally the data in the linked list return pat; } public int FindLongestLength() { int max = 0; // TODO for 'B' grade return max; }

public Patient RemovePatientById(int id) { Patient pat = null; // TODO for 'A' grade // remove the patient // return the data return pat; } } }

Patient.cs:

using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks;

namespace PatentData { public class Patient : IComparable { static public int Comparisons { get; set; }

public int Id { get; set; } public string FirstName { get; set; } public string LastName { get; set; } public double ProcedureCost { get; }

public Patient(string first, string last, double cost, int id) { FirstName = first; LastName = last; ProcedureCost = cost; Id = id; }

public Patient(string first, string last, double cost) : this(first, last, cost, -1 ) { Id = genPatientId(first, last); }

public static int genPatientId(string first, string last) { int id = Math.Abs((last.ToUpper() + first.ToUpper()).GetHashCode())%799993; if (id < 100000) id += 99997;

return id; }

public int CompareTo(Patient other) { Comparisons++; return Id - other.Id; } } }

ListNode.cs:

using System;

namespace SimpleLinkedList { public class ListNode { ///

/// The field that hold the data for the node. /// public T Data { get; set; }

///

/// Pointer to the next node in the list, if applicable. /// public ListNode Next { get; set; }

///

/// noarg constructor /// public ListNode(){}

///

/// Constructor sets the Data property from its argument. /// /// Data for this node. public ListNode(T data) { Data = data; } } }

SimpleLinkedList.cs:

using System; using System.Text;

namespace SimpleLinkedList { public class SimpleLinkedList where T : IComparable { private ListNode head; public int Count { get; private set; }

///

/// Constructor simply creates the sentinel node. /// public SimpleLinkedList() { head = new ListNode(); }

///

/// Adds an entry to the head of the list. A node is created with the object passed in as its data. /// /// The data to be added. public void AddAtHead(T element) { ListNode node = new ListNode(); node.Data = element; node.Next = head.Next; head.Next = node; Count++; }

///

/// Remove the first entry in the list and return its data. /// /// public T RemoveFromHead() { ListNode node = head.Next; T data; if (head.Next != null) { head.Next = head.Next.Next; } Count--;

data = node.Data; node.Data = default(T); // probably not needed since result is no longer accessible

return data; }

///

/// Walks through the list looking for the node that preceeds the node containing the target. /// The object's CompareTo method is used to determine equality. /// /// The object to be found. /// The node prior to the node containing the target, or null if it is not found. private ListNode FindNodeBefore(T target) { ListNode prev = null; prev = head; while (prev.Next != null) { if (prev.Next.Data.CompareTo(target) == 0) { return prev; } prev = prev.Next; }

// never found return null; }

///

/// Find the specified target. The object is considered 'found' if the object's CompareTo method returns zero. /// /// The object to be found. /// public T Find(T target) { ListNode result = FindNodeBefore(target); if (result == null) return default(T);

// advance result to the one we are looking for. result = result.Next; return result.Next.Data; }

///

/// Removes the specified target if the target's CompareTo method returns zero. /// /// The object to be removed. /// public T Remove(T target) { T data = default(T); // TODO needed for 'A' work return data; } } }

The parts of the code that is in Bold and Italics is the code that I need to fix of the program. It is all the ToDo's in the program and then I also need to answer the questions at the end of instructions. All of this should be in C#.

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image_2

Step: 3

blur-text-image_3

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Entity Alignment Concepts Recent Advances And Novel Approaches

Authors: Xiang Zhao ,Weixin Zeng ,Jiuyang Tang

1st Edition

9819942527, 978-9819942527

More Books

Students also viewed these Databases questions