Generating a string from a linked list (with no duplicates) ?Help

cppppc (26)

Hello!
I'm making a function that generates a random name (only once). The names are originally stored in a linked list (doubly circular)
1)I copy the names in an array of strings (in order to generate a random index each time, 2) look for the string( with the given index)in the linked list and if existing, will call a delete function to delete it, if not found it will be called again, after generating many strings, my program crashes.
here is the function:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
string generate(Bloc*root){
string str;
k= rand();
if(k <= nbrElements){
str=savedArray[k];

for(Bloc*it = root->nxt; it!=root; it= it->nxt){
if(it->name==str)
return str;

}
}
else return genererKenfant(root);
}


in the main, here's what happens:

1) store the generated string in a variable
2) send this variable to a search function that returns the adress of the block contating this string

3)create another list and call the AddAfterRoot function(to save the variable generated in this list)

4) delete the block by passing it to my delete function


Please help!
Last edited on
gunnerfunner (2127)
OP: could you please re-read your post and see if it makes full sense to you and whether some bits of it might do with an edit for greater clarity? Thanks
dhayden (5798)
Please post your full code. I think the bug is not in the code you showed us.
cppppc (26)
Yes sorry ! here's the code
You are right the problem comes from the delete function! How to fix it?
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
 

Bloc* searchKname(Bloc* root, string kName)
{


for(Bloc*it = root->nxt; it!=root; it=it->nxt) {
    if(it->name==kName) return it;

}

}



void deleteKname(Bloc*&root, Bloc*p)
{


    if(p->prev!=root) {p->prev->nxt = p->nxt;}
    else {root=p->nxt;} 

    if(p->nxt!=root) {p->nxt->prev = p->prev;}

    delete(p);
}





// int the main
for(Bloc* it = root->nxt; it!=root ; it= it->nxt ){


randName=generate(root);
//tmp is a pointer to hold the returned block that contains the randName
tmp=searchKname(root, randName);

//deletedList is for saving the deleted names from the original one
deletedList=createList();
//addAfterRoot to keep the order of deleted list elements
addAfterRoot(deletedList, randName);
//sending the original list (root) and the element to delete (tmp)
deleteKname(racine,tmp);


}
Last edited on
cire (8284)
15
16
17
18
19
20
21
22
23
24
25
 
void deleteKname(Bloc*&root, Bloc*p)
{


    if(p->prev!=root) {p->prev->nxt = p->nxt;}
    else {root=p->nxt;} 

    if(p->nxt!=root) {p->nxt->prev = p->prev;}

    delete(p);
}


It is impossible to say if line 19 is safe as we don't know of any invariants that hold true for your linked list. If it is possible that p->prev is null and that root is not null, then line 19 will result in dereferencing a null pointer.

The same issue occurs on line 22 with p->next.

Also, delete is not a function. delete p; is equivalent to delete (p);.

cppppc (26)
Could you correct this attemp?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
void deleteElt(Bloc*&root, Bloc*p)
{
if(p->prev!=root )
{
p->prev->nxt=p->nxt;
p->nxt->prev=p->prev;
 
}else root->prev=p->nxt;
if(p->nxt!=root)
{
p->prev->nxt=p->nxt;
p->nxt->prev=p->prev;
}else root->nxt=p->prev;
 
delete p; //same as delete(p);

}
Last edited on
cire (8284)
// caveat: untested code

1
2
3
4
5
6
7
8
9
10
11
12
13
 
void deleteElt(Block*& root, Bloc* p)
{
    if ( !p || !root ) return;   // sanity check

    Bloc* next = p->nxt;
    Bloc* prev = p->prev;

    if ( prev ) prev->nxt = next;
    if ( next ) next->prev = prev;

    if ( p == root ) root = next;
    delete p;
}
cppppc (26)
Thank you so so so so much :D you have made me one very happy person, the game works :)
Have an amazing week !! Will work harder
Last edited on
Topic archived. No new replies allowed.