C++

Forum

 
User input to determine the head of linked list

clarkkent (57)
I need to create a program where the user is asked to enter two chars which will represent a starting node and and ending node, the program is then supposed to go from start to finish and return the path it took. How do I tell the program that the starting node should be the one that the user entered?
clarkkent (57)
I was guessing that this would work...
1
2
3
4
5
6
 
char start;
.
.
.
.
Node *ptr = start;


..but it does not, the error code is "a value of type char cannot be used to initialize an entity of type Node"... so what else can I do?
Smac89 (1727)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
string path = "";
bool found_path = false;

for ( /*loop until end of list or found last char*/ )
{
    if (!found_path and (value == start or value == last))
    {
        append value to path string
        found_path = true;
    }

    else if (found_path)
        append current value to the path string
}

return path;

ritstudent (27)
@Smac89: I don't think that OP is asking for the algorithm that handles finding the path, but is instead asking how to ensure that they can get input that represents the nodes so that the algorithm can be called.

@clarkkent: We may need a few more details such as:
1. How are node names/id's represented in your code?
2. Do you have access to a master list of the existing nodes in the graph?

Despite the lack of clarity, here is my high level suggestion.
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
 
#include <iostream>

using namespace std;

int main( void ){

	// I am assuming that you have a predefined map:
	NodeMap nMap = mkNodeMap();
	
	// Read the user input:
	char start_node_char;
	char end_node_char;
	cin >> start_node_char;
	cin >> end_node_char;
	
	// Search the node map for the start and end nodes:
	Node start = nMap.get(start_node_char);
	Node end = nMap.get(end_node_char);
	
	// Check to see if both are not null
	// If either one is null, then the node does not exist
	if( start == NULL || end == NULL ){
		return EXIT_FAILURE;
	}else{ // search for node:
		nMap.getPath(start,end); // Call your search function
	}
}



Keep this in mind when you post test cases so that we can give more direct feedback:
http://www.eelis.net/iso-c++/testcase.xhtml
Last edited on
clarkkent (57)
Thanks for your responses. Here is the code I have so far, it is not working at the moment, as it goes into an infinite loop :/
I just dont know how to get the user to dictate where the list starts and ends. 

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
 
#include <iostream>
#include <istream>
using namespace std;

struct ListNode
{
	ListNode *right;
	ListNode *left;
	ListNode *up;
	ListNode *down;

	ListNode()
	{
		right = NULL;
		left = NULL;
		up = NULL;
		down = NULL;
	}

};

void run(ListNode *, ListNode*);
int main()
{

	char starting;
	char destination;

	ListNode *A = NULL;
	A = new ListNode();

	ListNode *B = NULL;
	B = new ListNode();
	A->right = B;
	B->left = A;

	ListNode *C = NULL;
	C = new ListNode();

	ListNode *D = NULL;
	D = new ListNode();
	D->up = A;
	A->down = D;

	ListNode *E = NULL;
	E = new ListNode();
	E->up = B;
	B->down = E;

	ListNode *F = NULL;
	F = new ListNode();
	F->up = C;
	C->down = F;
	F->left = E;
	E->right = F;

	ListNode *G = NULL;
	G = new ListNode();

	ListNode *H = NULL;
	H = new ListNode();
	H->left = G;
	G->right = H;
	H->up = E;
	E->down = H;

	ListNode *I = NULL;
	I = new ListNode();
	I->up = F;
	F->down = I;

	cout << "Please enter the starting node: ";
	cin >> starting;
	cout << "Pleasae enter the destination node: ";
	cin >> destination;
	cout << endl;

	ListNode *ptr = F; //cannot get the user input into the list :( 
						// if i tried using 'starting' instead of 'f' 
						// i got an error saying that they were different types
	ListNode *ptr2 = B;
	run(ptr, ptr2); // so had to use a pre determined start and end to the list

	return 0;
}

void run(ListNode *ptr, ListNode *ptr2)
{
	
	if (ptr != ptr2)
	{
		if (ptr->up != NULL)
		{
			ptr = ptr->up;
			cout << "going up"<<endl;
		}
		if (ptr->down != NULL)
		{
			ptr = ptr->down;
			cout << "goingn down"<<endl;
		}
		if (ptr->left != NULL)
		{
			ptr = ptr->left;
			cout << "going left"<<endl;
		}
		if (ptr->right != NULL)
		{
			ptr = ptr->right;
			cout << "going rigth"<<endl;
		}
		
	run(ptr, ptr2);
	}
	else
	{
		cout << "YOu have reached B ";
	}
	


}
heebleworp (66)
To set the correct pointer from user input you can do something like:
1
2
3
4
 
cin.get(starting);
cin.get(); //clear newline
cin.get(destination);
cin.get(); //clear newline, not necessary though

or compact into
1
2
 
cin.get(starting).get();
cin.get(destination).get();

Then set up a switch statement to determine what to set ptr and ptr2 to.

As for your looping problem, your program is working fine. Feel free to look at this version I modified so you can see what's going on (no user input):
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
 
#include <iostream>
#include <istream>
using namespace std;

struct ListNode
{
	ListNode *right;
	ListNode *left;
	ListNode *up;
	ListNode *down;

	ListNode()
	{
		right = NULL;
		left = NULL;
		up = NULL;
		down = NULL;
	}

};

void run(ListNode *, ListNode*);
int main()
{

	char starting;
	char destination;

	ListNode *A = NULL;
	A = new ListNode();

	ListNode *B = NULL;
	B = new ListNode();
	A->right = B;
	B->left = A;

	ListNode *C = NULL;
	C = new ListNode();

	ListNode *D = NULL;
	D = new ListNode();
	D->up = A;
	A->down = D;

	ListNode *E = NULL;
	E = new ListNode();
	E->up = B;
	B->down = E;

	ListNode *F = NULL;
	F = new ListNode();
	F->up = C;
	C->down = F;
	F->left = E;
	E->right = F;

	ListNode *G = NULL;
	G = new ListNode();

	ListNode *H = NULL;
	H = new ListNode();
	H->left = G;
	G->right = H;
	H->up = E;
	E->down = H;

	ListNode *I = NULL;
	I = new ListNode();
	I->up = F;
	F->down = I;

	/*cout << "Please enter the starting node: ";
	cin >> starting;
	cin.get();
	cout << "Pleasae enter the destination node: ";
	cin >> destination;
	cin.get();
	cout << endl;*/
	for (char label = 'A'; label <= 'I'; ++label)
	{
		cout << label << ": ";
		switch (label)
		{
		case 'A':
			cout << A << endl;
			break;
		case 'B':
			cout << B << endl;
			break;
		case 'C':
			cout << C << endl;
			break;
		case 'D':
			cout << D << endl;
			break;
		case 'E':
			cout << E << endl;
			break;
		case 'F':
			cout << F << endl;
			break;
		case 'G':
			cout << G << endl;
			break;
		case 'H':
			cout << H << endl;
			break;
		case 'I':
			cout << I << endl;
			break;
		}
	}

	ListNode *ptr = F; //cannot get the user input into the list :( 
						// if i tried using 'starting' instead of 'f' 
						// i got an error saying that they were different types
	ListNode *ptr2 = B;
	run(ptr, ptr2); // so had to use a pre determined start and end to the list

	return 0;
}

void run(ListNode *ptr, ListNode *ptr2)
{
	cout << "starting ptr: " << ptr << endl; //F
	while (ptr != ptr2)
	{
		if (ptr->up != NULL)
		{
			ptr = ptr->up; //F to C
			cout << "going up"<<endl;
			cout << "current ptr: " << ptr << endl; //C
		}
		if (ptr->down != NULL)
		{
			ptr = ptr->down; //C to F
			cout << "goingn down"<<endl;
			cout << "current ptr: " << ptr << endl; //F
		}
		if (ptr->left != NULL)
		{
			ptr = ptr->left; //F to E
			cout << "going left"<<endl;
			cout << "current ptr: " << ptr << endl; //E
		}
		if (ptr->right != NULL)
		{
			ptr = ptr->right; //E to F
			cout << "going rigth"<<endl;
			cout << "current ptr: " << ptr << endl; //F, stuck in infinite cycle
		}
	cout << "pausing, hit enter to continue";
	cin.get();
	}
	cout << "YOu have reached B ";
	


}
clarkkent (57)
Thanks for your response, I have a couple of questions...what do I do with the starting and destination variables, how do I make a pointer point to them so they can be the start and end of the list? Ive tried something like
 
 
ListNode *ptr = starting; //but since they are different types I get an error


And why does the loop not stop when ptr and ptr2 are the same? could it be that once inside the loop all the if statements have to happen and the program does not know when they are equal since by the end of each loop they are not equal anymore?

Thanks again to all who have tried to help, i really appreciate it.
clarkkent (57)
Finally got it to take the user input, using a switch case as you said...thanks, glad I got past that part, now to the looping problem.
heebleworp (66)
Not sure how the program should be set up but right now the reason you're stuck in an infinite loop isn't that ptr equals B and is then changed before the next loop iteration (though this is also a possible problem which needs to be fixed). The reason is that ptr goes through the following repeating cycle and is never equal to B:
F to C to F to E to F, then next while() iteration
F to C to F to E to F, then next while() iteration
and so on.

Maybe you didn't copy down A-I correctly (assuming they're copied), maybe your if tests should be a series of if-else tests, maybe something else. Sadly there's no way for us to know for certain.
Topic archived. No new replies allowed.