SegFault in a While Loop Condition

Baelix (16)
Hey guys, I'm apologizing in advance for the length of this. I'm incorporating a Linked List class via a Node structure (i.e. pointers). This is usually a breeze for me, but I'm getting caught on one step. During this program's execution, any number in the LL specified by head1 should end up in the LL specified by head2. The catch is that if it has a duplicate in the list, it is to be rerouted from the first LL to the second LL, not simply copied. If it is the only number of its kind in the list, it is to be copied.
Here's a bit of my code (minus the guts):

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
 
void CopySingletonsGatherDups (Node*& head1, Node*& head2)
{
   head2 = 0;
   
   if(head1 == 0 || head1->link == 0)
   {
      cerr << "CopySingletonsGatherDups() attempted on empty list" << endl;
      cerr << "No operation performed." << endl;
   }
   else
   {
      Node *cur1 = head1, *cur2 = head2, *old1 = head1;
      cur1 = old1->link;
      Node *pre = old1;
      
      while(old1 != 0)
      {         
         bool found = false; //tracking if value found already
         
         while(cur1 != 0)
         {
            int anchor = old1->data;  //value searching for
      
            if(cur1->link != 0 && cur1->link->data == anchor)
            {
               found = true;
               
               if(head2 != 0)
               {
                  Node *old2 = cur1->link;
                  cur2->link = old2;
                  cur1->link = old2->link;
                  old2->link = 0;
                  cur2 = old2;
               }
               else
               {
                  Node *old2 = cur1->link;
                  cur2 = old2;
                  cur1->link = cur2->link;
                  cur2->link = 0;
                  head2 = cur2;
               }
               
               pre = cur1;
               cur1 = cur1->link;
            }
            else if(cur1->link == 0 && found == false)
            {
               if(head2 != 0)
               {
                  Node *old2 = new Node;
                  old2->data = anchor;
                  old2->link = 0;
                  cur2->link = old2;
                  cur2 = cur2->link;
               }
               else
               {
                  Node *old2 = new Node;
                  old2->data = anchor;
                  old2->link = 0;
                  cur2 = old2;
                  head2 = cur2;
               }
               
               pre = cur1;
               cur1 = cur1->link;
            }
            else if(cur1 != 0 && cur1->data == anchor && head2 != 0)
            {
               found = true;
               Node *old2 = cur1;
               cur2->link = old2;
               cur1 = old2->link;
               cur2 = old2;
               old2->link = 0;
               pre->link = cur1;
            }
            else
            {
               pre = cur1;
               cur1 = cur1->link;
            }
         }
         cur1 = old1->link;
         old1 = cur1;
         
         if(old1 != 0 && old1->link != 0)
            cur1 = cur1->link;
      }
   }

}


Here is some detailed output of the program:
H1 4 0 3 1 2 1 2 1 5 4 0 0 4 4 5 2 //starts search with 4
First IF statement, the nested ELSE is called, re-routes 2nd 4 in H1
H1 4 0 3 1 2 1 2 1 5 0 0 4 4 5 2
H2 4
First IF statement, the nested IF is called, re-routes 3rd 4 in H1
H1 4 0 3 1 2 1 2 1 5 0 0 4 5 2
H2 4 4
Third else/IF statement is called, re-routes last 4 in H1
H1 4 0 3 1 2 1 2 1 5 0 0 5 2
H2 4 4 4

Now searches for all 0's First IF statement, the nested IF is called, re-routes 2nd 0 in H1\
H1 4 0 3 1 2 1 2 1 5 0 5 2
H2 4 4 4 0
Third else/IF statement called, re-routes final 0 in H1
H1 4 0 3 1 2 1 2 1 5 5 2
H2 4 4 4 0 0

The search will continue in this manner, searching next for 3 (which it doesn't find, and makes a new Node and copies the data), then searches for 1(re-routes 2nd and 3rd 1's) until we have these two lists:
H1 4 0 3 1 2 2 5 5 2
H2 4 4 4 0 0 3 1 1

This is where we hit the snag:
Third else/IF statement called, re-routes 2nd 2 in H1
H1 4 0 3 1 2 2
H2 4 4 4 0 0 3 1 1 2

As you can see, not only does it not re-route the 2nd 2, but it eliminates the last 3 characters. I'm not sure what causes this error, seeing how it works on every other call. Any suggestions? I can offer more in depth output for those who would like it. Thanks!
lemonaid (2)
Were you able to solve your problem, I am having similar issues.
Baelix (16)
Not as of yet. I'm hoping to fix it by tonight, I have a pretty good guess that the reason its failing is because I'm not accounting for one last situation, in which old1/pre/cur1 have just been moved again right after the 3rd else/IF is called. I will let you know if I am able to fix it.
Last edited on
cire (8284)
On line 24 you test the data of the next node in the list. On line 70 you test the data of the current node in the list. Line 70 is never reached in iterations where the condition in line 24 evaluates to true. This is part of your problem and reveals a flaw in your algorithm.

For every iteration of the loop you should process only the current node.

I actually couldn't follow your code with all the crappily named variables (cur1, cur2, old1, old2) without getting confused so I worked it over a bit to simplify things and ended up doing a bit more than I meant to. I suspect this is a homework assignment, but I'm going to share anyway in the hopes you'll learn something from it (and so I don't feel like I wasted my time screwing around. =P)

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
 
#include <iostream>

using namespace std ;

struct Node {
	Node * link ;
	int data ;
};

void Add(Node*& n, int d) ;
Node* CopySingletonsGatherDups(Node*&); 
ostream& operator<<(ostream&, Node*);

int main()
{
	int values[] = { 2, 5, 4, 4, 0, 0, 4, 5, 1, 2, 1, 2, 1, 3, 0, 4 } ;

	Node * l1 = 0 ;

	for ( unsigned i=0; i<sizeof(values)/sizeof(values[0]) ; ++i )
		Add(l1, values[i]) ;

        cout << "List 1: " << l1 << '\n' ;

	Node* l2 = CopySingletonsGatherDups(l1) ;
	
	cout << "List 1: " << l1 ;
	cout << "List 2: " << l2 ;

        // free memory here.
}

ostream& operator<<(ostream& os, Node* list)
{
	if ( list == 0 )
	{
		os << "{empty}\n" ;
		return os ;
	}

	os << '{' ;
	while (list != nullptr )
	{
		os << ' ' << list->data ;
		list = list->link ;
	}
	os << " }\n" ;
	return os ;
}

void Add( Node *& n, int d )
{
	Node* newNode = new Node ;
	newNode->data = d ;
	newNode->link = n ;
	n = newNode ;
}

Node* CopySingletonsGatherDups (Node*& list)
{
	if(list == 0 || list->link == 0)
		return 0 ;

	Node* destList = 0 ;
	Node* destTail = 0 ;

	Node* workingHead = list ;
	Node* workingNode = list->link ;
	Node* prevNode = list ;

	while(workingHead != 0)
	{         
		bool isUnique = true; 

		// cout << "List 1: " << list ;
		// cout << "List 2: " << destList ;

		while(workingNode != 0)
		{	
			if( workingNode->data == workingHead->data)
			{
				isUnique = false;

				// remove from list
				prevNode->link = workingNode->link ;
				workingNode->link = 0 ;

				// add to destination list
				if ( destList==0 )
					destList = destTail = workingNode ;
				else
				{
					destTail->link = workingNode ;
					destTail = workingNode ;
				}

				workingNode = prevNode->link ;
			}
			else
			{
				prevNode = workingNode ;
				workingNode = workingNode->link ;
			}
		}

		if ( isUnique )
		{   // add a copy to the destination list
			Node * newNode = new Node ;
			newNode->data = workingHead-> data;
			newNode->link = 0 ;

			if ( destList == 0 )
				destList = destTail = newNode ;
			else
			{
				destTail->link = newNode ;
				destTail = newNode ;
			}
		}

		if ( workingHead->link == 0 )
			return destList ;

		workingHead = workingHead->link ;
		prevNode = workingHead ;
		workingNode = workingHead->link ;
	}
}

List 1: { 4 0 3 1 2 1 2 1 5 4 0 0 4 4 5 2 }

List 1: { 4 0 3 1 2 5 }
List 2: { 4 4 4 0 0 3 1 1 2 2 5 }
Press any key to continue . . .


Last edited on
Baelix (16)
Yeah, my apologies on the pointer names. They're more useful in our classroom context, as they're based off of pointer names used by my teacher in his examples. Thank you very much for your response though! I can see where I went wrong; I was hoping that the last else/IF statement would catch the situation in which the cursor1 was moved ahead a node, and the node it was placed on happened to be one that I was searching for.
lemonaid (2)
What does your final code look like?
Topic archived. No new replies allowed.