C++

Forum

 
 
deleting the max element in queue

Heiru (7)
I have to delete the max element from the queue without using the queue library, arrays or anything like that. I'm positive the first two functions work like they supposed to but I'm not sure about the del_max function. Also the program seems to just exit after printing the count. I'm not sure why this happens.

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

using namespace std;

void push(int n);
int pop(int& n);
int del_max(int m, int c);

struct elem
{
	int key;
	elem* next;
}*first = NULL, * last = NULL;

int main()
{
	int num;
	int count = 0;

	cout << "Enter elements to queue: " << endl;

	while (cin >> num)
		push(num);

	cout << "\n";

	while (pop(num))
	{
		cout << num << "  ";
		count++;
	}

	cout << "\n";

	cout << "The count is :" << " " << count << endl;
	
	while (del_max(num, count))
	{
		cout << num << "\t";
	}

	return 0;
}

void push(int n)
{
	elem* p = last;
	last = new elem;
	last->key = n;
	last->next = NULL;
	if (p != NULL)
		p->next = last;
	if (first == NULL)
	{
		first = last;
	}
}

int pop(int& n)
{
	if (first)
	{
		elem* p = first;
		n = first->key;
		first = first->next;
		delete p;
		return 1;
	}
	else
		return 0;
}

int del_max(int m, int c)
{
	if (first)
	{
		elem* p = first;
		elem* max = first;
		m = max->key;

		for (int i = 0; i <= c; i++)
		{
			p = p->next;

			if (p->key > max->key)
			{
				max->key = p->key;
			}
		}
		delete max;
		return 1;
	}
	else
		return 0;
}
Last edited on
jonnin (11437)
ok, you have a couple of issues. Also, please use code tags next time. 

1
2
3
4
5
6
 
if (p->key > max->key)
{
max->key = p->key;
}
}
delete max;


ok, if the list is
1,10,2,3,4
lets do it:)
first is 1, max is 1, blah blah
p is next, so p is 10
if(p value > max value) // it is
max-> key = p-> key //oops
ok so max is first. the list therefore is now
10,10,2,3,4 and your 1 went poof.

second, you ignore the linked listedness of the list.
if you have
1,10,2,3,4
you want your list to be, after delete max,
1,2,3,4
so you have to somehow say that
1-> next = 2
after deleting the 10. there are 3 cases here:
its the first one, in which case you can shuffle it but its easier to just assign
via tmp = first, first = first-> next, delete tmp type logic.
second, its the last one, in which case you can set the next to last one's next to null, decrement your counters, and as before use a temp to delete the last one.
and finally in the middle, you need to connect the previous node's next to the one after what is deleted.
you can simplify that in the code though, by exploiting null. If you want to do the pointer shuffles on last, for example, its fine. next to last = last-> next which is null, so next to last -> next becomes null automatically: its the same logic as in the middle of the list! That leaves just a special case for deleting the first one, which can reuse your pop function to make that super simple!

fix those 2 ideas (reconnecting in the middle & logic for first and assigning the key when you should not have) and you will get it; its getting close.

bonus points, you can greatly simplify all the logic but get it working as-is before you take that on.
Last edited on
Heiru (7)
I understand but im not sure if i executed that correctly.

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
 
int del_max(int m)
{
	if (first)
	{
		elem* p = first;
		elem* max = first;

		while (p->next != 0)
		{
			p = p->next;
			if (max->key < p->key)
				max = p;
		}
		elem* q = first;
		if (q = max)
			first = first->next;
		else
			while (q->next != max)
				q = q->next;
		q->next = max->next;
		m = max->key;
		delete max;
		return 1;
	}
	else
		return 0;
}


and i deleted the count from the main 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
 
int main()
{
	int num;

	cout << "Enter elements to queue: " << endl;

	while (cin >> num)
		push(num);

	cout << "\n";

	while (pop(num))
	{
		cout << num << "\t";
	}

	cout << "\n";

	while (del_max(num))
	{
		cout << num << "\t";
	}

	return 0;
}


the program still exits before while(del_max(num)), so i guess im still making a mistake and not seeing it.
lastchance (6980)
Hang on, having popped every element off the queue ... what is there left to find the maximum of?
Heiru (7)
sorry, where do i exactly delete all the elements?

1
2
3
4
 
while (pop(num))
	{
		cout << num << "\t";
	}


the function pop from the main function is this one:

1
2
3
4
5
6
7
8
9
10
11
12
13
 
int pop(int& n)
{
	if (first)
	{
		elem* p = first;
		n = first->key;
		first = first->next;
		delete p;
		return 1;
	}
	else
		return 0;
}


so it only deletes the first element, which is the letter you enter to stop the input.

Or are you talking about something entirely different?
Last edited on
ningfan666 (14)
The function "del_max(num)" return 0 directly , because before you call this function. All elements are deleted. There are no elements, so "if" will not execute at all. First of all, int pop(int& n) just deletes first element ,that's true,but you put this function to conditional part of "while" statement. That means every time you delete first element successfully, the function will return 1, and "while" statement will execute continuously until all elements are deleted. Because at that time, "if" statement in "int pop(int& n)" will not execute(because first is NULL),and "else" part will execute and return 0.Finally,all elements are not exist.
lastchance (6980)
Heiru wrote:
sorry, where do i exactly delete all the elements?


Well you wrote:
while (pop(num))
So you kept deleting all elements until there were none left!

Then you tried to find the maximum of no elements.

Old Mother Hubbard ...
Last edited on
Heiru (7)
Well, this was how we were taught to do so i just did it like that...
I finally finished it and it works. Thank you everyone!
seeplus (6591)
Possibly:

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

struct elem {
	int key {};
	elem* next {};
	elem(int k) : key(k) {}
};

void push(int n);
bool pop(int& n);
bool del_max(int& m);
void display(const elem* node);

elem *first {}, *last {};

int main() {
	size_t count {};

	std::cout << "Enter elements to queue: ";

	for (int num; std::cin >> num; ++count)
		push(num);

	std::cout << "\nThe count is : " << count << '\n';
	display(first);

	//for (int n {}; pop(n); std::cout << n << ' ');
	//std::cout << '\n';

	for (int num {}; del_max(num); )
		std::cout << num << "  ";

	std::cout << '\n';
}

void display(const elem* node) {
	for (; node; node = node->next)
		std::cout << node->key << ' ';

	std::cout << '\n';
}

void push(int n) {
	auto p { last };

	last = new elem(n);

	if (p != nullptr)
		p->next = last;

	if (first == nullptr)
		first = last;
}

bool pop(int& n) {
	if (first) {
		elem* p { first };

		n = first->key;
		first = first->next;
		delete p;
		return true;
	}

	return false;
}

bool del_max(int& m) {
	if (first) {
		auto max { first };
		elem* maxprev {};

		for (elem *p { first }, *prev {}; p; prev = p, p = p->next)
			if (p->key > max->key) {
				max = p;
				maxprev = prev;
			}

		m = max->key;

		// remove max node here
		if (maxprev != nullptr)
			maxprev->next = max->next;
		else
			first = max->next;

		if (max->next == nullptr)
			last = maxprev;

		delete max;
		return true;
	}

	return false;
}


NB. After posting I see the OP has now got it work!
Last edited on
Topic archived. No new replies allowed.