C++

Forum

 
 
Queue using doubly linked list

Sep 9, 2012 at 4:45pm
Keshav2050 (26)
I actually didn't finish my program, but I am not able to remove an element or display all the elements in the following program


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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
 
/*Queue using doubly linked list*/

#include <iostream>
#include<stdlib.h>

using namespace std;

template<class t>

class dll{
    public:
    t data;
    dll<t> *p,*n;

};

template<class t>

class que{
    public:
    dll<t> *temp,*newn,*f,*r;
    que(){
    f=r=NULL;
    }
    void insert(t);
    void remove();
    void display();
    int search(t);
    t get(int);
};

template<class t>void que<t>::insert(t x){
    newn->data=x;
    if(r==NULL){
        newn->n=newn->p=NULL;
        f=r=newn;
    }

    else{
        newn->n=NULL;
        newn->p=r;
        r->n=newn;
        r=newn;
    }
}

template<class t>void que<t>::remove(){
    if(r==NULL)
        cout<<"Queue is empty."<<endl;
    else if(f==r){
        newn=f;
        f=r=NULL;
        delete(newn);
    }
    else{
        newn=f;
        f=f->n;
        f->p=NULL;
        delete(newn);
    }
}

template<class t>void que<t>::display(){
    if(r==NULL)
        cout<<"Queue is empty."<<endl;
    else if(f==r)
        cout<<f->data;
    else{
        for(newn=f;newn->p->n!=NULL;newn=newn->n)
            cout<<newn->data<<endl;
    }
}

template<class t>int que<t>::search(t x){
    int i=1;
    if(r==NULL)
        cout<<"Queue is empty."<<endl;
    else if(f==r){
        if(f->data==x)
            return i;
    }
    else{
        for(newn=f;newn->p->n!=NULL;newn=newn->n){
            if(newn->data==x)
                return i;
            else i++;
        }
    }
    return 0;
}

template<class t>t que<t>::get(int x){
    int i;
    newn=f;
    for(i=0;i<x;i++){
        if(i+1==x)
            return newn->data;
        newn=newn->n;
    }
}

main()
{
    char c;
    que<int> q;
    do{
        int o,x;
        cout<<"1.Insert\n2.Remove\n3.Display\n4.search\n5.get\n6.exit\nchoose an option: ";
        cin>>o;
        switch(o){
            default:
            cout<<"You didn't choose correct option, by default queue is displayed"<<endl;
            case 3:
            q.display();
            break;
            case 1:
            cout<<"what element you want to insert :";
            cin>>x;
            q.insert(x);
            break;
            case 2:
            q.remove();
            break;
        }
        cout<<"Do you want to continue[y/n] :";
        cin>>c;
    }while(c=='y'||c=='Y');

}
Edit & run on cpp.sh



I'm getting

Segmentation fault (core dumped)

when I try to remove any element,

and I've also obsered that always that below statements

1
2
 
else if(f==r)
        cout<<f->data;



in the program(line no. 66,67) are getting executed irrespective of the no. of elements in the queue, where 'f' and 'r' are the pointers to front and rear elements of the queue.

Can anyone please tell me why is it happening?
Sep 9, 2012 at 5:03pm
AbstractionAnon (6954)
You've got a couple of problems here.

1) Line 21, why are temp and newn members of que? There's not attributes of your que. They should be locals where you use them.

2) Line 33, Your insert is going to fail with an address violation (or other undefined behavior). newn is not initialized.
Sep 10, 2012 at 2:34am
Keshav2050 (26)
Thank you, for replying but I didn't understand. newn is declared inline 21 and what happens if they are in public mode newn is a data member of que which can be used anywhere in the class and are objects of dll.
Last edited on Sep 10, 2012 at 8:22am
Sep 10, 2012 at 8:22am
Keshav2050 (26)
Did I do any mistakes using templates?
Sep 10, 2012 at 12:22pm
Keshav2050 (26)
Can anyone please respond.
Sep 10, 2012 at 1:13pm
AbstractionAnon (6954)
1) Making newn and temp public members of que is sloppy coding. There is no reason they should be public members of que. Variables should be as local as possible. Since newn and temp are not used across calls, they should be local where they are used and not public members of que.

2) Regarding line 33, where is newn initialized? This is what I mean by sloppy coding. Had you made newn local to insert, you probably would have recognized sooner that it was never initialized. Because newn is uninitialized, it is going to cause undefined behavior. Probably an address violation.


Sep 10, 2012 at 1:16pm
Moooce (216)
Like AbstractionAnon said, maybe something is not initialised. Set a break point at the lines where the error occurs, run debug build and have a look at the values of the variables.

1
2
 
    else if(f==r)
        cout<<f->data;


My guess is that the variable f is pointing to something invalid.
Sep 10, 2012 at 2:15pm
gtkano (44)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
template<class t>void que<t>::insert(t x){
    newn = new dll<t>;  //initialize the pointer newn
    newn->data=x;
    if(r==NULL){
        newn->n=newn->p=NULL;
        f=r=newn;
    }

    else{
        newn->n=NULL;
        newn->p=r;
        r->n=newn;
        r=newn;
    }
}



pointers *temp,*newn,*f,*r; are not initialized
Last edited on Sep 10, 2012 at 2:18pm
Sep 10, 2012 at 2:56pm
Keshav2050 (26)
Thank you for your advices, I have changed the code a bit into 

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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
 
/*Queue using doubly linked list*/

#include <iostream>
#include<stdlib.h>

using namespace std;

template<class t>

class dll{
    public:
    t data;
    dll<t> *p,*n;

};

template<class t>

class que{
    dll<t> *newn,*f,*r;
    public:
    que(){
        newn=NULL;
        f=NULL;
        r=NULL;
    }
    void insert(t);
    void remove();
    void display();
    int search(t);
    t get(int);
    int count();
};

template<class t>int que<t>::count(){
    if(r==NULL)
        return 0;
    else{
        int i=1;
        for(newn=f;newn!=r;newn=newn->n);
        return i;
    }
}

template<class t>void que<t>::insert(t x){
    newn->data=x;
    if(r==NULL){
        newn->n=newn->p=NULL;
        f=r=newn;
    }

    else{
        newn->n=NULL;
        newn->p=r;
        r->n=newn;
        r=newn;
    }
}

template<class t>void que<t>::remove(){
    if(r==NULL)
        cout<<"Queue is empty."<<endl;
    else if(f==r){
        newn=f;
        f=r=NULL;
        delete(newn);
    }
    else{
        newn=f;
        f=f->n;
        f->p=NULL;
        delete(newn);
    }
}

template<class t>void que<t>::display(){
    if(r==NULL)
        cout<<"Queue is empty."<<endl;
    else if(f==r)
        cout<<f->data;
    else{
        for(newn=f;newn->p->n!=NULL;newn=newn->n)
            cout<<newn->data<<endl;
    }
}

template<class t>int que<t>::search(t x){
    int i=1;
    if(r==NULL)
        return 0;
    else if(f==r){
        if(f->data==x)
            return i;
    }
    else{
        for(newn=f;newn->p->n!=NULL;newn=newn->n){
            if(newn->data==x)
                return i;
            else i++;
        }
    }
    return 0;
}

template<class t>t que<t>::get(int x){
    int i;
    newn=f;
    for(i=0;i<x;i++){
        if(i+1==x)
            return newn->data;
        newn=newn->n;
    }
}

int main()
{
    char c;
    que<int> q;
    do{
        int o,x;
        int y;
        cout<<"1.Insert\n2.Remove\n3.Display\n4.search\n5.get\n6.exit\nchoose an option: ";
        cin>>o;
        switch(o){
            default:
            cout<<"You didn't choose correct option, by default queue is displayed"<<endl;
            case 3:
            q.display();
            break;
            case 1:
            cout<<"what element you want to insert :";
            cin>>x;
            q.insert(x);
            break;
            case 2:
            q.remove();
            break;
            case 4:
            cout<<"What do you want to search :";
            cin>>x;
            y=q.search(x);
            if(y==0)
                cout<<"Element not found"<<endl;
            else
                cout<<x<<" is in position "<<y<<"."<<endl;
            break;
            case 5:
            cout<<"Which element do you want to know :";
            cin>>y;
            if(y>q.count()||y<=0)
                cout<<"There's no element in that position"<<endl;
            else{
                x=q.get(y);
                cout<<x<<" is in position "<<y<<endl;
            }
            break;
            case 6:
            exit(0);
        }
        cout<<"Do you want to continue[y/n] :";
        cin>>c;
    }while(c=='y'||c=='Y');
return 0;
}
Edit & run on cpp.sh


Here I've observed that I am not able to insert an element, what I am getting is 

1.Insert
2.Remove
3.Display
4.search
5.get
6.exit
choose an option: 1
what element you want to insert :1
Segmentation fault (core dumped)


Similar to what I was getting when I tried to remove an element before, and I've also observed that I'm not getting this error for inserting an element if I don't initialize newn value to NULL in the constructor in line 23 as,

1
2
3
4
 
que(){        
        f=NULL;
        r=NULL;
    }


Last edited on Sep 10, 2012 at 3:16pm
Sep 10, 2012 at 3:16pm
Keshav2050 (26)
I've also observed that if I add a new element to the queue the previous element is automatically getting removed, as if I didn't use break; in the switch block. And I've checked the values in the data in f and r after inserting a new element and both are pointing towards the new element instead of f pointing the first element, if I try to print a NULL value I'm getting 
Segmentation fault (core dumped)
(may be something related to the situation).
Sep 10, 2012 at 3:17pm
Moooce (216)
take a look at line 2 of gtkano posted code.....
Sep 10, 2012 at 3:41pm
Keshav2050 (26)
Thank you, I've learned to initialize the pointer I'm able to insert and remove accordingly but there seems some problem with the display function

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
 
template<class t>void que<t>::insert(t x){
    newn = new dll<t>;
    newn->data=x;
    if(r==NULL){
        newn->n=newn->p=NULL;
        f=r=newn;
    }

    else{
        newn->n=NULL;
        newn->p=r;
        r->n=newn;
        r=newn;
    }
    delete(newn);
}

template<class t>void que<t>::remove(){
    newn = new dll<t>;
    if(r==NULL)
        cout<<"Queue is empty."<<endl;
    else if(f==r){
        newn=f;
        f=r=NULL;
    }
    else{
        newn=f;
        f=f->n;
        f->p=NULL;
    }
    delete(newn);
}

template<class t>void que<t>::display(){
    if(r==NULL)
        cout<<"Queue is empty."<<endl;
    else if(f==r)
        cout<<f->data;
    else{
        newn = new dll<t>;
        for(newn=f;newn->p->n!=NULL;newn=newn->n)
            cout<<newn->data<<endl;
        delete(newn);
    }
}


Always 0 is getting displayed, irrespective of the no. of elements in queue whereas remove is working fine if we take no. of elements into consideration. If I try to print the data in f and r, 0 is getting displayed.(may be I've done more blunders than before)
Sep 11, 2012 at 3:13pm
Keshav2050 (26)
Can anyone please tell me why the display function is displaying a single 0(numeric zero)?
Last edited on Sep 11, 2012 at 3:13pm
Sep 11, 2012 at 3:31pm
Peter87 (11251)
You shouldn't delete newn at the end of insert().

There is no reason to create a new dll<t> object in remove(). You are not using it for anything and it's a memory leak because you never delete it.
Sep 12, 2012 at 12:18pm
Keshav2050 (26)
Oh, thanks I understood how to use new and delete, but I still get segmentation error when I try to display the queue with more than one element.

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
 
template<class t>void que<t>::insert(t x){
    newn = new dll<t>;
    newn->data=x;
    if(r==NULL){
        newn->n=newn->p=NULL;
        f=r=newn;
    }

    else{
        newn->n=NULL;
        newn->p=r;
        r->n=newn;
        r=newn;
    }
}

template<class t>void que<t>::remove(){
    if(r==NULL)
        cout<<"Queue is empty."<<endl;
    else if(f==r){
        newn=f;
        f=r=NULL;
        delete(newn);
    }
    else{
        newn=f;
        f=f->n;
        f->p=NULL;
        delete(newn);
    }
}

template<class t>void que<t>::display(){
    if(r==NULL)
        cout<<"Queue is empty."<<endl;
    else if(f==r)
        cout<<f->data<<endl;
    else{
        for(newn=f;newn->p->n!=NULL;newn=newn->n)
            cout<<newn->data<<endl;
    }
}


Program Output:
1.Insert
2.Remove
3.Display
4.search
5.get
6.exit
choose an option: 1
what element you want to insert :9
Do you want to continue[y/n] :y
1.Insert
2.Remove
3.Display
4.search
5.get
6.exit
choose an option: 1
what element you want to insert :8
Do you want to continue[y/n] :y
1.Insert
2.Remove
3.Display
4.search
5.get
6.exit
choose an option: 3
Segmentation fault (core dumped)
Sep 12, 2012 at 12:31pm
Peter87 (11251)
The problem is on this line: for(newn=f;newn->p->n!=NULL;newn=newn->n)
Sep 12, 2012 at 1:08pm
Keshav2050 (26)
Thank you very much, no node's 'n' pointer will be NULL if next element actually exists, I shouldn't have done it so blindly. Thank you once again for helping me complete the program, I've just inserted another cout<<newn->data<<endl; after removing ->p.
1
2
3
 
for(newn=f;newn->n!=NULL;newn=newn->n)
            cout<<newn->data<<endl;
        cout<<newn->data<<endl;

And the program is working!
Sep 12, 2012 at 1:41pm
Peter87 (11251)
If you compare newn against NULL instead you don't need the extra cout at the end.
1
2
3
 
for(newn=f;newn->n!=NULL;newn=newn->n)
	cout<<newn->data<<endl;
cout<<newn->data<<endl;
Last edited on Sep 12, 2012 at 1:42pm
Sep 22, 2012 at 10:48am
Keshav2050 (26)
Thanks.
Topic archived. No new replies allowed.