to be in unsorted order in the file but they have to be placed in sorted order within the linked list. The program should use a doubly linked list. Each node in the doubly linked list should have the student’s name, a pointer to the next student, and a pointer to the previous student. Here is a sample visual. The head points to the beginning of the list. The tail points to the end of the list. When inserting consider all the following conditio

Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
icon
Related questions
Question
 
Write a program in c++ and make sure it works, that reads a list of students (first names only) from a file. It is possible for the names to
be in unsorted order in the file but they have to be placed in sorted order within the linked list.
The program should use a doubly linked list.
Each node in the doubly linked list should have the student’s name, a pointer to the next student, and a
pointer to the previous student. Here is a sample visual. The head points to the beginning of the list. The
tail points to the end of the list.
When inserting consider all the following conditions:
if(!head){ //no other nodes
}else if (strcmp(data, head->name)<0){ //smaller than head
}else if (strcmp(data, tail->name)>0){ //larger than tail
}else{ //somewhere in the middle
}
 
 
 
 
 
 
 
When deleting a student consider all the following conditions:
student may be at the head, the tail or in the middle
Below, you will find a sample of what the file looks like. Notice the names are in unsorted order but the
information placed in the linked list (above visual) is in sorted order. The name of the file should be
“input.txt”.
In the text file, the word delete followed by a name, should delete the node with that specific student’s
name from the doubly linked list. If the name is not found, then nothing is deleted.
(NOTE: The above visual represents only the first three lines from the text file below.)
Jim
jill
John
delete jill
Bob
Jack
delete jim
At the end of the program, traverse through the contents of the linked list in both ascending and
descending order, using the doubly linked list, and write the contents into the file output.txt. For
example, given the above list, here is the sample display:
Bob
Jack
John
=============
John
Jack
Bob
  1. Do you have any suggestions about how I should start this lab?

A: Make sure that you draw out the nodes on a piece of paper so that you know exactly what is being connected to what. If you try to do this in your head, then more than likely, you will not do well.

 

  1. What do I do with duplicate names?

A: Ignore it.

 

  1. Do I need to use some sort of sort function to sort the nodes?

A: No, do not use any of the usual sorting algorithms. It will complicate life. Once you create a node, you need to decide where it goes in the doubly linked list. It can go in the beginning which affects the head. It can go at the end which affects the tail. It can go in the middle which means it doesn’t affect either 

 

Once you create your node, start traversing through your linked list. A variable like curr will point to the node in your linked list that you are on. Compare the name in curr with the name in the newly created node. If the name in curr node is bigger, then you have found the spot to insert your node. If the name in curr node is smaller, then you continue to move to the next node in your list. If you have reached the end of the list and the name in curr node is smaller, then you have to insert at the end and update the tail. If the name in the curr node is bigger and you are at the beginning of your list, then you have a new head. If the names are the same, then you can just get out because you have a duplicate

 

if(!head){                            //no other nodes

}else if (strcmp(data, head->name)<0){ //smaller than head

}else if (strcmp(data, tail->name)>0){   //larger than tail

}else{                                //somewhere in the middle

Use a loop to traverse through the list to find the location of where you need to insert

}

  1. Can I use any of the built-in library for linked lists?

A: No, you create everything from scratch

 

  1. Can I read the items from the file into some other data structure, sort it and then recreate my linked list

A: No, you sort as you insert into your linked list.

 

  1. Can you provide a general pseudocode to get me started?

 

//you will not be reading the entire line but rather one word at a time

Loop through the file as long as there is something to read

Read word//reads first word which could be the word delete or a name

If the string==’delete’

Read word   //this means that the next word is a name

Delete (word)  //look for the node and delete it

Else

//the line just contained a name which means you insert

Insert (word)

 

Traverse()   //Traverse through the list, display in ascending, descending order

 

 

Doubly contains head and tail as instance variables, delete,insert, traverseAsending, traverseDescnding methods. Since all variables are private, provide getter and setter methods

 

Node will contain value, prev, next as instance variables, Since all the variables will be private, provide getter and setter methods.

 

Driver will contain the main method which will contain the content from item 6 in this document

 

 

Expert Solution
Step 1

the c++ code is an given below :

 

steps

Step by step

Solved in 2 steps

Blurred answer
Knowledge Booster
Structure
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.
Similar questions
  • SEE MORE QUESTIONS
Recommended textbooks for you
Database System Concepts
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education