PPP2 Chapter 17 Exercise 11

Pages: 1... 89101112... 16
If it was working correctly, that would be the simplest way to make sure I got the correct output.

Why do you think that?

I think it's possible that what's happening is that it puts the string that's greater than the one before it before the other string when they're in the correct order and side-by-side like that. Though I could be wrong.


Why do you just "think" something is possible. You need to follow your logic manually to see what is actually happening. Your guess as to what is happening is incorrect. As I have said in the past your "logic" is not precise enough. For example:
I think it's possible that what's happening is that it puts the string1 that's greater than2 the one before it3 before the other string when they're in the correct order and side-by-side like that4. Though I could be wrong.5

1. What exactly is the string you are talking about?
2. Again why are you thinking about greater, you should be thinking in terms of less than.
3. What exactly is the string you're talking about here?
4. What? This really doesn't make much sense. Perhaps you want to clarify what you're talking about.
5. That's hard to tell since your statement is not very clear.

By the way it is working exactly the way I would expect.

I know my other question has nothing to do with this, but I was trying to do that exercise and thought I'd ask about it here. So I'd be better making a different for it, after all?


Well, IMO, you would be better off sticking with one problem until you solve it. Working on multiple things at once, especially when those other topics rely on you understanding previous material, is just going to be confusing.

1. In this case, that would be the name string in the second node being inserted through add_ordered() in that particular scenario, so "Zeus".
2. Then "not less than".
3. "Odin". I was talking about the name string in the node adjacent to the one mentioned in #1.
4. Two adjacent strings that should be in order. But aren't. That's what I was talking about.
5. It should be now.

And I managed to fix the problem of the memory leak in that other program.
And I managed to fix the problem of the memory leak in that other program.

So what, have you fixed this problem yet?

1. In this case, that would be the name string in the second node being inserted through add_ordered() in that particular scenario, so "Zeus".

Why are you talking about Zeus? Zeus is the last god being added not the first or the second.

Okay entering the gods in the following order Apollo, Odin, Zeus can you tell me if Odin is added correctly using add_ordered()? This should not require you to run the program just follow the logic of the add ordered function.

2. Then "not less than".

NO! LESS THAN, period. Is god 1 (Apollo) less than god 2 (Odin)?

5. It should be now.

Not really.



I was talking about the two gods being inserted through add_ordered(). First is Odin, second is Zeus. And as for the not less than, I meant that Zeus is not less than Odin, but that it's still going before it. That's what I was saying.

I already know what's happening with Odin and Zeus since I ran the program to check for that. It correctly inserts Odin after Apollo, but then it only compares Zeus with Apollo and inserts it after Apollo. So it works correctly when there's one node in the list (or less), but when there are two or more, and you try to insert in a certain order, there'll be problems.

How about this pseudocode for the problem?
1
2
3
4
5
6
7
8
9
10
11
if # of nodes in list is 0
    insert the node
else if # of nodes in list is exactly 1
    if current node in list is less than the node to insert
        insert node after
    else
        insert node before
else if # of nodes is greater than 1
    while current node in list is less than the node to insert and the next pointer is not null
        insert node after
        advance to the next node


Is that closer to the desired solution?
I was talking about the two gods being inserted through add_ordered(). First is Odin, second is Zeus. And as for the not less than, I meant that Zeus is not less than Odin, but that it's still going before it. That's what I was saying.


Do you realize that the problem actually has nothing to do with Odin and Zeus because Odin is never seen when you try to place Zeus?

If you manually follow the logic you should be able to see what I'm talking about.


Did you try to manually follow this logic?

Does the logic seem to work when you manually try to "add" the third god?

By the way your logic doesn't seem correct to me.



I did say,
It correctly inserts Odin after Apollo, but then it only compares Zeus with Apollo and inserts it after Apollo.


Doesn't what I quoted also mean that because the code doesn't compare Odin and Zeus, and only Apollo and Zeus, it just inserts Zeus after Apollo? Unless you're saying that that's wrong, too.

And as for what's wrong in my pseudocode. Please let me know what it is so I can fix it.

Doesn't what I quoted also mean that because the code doesn't compare Odin and Zeus, and only Apollo and Zeus, it just inserts Zeus after Apollo?

No I'm not saying this is wrong. I was saying that the following is not totally correct.
I was talking about the two gods being inserted through add_ordered(). First is Odin, second is Zeus. And as for the not less than, I meant that Zeus is not less than Odin, but that it's still going before it. That's what I was saying.

The problem has nothing to do with Zeus and Odin. When you're inserting Zeus Odin is never seen, why?

And as for what's wrong in my pseudocode. Please let me know what it is so I can fix it.

No, this is your program you need to solve the problem. If I just give you the solution it won't help you learn how to properly design and implement the solution, besides I've already told you several times where the problem is occurring.


Isn't Odin not seen because there's no loop to see where to best insert the subsequent nodes? It just inserts it after comparing it with the first node it sees. Or is that the part that I'm wrong about here?

I know you tried to tell me where the problem is several times, but I didn't understand those hints. My bad, there.
Last edited on
Isn't Odin not seen because there's no loop to see where to best insert the subsequent nodes?


Yes.

But your pseudo code is still wrong, even though it contains a loop, for a couple of reasons, if you try to actually follow the logic of your pseudo code you should see where the errors are located in your pseudo logic.

It just inserts it after comparing it with the first node it sees.


Yes. So what should you be doing instead to solve this problem. This one of the major flaws with your pseudo code by the way.


I know you tried to tell me where the problem is several times, but I didn't understand those hints. My bad, there.

So what is this supposed to mean? Did you go back and read the posts to see what you missed? Those hints are still there you know?
This was one of the hints, right?
Who told you that you would need use either insert() or add() in any loop?


TheIdeasMan and/or someone else had told me I might need both of my inserting functions, so I thought I might need to use one or both of them in a loop. But is that one of the problems in my code? I don't need to use either one of the inserting functions in the loop that traverses the list? Then where do I insert the node? After the loop? But that would insert it before or after the last node, wouldn't it?
This was one of the hints, right?

Yes, but that's only one of the many hints. Some of those other hints should also help to clarify why your last attempt at pseudo code is incorrect.

TheIdeasMan and/or someone else had told me I might need both of my inserting functions,

That's right look at your current code, how many of your "inserting functions" is that code using?

so I thought I might need to use one or both of them in a loop. But is that one of the problems in my code?

Possibly, what can you do to find out if your current suspicions are correct? Hint: see the first answer for more help.

I don't need to use either one of the inserting functions in the loop that traverses the list?

Possibly, what can you do to find out what you need the loop to do? See the first answer for more help.

Then where do I insert the node?

That's a good question. What can you do to find out were you need to insert the node? Hint: See the last paragraph below, along with the first answer above.

After the loop?

See above.

But that would insert it before or after the last node, wouldn't it?

Would it? Hint: yes. Would that be good or bad?

Have you considered using pseudo code to help you answer the above questions? Example write up some pseudo code that is using the loop you're thinking about, then follow the logic. When following the logic, since you already know that the first two gods are "inserted" correctly, you only need to worry about the placing the third god into the list in the proper place.


Last edited on
About that last question (if it'd be bad to insert the third node before or after the last node): I'm not sure about other scenarios, but at least in this scenario I think it's good. Because Zeus has to go after Odin. I also tried doing it on my Windows notepad editor and it seems fine (if I did it correctly).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
if # of nodes in list is 0
    insert the node
else if # of nodes in list is exactly 1
    if current node in list is less than the node to insert
        insert node after
    else
        insert node before
else if # of nodes is greater than 1
    while previous pointer is not null
        advance backwards through the list and reach head of list
    while current node is less than node to insert and next pointer is not null
        advance to the next node
    insert node after


NULL<-Apollo-><-Odin->NULL

NULL<-Apollo-><-Odin

n = Zeus
NULL<-Apollo-><-Odin-><-Zeus->NULL
Last edited on
I also tried doing it on my Windows notepad editor and it seems fine (if I did it correctly).

You tried to do what in Windows notepad?

Why do you even care how many nodes are in the list?

Do you realize that your second while statement has two terminating conditions?

What is the purpose of having two conditions?


By the way:
if # of nodes in list is 0
how are you going to determine if there are zero nodes in the list?

That's not one loop with two conditions, inside the if-statement for when there's more than one node in the list. That's two separate while loops. One for making sure we start at the head, and the other for traversing the list to find the right place for the node.

I care about the number of nodes because the trouble here is happening partly because it only looked at the first node regardless of how many nodes were in the list. If it knows there's more than node when there is more than one node, I'll have one less problem to worry about.

As for how I'll know how many nodes there are. I made a function that counts them, if you recall.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int Link::element_count()
{
	Link *trav = this;
	int size = 0;
        int non_null_next = 0;
	if (trav)
	{
		while (trav->m_prev)
		{
			trav = trav->m_prev;
		}

		while (trav->m_succ)
		{
			non_null_next++;
			trav = trav->m_succ;
		}
	}
        size = non_null_next + 1;
	return size;
}


I'm trying to count the number of next pointers that aren't null and adding one to that on return. I'll call this function in add_ordered() to check how many nodes there are. How do I tell the program that that function is returning the number of nodes, though?

I typed the pseudo code and tried to follow it on the notepad.
Last edited on
I care about the number of nodes because the trouble here is happening partly because it only looked at the first node regardless of how many nodes were in the list. If it knows there's more than node when there is more than one node, I'll have one less problem to worry about.

No, if you get your logic correct you don't need to worry about how many records are in the list.


As for how I'll know how many nodes there are. I made a function that counts them, if you recall.

Yes I recall, I also recall questioning the need for that function when you first introduced it as well.

That's two separate while loops. One for making sure we start at the head, and the other for traversing the list to find the right place for the node.


Yes and that second loop has two termination conditions. Why does it have two terminating conditions?

while current node is less than node to insert and next pointer is not null


I was doing what TheIdeasMan had suggested here:

Here's another massive hint:

I reckon we only need two comparisons: NextPtr with nullptr ; and a less than . They both form the condition for the while loop. If either of them is true, insert the item after the current pointer, otherwise move to the next item. There we go, 1 line of pseudo code. Only a few lines of actual code. Note I didn't actually have any if statements.


Then I was told later that I'd have to do while (trav->m_god.name() < n->m_god.name() && trav->m_succ) as the loop condition. Unless I misunderstood something?

So how about this?
1
2
3
4
5
6
while current node is less than node to insert and next pointer is not null
    advance to the next node
if current node is less than node to insert
    insert node after
else
    insert node before


I put the comparison and insertion after the loop.

I purposefully left out the loop for going back to the head of the list. But I'll include that in the actual code.

I'll look at the other to find the other hints after this. But anyway, I just looked at my code again and saw that I'm already using both add() and insert().
So how about this?

Why the guess? Did you manually check if this would help with the current problem?

Then I was told later that I'd have to do while (trav->m_god.name() < n->m_god.name() && trav->m_succ) as the loop condition. Unless I misunderstood something?


No, I think you're finally starting to understand the problem.

I suggest you post your proposed new code to see if your pseudo code and actual code match.

Edit: One more question:
I put the comparison and insertion after the loop.

Why?
Last edited on
Because putting inside or before the loop didn't work and my manual test seemed to show that putting it after the loop would work. And I just tried it by running the program, too. It worked.

Here's the 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
Link *Link::add_ordered(Link *n)
{
	if (!n)
	{
		error("Node to insert cannot be null");
	}
	
	Link *trav = this;
	if (!trav)
	{
		return this;
	}

	std::cout << "Before loop:\n";
	std::cout << "*trav:\n";
	print(*trav);
	std::cout << "*n:\n";
	print(*n);

	// to make sure to start at head of the list
	while (trav->m_prev)
	{
		std::cout << "\nInside loop (before \"trav = trav->m_prev\"):\n";
		std::cout << "*trav:\n";
		print(*trav);
		trav = trav->m_prev;
		std::cout << "\nInside loop (after \"trav = trav->m_prev\"):\n";
		std::cout << "*trav:\n";
		print(*trav);
	}

	std::cout << "\nAfter loop:\n";
	std::cout << "*trav:\n";
	print(*trav);

	while (trav->m_god.name() < n->m_god.name() && trav->m_succ)
	{
		trav = trav->m_succ;
	}

	if (n->m_god.name() < trav->m_god.name())
	{
		std::cout << "Inside first conditional check, before insertion:\n";
		std::cout << "*trav:\n";
		print(*trav);
		trav = trav->insert(n);
		std::cout << "Inside first conditional check, after insertion:\n";
		std::cout << "*trav:\n";
		print(*trav);
	}
	else
	{
		std::cout << "Inside first else-if conditional check, before insertion:\n";
		std::cout << "*trav:\n";
		print(*trav);
		trav = trav->add(n);
		std::cout << "Inside first else-if conditional check, after insertion:\n";
		std::cout << "*trav:\n";
		print(*trav);
	}

	std::cout << "After conditional for adding n to list:\n";
	std::cout << "*trav:\n";
	print(*trav);

	return trav;
}


Here's my main():
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
int main()
{
	try
	{
		Link *norse_gods = new Link{{ "Odin", "Norse", 
			"Eight-legged flying horse called Sleipnir", "Spear called Gungnir" } };
		norse_gods = norse_gods->add_ordered(new Link{ { "Baldr", "Norse", "Ship called Hringorni", "None" } });
		norse_gods = norse_gods->add_ordered(new Link{ { "Thor", "Norse", 
			"Chariot pulled by goats Tanngrisnir and Tanngnjostr", "Hammer called Mjolnir" } });
		norse_gods = norse_gods->add_ordered(new Link{ { "Frejya", "Norse", 
			"Chariot pulled by two cats", "Magic called seidr" } });

		Link *greek_gods = new Link{ { "Ares", "Greek", "War chariot", "Sword and spear" } };
		greek_gods = greek_gods->add_ordered(new Link{ { "Zeus", "Greek", 
			"A chariot pulled by the four major winds shaped as horses", "Thunderbolt" } });
		greek_gods = greek_gods->add_ordered(new Link{ { "Apollo", "Greek",
			"Chariot pulled by the four horses Aethon, Pyrois, Phlegon and Eous", "A bow" } });
		greek_gods = greek_gods->add_ordered(new Link{ {"Hera", "Greek", "A chariot drawn by peacocks", "Her intelligence"} });
		
		print_all(norse_gods);
		print_all(greek_gods);
	}
	catch (const std::runtime_error &rte)
	{
		std::cerr << "Runtime error: " << rte.what() << '\n';
		keep_window_open();
		return 1;
	}
	catch (const std::exception &e)
	{
		std::cerr << "Exception: " << e.what() << "\n";
		keep_window_open();
		return 2;
	}
	catch (...)
	{
		std::cerr << "An unknown exception occurred\n";
		keep_window_open();
		return 3;
	}

	keep_window_open();
}
Last edited on
Because putting inside or before the loop didn't work and my manual test seemed to show that putting it after the loop would work.


Now was that so hard?

Hopefully you now have at least a little bit of an idea of how to troubleshoot problems. Remember you need to first understand the problem, then start to design the program to solve that problem, using things like flowcharts and pseudo code to aid in the design. Once you have designed the code, and not before, it is time to start writing the code.
Yeah, but how do I define the class' destructor now? I know I have to go to the end of the list delete each node while going back to the head. But what I tried to do just now didn't work. And I need to do this because right now the program leaks memory.

Here's what I have right now:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Link::~Link()
{
	Link *trav = this;
	if (trav && trav->m_succ && trav->m_prev)
	{
		while (trav->m_succ)
		{
			trav = trav->m_succ;
		}

		while (trav->m_prev)
		{
			trav = trav->erase();
			trav = trav->m_prev;
		}
	}
	delete this;
}


And in case it's needed, here's the class definition again:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Link
{
public:
	Link(const God &god, Link *p = nullptr, Link *s = nullptr)
		: m_god{ god }, m_prev{ p }, m_succ{ s } { }
	~Link();
	Link *insert(Link *n);                              // insert n before this object
	Link *add(Link *n);                                 // insert n after this object
	Link *erase();                                      // remove this object from list
	Link *find(const std::string &name);                // find values in list
	const Link *find(const std::string &name) const;    // find values in const list
	Link *advance(int n) const;                         // advance n positions in list
	Link *add_ordered(Link *n);							// insert n in its correct lexicographical position

	God god() const { return m_god; }
	Link *next() const { return m_succ; }
	Link *previous() const { return m_prev; }

private:
	God m_god;
	Link *m_prev;
	Link *m_succ;
};


So yeah, how do I delete all of the nodes and free the memory?
Pages: 1... 89101112... 16