Problems with stack !

[WILL]

I'm reading the book "Data Structures And Program Design In C++". Just chapter 2 "stack".
The exercise is :
- write 3 function : void clear(), bool full() const, int size() const, and copy_stack(Stack &destination, Stack &source)
I've already done those but I'm not sure am I right or not.The one that confused me is the function "copy_stack" because as I know when we need to assign an object to another we have to use "overloading operator '=' ". But when I tried something like this :
[syntax="cpp"]
Error_code copy_stack(Stack &destination, Stack &source)
{
destination = source;
}
[/syntax] It still works correctly.
I guess it's probably because I don't have data create on heap in my program. But am I right at this point ?

Here is the code that I tried:
Stack.h
[syntax="cpp"]
#include <iostream>
#include <cctype>
#include <iomanip>

using namespace std;

enum Error_code {success, fail, underflow, overflow};
const int maxstack = 10;
typedef char Stack_entry;


class Stack
{
public :
Stack();
bool empty() const;
bool full() const;
void clear();
int size() const;
Error_code pop();
Error_code top(Stack_entry &item) const;
Error_code push(const Stack_entry &item);
Error_code copy_stack(Stack &destination, Stack &source);
friend ostream& operator << (ostream &output , const Stack &obj);

private :
int count;
Stack_entry entry[maxstack];
};

/*Constructor initializes data*/
Stack::Stack()
{
count = 0;
for(int i = 0; i <= maxstack; i++)
{
entry[i] = '_';
}
}


Error_code copy_stack(Stack &destination, Stack &source)
{
destination = source;
}


ostream &operator << (ostream &output, const Stack &obj)
{
for (int i = 0; i < maxstack; i++)
{
output << setw(2) << obj.entry[i];
}
output << endl;

return output;
}


bool Stack::empty() const
{
bool outcome = true;
if (count > 0)
outcome = false;

return outcome;
}


bool Stack::full() const
{
bool outcome = false;
if (count >= maxstack)
outcome = true;

return outcome;
}


void Stack::clear()
{
count = 0;
}

int Stack::size() const
{
return count;
}


Error_code Stack::push(const Stack_entry &item)
{
Error_code outcome = success;

if (count >= maxstack)
outcome = overflow;
else
entry[count++] = item;

return outcome;
}


Error_code Stack::pop()
{
Error_code outcome = success;

if (count == 0)
outcome = underflow;
else
count--;

return outcome;
}


Error_code Stack::top(Stack_entry &item) const
{
Error_code outcome = success;
if (count == 0)
outcome = underflow;
else
item = entry[count-1];

return outcome;
}

int main()
{
Stack openings;
Stack tmp;
char symbol;
bool is_matched = true;

while(is_matched && (symbol = cin.get()) != '\n')
{
if (symbol == '{' || symbol == '(' || symbol == '[')
{
openings.push(symbol);
cout << openings << endl;
}
if (symbol == '}' || symbol == ')' || symbol == ']')
{
if(openings.empty())
{
cout << "Unmatched closing bracket " << symbol
<< "detected" << endl;

is_matched = false;
}
else
{
char match;
openings.top(match);
openings.pop();

is_matched = ( symbol == '}' && match == '{'
|| symbol == ']' && match == '['
|| symbol == ')' && match == '(' );

if(!is_matched)
cout << "Bad match " << match << symbol << endl;
}
}
}

if(openings.full())
{
cout << "Are you crazy !! man!, too full " << endl;
}

if(openings.empty())
{
cout << "Unmatched opening bracket(s) detected !" << endl;
}

copy_stack(tmp, openings);
cout << "The tmp obj" << endl;
cout << tmp;

system("pause");
return 0;
}
[/syntax]
About the function :
[syntax="cpp"]
void Stack::clear()
{
count = 0;
}[/syntax]
I did like this because I think after we close the program, all the data will be deleted (because we don't have data on heap) (just my objective thought). But I know there are still data on the array "entry", how can I delete all these entries ?
Any suggestion would be appreciated ! thanks !

[Alvaro]

[...]
I've already done those but I'm not sure am I right or not.The one that confused me is the function "copy_stack" because as I know when we need to assign an object to another we have to use "overloading operator '=' ". But when I tried something like this :
[syntax="cpp"]
Error_code copy_stack(Stack &destination, Stack &source)
{
destination = source;
}
[/syntax] It still works correctly.
I guess it's probably because I don't have data create on heap in my program. But am I right at this point ?

Yes, C++ provides a default copy constructor that just copies every data member in your class. This will not do what you want if you have pointers to data outside the class.

About the function :
[syntax="cpp"]
void Stack::clear()
{
count = 0;
}[/syntax]
I did like this because I think after we close the program, all the data will be deleted (because we don't have data on heap) (just my objective thought). But I know there are still data on the array "entry", how can I delete all these entries ?

You are also not constructing the objects when they are pushed. If Stack_entry were a type with non-trivial constructors and destructors, you would call the default constructor maxstack times when Stack is constructed, and maxstack destructors when Stack is destroyed, instead of doing it as required when you push or pop elements.

If you want to deal with constructors and destructors correctly, your code will get more complicated; you need to use "placement new". Here's an example:
[syntax="cpp"]#include <iostream>

class VCD { // Verbose Construction and Destruction
char c;

public:
VCD():c('_'){
std::cerr << "Default constructor called!\n";
}
VCD(VCD const &vcd):c(vcd.c){
std::cerr << "Copy constructor called!\n";
}
VCD(char c){
std::cerr << "Constructor from '" << c << "' called!\n";
}
~VCD(){
std::cerr << "Destructor called!\n";
}
};

int main(){
char raw_memory[10*sizeof(VCD)];
VCD *entry = reinterpret_cast<VCD *>(raw_memory);

for(int i=0;i<10;++i)
::new(static_cast<void*>(entry+i)) VCD('A'+i); // <-- Tricky!

for(int i=9;i>=0;--i)
entry[i].~VCD(); // <-- Yes, an explicit destructor call!
}

[/syntax]

[WILL]

Because the book mentioned "reusability" of class, that's why I did according to the book's style. I understand that :

typedef char Stack_entry;

using "typedef" in this way will help me to reuse this program if I want to change to another type of data. But I really don't know there's influences in constructor and destructor.

You are also not constructing the objects when they are pushed. If Stack_entry were a type with non-trivial constructors and destructors, you would call the default constructor maxstack times when Stack is constructed, and maxstack destructors when Stack is destroyed, instead of doing it as required when you push or pop elements.

- But I still didn't get this point yet.
- I think I'd rather tell you what I thought first and then you correct me is better ^^ :

You are also not constructing the objects when they are pushed.

When we create an object, the constructor is automatically called ?

f Stack_entry were a type with non-trivial constructors and destructors, you would call the default constructor maxstack times when Stack is constructed, and maxstack destructors when Stack is destroyed, instead of doing it as required when you push or pop elements.

Why did it call "maxstack" times ? I really confused this point.
I think I had my constructor declared here :
[syntax="cpp"]
Stack::Stack()
{
count = 0;
for(int i = 0; i <= maxstack; i++)
{
entry[i] = '_';
}
} [/syntax]
Is it default constructor that you mentioned ? Because I thought "default constructor" is implicitly called if we don't declare the constructor ? But I declared it
So like you said "If Stack_entry were a type with non-trivial constructors and destructors ". If I use non-trivial type for class, the destructor and constructor have to change accordingly ?
I will read your code now and I will ask where I stuck ! Thanks a lot Alvaro !

[ventsyv]

Let me try to explain about constructors. Lets look at your Stack class first. Stack::Stack() is your default constructor, because it has no arguments.
You can have additional constructors. For example:

Code: Select all

Stack::Stack(char default)
{
    count = 0;
    for(int i = 0; i <= maxstack; i++)
    {
        entry[i] = default;
    }
}

// now you can do this:

Stack myStack('K');


If you have constructor such as Stack::Stack(char) you'll have to call it explicitly, while your default one is called implicitly, for example here:

Code: Select all

Stack myStack;


Built in types (char, int, etc) do not have constructors, but they do support the constructor syntax for consistency. For example you can declare a char like this:

Code: Select all

char myChar('B');


Now lets assume your Stack needs to handle more complicated objects that also need to be constructed (as opposed to simple chars which do not). In your Stack::Stack() you'll need to construct each "space" in your stack.

Code: Select all

//since Stack_entry == char no Stack_entry::Stack_entry() are needed here
Stack_entry entry[maxstack];


What Al is doing in his own crazy obscure way is this:

Code: Select all

Stack::Stack()
{
   count = 0;
    for(int i = 0; i <= maxstack; i++)
    {
        entry[i] = new char('A'); //given that we have such constructor for our datatype
    }
}

Hope that helps ...

[Alvaro]

Because the book mentioned "reusability" of class, that's why I did according to the book's style. I understand that :

typedef char Stack_entry;

using "typedef" in this way will help me to reuse this program if I want to change to another type of data. But I really don't know there's influences in constructor and destructor.

The typedef part was fine. A template is probably a better way to do it, but it's complicated and I understand that you have to learn things in some order.

- I think I'd rather tell you what I thought first and then you correct me is better ^^ :

You are also not constructing the objects when they are pushed.

When we create an object, the constructor is automatically called ?

Yes.

f Stack_entry were a type with non-trivial constructors and destructors, you would call the default constructor maxstack times when Stack is constructed, and maxstack destructors when Stack is destroyed, instead of doing it as required when you push or pop elements.

Why did it call "maxstack" times ? I really confused this point.

Because when you create an array of objects, all the objects in the array are constructed.

I think I had my constructor declared here :
[syntax="cpp"]
Stack::Stack()
{
count = 0;
for(int i = 0; i <= maxstack; i++)
{
entry[i] = '_';
}
} [/syntax]
Is it default constructor that you mentioned ? Because I thought "default constructor" is implicitly called if we don't declare the constructor ? But I declared it

As ventsyv said, the constructor that takes no arguments is the default constructor, even if you define your own.

So like you said "If Stack_entry were a type with non-trivial constructors and destructors ". If I use non-trivial type for class, the destructor and constructor have to change accordingly ?

No, I am talking about the constructor and the destructor of the type Stack_entry.

What Al is doing in his own crazy obscure way is this:

Code: Select all

Stack::Stack()
{
   count = 0;
    for(int i = 0; i <= maxstack; i++)
    {
        entry[i] = new char('A'); //given that we have such constructor for our datatype
    }
}

Except that code will do something very different. When you use `new' like you just did, it allocates memory in the heap and then constructs the object there. But in the case of his stack class, he has an array already "allocated", and if he wants to construct and destruct things on it, he has to use the obscure syntax that I posted earlier.

If you ever try to implement std::vector on your own, you'll feel the need for that construction (placement new).

[WILL]

-Thanks ventsyv ! I got the point now, default constructor is the constructor which have no parameter(s).

-I lost with your idea, Alvaro! I tried to understand it but I couldn't. I looked up in google and understand only a few parts of your code. For example :
[syntax="cpp"]
char raw_memory[10*sizeof(VCD)];
//Allows any pointer to be converted into any other pointer type.
VCD *entry = reinterpret_cast<VCD *>(raw_memory);[/syntax]
I tried to explain that :
First, you created a array of character named "raw_memory" with the size of object from class VCD. Then you created a pointer object "entry". And on the right side of assignment, you converted the pointer which point to the address of "raw_memory". And then the next line which you implied "tricky" :
[syntax="cpp"]
for(int i=0;i<10;++i)
::new(static_cast<void*>(entry+i)) VCD('A'+i); // <-- Tricky! [/syntax]
I completely lost at this point!! I don't really know what did you do here? [syntax="cpp"]
for(int i=9;i>=0;--i)
entry[i].~VCD(); [/syntax]
Why do we have to call it explicitly ? I think this question would probably the most stupid one ^^ but I do want understand it !!!
Another thing is your class VCD:
[syntax="cpp"]
VCD():c('_')
{
std::cerr << "Default constructor called!\n";
}
[/syntax] Here I got it, you just use the "initializer" to initialize for data, I read over this part in the book. They said we use this method for "const data member", but I guess you wanna use it for short, I will try to familiar with this style.
[syntax="cpp"]
VCD(const VCD &vcd):c(vcd.c)
{
std::cerr << "Copy constructor called!\n";
}
[/syntax]
Because your original code is "VCD" before const, so at first I was a little confused, ;however, I changed it back and forth and figured out it worked the same way. I got this syntax too.


[syntax="cpp"]
VCD(char c)
{
std::cerr << "Constructor from '" << c << "' called!\n";
}
[/syntax]
About this constructor, I don't know what kind of constructor is it ? I guess it's also an overloading constructor but I don't really understand what this constructor use for ?



[syntax="cpp"]
~VCD()
{
std::cerr << "Destructor called!\n";
}[/syntax]
I got this point.

Quote:
Quote:
f Stack_entry were a type with non-trivial constructors and destructors, you would call the default constructor maxstack times when Stack is constructed, and maxstack destructors when Stack is destroyed, instead of doing it as required when you push or pop elements.
Why did it call "maxstack" times ? I really confused this point.

Because when you create an array of objects, all the objects in the array are constructed.

As you said here. So it means whenever I have "array" data member I have to use your idea if I want to deal with constructor and destructor correctly ? Or it's because I used "non-trivial" type ? I suppose if I purely declared a fix type for my data and then eliminate the "typedef" method, do I have to use this method ?

The typedef part was fine. A template is probably a better way to do it, but it's complicated and I understand that you have to learn things in some order.

I've already read about "template" but it's just complete theory. Because I haven't felt confident with class and object yet, so I save it^^! I will try to lean it soon. I have two weeks off from school now hihi
And here all I tried to integrate your idea into my code :
[syntax="cpp"]
Stack():count(0);
{
for(int i = 0; i < maxstack; i++)
entry[i] = '_';

cerr << "Default constructor called !\n";
}

Stack(const Stack &obj):count(obj.count)
{
for(int i = 0; i <= maxstack; i++)
{
entry[i] = obj.entry[i];
}
cerr << "Copy constructor called !\n";
}
[/syntax]
Just 2 constructor, the third one I got stuck because the one you gave me, date member is only a character, so I lost because I don't understand the code of the "main" ! Could you show me how to do it ? Thanks !

[Alvaro]

The general idea of what my code does is to take a chunk of memory (the char array) and construct and destruct objects on it explicitly. It is advanced wizardry, so feel perfectly fine if you don't understand it now. You can come back to it in a year, after you are familiar with all the more common ways of using C++.

The key words to understand what the "tricky" line does are "placement new". http://www.parashift.com/c++-faq-lite/d ... #faq-11.10

The code you posted at the end is hilarious. It seriously lies about what has been called. Those "<blah> constructor called" messages were there to try to clarify how the program I posted works, but yours doesn't work the same way. Working with a data type that is very verbose about being constructed or destructed is a good way to test your understanding of when those operations happen.

[WILL]

w. You can come back to it in a year, after you are familiar with all the more common ways of using C++.

So for now, I've just accepted the code in the book and come back with it later !
Today, I've just written a program to solve "Knapstack" problem, I've just wanted tried to use all the things that you taught me to practice with class and object. It run with no errors but when I enter data it doesn't show the result instead of something which quickly appeared and then disappeared and it give me the file.exe.core, could you help me with this one? I means just some suggestion and I will debug myself ^^:
I used to method here : one is dynamic programming, other is greedy. Here's all I tried :
[syntax="cpp"]
#include <iostream>
#include <string>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <algorithm> //sort function
using namespace std;


class Knapstack
{
public :

Knapstack(int number_of_items, int weight_of_bag);
~Knapstack();

//Copy constructor
Knapstack::Knapstack(Knapstack &copy_object);
//overloading operator "="
const Knapstack &operator = (Knapstack &);

/*method for greedy*/
void Solving_by_greedy();
void SortItems();

/*method for dynamic programming*/
void Solving_by_dynamic_programming();
void Dynamic_programming_trace_solution();
friend istream &operator >> (istream &, Knapstack &);


private :

int weight_of_bag;
int number_of_items;

//data information
int *items_No;
int *items_value;
int *items_weight;
//solution array
float *greedy_solution;
int **dynamic_solution;
};


Knapstack::Knapstack(int number_of_items, int weight_of_bag)
:number_of_items(number_of_items), weight_of_bag(weight_of_bag)
{
greedy_solution = new float[number_of_items+1];
items_No = new int[number_of_items+1];
items_value = new int[number_of_items+1];
items_weight = new int[number_of_items+1];


int **dynamic_solution = new int *[number_of_items+1];
for(int x = 0; x <= number_of_items; x++)
{
dynamic_solution[x] = new int[weight_of_bag+1];
}

for(int i = 0; i <= number_of_items; i++)
{
*(items_No + i) = 0;
*(items_value + i) = 0;
*(items_weight + i) = 0;
*(greedy_solution + i) = 0.0;
}

for(int i = 0; i <= number_of_items; i++){
for(int j = 0; j <= weight_of_bag; j++){
dynamic_solution[i][j] = 0;
}
}
}


//Destructor
Knapstack::~Knapstack()
{
delete[] greedy_solution;

delete[] items_No;
delete[] items_value;
delete[] items_weight;

for(int x = 0; x <= number_of_items; x++){
delete[] dynamic_solution[x];
}
delete[] dynamic_solution;
}


//Copy constructor
Knapstack::Knapstack(Knapstack &copy_object)
:number_of_items(copy_object.number_of_items), weight_of_bag(copy_object.weight_of_bag)
{
greedy_solution = new float[number_of_items+1];
items_No = new int[number_of_items+1];
items_value = new int[number_of_items+1];
items_weight = new int[number_of_items+1];

for(int i = 0; i <= number_of_items; i++)
{
*(items_No + i) = copy_object.items_No[i];
*(items_value + i) = copy_object.items_value[i];
*(items_weight + i) = copy_object.items_weight[i];
*(greedy_solution + i) = copy_object.greedy_solution[i];
}


int **dynamic_solution = new int *[number_of_items+1];
for(int x = 0; x <= number_of_items; x++)
{
dynamic_solution[x] = new int[weight_of_bag+1];
}

for (int x = 0; x <= number_of_items; ++x)
{
for ( int y = 0; y <= weight_of_bag; ++y )
{
dynamic_solution[x][y] = copy_object.dynamic_solution[x][y];
}
}
}

const Knapstack &Knapstack::operator = (Knapstack &obj)
{
if (&obj != this)
{
if((number_of_items != obj.number_of_items) || (weight_of_bag != obj.weight_of_bag))
{
delete[] items_No;
delete[] items_value;
delete[] items_weight;
delete[] greedy_solution;

for( int x = 0; x <= number_of_items; x++){
delete[] dynamic_solution[x];
}
delete[] dynamic_solution;
}


items_No = new int[number_of_items+1];
items_value = new int[number_of_items+1];
items_weight = new int[number_of_items+1];
greedy_solution = new float[number_of_items+1];

for(int i = 0; i <= number_of_items; i++)
{
*(items_No + i) = obj.items_No[i];
*(items_value + i) = obj.items_value[i];
*(items_weight + i) = obj.items_weight[i];
*(greedy_solution + i) = obj.greedy_solution[i];
}

dynamic_solution = new int*[number_of_items+1];
for(int i = 0; i <= number_of_items; i++)
{
dynamic_solution[i] = new int[weight_of_bag];
}
for (int i = 0; i <= number_of_items; i++)
{
for (int j = 0; j <= weight_of_bag; j++)
{
dynamic_solution[i][j] = obj.dynamic_solution[i][j];
}
}
}
return *this;
}


istream &operator >> (istream &input, Knapstack &obj)
{
cout << "The number of items : \n";
input >> obj.number_of_items;
cout << "The maximum capacity of bags : \n";
input >> obj.weight_of_bag;

for(int i = 1; i <= obj.number_of_items; i++)
{
cout << " The [" << i << "] item weigh : ";
input >> obj.items_weight[i];
cout << " Its value is : ";
input >> obj.items_value[i];
cout << endl;
}

return input;
}

void Knapstack::SortItems()
{
for(int i = 1; i <= number_of_items ; i++)
{
for(int j = 1;j <= number_of_items; j++)
{
if(((float)items_value[i]/items_weight[i]) < ((float)items_value[i+1]/items_weight[i+1]))
{
swap(items_weight[i], items_weight[i+1]);
swap(items_value[i], items_value[i+1]);
}
}
}
}


void Knapstack::Solving_by_greedy()
{
int i;
float max_profit = 0.0;

SortItems();

for(i = 1; i < number_of_items; i++)
{

if(items_weight[i] > weight_of_bag)
break;

greedy_solution[i] = 1.0;

weight_of_bag = weight_of_bag - items_weight[i];
max_profit += items_value[i];

cout << "\n Items chosen : "<< items_No[i]
<< "with the % quantiy %:" << greedy_solution[i] << endl;

}


if(i <= number_of_items)
{
greedy_solution[i] = (float)weight_of_bag/items_weight[i];
cout << "\n" << items_No[i] << "with the quantiy % chosen : " << greedy_solution[i] << endl;
max_profit = max_profit + (greedy_solution[i]*items_value[i]);
}
cout << "\n Maximum value the thief can get : " << max_profit;
}


void Knapstack::Solving_by_dynamic_programming()
{
for (int i = 1; i <= number_of_items; i++)
{
for (int j = 0; j <= weight_of_bag; j++)
{
dynamic_solution[i][j] = dynamic_solution[i-1][j];
if (j >= items_weight[i] && dynamic_solution[i][j] < dynamic_solution[i-1][j-items_weight[i]] + items_value[i] )
{
dynamic_solution[i][j] = dynamic_solution[i-1][j-items_weight[i]] + items_value[i];
}
}
}
}

void Knapstack::Dynamic_programming_trace_solution()
{
cout << "Maximum value the thief can get : "
<< dynamic_solution[number_of_items][weight_of_bag] << endl;

while (number_of_items != 0)
{
if(dynamic_solution[number_of_items][weight_of_bag] != dynamic_solution[number_of_items-1][weight_of_bag])
{
cout << "Chosen items are : " << number_of_items;
weight_of_bag = weight_of_bag - items_weight[number_of_items];
}
number_of_items--;
}
}

void Menu()
{
Knapstack problem(1,1);
cout << "\nInformation data\n";
cin >> problem;
int command;
cout << "Enter a method for solving knapstack problems [1].Greedy\n"
<< "[2].Dynamic programming\n" << endl;
cin >> command;


if (command == 1)
{
problem.Solving_by_greedy();
}
else
{
problem.Solving_by_dynamic_programming();
problem.Dynamic_programming_trace_solution();
}
}

int main()
{
Menu();
system("pause");
return 0;
}
[/syntax]
I opened the file.core.exe with notepad, it had this message :

[main] KnapStackUseClass 1000 (0) exception: trapped!
[main] KnapStackUseClass 1000 (0) exception: code 0xC0000005 at 0x6105AFE2
[main] KnapStackUseClass 1000 (0) exception: ax 0x0 bx 0xA031630 cx 0xA dx 0x0
[main] KnapStackUseClass 1000 (0) exception: si 0x30 di 0xA031610 bp 0x246FE2C sp 0x246FE00
[main] KnapStackUseClass 1000 (0) exception: exception is: STATUS_ACCESS_VIOLATION
[main] KnapStackUseClass 1000 (1) stack: Stack trace:
[main] KnapStackUseClass 1000 (0) stack: frame 0: sp = 0x246F9F0, pc = 0x6100A2C3
[main] KnapStackUseClass 1000 (0) stack: frame 1: sp = 0x246FA2C, pc = 0x7C9037BF
[main] KnapStackUseClass 1000 (0) stack: frame 2: sp = 0x246FA50, pc = 0x7C90378B
[main] KnapStackUseClass 1000 (0) stack: frame 3: sp = 0x246FB00, pc = 0x7C90EAFA
[main] KnapStackUseClass 1000 (0) stack: frame 4: sp = 0x246FE2C, pc = 0x6101A4A7
[main] KnapStackUseClass 1000 (0) stack: frame 5: sp = 0x246FE3C, pc = 0x40E927
[main] KnapStackUseClass 1000 (0) stack: frame 6: sp = 0x246FEC4, pc = 0x401265
[main] KnapStackUseClass 1000 (0) stack: frame 7: sp = 0x246FEE4, pc = 0x4023D1
[main] KnapStackUseClass 1000 (0) stack: frame 8: sp = 0x246FF2C, pc = 0x4023F1
[main] KnapStackUseClass 1000 (0) stack: frame 9: sp = 0x246FF34, pc = 0x61004402
[main] KnapStackUseClass 1000 (0) stack: frame 10: sp = 0x246FF88, pc = 0x61004420
[main] KnapStackUseClass 1000 (0) stack: frame 11: sp = 0x246FF94, pc = 0x4144AE
[main] KnapStackUseClass 1000 (0) stack: frame 12: sp = 0x246FFA4, pc = 0x40103A
[main] KnapStackUseClass 1000 (0) stack: frame 13: sp = 0x246FFC0, pc = 0x7C816FD7
[main] KnapStackUseClass 1000 (0) stack: frame 14: sp = 0x246FFF0, pc = 0x0
[main] KnapStackUseClass 1000 (0) stack: End of stack trace

I already checked each algorithm by separate small program. It worked really fine ! But when I used class stuff....^^! Thanks !

[MXP]

The error implies that you've written past the bounds of one of your arrays.

[Alvaro]

The error implies that you've written past the bounds of one of your arrays.

Speaking of which, in the code you posted earlier, there was a place where you did exactly that:
[syntax="cpp"]
Stack::Stack()
{
count = 0;
for(int i = 0; i <= maxstack; i++)
{
entry[i] = '_';
}
} [/syntax]

In general, I don't know why you have number_of_items+1 ints in places like items_value or items_weight. If you have 10 items, you need 10 ints, not 11. Most of your loops should start at 0 and only continue while i<number_of_items (instead of <=).

[Alvaro]

I am not sure if this is your problem (probably not), but in operator= you have a line that says
[syntax="cpp"] dynamic_solution[i] = new int[weight_of_bag];[/syntax]
...and then you proceed to write to it using indices up to and including weight_of_bag.

Also, earlier in that function you seem to only delete all your member arrays if the size of the problem is different. But if it is the same, you are allocating new things and leaking the old ones.

This business of doing all the memory allocation and deallocation yourself is very error prone, and you should consider learning about std::vector and letting it do a lot of the dirty work for you.

Your SortItems method also accesses things out of bounds, plus its logic is sort of broken (you probably meant to loop over j first, then over i).

[WILL]

Thanks ! Finally I found the error^_^ ! I was so careless.

Your SortItems method also accesses things out of bounds, plus its logic is sort of broken (you probably meant to loop over j first, then over i).

thanks !
This is the first time I wrote too many codes like this so I will be more carefull next time

In general, I don't know why you have number_of_items+1 ints in places like items_value or items_weight. If you have 10 items, you need 10 ints, not 11. Most of your loops should start at 0 and only continue while i<number_of_items (instead of <=).

I did this because in dynamic programming, the array usually needs an extra space for some initial values, so I often save one space ( indice [0] ) for this purpose.

This business of doing all the memory allocation and deallocation yourself is very error prone, and you should consider learning about std::vector and letting it do a lot of the dirty work for you.

I'm reading it now !
By the way thanks collin !
This line is really annoying, haha :
[syntax="cpp"]
int **dynamic_solution = new int *[number_of_items+1]; [/syntax]

[ventsyv]

You might also be interested in reading about templates.
A good discussion on the topic here
By the way, the example used in the chapter I mentioned above deals with stacks, which is exactly what you were dealing with.

[WILL]

Thanks a lot ventsyv! The link you gave me is really helpful and interesting !