C++

Forum

 
Nested class/Double-linked list confusion

phazed99 (21)
Hi everyone, we were provided all the following code and told to write the addLongInt() function. We are supposed to be adding numbers using a double-linked list. I understand double-linked list, however, I can't seem to understand the provide code at all. All I could add I knew wasn't completely wrong was LongInt sum and return sum. I feel like this would be a simple program without using his code (why do we need this nested class stuff?). My monkey brain is hurting and no one else in my group can figure it out either. Please help with as much explanation as possible. Thank you very much.

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
 
#include<iostream>
using namespace std;
class LongInt {
private:
	struct digit {
		int d_val;
		digit* more, * less;
	};
	struct Ibase {
		digit* most, * least;
	};
	Ibase _base;
	void zeroStrip();
public:
	LongInt();
	friend void printLongInt(LongInt);
	friend LongInt inputLongInt();
	friend LongInt addLongInt(LongInt, LongInt);
};
void LongInt::zeroStrip() {
	LongInt::digit* dptr = _base.most;
	LongInt::digit* extra = 0;
	while ((!dptr->d_val) && dptr->less) {
		extra = dptr;
		_base.most = dptr->less;
		dptr = dptr->less;
		dptr->more = 0;
	}
}
LongInt::LongInt() {
	_base.most = _base.least = new digit;
	_base.most->d_val = 0;
	_base.most->more = _base.most->less = 0;
};
void printLongInt(LongInt LIval) {
	LongInt::digit* dptr = LIval._base.most;
	while (dptr) {
		cout << dptr->d_val;
		dptr = dptr->less;
	}
}
LongInt inputLongInt() {
	LongInt returnValue;
	int inValue;
	LongInt::digit* dptr = 0;
	LongInt::digit* inputList = 0;
	inputList = returnValue._base.least;
	inValue = cin.get();
	while ('0' <= inValue && inValue <= '9') {
		dptr = new LongInt::digit;
		dptr->d_val = inValue - '0';
		dptr->less = 0;
		dptr->more = inputList;
		returnValue._base.least = dptr;
		inputList->less = dptr;
		inputList = dptr;
		inValue = cin.get();
	}
	returnValue.zeroStrip();
		return returnValue;
}
LongInt addLongInt(LongInt s1, LongInt s2) {
	LongInt sum;

	return sum;
}
int main() {
	LongInt summand1, summand2, sum;
	cout << "-> " << flush;
	summand1 = inputLongInt();
	cout << "-> " << flush;
	summand2 = inputLongInt();
	cout << "\n-----\n";
	sum = addLongInt(summand1, summand2);
	printLongInt(sum);
	cout << endl;
}
jonnin (11442)
you don't need nested objects of this kind here, but you have to use what you have been given, probably. Not everything people do is necessary or awesome.

to add 2 things just add and carry like you did in the first grade..
123456789990
999933344112
-----------------
add 0 and 2, get 2, carry = 0.
add 9 and 1, get 0, carry 1.
add 9,1, and carry get 1, carry 1
...
if its a list you iterate the lists to get the digits.
Last edited on
seeplus (6597)
The first issue is that the provided code doesn't have a destructor - so there are memory leaks! The second issue is that neither copy constructor nor copy assignment are provided. If they are not needed, than at least set them as deleted - otherwise if used there will be problems!

(PS. They are indeed needed. As provided, the code has serious issues as the used copy constructor is being done using a shallow copy rather than a required deep copy. This is a big problem).

The provided code IMO is quite poor!!

There is no need for Ibase which IMO just complicates the code!

In terms of double linked lists and usual names:

struct digit is a node.
d_val is the value
more is a pointer one way to the next digit(node)
less is a pointer the other way to the previous digit

Ibase.most is a pointer to one end of the list
Ibase.least is a pointer to the other end of the list

To iterate the list one way, start at Ibase.most and follow the .less pointers.
To iterate the other way, start at Ibase.least and follow the .more pointers.

There is no provided code to add a node to the list. I'd suggest this as a possible first start. Once you can add a new node at Ibase.most, then you can start coding addLongInt() based upon jonnin's post above.

Last edited on
seeplus (6597)
After fixing issues with the original code and adding some extra functions, operators etc, perhaps consider:

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
160
161
162
163
164
165
166
167
168
169
 
#include <iostream>
#include <algorithm>

class LongInt {
	struct digit {
		int d_val {};
		digit *more {}, *less {};

		digit() {}
		digit(int d) : d_val(d) {}
	};

	struct Ibase {
		digit *most {}, *least {};

		Ibase() {}
	};

	Ibase _base;
	void zeroStrip();

public:
	LongInt();
	~LongInt();

	LongInt(const LongInt&);
	LongInt& operator=(LongInt);

	void addLeast(int v);
	void addMost(int v);
	LongInt& swap(LongInt&);

	friend void printLongInt(const LongInt&);
	friend void printReverse(const LongInt&);
	friend LongInt inputLongInt();
	friend LongInt addLongInt(const LongInt&, const LongInt&);

	friend std::ostream& operator<<(std::ostream& os, const LongInt&);
	friend LongInt operator+(const LongInt&, const LongInt&);
};

std::ostream& operator<<(std::ostream& os, const LongInt& li)
{
	for (auto dptr {li._base.most}; dptr; dptr = dptr->less)
		os << dptr->d_val;

	return os;
}

LongInt operator+(const LongInt& s1, const LongInt& s2)
{
	return addLongInt(s1, s2);
}

LongInt& LongInt::swap(LongInt& li)
{
	std::swap(li._base.least, _base.least);
	std::swap(li._base.most, _base.most);

	return *this;
}

LongInt& LongInt::operator=(LongInt li)
{
	swap(li);

	return *this;
}

LongInt::~LongInt()
{
	while (_base.most) {
		auto t {_base.most->less};
		delete _base.most;
		_base.most = t;
	}
}

LongInt::LongInt(const LongInt& li)
{
	for (auto n = li._base.most; n; n = n->less)
		addLeast(n->d_val);
}

void LongInt::addLeast(int v)
{
	const auto nd {new digit(v)};

	if (_base.least) {
		_base.least->less = nd;
		nd->more = _base.least;
	} else
		_base.most = nd;

	_base.least = nd;
}

void LongInt::addMost(int v)
{
	const auto nd {new digit(v)};

	if (_base.most) {
		_base.most->more = nd;
		nd->less = _base.most;
	} else
		_base.least = nd;

	_base.most = nd;
}

void LongInt::zeroStrip() {
	for (auto dptr = _base.most; !dptr->d_val && dptr->less; ) {
		_base.most = dptr->less;
		dptr = dptr->less;
		dptr->more = 0;
	}
}

LongInt::LongInt() {}

void printLongInt(const LongInt& LIval) {
	std::cout << LIval;
}

void printReverse(const LongInt& LIval)
{
	for (auto dptr {LIval._base.least}; dptr; dptr = dptr->more)
		std::cout << dptr->d_val;
}

LongInt inputLongInt() {
	LongInt li;

	for (char inValue = 0; std::cin.get(inValue) && ('0' <= inValue && inValue <= '9'); )
		li.addLeast(inValue - '0');

	li.zeroStrip();
	return li;
}

LongInt addLongInt(const LongInt& s1, const LongInt& s2) {
	LongInt sum;
	int carry {};

	for (auto s1p {s1._base.least}, s2p {s2._base.least}; s1p || s2p; (s1p ? s1p = s1p->more : nullptr), (s2p ? s2p = s2p->more : nullptr)) {
		const auto t {(s1p ? s1p->d_val: 0) + (s2p ? s2p->d_val : 0) + carry};

		carry = t / 10;
		sum.addMost(t % 10);
	}

	if (carry)
		sum.addMost(carry);

	return sum;
}

int main() {
	std::cout << "-> ";

	const auto summand1 {inputLongInt()};

	std::cout << "-> ";

	const auto summand2 {inputLongInt()};

	std::cout << "-----\n";
	std::cout << summand1 + summand2 << '\n';
}



-> 12345678
-> 9876
-----
12355554

Last edited on
phazed99 (21)
Thanks for the help. There is still a lot I have to learn. I really appreciate the response. Our group had to submit it yesterday. The following is what we ending up going with. Let me know what you think, I would love some criticism.

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
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
 
#include <iostream>
using namespace std;

struct dlink {
	int value;
	dlink* next;
	dlink* previous;
};

int main() {
	dlink* summand_one = 0;
	dlink* summand_two = 0;
	dlink* sum = 0;
	dlink* dlptr;
	dlink* current;
	int val = 0;
	//inputing summand one
	cout << "-> " << flush;
	val = cin.get();
	while ('0' <= val && val <= '9') {
		dlptr = new dlink;
		if (!summand_one)
		{
			dlptr->value = val - '0';
			dlptr->next = 0;
			dlptr->previous = 0;
			summand_one = dlptr;
			val = cin.get();
		}
		else
		{
			dlptr->value = val - '0';
			summand_one->next = dlptr;
			dlptr->previous = summand_one;
			dlptr->next = 0;
			summand_one = dlptr;
			val = cin.get();
		}
	}
	//inputing summand two
	cout << "-> " << flush;
	val = cin.get();
	while ('0' <= val && val <= '9') {
		dlptr = new dlink;
		if (!summand_two)
		{
			dlptr->value = val - '0';
			dlptr->next = 0;
			dlptr->previous = 0;
			summand_two = dlptr;
			val = cin.get();
		}
		else
		{
			dlptr->value = val - '0';
			summand_two->next = dlptr;
			dlptr->previous = summand_two;
			dlptr->next = 0;
			summand_two = dlptr;
			val = cin.get();
		}
	}
	//now for the actually adding
	int total = 0;
	int carry = 0;
	while (summand_one || summand_two)
	{
		//first time
		if (!sum)
		{
			dlptr = new dlink;
			total = summand_one->value + summand_two->value;
			if (total > 9)
			{
				carry++;
				total = total - 10;
			}
			dlptr->value = total;
			dlptr->next = 0;
			dlptr->previous = 0;
			summand_one = summand_one->previous;
			summand_two = summand_two->previous;
			sum = dlptr;
		}
		else
		{
			//if only summand1 is empty
			if (!summand_one && summand_two)
			{
				dlptr = new dlink;
				if (carry == 0)
				{
					total = summand_two->value;
				}
				else
				{
					total = summand_two->value + carry;
					carry--;
				}
				if (total > 9)
				{
					carry++;
					total = total - 10;
				}
				dlptr->value = total;
				summand_two = summand_two->previous;
				sum->previous = dlptr;
				dlptr->next = sum;
				dlptr->previous = 0;
				sum = dlptr;
			}
			//if only summand2 is empty
			else if (summand_one && !summand_two)
			{
				dlptr = new dlink;
				if (carry == 0)
				{
					total = summand_one->value;
				}
				else
				{
					total = summand_one->value + carry;
					carry--;
				}
				if (total > 9)
				{
					carry++;
					total = total - 10;
				}
				dlptr->value = total;
				summand_one = summand_one->previous;
				sum->previous = dlptr;
				dlptr->next = sum;
				dlptr->previous = 0;
				sum = dlptr;
			}
			//both still have nums
			else
			{
				dlptr = new dlink;
				if (carry == 0)
				{
					total = summand_one->value + summand_two->value;
				}
				else
				{
					total = summand_one->value + summand_two->value + carry;
					carry--;
				}
				if (total > 9)
				{
					carry++;
					total = total - 10;
				}
				dlptr->value = total;
				summand_one = summand_one->previous;
				summand_two = summand_two->previous;
				sum->previous = dlptr;
				dlptr->next = sum;
				dlptr->previous = 0;
				sum = dlptr;
			}
		}
	}
	//need to take care of last carry
	if (carry == 1)
	{
		dlptr = new dlink;
		dlptr->value = 1;
		sum->previous = dlptr;
		dlptr->next = sum;
		dlptr->previous = 0;
		sum = dlptr;
	}
	//print sum
	cout << "\n-----\n";
	dlptr = sum;
	while (dlptr)
	{
		cout << dlptr->value;
		dlptr = dlptr->next;
	}
	cout << endl;
	return 0;
}
jonnin (11442)
if it works and you learned something, its a winner :)

if you want nitpicks..
the lack of comments is bad. what does it do? how is it doing it? give some hints here and there.

magic numbers are usually frowned upon. If you must use them, say why.
eg line 153ish .. why is it 10? what is special about 10? (yes, I know, and yes, you know, but it needs a comment).

it is not really normal for main to do all the work. Its ok in a small program but normally you want to break things into functions and have main be quite simple. You may not know how to do that yet, and that is ok.

at a drive-by glance the blocks in the loop look similar, and there are better ways (eg, functions as I already said) to handle similar code than to copy it and make small changes over and over.

those last 2 ideas ... its very weird to tackle a linked list and not know how to write functions and factor code into reusable blocks.

finally, doing large numbers digit by digit is the slow, brute force way. can you think of any way to do more work per loop iteration? The computer knows how to add up to 64 bit values already, in the cpu hardware...
Last edited on
phazed99 (21)
Thanks for the tips. I took out most comments to make it look cleaner when I submitted it. My comments are always messy gibberish only I can understand. I have noticed other people using functions for everything. That's something I definitely need to work on.
seeplus (6597)
There is still a lot I have to learn.


Compare your approach to my code above - based upon the original supplied class.

In C++ nullptr is used to indicate a non-initialised pointer, not 0.
Topic archived. No new replies allowed.