C++ 帶有入度和路徑權(quán)值的領(lǐng)接表的建立
//輸入?yún)?shù)?
//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;
}
