Question
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
public PatientData(int size) { list = new SimpleLinkedList
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 } }
///
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
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
///
///
///
SimpleLinkedList.cs:
using System; using System.Text;
namespace SimpleLinkedList { public class SimpleLinkedList
///
///
///
data = node.Data; node.Data = default(T); // probably not needed since result is no longer accessible
return data; }
///
// never found return null; }
///
// advance result to the one we are looking for. result = result.Next; return result.Next.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
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started