столкнулся с тем, что у меня программа работает неправильно если я "просто" запускаю её на выполнение. Но если поставить в IDE брейкпоинты, то она работает нормально. Реализую список с пропусками и для теста просто заполняю его числами от 1 до 10. Если запускаю "просто", то получается это:
lvl 0 :1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10
lvl 1 :1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10
lvl 2 :1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10
lvl 3 :1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10
Или это:
lvl 0 :1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10
lvl 1 :1
lvl 2 :1
lvl 3 :1
Если с брейкпоинтами, то примерно вот это:
lvl 0 :1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10
lvl 1 :1 -> 2 -> 4 -> 6 -> 9
lvl 2 :1 -> 6 -> 9
lvl 3 :1
Я пользуюсь CLion.
Код:
main:
#include <iostream>
#include "SkipList.h"
int main()
{
SkipList list{4, 1/4.0};
for (int i = 0; i < 10; i++)
{
list.push(i + 1);
list.out();
}
//list.out();
}
SkipList.h:
//
// Created by nail1 on 09.08.2018.
//
#ifndef INC_18_11_SKIPLIST_H
#define INC_18_11_SKIPLIST_H
struct intList
{
int value;
intList* next {nullptr};
};
class SkipList
{
intList** lvls;
int numb_lvls;
double p;
void pushInLvl(int numb, int val);
void findPlace(intList **prev, intList **next, int numb, int val);
public:
SkipList(int numb, double pp) : numb_lvls{numb}, p{pp} {lvls = new intList*[numb]{nullptr};}
void push(int val);
void out();
};
#endif //INC_18_11_SKIPLIST_H
SkipList.cpp:
//
// Created by nail1 on 09.08.2018.
//
#include "SkipList.h"
#include <cstdlib>
#include <ctime>
#include <iostream>
void SkipList::push(int val)
{
for (int i = 0; i < numb_lvls; i++)
{
srand(time(NULL));
double rand_numb = ( rand() % 101 ) / 100.0;
if (i == 0 || !lvls[i] || rand_numb < p)
pushInLvl(i, val);
else
return;
}
}
void SkipList::pushInLvl(int numb, int val)
{
intList* prev{nullptr};
intList* next{nullptr};
findPlace(&prev, &next, numb, val);
intList* newMemb = new intList{val, nullptr};
if (!prev && !next)
{
lvls[numb] = newMemb;
return;
}
else if (!prev)
{
newMemb->next = next;
lvls[numb] = newMemb;
return;
}
else if (!next)
{
prev->next = newMemb;
return;
}
else if (prev && next)
{
newMemb->next = next;
prev->next = newMemb;
return;
}
}
void SkipList::findPlace(intList **prev, intList **next, int numb, int val)
{
*prev = nullptr;
*next = nullptr;
intList* curLvl{lvls[numb]};
if (!curLvl)
return;
else if(val < curLvl->value)
{
*next = curLvl;
return;
} else
{
*prev = curLvl;
*next = curLvl->next;
while (*next && (*next)->value < val)
{
*prev = *next;
*next = (*next)->next;
}
}
}
void SkipList::out() {
for (int i = 0; i < numb_lvls; i++)
{
std::cout << "lvl " << i << " :";
intList* curLvl = lvls[i];
while(curLvl)
{
std::cout << curLvl->value;
if (curLvl->next)
std::cout << " -> ";
curLvl = curLvl->next;
}
std::cout << std::endl;
}
}
У вас srand(time(NULL));
вызывается при каждом push
, соответственно с большой долей вероятности запуская ту же последовательность случайных чисел, что и на предыдущем шаге. А брейкпоинты разбивают эти последовательные вызовы.
srand
имеет смысл вызвать один раз на поток. Ну или использовать более продвинутые генераторы случайных чисел.
В SkipList.h конструкторе вызываете
lvls = new intList*[numb]{nullptr};
Это не то, что вы думаете. Эту запись вообще нельзя делать. (В стандарте нет.) Инициализируется только lvls[0] := nullptr;
Все остальные значения по-умолчанию забиваются нулём. Уберите {nullptr}
. Делайте просто пустую инициализацию.
lvls = new intList*[numb]{};
Кофе для программистов: как напиток влияет на продуктивность кодеров?
Рекламные вывески: как привлечь внимание и увеличить продажи
Стратегії та тренди в SMM - Технології, що формують майбутнє сьогодні
Выделенный сервер, что это, для чего нужен и какие характеристики важны?
Современные решения для бизнеса: как облачные и виртуальные технологии меняют рынок
Использую битовые операции для опций в GUI, возникла необходимость проверить установлен ли хоть 1 битПравильно ли я понимаю что если число...
Допустим, будет ли выигрыш по времени выполнения/памяти во втором случае или нет?