C ++ Как сгенерировать 10000 уникальных случайных целых чисел для хранения в BST?

В вашем коде есть пара проблем. Но давайте прямо к больно.

В чем главная проблема?

Из вашего кода очевидно, что tree1Ptr является указателем. В принципе, он должен указывать на узел дерева, который имеет два указателя, один на левый узел и один на правый узел.

Итак, где-то в вашем коде вы должны иметь:

tree1Ptr = new Node;   // or whatever the type of your node is called

Однако, во внутреннем цикле вы просто используете его, как если бы это был массив:

for (int i = 0; i < 10000; i++) 
{
    int random = rand() % 20000;
    tree1Ptr->add(random);
    for (int j = 0; j < i; j++) {
        if (tree1Ptr[j]==random)  //<============ OUCH !!
            i--;
    }
}

Компилятор не будет жаловаться, потому что это правильный синтаксис: вы можете использовать индексирование массива по указателю. Но вам нужно убедиться, что вы не выходите за пределы (так что здесь, j остается < 1).

Другие замечания

Кстати, во внутреннем цикле вы просто хотите сказать, что вы должны повторить попытку, если число найдено. Вы можете break выполнить внутренний цикл, если номер уже найден, чтобы не продолжать.

Вы также должны заполнить свой генератор случайных чисел, чтобы избежать запуска программы всегда с одинаковой последовательностью.

Как ее решить?

Вам действительно нужно углубить свое понимание BST. Навигация по узлу требует сравнения со значением в текущем узле и, в зависимости от результата, повторяется, продолжая либо с указателем влево или вправо, не используя индексацию. Но это было бы слишком долго, чтобы объяснить здесь. Так что, может быть, вы должны искать учебник, как этот

Для множества уникальных «случайных» чисел я обычно использую Формат сохраняющего шифрование . Поскольку шифрование является взаимно-однозначным, вам гарантированы уникальные выходные данные, если они являются уникальными. Другой ключ шифрования будет генерировать другой набор выходных данных, то есть другую перестановку входных данных. Просто зашифруйте 0, 1, 2, 3, 4, ... и выходные данные гарантированно уникальны.

Вы хотите цифры в диапазоне [1 .. 20 000]. К сожалению, для 20000 требуется 21 бит, и большинство схем шифрования имеют четное количество бит: в вашем случае 22 бита. Это означает, что вам нужно будет ездить на велосипеде; повторно зашифруйте вывод, если число слишком велико, пока не получите число в нужном диапазоне. Поскольку ваши входные данные доходят только до 10 000, а количество циклов выше 20 000, вы все равно избегаете дублирования.

Единственный известный мне стандартный шифр, который допускает 22-битный размер блока, - это шифр Hasty Pudding. В качестве альтернативы достаточно просто написать свой собственный простой шифр Фейстеля . Четыре раунда достаточно, если вы не хотите криптографическую безопасность. Для защиты на криптографическом уровне вам необходимо использовать AES / FFX, который одобрен NIST.

Есть два способа, с помощью которых вы можете выбрать случайные уникальные числа из последовательности , не проверяя по ранее выбранным номерам (т. Е. Уже в вашем BST).

Использовать random_shuffle

Простой способ - перетасовать отсортированный массив из 1 ... 20 000 и просто выбрать первые 10000 элементов:

#include <algorithm>
#include <vector>

std::vector<int> values(20000);
for (int i = 0; i < 20000; ++i) {
  values[i] = i+1;
}
std::random_shuffle(values.begin(), values.end());

for (int i = 0; i < 10000; ++i) {
  // Insert values[i] into your BST
}

Этот метод хорошо работает, если размер случайных чисел (10000) для выбора сравнимо с размером общих чисел (20000), потому что сложность случайного перетасовки амортизируется по большему набору результатов.

Использоватьiform_int_distribution

Если размер случайных чисел для выбора намного меньше, чем размер общих чисел, то можно использовать альтернативный способ:

#include <chrono>
#include <random>
#include <vector>

// Use timed seed so every run produces different random picks.
std::default_random_engine reng(
    std::chrono::steady_clock::now().time_since_epoch().count());

int num_pick  = 1000;   // # of random numbers remained to pick
int num_total = 20000;  // Total # of numbers to pick from

int cur_value = 1;  // Current prospective number to be picked
while (num_pick > 0) {
  // Probability to pick `cur_value` is num_pick / (num_total-cur_value+1)
  std::uniform_int_distribution<int> distrib(0, num_total-cur_value);

  if (distrib(reng) < num_pick) {
    bst.insert(cur_value);  // insert `cur_value` to your BST
    --num_pick;
  }
  ++cur_value;
}