C++ 带有入度和路径权值的领接表的建立
//输入参数
//a b c d e q 空格
//ab5 ae4 ac3 bc2 cd8 ce6 de10 q 空格
#include <cstddef>
#include <iostream>
#include <sstream>
#include <string>
#include <array>
#include <memory>
#include <map>
using namespace std;
union VexItem
{
char value_;
int index_;
};
class Vex
{
public:
Vex(Vex&&) = default;
Vex& operator =(Vex&&) = default;
Vex() = default;
explicit Vex(char ch, int cost = 0)
: cost_(cost)
, rudu_(0)
, next_(nullptr)
{
vex_item_.value_ = ch;
//cout << "init vex_item_.value_: " << vex_item_.value_ << endl;
}
explicit Vex(int index, int cost = 0)
: cost_(cost)
, rudu_(0)
, next_(nullptr)
{
vex_item_.index_ = index;
//cout << "init vex_item_.index_: " << vex_item_.index_ << endl;
}
VexItem vex_item_;
int cost_;
int rudu_;
shared_ptr<Vex> next_;
};
int main() {
constexpr int input_len{2 + 10};
constexpr auto vex_len{100};
int vex_count{0};
array<Vex, vex_len> vex;
map<char, int> vex_index;
auto string2num = [](const char* str)
{
int cost{0};
stringstream ss;
ss << str;
ss >> cost;
return cost;
};
for(int i = 0 ;; ++i)
{
array<char, input_len> input;
cout << "input vex point" << endl;
cin.getline(input.data(), input_len, ' ');
//cout << "you input vex point:" << input.data() << endl;
if(input[0] == 'q')
break;
vex[i] = Vex(input[0]);
vex_index[input[0]] = i;
vex_count++;
//cout << input[0] << " map to " << i << endl;
}
cin.ignore(std::numeric_limits< streamsize >::max(), '\n');
do
{
array<char, input_len> input;
cout << "input vex pair and cost" << endl;
cin.getline(input.data(), input_len, ' ');
//cout << "you input vex pair and cost:" << input.data() << endl;
if(input[0] == 'q')
break;
cout << input[0] << "}}" << input[1] << endl;
auto from_index = vex_index[input[0]];
auto to_idnex = vex_index[input[1]];
auto tmp = make_shared<Vex>(to_idnex, string2num(input.data() + 2));
tmp->next_ = vex[from_index].next_;
vex[from_index].next_ = tmp;
vex[to_idnex].rudu_++;
}while(true);
//a b c d e q
//ab5 ae4 ac3 bc2 cd8 ce6 de10 q
for(int i = 0; i < vex_count; i++)
{
auto& item = vex[i];
if(item.vex_item_.value_ == '\0' && item.vex_item_.index_ == 0)
break;
auto ptr = item.next_;
cout << "vex :" << item.vex_item_.value_ << ", rudu:" << item.rudu_ << endl;
if(ptr == nullptr)
{
cout << "end vex:" << item.vex_item_.value_ << endl;
}
for(; ptr != nullptr; ptr = ptr->next_)
{
cout << item.vex_item_.value_ << "-" << ptr->cost_ << "->" << vex[ptr->vex_item_.index_].vex_item_.value_ << " ";
}
cout << endl;
}
return 1;
}
