Linked List Utilities in Three Parts: Part A
CS 3358
75 out of 200 points
________________________________________
Problem Statement
This assignment is to implement two linked lists, two stacks, and two queues. This is done in three parts.
1. Part A implements a linked list using nodes defined as parallel C++ arrays
2. Part B implements a linked list using nodes defined by a C++ abstract data type (ADT) which includes pointers.
3. Part C implements stacks and queues using a linked list.
a. A stack or queue may be implemented with either the linked list files from Part A or the files from Part B.
b. It should operate the same way with either linked list implementation.
You will implement one stack and one queue for each type of linked list.
Parts A, B, and C are submitted to TRACS separately, for convenience and to keep the number of file attachments small. Some files are submitted to more than one Part, as indicated below. The separate TRACS locations are for convenience, however: together, the parts constitute one assignment with one due date.
Considerations
All of the techniques for implementing linked lists with nodes and pointers (Part B) are standard and readily available in almost any textbook. Their analogous construction using C++ arrays should be fairly straightforward. Stack and Queue implementations (Part C) are also given in most textbook illustrations. In addition, we will be discussing all the steps of each implementation, and each part of the assignment, in lectures -- to the point of pseudocode in many cases.
The point is that writing the class definitions and methods has, for a great deal of this assignment, been done in forms you can access. It is not quite a matter of simply learning to use existing STL objects and functions: you must write, document, compile, and test these routines. The C++ array implementations are not readily available and most textbook illustrations use templates and other features we are not including at the moment. So code that is simply copied will stand out and will probably not run as is.
But you do have a lot of resources to draw upon that makes the scope of this assignment smaller than it may seem at first glance. I will, therefore, pay extra attention to your documentation (including header comments for every function, every separate .h and .cpp file, etc.). I will also pay special attention to the robustness of your code: memory management, handling data leakage, avoiding runaway loops, stray links and “lost” nodes, running over array bounds, and other “marginal” situations and conditions. I want to know that you have tested it thoroughly. This means I expect you to devise good tests to shake out the glitches, not just fill a list and display it once, safely.
Your documentation and testing will show me that you understand what you have written, however much of those available resources you draw upon. It will also identify you as the sole author of your submissions. I will consider identical submissions as violations of the university’s cheating policy, as referenced in the syllabus.
Specifications
Every file must have a header block with the name of the file, your name, and your TxState ID#.
Header (.h) files must have the line “Defines class” followed by the name of the class being defined.
Source code (.cpp) files must have the line “Functions defined” followed by a list of the functions defined in the file (one name per line).
Part A (75 points)
Implement a singly-linked list using the C++ array data type. It is important to remember that you are not implementing an Array data structure, you are using the array data type to implement a Linked List data structure.
Defined constants (defined in the main header file prog3.h):
const int A_SIZE = 30 (subject to change when uses require it)
const int NULL_X = -1 (“null index” for array data type)
Define Class LLArray
1. Minimum set of private variables (you may use more, e.g. size of list):
a. int listNode[A_SIZE]
b. int next[A_SIZE ]
c. “trackers” (all hold link values, which are indices in this implementation)
i. int head
ii. int current
2. Minimum set of methods. Methods must return values where indicated, may or may not return values in other cases, at your discretion. You should be able to determine the method type required when returning a value.
a. Two types of Traversal:
i. Display( ): displays all items and returns the number of items in the list)
ii. Search(x): returns a link to the first node containing the value x, or NULL_X if not found)
b. Three types of Insert (all return values indicating success or failure)
i. Insert(v, x): inserts new node with value v before the first node in the list which contains the value x
ii. Insert(v): inserts new node with value v at head of list
iii. Append(v): inserts new node with value v at end of list
c. Three types of Delete (all return values indicating success or failure)
i. Delete(x): deletes the first node in the list which contains the value x
ii. Delete( ): deletes the node at the end of the list
iii. Chop( ): deletes the node at the beginning of the list
d. const accessor methods to return private values, as needed. Must have
i. isEmpty( )
ii. isFull( ) [true when the list size equals A_SIZE]
iii. listSize( ) [may traverse and count, or if a private variable has been maintained, its value]
iv. firstValue( ) returns the value of the first node in the list
v. lastValue( ) returns the value of the last node in the list
The class definition is contained in its own header file (llarray.h). The class methods are prototyped in the class definition and defined in a source file ([login to view URL]) separate from the main program file ([login to view URL]).
Notes: Since you are using a fixed array, insertion and deletion do not change allocated memory. The arrays should be deleted by the Destructor, however. Insert( ) and Delete( ) are, of course, overloaded functions.
Required files:
1. Main program
a. prog3.h header file
b. [login to view URL] source code
2. Files for LLArray:
a. llarray.h for class definition
b. [login to view URL] for methods
3. Makefile: compiles
a. llarray or [login to view URL] from
prog3.h, [login to view URL], llarray.h, [login to view URL]
________________________________________
Submit all indicated files through TRACS as attachments to the assignment portal: Source (.cpp) files, header (.h) files, executable file (llarray or [login to view URL]), and makefile (makefile).
Note: This program must compile and execute in Linux.
Linked List Utilities in Three Parts: Part B
CS 3358
75 out of 200 points
________________________________________
Problem Statement
This assignment is to implement two linked lists, two stacks, and two queues. This is done in three parts.
1. Part A implements a linked list using nodes defined as parallel C++ arrays
2. Part B implements a linked list using nodes defined by a C++ abstract data type (ADT) which includes pointers.
3. Part C implements stacks and queues using a linked list.
a. A stack or queue may be implemented with either the linked list files from Part A or the files from Part B.
b. It should operate the same way with either linked list implementation.
You will implement one stack and one queue for each type of linked list.
Parts A, B, and C are submitted to TRACS separately, for convenience and to keep the number of file attachments small. Some files are submitted to more than one Part, as indicated below. The separate TRACS locations are for convenience, however: together, the parts constitute one assignment with one due date.
Considerations
All of the techniques for implementing linked lists with nodes and pointers (Part B) are standard and readily available in almost any textbook. Their analogous construction using C++ arrays should be fairly straightforward. Stack and Queue implementations (Part C) are also given in most textbook illustrations. In addition, we will be discussing all the steps of each implementation, and each part of the assignment, in lectures -- to the point of pseudocode in many cases.
The point is that writing the class definitions and methods has, for a great deal of this assignment, been done in forms you can access. It is not quite a matter of simply learning to use existing STL objects and functions: you must write, document, compile, and test these routines. The C++ array implementations are not readily available and most textbook illustrations use templates and other features we are not including at the moment. So code that is simply copied will stand out and will probably not run as is.
But you do have a lot of resources to draw upon that makes the scope of this assignment smaller than it may seem at first glance. I will, therefore, pay extra attention to your documentation (including header comments for every function, every separate .h and .cpp file, etc.). I will also pay special attention to the robustness of your code: memory management, handling data leakage, avoiding runaway loops, stray links and “lost” nodes, running over array bounds, and other “marginal” situations and conditions. I want to know that you have tested it thoroughly. This means I expect you to devise good tests to shake out the glitches, not just fill a list and display it once, safely.
Your documentation and testing will show me that you understand what you have written, however much of those available resources you draw upon. It will also identify you as the sole author of your submissions. I will consider identical submissions as violations of the university’s cheating policy, as referenced in the syllabus.
Specifications
Every file must have a header block with the name of the file, your name, and your TxState ID#.
Header (.h) files must have the line “Defines class” followed by the name of the class being defined.
Source code (.cpp) files must have the line “Functions defined” followed by a list of the functions defined in the file (one name per line).
Part B (75 points)
Implement a singly-linked list using nodes which are C++ ADTs.
Define Class LLNodePtr
1. Node definition:
struct listNode
{
int value;
listNode* next;
}
2. Minimum set of private variables (you may use more, e.g. size of list, last node of list):
a. listNode * head
b. listNode * current
3. Minimum set of methods. Methods must return values where indicated, may or may not return values in other cases, at your discretion. You should be able to determine the method type required when returning a value.
a. Two types of Traversal:
i. Display( ): displays all items and returns the number of items in the list)
ii. Search(x): returns a link to the first node containing the value x, or NULL_X if not found)
b. Three types of Insert (all return values indicating success or failure)
iii. Insert(v, x): inserts new node with value v before the first node in the list which contains the value x
iv. Insert(v): inserts new node with value v at head of list
v. Append(v): inserts new node with value v at end of list
c. Three types of Delete (all return values indicating success or failure)
vi. Delete(x): deletes the first node in the list which contains the value x
vii. Delete( ): deletes the node at the end of the list
viii. Chop( ): deletes the node at the beginning of the list
d. const accessor methods to return private values, as needed. Must have
i. isEmpty( )
ii. isFull( ) [true when allocating a new node fails]
iii. listSize( ) [may traverse and count, or if a private variable has been maintained, its value]
iv. firstValue( ) returns the value of the first node in the list
v. lastValue( ) returns the value of the last node in the list
The class definition is contained in its own header file, (llnodeptr.h). The class methods are prototyped in the class definition and defined in a source file ([login to view URL]) separate from the main program file ([login to view URL]).
Notes: The methods for LLNodePtr have exactly the same names and perform exactly the same operations as the methods for LLArray; they have the same interface. They are simply implemented for a differently defined list object.
Required files:
1. Main program
a. prog3.h header file
b. [login to view URL] source code
2. Files for LLNodePtr
a. llnodeptr.h for class definition
b. [login to view URL] for methods
3. Makefile: compiles
a. llnodeptr or [login to view URL] from
prog3.h, [login to view URL], llnodeptr.h, [login to view URL]
________________________________________
Submit all indicated files through TRACS as attachments to the assignment portal: Source (.cpp) files, header (.h) files, executable file (llnodeptr or [login to view URL]), and makefile (makefile).
Note: This program must compile and execute in Linux.
Linked List Utilities in Three Parts: Part C
CS 3358
50 out of 200 points
________________________________________
Problem Statement
This assignment is to implement two linked lists, two stacks, and two queues. This is done in three parts.
1. Part A implements a linked list using nodes defined as parallel C++ arrays
2. Part B implements a linked list using nodes defined by a C++ abstract data type (ADT) which includes pointers.
3. Part C implements stacks and queues using a linked list.
a. A stack or queue may be implemented with either the linked list files from Part A or the files from Part B.
b. It should operate the same way with either linked list implementation.
You will implement one stack and one queue for each type of linked list.
Parts A, B, and C are submitted to TRACS separately, for convenience and to keep the number of file attachments small. Some files are submitted to more than one Part, as indicated below. The separate TRACS locations are for convenience, however: together, the parts constitute one assignment with one due date.
Considerations
All of the techniques for implementing linked lists with nodes and pointers (Part B) are standard and readily available in almost any textbook. Their analogous construction using C++ arrays should be fairly straightforward. Stack and Queue implementations (Part C) are also given in most textbook illustrations. In addition, we will be discussing all the steps of each implementation, and each part of the assignment, in lectures -- to the point of pseudocode in many cases.
The point is that writing the class definitions and methods has, for a great deal of this assignment, been done in forms you can access. It is not quite a matter of simply learning to use existing STL objects and functions: you must write, document, compile, and test these routines. The C++ array implementations are not readily available and most textbook illustrations use templates and other features we are not including at the moment. So code that is simply copied will stand out and will probably not run as is.
But you do have a lot of resources to draw upon that makes the scope of this assignment smaller than it may seem at first glance. I will, therefore, pay extra attention to your documentation (including header comments for every function, every separate .h and .cpp file, etc.). I will also pay special attention to the robustness of your code: memory management, handling data leakage, avoiding runaway loops, stray links and “lost” nodes, running over array bounds, and other “marginal” situations and conditions. I want to know that you have tested it thoroughly. This means I expect you to devise good tests to shake out the glitches, not just fill a list and display it once, safely.
Your documentation and testing will show me that you understand what you have written, however much of those available resources you draw upon. It will also identify you as the sole author of your submissions. I will consider identical submissions as violations of the university’s cheating policy, as referenced in the syllabus.
Specifications
Every file must have a header block with the name of the file, your name, and your TxState ID#.
Header (.h) files must have the line “Defines class” followed by the name of the class being defined.
Source code (.cpp) files must have the line “Functions defined” followed by a list of the functions defined in the file (one name per line).
Part C (50 points)
Implement two Stack classes and two Queue classes as linked lists. They should be able to use either of the implementations in parts A and B, that is, all their references should be to a linked list object and its methods, and the only difference will be which class is used to define the object they use.
1. Stack and Queue classes
a. Minimum set of private variables:
i. arrayStack and arrayQueue:
1. LLArray linkedList
ii. nodeStack and nodeQueue:
1. LLNodePtr linkedList
2. Stack and Queue functions:
a. arrayStack and nodeStack
i. frontPush(v) puts a node with value v on the stack
ii. frontPop( ) removes the node from the top of the stack, returns its value
iii. endPush(v) puts a node with value v on the stack
iv. endPop( ) removes the node from the top of the stack, returns its value
b. arrayQueue and nodeQueue
i. frontEnqueue(v) puts a node with value v in the queue
ii. frontDequeue( ) removes the node from the end of the queue, returns its value
iii. endEnqueue(v) puts a node with value v in the queue
iv. endDequeue( ) removes the node from the end of the queue, returns its value
Notes: All classes use a private linked list named linkedList. In classes arrayStack and arrayQueue, linkedList is an LLArray object; in classes nodeStack and nodeQueue, stackList is an LLNodePtr object. This means that the stack methods frontPush, frontPop, endPush, and endPop are the same for both stack classes, as are queue methods frontEnqueue, frontDequeue, endEnqueue and endDequeue. All are written using linkedList.
Why can they be the same? Because the stack and queue class methods are implemented using linkedList class methods. The operations Push and Enqueue are inserts, while Pop and Dequeue are value extractions followed by deletes. They will, however, be implemented differently depending on whether the insert and delete are occurring at the beginning or at the end of linkedList. In the first case, frontPush is Insert( ) and frontPop is firstValue( ) and Chop( ); in the second case, endPush is Append( ) and endPop is lastValue( ) and Delete( ). Similarly, frontEnqueue is Insert( ), endDequeue is lastValue( ) and Delete( ), endEnqueue is Append( ), and frontDequeue is firstValue( ) and Chop( ). We are implementing all these forms of Push, Pop, Enqueue, and Dequeue in order to compare their behavior in a later assignment.
Required files:
1. Main program
a. prog3.h header file
b. [login to view URL] source code
2. Files for LLArray:
a. llarray.h for class definition
b. [login to view URL] file for methods
3. Files for LLNodePtr
a. llnodeptr.h for class definition
b. [login to view URL] file for methods
4. Files for Stack and Queue
a. SandQ.h for class definitions
b. [login to view URL] for methods
5. Makefile compiles
a. SandQ or [login to view URL] from
prog3.h, [login to view URL], SandQ.h, [login to view URL], llarray.h, [login to view URL] , llnodeptr.h, [login to view URL]
________________________________________
Submit through TRACS as attachments to the assignment portal: Source (.cpp) files, input (.dat) file, executable file (SandQ or [login to view URL]), and makefile (makefile).
Note: This program must compile and execute in [login to view URL] Regards,