CSE 240 – Assignment 5
Topics:
- C/C++ Syntax
- Pointers
- Functions
- Dynamic Allocation of Memory
- Data Structures: Linked Lists
- Object Orientation
Overall Specifications:
You are to create a Linked List or Binary Search Tree data structure from scratch. This structure should be Templated so that any data could be stored within it.
The primary goal of this assignment is to make a Linked List that you can use and re-use. The Linked List itself is the majority of the specifications grade.
Specifications Scoring Breakdown:
Templated Linked List/BST + Problem – 100% of specificationsTemplated Linked List/BST only – 80% of specifications
Untemplated Linked List/BST + Problem – 80% of specifications
Untemplated Linked List/BST only – 70% of specifications
** BIG GIANT NOTE – TEMPLATES AND FILES **
When you use a templated type in C++ ALL templated code must be done in the .h file. This means that ALL of your methods will be defined in the .h file as well as your class.You should still forward declare Classes above then Methods below.
Your .h file should have your LinkedList/BST class and your Node class and the method definitions for both. Remember to use your :: operator correctly.
Feel free to use friendship if needed.
Option 1
“I like trains” - Linked Lists
You will create a Linked List Class and a Node Class/StructThe Linked List should contain the following methods in its public interface:
NOTE: T stands for the template data type, so T data means the variable of type T (whatever T is)
More methods private or public should be created as needed to facilitate the functionality of the Interface methods. If you feel your list needs more functionality, feel free to create it.
As per usual, I have not made a perfect representation of the parameters you might need, etc. I have made suggestions where appropriate, but you might need more depending on how you code things.
Node Class
- Constructor
- Destructor
- Getters & Setters (if class)
Note: Node can be a struct if you so choose.
Description:
The goal of this problem is to simulate a train delivering cargo and people. This is a very rudimentary demonstration of the idea and does not necessarily reflect real world policies regarding trains.For this section you will use many (but probably not all) of the functionality of your linked list.
You will create a Struct or Class called TrainCar. This TrainCar will have three major pieces of information: int id, char (or enum) typeOfCar and int numberOfStops.
Use a static variable to make sure each car gets a unique ID number. char typeOfCar:
Each type of car will use their own insertion algorithm: addToFront, addAtIndex, and addToEnd respectively.
The trains should start with 10 random cars with random numberOfStops values (say 1 to 5).
At every stop you will reduce the numberOfStops by 1. Each car will have a random number (between say 1 and 5) of stops before it is removed from the train.
At each stop you will add between 1 and 5 new RANDOM cars and add them to the train where they should go.
You then send the train on its merry way.
You must show the results of every stop. You should output the cars being removed, the cars being added and the resulting train. You should give the user an interface to determine how many stops they want the train to run for. When the train runs for that many, prompt the user to either run more stops, or to end the program.
Sample output:
Stop #2:
Train Arriving: [5:P:1][6:P:4][3:P:2][2:C:3][4:C:1][1:M:1][7:M:3]
Removing cars:
[5:P] removed
[4:C] removed
[1:M] removed
Adding cars:
[8:P:3] added
[9:M:2] added
Train Exiting: [8:P:3][6:P:3][3:P:1][2:C:2][7:M:3][9:M:2]
Option 2:
Word Frequency Analysis – Binary Search Tree
You will create a Binary Search Tree Class and a Node Class/Struct
The Binary Search Tree should contain the following methods in its public interface:
More methods private or public should be created as needed to facilitate the functionality of the Interface methods. If you feel your tree needs more functionality, feel free to create it.
Note: I’m leaving some of these vague so that you can customize your tree a bit. For example, insert often returns a pointer to the node that was created when you add the element to the tree – or if it was a duplicate, it returns a pointer to the node where the element was found. Sometimes insert just returns a Boolean stating that the operation was successful or not. Etc.
Description
The goal will be to parse a large text file and determine the word frequency of every word in the text file.
You will use file input to read in, analyze and output statistics about the file. You should provide an adequate user interface to accomplish the following tasks:
You will use a Binary Search Tree to accomplish these goals (and any other algorithms or data structures needed to accomplish those goals - i.e.: if you need a stack for certain algorithms, you may use it ... if you need a linked list, you may use it ... but remember the star of the show is the BST)
Your word counts should ignore capitalization, so the, The, THE, and tHe all increase the count for the word “the” by one. For purposes of this assignment, a word is any consecutive string of letters and the apostrophe character, so don’t counts as a single word, and best-selling counts as two words: best and selling. Notice that a blank space will not necessarily occur between two words. Numbers such as 27 and 2/3 will NOT be counted as words.
Grading of Programming Assignment
The TA will grade your program following these steps:- Compile the code. If it does not compile, If it does not compile you will receive a U on the Specifications in the Rubric.
- The TA will read your program and give points based on the points allocated to each component, the readability of your code (organization of the code and comments), logic, inclusion of the required functions, and correctness of the implementations of each function.
Rubric:
What to Submit?
You are required to submit your solutions in a compressed format (.zip). Zip all files into a single zip file. Make sure your compressed file is labeled correctly - lastname_firstname7.zip.
For this home assignment, the compressed file MUST contain the following:
No other files should be in the compressed folder.
If multiple submissions are made, the most recent submission will be graded, even if the assignment is submitted late.
Where to Submit?
All submissions must be electronically submitted to the respected homework link in the course web page where you downloaded the assignment.
You are encouraged to cooperate in study group on learning the course materials. However, you may not cooperate on preparing the individual assignments. Anything that you turn in must be your own work: You must write up your own solution with your own understanding. If you use an idea that is found in a book or from other sources, or that was developed by someone else or jointly with some group, make sure you acknowledge the source and/or the names of the persons in the write-up for each problem. When you help your peers, you should never show your work to them. All assignment questions must be asked in the course discussion board. Asking assignment questions or making your assignment available in the public websites before the assignment due will be considered cheating.
The instructor and the TA will CAREFULLY check any possible proliferation or plagiarism. We will use the document/program comparison tools like MOSS (Measure Of Software Similarity: http://moss.stanford.edu/) to check any assignment that you submitted for grading. The Ira A. Fulton Schools of Engineering expect all students to adhere to ASU's policy on Academic Dishonesty. These policies can be found in the Code of Student Conduct:
2019-04-02