Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

por page 1 of 4) Edited Project 1 (in C++): Linked-list implementation of Stack, Queue, and ordered list (in ascending order). The operations include insertion,

image text in transcribed
image text in transcribed
image text in transcribed
image text in transcribed
image text in transcribed
image text in transcribed
image text in transcribed
por page 1 of 4) Edited Project 1 (in C++): Linked-list implementation of Stack, Queue, and ordered list (in ascending order). The operations include insertion, deletion and print. The input file contains a list of pair (op, data>) where op is either + or, where + means insert, -thians delete, and data is a positive integer. For example, +20, means insert 20,-20 means delete 20. Your program will construct a stack, then, a queue and then, an ordered list, all in linked list implementations. Reading from the input pairs, your program will perform operations, given by the pairs, on the Stack. Then, reading the same input pairs, your program will perform operations on a queue, then do the same on an ordered list. ** For Stack and Queue, the data after the is not used. Language: CH // CHTutorial and C project Tutorial are posted in Google Classroom Project points: 10 pts Due Date: Soft copy (*.zip) and hard copies (.pdf): -02/10/2021 Wednesday before midnight -1 for 1 day late: 2/11/2021 Thursday before midnight -2 for 2 days late: 2/12/2021 Friday before midnight -10/10: 2/12/2021 Friday after midnight *** Name your soft copy and hard copy files using the naming convention as given in the project submission requirement discussed in a lecture and is posted in Google Classroom. *** All on-line submission MUST include Soft copy (zip) and hard copy .pdf) in the same email attachments with correct email subject as stated in the email requirement, otherwise, your submission will be rejected * + 12 +6 I. Input (use argv[1]): a text file contain a list of pair (}, one pair per text line, where op is either - or + - means delete,+ means insert and data is a positive integer. For example, please +8 solve this coding II. Outputs: There will be three output files. using C++ 1) outFilel (use argv[2]): for stack outputs. 2) outFile2 (use argv[3]): for queue outputs. 3) outFile3 (use argv[4]: for ordered List output. + 25 - 8 - 10 sed III. Data structure: 80 III. Data structure: I - listNode class friend of LL-Stack, LLQucus, LLlist - data (int) - next (listNode) Method: - constructor (data) //create a node with given data -printNode (node, outFile) in the format as below: (node's data, data of node's next) LLStack class - listNode top Methods: - constructor (...) // creates a new stack with a dummy node, set the data in the dummy node to -9999 and set next to null; and let top points to the dummy node - buildStack (inFile) // see algorithm below. Implement all other stack operations on your own. Use the following stack operations in buildStack. You may add other operations as needed. -push (newNode) //puts new Node at the top of Stack, after the dummy node, - listNode pop(...) // if stack is empty returns null, otherwise deletes and returns the top node of Stack. - bool isEmpty (...) // if Stack is empty returns true, otherwise returns false. - printStack (outFilel) // DO NOT delete nodes in Stack! Outputs to outFilel, the entire stack, including dummy node, you may call printNode(...) using the following format: Top -->-9999, next's data )(data, next's data)...(data, NULL)> NULL For example Top 4.9999, 8)>(8, 11) -11,21) (21, 42).-(87, NULL)-> NULL - LLQueue class - listNode head // head always points to the dummy node! - listNode* tail // tail always points to the last node of the queue; tail points to dummy initially. Methods: - constructor (...) // creates a new Queue with a dummy node, set the data in the dummy node to -9999 and sets next to null; let both head and tail point to the dummy node. - buildQueue (inFile) // see algorithm below. Implement all other Queue operations on your own. 5 Top 2 UNULSULLE - LL Queue class - listNode* head // head always points to the dummy node! - listNode tail // tail always points to the last node of the queue; tail points to dummy initially. I Methods: - constructor (...) // creates a new Queue with a dummy node, set the data in the dummy node to -9999 and sets next to null; let both head and tail point to the dummy node. - buildQueue (inFile) // see algorithm below. Implement all other Queue operations on your own. ** Use the following queue operations in buildQ. You may add other operations as needed. - insertQ (newNode) // insert the new Node after the tail of Q. - listNode deleteQ (...) // if Q is not empty, deletes the first node, after the dummy from Q and returns the // deleted node, otherwise, returns null. - bool isEmpty (...) // checks to see if Q is empty, i.e., tail points to the dummy node. It retums true is Q is empty and false otherwise. - print (outFile2) // DO NOT delete nodes in Queue! Outputs to outFile2, the entire Q, including the dummy node, you may calling printNode (...) using the following format: Front -9999, next's data:)->data, next's data)__ =>(dista, NULL)> NULL Front -9999, 8)-8, 11) --X11,21)21,42) -> 87, NULL)-> NULL - LLlist class - listNode* listHead // always points to the dummy node Methods: - constructor (...) // create new list with a dummy node, set the data in the dummy node to -9999 and let listHead points to the dummy node. - buildList (inFile) // see algorithm below. Implement all other list operations on your own. ** Use the following queue operations in buildList. You may add other operations as needed. - listInsert (newNode) // Use the algorithm from the lecture note. - listNode deleteOneNode (data) // First searches a node in the list that contains data; if such node exits, deletes the node from the list and returns the deleted node, otherwise, returns null. -printList (outFile3) // Output to outFile3, the entire list, including the dummy node, by calling pimtNode(...) until at the end of the list, using the following format: listHead (-9999, next's data (data, next's data)_(data, NULL)-> NULL For example listHead -9999, )-(1)-(11,21) (21.42) (87, NULL) > NULL USCI Proect1.pd! (page 3 of 4) Edited -printList (outFile3) // Output to outFile3, the entire list, including the dummy node, by calling pimtNodel...) until at the end of the list, using the following format: Bistal -1999, est's dataduta, nek' data)__ (det, NULL)> NULL. For example listhead-9999,)->,11) (11.21) -21, 42) - 07, NULL NULL IV. main (...) Step 0: inFilet open from argv[1] outFilel, outFile2, outFile3 + open from argv[2], argv[3], argv[4). Step 1: buildStack (inFile, outFilel) // Algorithm steps is given below Step 2: close inFile Step 3: re-open inFile Step 4: buildQueue (inFile, outFilc2) // Algorithm steps is given below Step 5: close inFile Step 6: re-open inFile Step 7: buildList (inFile, outFile3) // Algorithm steps is given below Step 8: close all files V. buildStack (in File, outFilel) Step 0: S Use LLStack constructor to establish a stack Step 1: op, data read the pair from inFile outFilel output op, data // write description Step 2: if op "" new Node + get a listNode with data // Use listNode constructor Push (new Node) // put new Node onto the top of the stack Else if op junk Pop 0 if junk is not null free junk else outputs to outFilel a message: the Stack is empty. V. buildStack (inFile, outFilel) Step 0: S Use LLStack constructor to establish a stack Step 1: op, data read the pair from inFile outFilel output op, data // write description Step 2: if op "4" newNode get a listNode with data // Use listNode constructor Push (newNode) // put newNode onto the top of the stack Else if op == "-" junk Pop 0 if junk is not null free junk else outputs to outFilel a message: the Stack is empty. Step 3: printStack(outFilel) Step 4: repeat step 1 to step 3 until inFile is empty. ***** VI. buildQueueinFile, outFile2) Step 0:Q Use LL Queue constructor to establish a queue, with head and tail. Step 1: op, data read the pair from inFile outFile2 output op, data // write description Step 2: if op "4" newNode get a listNode with data // Use listNode constructor insertQ (newNode) // insert the newNode after the tail of Q; else if op Junk deleteQ 0 If junk not null Free junk else outputs to outFile2 a message: the Queue is empty. Step 3: printQ(outFile2) Step 4: repeat step 1 to step 3 until inFile is empty. 111 4 OT SURUP newNode - get a listNode with data // Use listNode constructor insertQ (newNode) // insert the newNode after the tail of Q: else if op Junk deleteQ0 If junk not null Free junk else outputs to outFile2 a message: the Queue is empty. Step 3: print (outFile2) Step 4: repeat step 1 to step 3 until inFile is empty. ***** VIL buildListinFile, outFile3) Step 0: listHead Use LList constructor to establish a Llist Step 1: op, data read the pair from inFile outFile3 output op, data // write description Step 2: if op "4" newNode get a listNode with data // Use listNode constructor listInsert (new Node) else if op -- Junk deleteOneNode (data) If junk not null Free junk else outputs to outFile3 a message: the data is not in the list Step 3: printList (outFile3) Step 4: repeat step I to step 3 until inFile is empty. Pseudo Code is given please Solve it in Ctt por page 1 of 4) Edited Project 1 (in C++): Linked-list implementation of Stack, Queue, and ordered list (in ascending order). The operations include insertion, deletion and print. The input file contains a list of pair (op, data>) where op is either + or, where + means insert, -thians delete, and data is a positive integer. For example, +20, means insert 20,-20 means delete 20. Your program will construct a stack, then, a queue and then, an ordered list, all in linked list implementations. Reading from the input pairs, your program will perform operations, given by the pairs, on the Stack. Then, reading the same input pairs, your program will perform operations on a queue, then do the same on an ordered list. ** For Stack and Queue, the data after the is not used. Language: CH // CHTutorial and C project Tutorial are posted in Google Classroom Project points: 10 pts Due Date: Soft copy (*.zip) and hard copies (.pdf): -02/10/2021 Wednesday before midnight -1 for 1 day late: 2/11/2021 Thursday before midnight -2 for 2 days late: 2/12/2021 Friday before midnight -10/10: 2/12/2021 Friday after midnight *** Name your soft copy and hard copy files using the naming convention as given in the project submission requirement discussed in a lecture and is posted in Google Classroom. *** All on-line submission MUST include Soft copy (zip) and hard copy .pdf) in the same email attachments with correct email subject as stated in the email requirement, otherwise, your submission will be rejected * + 12 +6 I. Input (use argv[1]): a text file contain a list of pair (}, one pair per text line, where op is either - or + - means delete,+ means insert and data is a positive integer. For example, please +8 solve this coding II. Outputs: There will be three output files. using C++ 1) outFilel (use argv[2]): for stack outputs. 2) outFile2 (use argv[3]): for queue outputs. 3) outFile3 (use argv[4]: for ordered List output. + 25 - 8 - 10 sed III. Data structure: 80 III. Data structure: I - listNode class friend of LL-Stack, LLQucus, LLlist - data (int) - next (listNode) Method: - constructor (data) //create a node with given data -printNode (node, outFile) in the format as below: (node's data, data of node's next) LLStack class - listNode top Methods: - constructor (...) // creates a new stack with a dummy node, set the data in the dummy node to -9999 and set next to null; and let top points to the dummy node - buildStack (inFile) // see algorithm below. Implement all other stack operations on your own. Use the following stack operations in buildStack. You may add other operations as needed. -push (newNode) //puts new Node at the top of Stack, after the dummy node, - listNode pop(...) // if stack is empty returns null, otherwise deletes and returns the top node of Stack. - bool isEmpty (...) // if Stack is empty returns true, otherwise returns false. - printStack (outFilel) // DO NOT delete nodes in Stack! Outputs to outFilel, the entire stack, including dummy node, you may call printNode(...) using the following format: Top -->-9999, next's data )(data, next's data)...(data, NULL)> NULL For example Top 4.9999, 8)>(8, 11) -11,21) (21, 42).-(87, NULL)-> NULL - LLQueue class - listNode head // head always points to the dummy node! - listNode* tail // tail always points to the last node of the queue; tail points to dummy initially. Methods: - constructor (...) // creates a new Queue with a dummy node, set the data in the dummy node to -9999 and sets next to null; let both head and tail point to the dummy node. - buildQueue (inFile) // see algorithm below. Implement all other Queue operations on your own. 5 Top 2 UNULSULLE - LL Queue class - listNode* head // head always points to the dummy node! - listNode tail // tail always points to the last node of the queue; tail points to dummy initially. I Methods: - constructor (...) // creates a new Queue with a dummy node, set the data in the dummy node to -9999 and sets next to null; let both head and tail point to the dummy node. - buildQueue (inFile) // see algorithm below. Implement all other Queue operations on your own. ** Use the following queue operations in buildQ. You may add other operations as needed. - insertQ (newNode) // insert the new Node after the tail of Q. - listNode deleteQ (...) // if Q is not empty, deletes the first node, after the dummy from Q and returns the // deleted node, otherwise, returns null. - bool isEmpty (...) // checks to see if Q is empty, i.e., tail points to the dummy node. It retums true is Q is empty and false otherwise. - print (outFile2) // DO NOT delete nodes in Queue! Outputs to outFile2, the entire Q, including the dummy node, you may calling printNode (...) using the following format: Front -9999, next's data:)->data, next's data)__ =>(dista, NULL)> NULL Front -9999, 8)-8, 11) --X11,21)21,42) -> 87, NULL)-> NULL - LLlist class - listNode* listHead // always points to the dummy node Methods: - constructor (...) // create new list with a dummy node, set the data in the dummy node to -9999 and let listHead points to the dummy node. - buildList (inFile) // see algorithm below. Implement all other list operations on your own. ** Use the following queue operations in buildList. You may add other operations as needed. - listInsert (newNode) // Use the algorithm from the lecture note. - listNode deleteOneNode (data) // First searches a node in the list that contains data; if such node exits, deletes the node from the list and returns the deleted node, otherwise, returns null. -printList (outFile3) // Output to outFile3, the entire list, including the dummy node, by calling pimtNode(...) until at the end of the list, using the following format: listHead (-9999, next's data (data, next's data)_(data, NULL)-> NULL For example listHead -9999, )-(1)-(11,21) (21.42) (87, NULL) > NULL USCI Proect1.pd! (page 3 of 4) Edited -printList (outFile3) // Output to outFile3, the entire list, including the dummy node, by calling pimtNodel...) until at the end of the list, using the following format: Bistal -1999, est's dataduta, nek' data)__ (det, NULL)> NULL. For example listhead-9999,)->,11) (11.21) -21, 42) - 07, NULL NULL IV. main (...) Step 0: inFilet open from argv[1] outFilel, outFile2, outFile3 + open from argv[2], argv[3], argv[4). Step 1: buildStack (inFile, outFilel) // Algorithm steps is given below Step 2: close inFile Step 3: re-open inFile Step 4: buildQueue (inFile, outFilc2) // Algorithm steps is given below Step 5: close inFile Step 6: re-open inFile Step 7: buildList (inFile, outFile3) // Algorithm steps is given below Step 8: close all files V. buildStack (in File, outFilel) Step 0: S Use LLStack constructor to establish a stack Step 1: op, data read the pair from inFile outFilel output op, data // write description Step 2: if op "" new Node + get a listNode with data // Use listNode constructor Push (new Node) // put new Node onto the top of the stack Else if op junk Pop 0 if junk is not null free junk else outputs to outFilel a message: the Stack is empty. V. buildStack (inFile, outFilel) Step 0: S Use LLStack constructor to establish a stack Step 1: op, data read the pair from inFile outFilel output op, data // write description Step 2: if op "4" newNode get a listNode with data // Use listNode constructor Push (newNode) // put newNode onto the top of the stack Else if op == "-" junk Pop 0 if junk is not null free junk else outputs to outFilel a message: the Stack is empty. Step 3: printStack(outFilel) Step 4: repeat step 1 to step 3 until inFile is empty. ***** VI. buildQueueinFile, outFile2) Step 0:Q Use LL Queue constructor to establish a queue, with head and tail. Step 1: op, data read the pair from inFile outFile2 output op, data // write description Step 2: if op "4" newNode get a listNode with data // Use listNode constructor insertQ (newNode) // insert the newNode after the tail of Q; else if op Junk deleteQ 0 If junk not null Free junk else outputs to outFile2 a message: the Queue is empty. Step 3: printQ(outFile2) Step 4: repeat step 1 to step 3 until inFile is empty. 111 4 OT SURUP newNode - get a listNode with data // Use listNode constructor insertQ (newNode) // insert the newNode after the tail of Q: else if op Junk deleteQ0 If junk not null Free junk else outputs to outFile2 a message: the Queue is empty. Step 3: print (outFile2) Step 4: repeat step 1 to step 3 until inFile is empty. ***** VIL buildListinFile, outFile3) Step 0: listHead Use LList constructor to establish a Llist Step 1: op, data read the pair from inFile outFile3 output op, data // write description Step 2: if op "4" newNode get a listNode with data // Use listNode constructor listInsert (new Node) else if op -- Junk deleteOneNode (data) If junk not null Free junk else outputs to outFile3 a message: the data is not in the list Step 3: printList (outFile3) Step 4: repeat step I to step 3 until inFile is empty. Pseudo Code is given please Solve it in Ctt

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

Step: 3

blur-text-image

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

Database Systems For Advanced Applications 15th International Conference Dasfaa 2010 Tsukuba Japan April 2010 Proceedings Part 1 Lncs 5981

Authors: Hiroyuki Kitagawa ,Yoshiharu Ishikawa ,Wenjie Li ,Chiemi Watanabe

2010th Edition

3642120253, 978-3642120251

More Books

Students also viewed these Databases questions

Question

What is a decision structure?

Answered: 1 week ago