Блог

Главная - Вопросы по программированию - Векторы и карты в C

Векторы и карты в C

#c #stl

#c #stl

Вопрос:

У меня есть вектор A [9 3 6 9 3 6] , каждые 2 элемента которого представляют ребро графика, я хочу создать матрицу смежности из этого вектора.

Сначала я создал уникальный вектор A [3 6 9] , чтобы узнать размер моей матрицы

Во-вторых, я создаю матрицу и заполняю ее значением 0

В-третьих, я выполню цикл для A, чтобы узнать, какие ребра соединены, мой вопрос в том, как я могу сообщить C , что первый элемент в A, который равен трем, на самом деле представляет элемент 0 в моей матрице, то же самое для 6, что он представляет 1, а 9 представлен 3, например, когда я строю свою матрицу смежности, я знаю, что 0 1 2 на самом деле представляют 3 6 9, я слышал об использовании карты, но не знал, как ее построить в моей программе, потому что я новичок в C .

Ответ №1:

По сути, вы пытаетесь отслеживать метки для ваших вершин. Если каждой вершине последовательно присваивается номер, вы можете сканировать метки новых вершин и вставлять соответствующий порядковый номер в карту, например:

 std::map<int, std::size_t> labels;  // "int" is the label type; could be anything!

std::size_t store_vertex_label(int v)
{
  std::map<int, std::size_t>::const_iterator const it = labels.find(v);

  if (it != labels.end()) return it->second;

  const std::size_t new_number = labels.size();
  labels.insert(std::make_pair(v, new_number);
  return new_number;
}

Теперь, когда вы обрабатываете свои входные данные, вы читаете по одному маркеру метки v за раз, отправляете его в store_vertex_label() и получаете соответствующий последовательный индекс вершины обратно.

Ваша матрица смежности будет иметь размер labels.size() в квадрате.

Обратите внимание, что ваш тип метки не обязательно должен быть целым числом, это может быть что угодно (например, строка).

Комментарии:

1. Извините, это должно быть it->second — исправлено!

2. Да, потому что так и должно быть if (it != … Ладно, мне нужно немного поспать! Извините за это.

3. У меня есть последний вопрос, если я хочу сохранить карту, которую мы создали в этой функции, чтобы использовать ее позже, возможно ли это? или я должен создать другую функцию и поместить выходные данные в виде метки, а не в виде size_t?

4. @mona: Ну, да, вы бы сохранили labels карту в соответствующей области, где она вам нужна. Вы можете передать его в функцию store по ссылке, если хотите, или (вздох) даже сделать его глобальным, если у вас очень маленькая программа.

Ответ №2:

Несколько способов:

  1. Вы можете выполнить линейный поиск, чтобы найти индекс элемента в векторе
  2. Кажется, что ваш вектор отсортирован, также возможен двоичный поиск
  3. вы можете создать карту, а не вектор, если ваши элементы в vector не отсортированы. Заполните карту ключом в качестве «значений в вашем векторе» и значением в качестве индекса, в который вы вставляете.

Первое — наихудшее решение. Используйте 3rd в случае, если вектор не отсортирован. Используйте 2nd, если хотите уменьшить сложность пространства. 3-й также был бы хорош, если бы использовался большой размер и hashmap.