Здравствуйте, коллеги!
кажется, я в Седжвике еще одну ошибку нашел (брал код из родных его исходников — то же, что в книге). Он описываетя списки пропусков в 13 главе. Там есть функция удаления:
void removeR(link t, Key v, int k)
{
link x = t->next[k];
if(!(x->item.Key() < v)){
if(v == x->item.Key()){
t->next[k] = x->next[k];
}
if(k == 0){
delete x;
return;
}
removeR(t, v, k - 1);
return;
}
removeR(t->next[k], v, k);
}
Ошибку вызывает if(!(x->item.Key() < v)){. Как ее поправить?
Спасибо
05.12.05 18:39: Перенесено модератором из 'Алгоритмы' — Кодт
Здравствуйте, Аноним, Вы писали:
А>Здравствуйте, коллеги!
А>кажется, я в Седжвике еще одну ошибку нашел (брал код из родных его исходников — то же, что в книге). Он описываетя списки пропусков в 13 главе. Там есть функция удаления:
А>А>void removeR(link t, Key v, int k)
А>{
А> link x = t->next[k];
А> if(!(x->item.Key() < v)){
А> if(v == x->item.Key()){
t->>next[k] = x->next[k];
А> }
А> if(k == 0){
А> delete x;
А> return;
А> }
А> removeR(t, v, k - 1);
А> return;
А> }
А> removeR(t->next[k], v, k);
А>}
А>
А>Ошибку вызывает if(!(x->item.Key() < v)){. Как ее поправить?
А>Спасибо
Я сейчас открыл, посмотрел. Remove я исправил (по крайней мере, я не нашел за час случая, когда он вылетает), но у меня траблы с Insert: он иногда вылетает на строке if((tk == 0) || (v < tk->item.Key())){. Приведу код:
const int lgNmax = 10;
template <class Item, class Key>
class SkipList
{
private:
struct node
{
Item item;
node **next;
int sz;
node(Item x, int k)
{
item = x;
sz = k;
next = new node*[k];
for(int i = 0; i < k; i++)
next[i] = 0;
}
};
typedef node *link;
link head;
Item nullItem;
int lgN;
int N;
int _randX()
{
int i, j, t = rand();
for(i = 1, j = 2; i < lgNmax; i++, j += j)
if(t > RAND_MAX / j)
break;
if(i > lgN)
lgN = i;
return i;
}
void _insert(link t, link x, int k)
{
Key v = x->item.Key();
link tk = t->next[k];
if((tk == 0) || (v < tk->item.Key())){ // вот тут иногда вылетает,
if(k < x->sz){ // причем tk при этом всегда 0xfdfdfdfd
x->next[k] = tk;
t->next[k] = x;
}
if(k == 0)
return;
_insert(t, x, k - 1);
return;
}
_insert(tk, x, k);
}
Item _search(link t, Key v, int k)
{
if(!t)
return nullItem;
if(v == t->item.Key())
return t->item;
link x = t->next[k];
if(!x || (v < x->item.Key())){
if(k == 0)
return nullItem;
return _search(t, v, k - 1);
}
return _search(x, v, k);
}
// это уже исправленный мной вариант (не исправленный ты присылал)
void _remove(link t, Key v, int k)
{
link x = t->next[k];
if(!x){
if(k > 0)
_remove(t, v, k - 1);
return;
}
if(!(x->item.Key() < v)){
if(v == x->item.Key()){
t->next[k] = x->next[k];
if(k == 0){
delete x;
N --;
return;
}
}
if(k > 0)
_remove(t, v, k - 1);
return;
}
_remove(t->next[k], v, k);
}
public:
SkipList(int = 0)
{
head = new node(nullItem, lgNmax);
lgN = 0;
N = 0;
srand((unsigned int)time(NULL));
}
int Count() const
{
return N;
}
void Insert(Item v)
{
_insert(head, new node(v, _randX()), lgN);
N ++;
}
Item Search(Key v)
{
return _search(head, v, lgN);
}
void Remove(Key v)
{
_remove(head, v, lgN);
}
void Show()
{
for(link h = head->next[0]; h; h = h->next[0])
cout << h->item.Key() << ": " << h->item.Info() << endl;
}
};
Помогите, пожалуйста, все это исправить.
