assignment 8: Ancestors
Algorithm | assignment代做 | c++ – 本题是一个利用Algorithm进行练习的代做, 对Algorithm的流程进行训练解析, 包括了Algorithm等方面, 该题目是值得借鉴的assignment代写的题目
assignment 8: Ancestors
Description
Familys ancestors can be a mystery. Even with the family tree it can be quite the job to map out everyones relative. To make this assignment simple, we only need to map out all the ancestors of each relative. Well just output ancestors only in the family tree. For this assignment, you can use any STL class. The input in this file will be plain text file with an edge detail per line, where each line contains
from -> to
this line denotes there is a directed edge from from to to. You can use std::getline and std::stringstream to parse each line. You would need to create an out-neighbor adjacency list. I would recommend declaring the following structure
std::unordered_map< std::string, std::list<std::string> > adjList;
This maps a persons name to a linked list of children (or its direct descendants). So if you want to add descendants to "Bob" you can write the following code
adjList["Bob"].push_back("Janice"); adjList["Bob"].push_back("Marty"); adjList["Bob"].push_back("Patrick");
//If you want to traverse the descendants //of "Bob", then you can have for (auto descendant = adjList["Bob"].begin(); descendant != adjList["Bob"].end(); descendant++)
{
std::cout << *descendant << "\n";
}
In this scenario, descendant would be a linked list iterator, its type would be std::list<std::string>::iterator. Once you have read in the file and created the adjacency list, you will need to write an Algorithm similar to DFS traversal, to be able to gather all the ancestors of each node in the graph (so you will need to run DFS multiple times). The start node(s) will be the node(s) that have no ancestors, and from those node(s) you traverse the graph until you find your target
relative and incrementally build your list of ancestors. You might need a visited array but since the vertices are labelled by names, you would have
std::unordered_map<std::string, bool> visited;
You may also need to declare more objects as well. This program would output a sorted list of all ancestors for each person (if a person has no ancestors then output "None" without the quotes). Also you need to output each person sorted as well, otherwise code grade would have issues. You can use std::sort function from the #include
std::vector <std::string > names; //a s s u m i n g y o u i n s e r t e d s e v e r a l s t r i n g s i n t o n a m e s
//the code below will sort the list std::sort(names.begin(), names.end());
Specifications
- Sample program is provided to you
- Output must match the two output files provided
- Must be done in C++