Exam2下来就是Optional Exercise6，这是一个以树和StL map组合的数据结构，并要求递归来求解问题
具体看题目吧
它先是给了数据描述
对definitions.txt的叙述
hospital 10 floor
floor 4 wing
wing 2 long_corridor
wing 1 connecting_corridor
long_corridor 21 patient_room
connecting_corridor 5 supply_room
patient_room 2 bed
patient_room 4 outlet
patient_room 1 bathroom
outlet 1 face_plate
outlet 2 socket
bathroom 1 sink
sink 2 small_rubber_washer
sink 1 large_rubber_washer
floor 1 central_lobby
central_lobby 2 couch
central_lobby 1 television
In this assessment, you will construct a representation of a complex structure, a hospital that is composed of many parts. There are too many parts for a human to keep track of, which is why we want the computer to do it for us. The description of the hospital is contained in the file definitions.txt.
Figure 1 Layout of a floor in the hospital
The building has ten floors. Each floor has four wings emanating from a central core.
Each wing contains two long corridors joined at the end by a short connecting corridor.
Each long corridor contains twenty-one patient rooms. Each connecting corridor contains five supply rooms.
The hospital is described by a labeled tree, whose nodes are of type Part. A node contains children nodes corresponding to its subparts, as shown in the figure below. Each edge is labeled by the number of subparts the node contains. For example, the label 10 on the edge from hospital to floor indicates that the hospital has ten floors. You can assume there are no duplicate edges, that is, there is at most one edge between any two nodes.
即如下图所示
然后给了这函数的调用过程
The driver program main.cpp first loads the file definitions.txt, which contains the subpart relationships that define the hospital. It then processes queries from the file queries.txt, which contains two kinds of queries about the hospital. The whatis query requests the description of a Part. The howmany query is the heart of the exercise. It asks how many instances of a Part are contained in another Part.
要求我们完成
You are provided with main.cpp and a skeleton version of parts.h as a starting point. Your job is to complete the parts.h file (and write parts.cpp, if you deem necessary). The steps below point the way toward a solution, but they do not cover every detail, so if you find you need to create additional functions or member items, feel free to do so.
题目要求就完了
下来就是做吧，从main.cpp看起
// main.cpp -- driver program for "Sum of Its Parts" #include <iostream> #include <fstream> #include <cstdlib> using namespace std; #include "parts.h" void load_definitions(char* filename) { //文件读取 ifstream inf(filename); string part, subpart; int quantity; while ( inf.good() ) { inf >> part >> quantity >> subpart; if ( !inf.good() ) return ; //加入到容器中去 add_part(part, quantity, subpart); }; } void whatis_query(string const &x) { //是什么，然后再查找，找不到就创建 Part* xp = partContainer.lookup(x); cout << endl; //输出描述 xp->describe(); } void howmany_query(string const &x, string const &y) { //y是x的上级,调用函数计算y有多少个x Part* xp = partContainer.lookup(x); Part* yp = partContainer.lookup(y); cout << endl << y << " has " << yp->count_howmany(xp) << " " << x << endl; } void process_queries(char* filename) { ifstream inf(filename); string query, x, y; while ( inf.good() ) { inf >> query >> x; //如果是"howmany"就还得读入一个字符串 if ( query == "howmany" ) inf >> y; //不能则退出 if ( !inf.good() ) return ; if ( query == "howmany" ) //查找x,y howmany_query(x, y); else if ( query == "whatis" ) //查找x whatis_query(x); else { cerr << "*** Illegal query: " << query << endl; return ; }; }; } int main(void) { //只有两个函数而已 load_definitions("definitions.txt"); process_queries("queries.txt"); return EXIT_SUCCESS; }
下面是parts.h,我己经写好了，看注释把
// parts.h #ifndef _PARTS_H_ #define _PARTS_H_ #include <vector> #include <map> #include <string> using namespace std; //**************** Part **************** class Part { public: string name; //一步步来，我们按照他给的帮助来写 /*Begin by adding to class Part an additional member named subparts that is a container of type map. Your container should map a pointer (of type Part) to an integer. So, for example, the Part named hospital will have among its subparts an entry mapping a pointer to the Part named floor to the int 10, since a hospital contains 10 floors. */ map <Part*,int> subparts; Part(string const &n) : name(n) {}; void describe(void); int count_howmany(Part const *p); }; //**************** NameContainer **************** class NameContainer { private: map<string, Part*> name_map; public: NameContainer(void) {}; Part* lookup(string const &name) { //第四个要求 /* Next, complete the implementation of method lookup of class NameContainer, which maps a string to a pointer to an instance of type Part. Method lookup should automatically create an instance of class Part with the given name if one does not already exist in the map. The method should return a pointer to the instance. */ //通过查找name来找到part，如果没有则创建 if (name_map.count(name) == 0) { //通过构造函数创建对象 Part* newpart = new Part(name); name_map[name] = newpart; } return name_map[name]; } }; NameContainer partContainer; //**************** Part Member Functions **************** void Part::describe(void) { //第二个要求，要求我们使用迭代器遍历Part /*Next, implement the describe method of class Part. It should list the part name and all of the subparts and their quantities. Use iterators to process the subparts. */ cout << "Part " << name << " There are subparts:" << endl; if (subparts.empty()) { cout << "No subparts." << endl; } else { //迭代器类型和subparts类型一致 map<Part*, int>::iterator it; for (it = subparts.begin(); it != subparts.end(); it++) { //输出map的第二个的值，及第一个的name属性 cout << it->second << " " << it->first->name << endl; } } } int Part::count_howmany(Part const *p) { //第三个要求 /* Then, implement the recursive method count_howmany(Part const *p) of class Part that counts the number of instances of the part pointed to by p that occur in the invoking object. Counting proceeds by simple recursion on the subparts. For example, asking hospital how many wing subparts it contains, we see a hospital has 10 floors. Recursively asking floor how many wing subparts it contains, we see that a floor has four wings. Calling the recursive function again, we ask wing how many times it occurs in wing. The function returns the value 1 since this is the base case. The final answer is then 40 (10 * 4 * 1). */ //递归终止条件 if (this == p) { return 1; } //递归 else { int total = 0; //使用迭代器递归累加 map<Part*, int>::iterator it; for (it = subparts.begin(); it != subparts.end(); it++) { //取得第一个的count_howmany(p)再乘以map第二个值累加 total += (it->first->count_howmany(p) * it->second); } return total; } } //**************** Miscellaneous Functions **************** void add_part(string const &x, int q, string const &y) { //最后一个要求 /* Finally, write the helper function add_part(string const &x, int quantity, string const &y) that adds the part named y as a new subpart of the Part named x. This function is called by load_definitions in main.cpp. To obtain pointers to the Part objects specified by the string parameters, use method lookup of object partContainer. */ //通过查找x参数创建part，查找y参数创建subparts，一个x有q个y Part* part = partContainer.lookup(x); Part* subpart = partContainer.lookup(y); part->subparts[subpart] = q; } #endif
附上queries.txt
whatis connecting_corridor
whatis patient_room
whatis small_rubber_washer
whatis bathroom
whatis floor
howmany floor hospital
howmany wing hospital
howmany patient_room hospital
howmany bed hospital
howmany couch floor
howmany couch hospital
howmany couch couch
howmany small_rubber_washer floor
提交parts.h即可