Erreur de segmentation Skiplist
Bonsoir,
Pour mon cours d'algorithmique il m'a été demandé d'implémenter une skiplist, j'ai un soucis dans la méthode de ma classe SkipList qui réalise l'insertion des données.
Voici mon code pour la classe SkipList :
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
| #include <cstdlib>
#include <time.h>
#include "skiplist.hpp"
using namespace std;
SkipList::SkipList()
:level(0),size(0),proba(.5)
{
head = new Node(0, 32);
srand (time(NULL));
}
SkipList::~SkipList()
{
Node *prec = NULL;
for(Node *n = head; n != NULL; n = n->getNextAtLevel(0))
{
delete prec;
prec = n;
}
delete prec;
}
bool SkipList::contains(const int &key) const
{
Node *current = head;
for(int i = level; i >= 0; --i)
if(current->getNextAtLevel(i))
{
while(current->getNextAtLevel(i)->getKey() < key)
{
current = current->getNextAtLevel(i);
if(!current->getNextAtLevel(i))
break;
}
if(current->getNextAtLevel(i))
if(current->getNextAtLevel(i)->getKey() == key)
return true;
}
return false;
}
void SkipList::add(const int &key)
{
unsigned nodeSize = 1;
unsigned val = 1;
while(val)
{
val = rand()%2;
if(val)
++nodeSize;
}
if(nodeSize > level)
level = nodeSize - 1;
Node *newNode = new Node(key, nodeSize);
Node *current = head;
for(int i = level; i >= 0; --i)
{
if(!current->getNextAtLevel(i))
{
if(i < nodeSize)
current->setNextAtLevel(i, newNode);
continue;
}
while(1)
{
if(current->getNextAtLevel(i))
{
if(current->getNextAtLevel(i)->getKey() < key)
current = current->getNextAtLevel(i);
else
break;
}
else
break;
}
if(current->getNextAtLevel(i))
if(current->getNextAtLevel(i)->getKey() == key)
{
delete newNode;
return;
}
if(current->getNextAtLevel(i))
if(current->getNextAtLevel(i)->getKey() > key)
{
newNode->setNextAtLevel(i, current->getNextAtLevel(i));
current->setNextAtLevel(i, newNode);
}
++size;
}
} |
Et celui de ma classe Node :
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| #include "node.hpp"
Node::Node(const int &key, const unsigned &size)
:key(key), size(size)
{
next = new Node *[size];
for(unsigned i = 0; i < size; ++i)
next[i] = NULL;
}
Node::~Node()
{
delete []next;
}
unsigned Node::getSize() const
{
return size;
}
int Node::getKey() const
{
return key;
}
Node* Node::getNextAtLevel(const unsigned &level) const
{
return next[level];
}
void Node::setNextAtLevel(const unsigned &level, Node *node)
{
next[level] = node;
} |
Le problème semble se situer à la ligne 85 de SkipList.cpp, en effet l'appel de la fonction getNextAtLevel() renvoi 0x21 sous linux et 0xabababab sous windows. J'ai eu beau retourné le problème dans tous les sens je ne vois pas où se situe mon erreur.
