c++ - 如何修复我的 topological.cpp 输出错误?
问题描述
我被提供了 middleearth.h/cpp,并被要求制作一个 makefile、doxyfile(我做对了)和一个可以工作但在输出中有一个小错误的 topological.cpp,我需要帮助。请提供所有三个文件和我们用来测试的文本和错误。
cs2110 cs2150
cs2102 cs2150
cs1110 cs2110
cs3330 cs4414
cs2150 cs4414
cs2110 cs3330
cs1110 cs2102
0 0
中土.h
#ifndef MIDDLEEARTH_H
#define MIDDLEEARTH_H
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <random>
using namespace std;
// see the comments in the lab11 write-up, or in middleearth.cpp
class MiddleEarth {
public:
MiddleEarth(int xsize, int ysize, int num_cities, int seed);
void print();
void printTable();
float getDistance(const string& city1, const string& city2);
vector<string> getItinerary(unsigned int length);
private:
int num_city_names, xsize, ysize;
unordered_map<string, float> xpos, ypos;
vector<string> cities;
unordered_map<string, unordered_map<string, float>> distances;
mt19937 gen; // Mersenne-Twister random number engine
};
#endif
中土世界.cpp
#include "middleearth.h"
#include <algorithm>
#include <array>
#include <cstdlib>
#include <cmath>
// New shuffle method that uses the Mersenne Twister engine
void shuffle (vector<string>::iterator first, vector<string>::iterator last, mt19937& g) {
for (auto i=(last-first)-1; i>0; --i) {
unsigned int n = (g() / (double) g.max())*distance(first,last);
swap (first[i], first[n]);
}
}
// The list of all the place names that we'll be using
const array<string, 40> all_city_names{
// human towns, cities and strongholds
"Bree", // a human and hobbit town between the Shire and Rivendell
"Isengard", // the tower fortress where Saruman resided; Gandalf was imprisoned there.
"Minas Tirith", // capital of Gondor, the "white city"; home to Boromir, Denethor, and later, Aragorn
"Osgiliath", // city on the river Anduin; is at the other end of Pelennor Fields from M. Tirith
"Edoras", // the capital city of Rohan, where King Theoden resides
"Helm's Deep", // fortress of Rohan, it is where the people of Edoras fled to from the orc invasion
"Dunharrow", // a refuge of Rohan, it is where Elrond presents the sword to Aragorn in the movie
// dwarf cities
"Moria", // the enormous dwarven underground complex that the Fellowship traveled through
// elvish cities
"Lothlorien", // the elvish tree-city, home of Lady Galadriel and Lord Celeborn
"Rivendell", // the elvish city that is home to Lord Elrond
"The Grey Havens", // the port city on the western coast from which the elves travel westward
// hobbit villages
"Bucklebury", // a Shire village, it has a ferry across the Brandywine River that the Hobbits use
"Bywater", // a Shire village, it is the site of the Battle of Bywater (removed from the movie)
"Hobbiton", // a Shire village, it is home to Bilbo and, later, Frodo
"Michel Delving", // a Shire village, it is the chief town of the Shire
// Mordor places
"Orodruin", // Mount Doom in Mordor, it is where the Ring was made, and later, unmade
"Barad-Dur", // Sauron's fortress that was part castle, part mountain
"Minas Morgul", // formerly the Gondorian city of Minas Ithil; renamed when Sauron took it over
"Cirith Ungol", // the mountianous pass that Sam & Frodo went through; home of Shelob
"Gorgoroth", // the plains in Mordor that Frodo & Sam had to cross to reach Mount Doom
// places that are not cities
"Emyn Muil", // the rocky region that Sam & Frodo climb through after leaving the Fellowship
"Fangorn Forest", // the forest where Treebeard (and the other Ents) live
"Dagorlad", // great plain/swamp between Emyn Muil & Mordor where a great battle was fought long ago
"Weathertop", // the tower between Bree and Rivendell where Aragorn and the Hobbits take refuge
"Gladden Fields", // this is where the Ring is lost in the River Anduin, after Isildur is ambushed and killed by Orcs
"Entwash River", // a river through Rohan, which flows through Fangorn Forest
"River Isen", // river through the Gap of Rohan; Theoden's son was slain in a battle here.
"The Black Gate", // huge gate to Mordor that Aragorn and company attack as the ring is destroyed
"The Old Forest", // a forest to the west of the Shire (adventures there were removed from the movie)
"Trollshaws", // area to the west of Rivendell that was home to the trolls that Bilbo met
"Pelennor Fields", // great plain between M. Tirith and Osgiliath; site of the Battle of M. Tirith
"Hollin", // the empty plains that the Fellowship crosses between Rivendell and Moria
"Mirkwood", // Legolas' forest home; Bilbo travels there in 'The Hobbit'.
"Misty Mountains", // the north-south moutain range that runs through Middle-earth
"Prancing Pony", // an inn in Bree where the hobbits tried to meet Gandalf, but meet Aragorn instead
// places from the Hobbit book and movies
"Laketown", // also called Esgaorth, it is the town of men on the Long Lake near Erebor
"Dale", // the town of men outside Erebor, destroyed by Smaug long before the Hobbit story
"Erebor", // the Elvish name for the Lonely Mountain, where the dwarves had their fortress
"Beorn's House", // Beorn is the shape-shifter who shelters the dwarf party
"Dol Guldur", // fortress in Mirkwood where Sauron, as the Necromancer, hid during most of the Hobbit
};
// Iluvatar, the creator of Middle-Earth
MiddleEarth::MiddleEarth(int xsize, int ysize, int num_cities, int seed) {
this->xsize = xsize;
this->ysize = ysize;
// set up the random number generator
gen.seed(seed == -1 ? random_device{}() : seed);
// count the number of cities in the array
this->num_city_names = all_city_names.size();
if (num_cities > num_city_names) {
cout << "There are only " << num_city_names << " city names, so "
<< num_cities << " cities cannot be created." << endl;
cout << "Exiting." << endl;
exit(0);
}
if (num_cities < 5) {
num_cities = 5;
}
// copy all the cities into a mutable vector
this->cities = vector<string>(all_city_names.begin(), all_city_names.end());
shuffle(cities.begin(), cities.end(), gen); // shuffle all the cities
cities.erase(cities.begin() + num_cities, cities.end()); // then remove the ones we won't be using
// compute random city positions
for (auto city : cities) {
xpos.emplace(city, (gen() / (double) gen.max()) * xsize);
ypos.emplace(city, (gen() / (double) gen.max()) * ysize);
}
// compute the 2-d distance array
// we assume that num_cities < xsize * ysize
for (auto city1 : cities) {
for (auto city2 : cities) {
distances[city1].emplace(city2, sqrt((xpos[city2] - xpos[city1]) * (xpos[city2] - xpos[city1]) +
(ypos[city2] - ypos[city1]) * (ypos[city2] - ypos[city1])));
}
}
}
// The Mouth of Sauron!
// Prints out info on the created 'world'
void MiddleEarth::print() {
cout << "there are " << num_city_names
<< " locations to choose from; we are using " << cities.size() << endl;
cout << "they are: " << endl;
for (auto city : cities) {
cout << "\t" << city << " @ (" << xpos[city] << ", " << ypos[city]
<< ")" << endl;
}
}
// Prints a tab-separated table of the distances,
// which can be loaded into Excel or similar
void MiddleEarth::printTable() {
cout << "Table: " << endl << endl << "Location\txpos\typos\t";
for (auto city : cities) {
cout << city << "\t";
}
cout << endl;
for (auto city1 : cities) {
cout << city1 << "\t" << xpos[city1] << "\t" << ypos[city1] << "\t";
for (auto city2 : cities) {
cout << distances[city1][city2] << "\t";
}
cout << endl;
}
}
// This method returns the distance between the two passed cities.
// If we assume that the hash table (i.e. the map) is O(1),
// then this method call is also O(1)
float MiddleEarth::getDistance(const string& city1, const string& city2) {
return distances[city1][city2];
}
// Returns the list of cities to travel to.
// The first city is the original start point as well as the end point.
// The number of cities passed in does not include this start/end point
// (so there will be length+1 entries in the returned vector).
vector<string> MiddleEarth::getItinerary(unsigned int length) {
// check parameter
if (length >= cities.size()) {
cout << "You have requested an itinerary of " << length
<< " cities; you cannot ask for an itinerary of more than length "
<< cities.size() - 1 << endl;
exit(0);
}
length++; // to account for the start point
// we need to make a deep copy of the cities vector
vector<string> itinerary(cities.begin(), cities.end());
// shuffle, erase unneeded ones, and return the itinerary
shuffle(itinerary.begin(), itinerary.end(), gen);
itinerary.erase(itinerary.begin() + length, itinerary.end());
return itinerary;
}
拓扑.cpp
#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <list>
#include <stack>
#include <string>
#include <map>
using namespace std;
/**
@date 11/16/2020
*/
/** @brief
*/
class Graph
{
public:
Graph(int vert);
/** @brief adds an edge to the list
* @param string v
* @param string w
* @param map<string, int> m
*
*/
void addEdge(string v, string w, map<string, int> m);
void printSort();
private:
int vertices;
list<int> *myList;
void sort(int v, stack<int> &myStack, bool visited[]);
map<int, string> myMap;
};
Graph::Graph(int vert) {
vertices = vert;
myList = new list<int>[vertices];
}
void Graph::addEdge(string v, string w, map<string, int> m) {
int loc1 = m[v];
int loc2 = m[w];
myMap[loc1] = v;
myMap[loc2] = w;
myList[loc1].push_back(loc2);
}
void Graph::sort(int v, stack<int> &myStack, bool visited[]) {
visited[v] = true;
list<int>::iterator i;
for(i = myList[v].begin(); i != myList[v].end(); ++i) {
if(!visited[*i]) {
sort(*i, myStack, visited);
}
}
myStack.push(v);
}
void Graph::printSort() {
stack<int> myStack;
bool *visited = new bool[vertices];
for(int i = 0; i < vertices; i++) {
visited[i] = false;
}
for(int i = 0; i < vertices; i++) {
if(visited[i] == false)
sort(i, myStack, visited);
}
while(myStack.empty() == false) {
int x = myStack.top();
string output = myMap[x];
cout << output << " ";
myStack.pop();
}
}
int main (int argc, char **argv) {
if ( argc != 2 ) {
cout << "Must supply the input file name as the one and only parameter" << endl;
return 1;
}
ifstream file(argv[1], ifstream::binary);
ifstream file1(argv[1], ifstream::binary);
if ( !file.is_open() ) {
cout << "Unable to open file '" << argv[1] << "'." << endl;
return 1;
}
string s1, s2;
int count = 0;
list <string> edges;
while(!file.eof()) {
file >> s1;
file >> s2;
if(s1 == "0" && s2 == "0") {
break;
}
edges.push_back(s1);
edges.push_back(s2);
}
file.close();
edges.sort();
edges.unique();
int size = edges.size();
map<string, int> myMap;
Graph myGraph(size);
list<string>::iterator i;
for(i = edges.begin(); i != edges.end(); i++) {
string s = *i;
myMap[s] = count;
count++;
}
while(!file1.eof()) {
file1 >> s1;
file1 >> s2;
if(s1 == "0" && s2 == "0") {
break;
}
myGraph.addEdge(s1, s2, myMap);
}
myGraph.printSort();
cout<<endl;
file1.close();
return 0;
}
解决方案
推荐阅读
- java - recyclerview 单击转到新页面 android 页面 info.xml 并发送产品标题
- reactjs - 文档对象焦点事件在 React 中无法正常工作
- rxjs - 如何在 RxJs 5.5.6 中使用管道运算符
- asp.net-mvc - 如何在 *.cshtml 中使用 es6 类
- python - 如何仅用字典或文本文件中存在的单词替换熊猫数据框的列?
- scala - scala "console" 命令给出错误 "Missing scala-library.jar"
- javascript - 如何使用 Redux 将徽章值传递给 React Native 上的 BottomTabBar
- android-source - AOSP多窗口和多显示的区别
- python - PYODBC 将数据插入日期时间列会产生格式不正确的表
- python - 如何在多个条件下在数据框中的新列中填充值