LAB 7a: Write A Linked-List Solution

LAB 7a: Write A Linked-List Solution [ DvcSchedule7a.cpp ]
Purpose. In this lab you will learn how to create a linked list, add values to the front of the list, search the list for a match, and deallocate memory at the end of the program. You will also learn the equivalent nested for-loop sorting technique that you applied to arrays, now applied to linked-lists.
Requirements. Rewrite lab 6’s DvcSchedule6a.cpp as DvcSchedule7a.cpp , to parse dvc-schedule.txt. Apply a linked-list instead of the STL container. Do not use templates.

Note — the dvc-schedule.txt file may contain duplicate entries — skip duplicates! Use any method of your choosing — you do not need to use a linked list. You may use the exact same method you used in lab 6, if you wish.

While it is possible to solve this with a single struct by simply adding a next pointer to it, create a separate “Node” struct instead. This will make it easier to convert the solution to an ADT solution later.

// the data element
struct SubjectCode
{
string name;
int count;
};

// the linked-list node
struct Node
{
SubjectCode data;
Node* next;
};
// nested for-loop for sorting
Node* p;
Node* q;
for (p = start; p; p = p->next)
{
for (q = p->next; q; q = q->next)
{
if (p->data.name.compare(q->data.name) > 0)
{
// swap data
…
You may want to write an overloaded less-than or greater-than operator for the “SubjectCode” struct, although that is not necessary. Then you could use this in the nested for-loops: if (p->data > q->data).

Submit the CPP file to the class website for credit.

Program I/O. Same as for DvcSchedule6a.cpp.

LAB 7b: Applying Advanced Linked-List Techniques [ DvcSchedule7b.cpp ]
Purpose. In this lab you will learn how to insert nodes into their proper positions in a linked-list. One advantage that linked-lists have over arrays is that it is easy to insert new values in the middle of the existing ones. With arrays, that involves shifting of “downstream” values to make room for the insert. But with linked-lists, it’s just a matter of relinking nodes.
Requirements. Rewrite DvcSchedule7a.cpp as DvcSchedule7b.cpp so that it builds the linked-list in alphabetical order, instead of having to do a nested for-loop sort at the end. So when adding a new node to the linked-list, do not simply add it to the front of the list as you did in the previous lab. Instead, find the “insertion point” as explained in the lecture notes, and insert the node so that alphabetical order is maintained at all times. Start the clock before opening the input file, and stop the clock just BEFORE the printing starts.

// LAB 7a ALGORITHM
create linked list
open data file
start loop
if end of file is reached, exit loop
read and parse the line
if not a valid entry, skip to next cycle
see if subjectCode is already in the list
if found
increment count
else
create a new node
add to front of list
end loop
sort list with nested for-loops
print results

// LAB 7b ALGORITHM
create linked list
open data file
start loop
if end of file is reached, exit loop
read and parse the line
if not a valid entry, skip to next cycle
see if subjectCode is already in the list
if found
increment count
else
create a new node
find insertion point
insert into list
end loop
print results

You may want to write an overloaded less-than or greater-than operator for the “SubjectCode” struct, although that is not necessary. Also note that the algorithm has two passes — once to find that a matching node is not already there, and another to find out where to insert a new one. If you can figure out how to combine these into a single pass, go ahead.

Submit the CPP file to the class website for credit.

Our website has a team of professional writers who can help you write any of your homework. They will write your papers from scratch. We also have a team of editors just to make sure all papers are of HIGH QUALITY & PLAGIARISM FREE. To make an Order you only need to click Ask A Question and we will direct you to our Order Page at WriteDemy. Then fill Our Order Form with all your assignment instructions. Select your deadline and pay for your paper. You will get it few hours before your set deadline.