159.201 Algorithms & Data Structures Tutorial 4
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
159.201 Algorithms & Data Structures
Tutorial 4
Answers
1. Write a C++ method to the template class List called Reverse(). This operation reverses the items in the list (so that the first item becomes the last item).
Answer:
template <class T>
bool List<T>::Reverse() {
Node * temp1, *temp2;
current = front>next;
temp2=front;
while (current != NULL){
temp1=current>next;
current>next = front;
front = current;
current=temp1;
}
temp2>next=NULL;
}
2. Write a C++ method to the template class List called MakeCopy(List &L). This copies all items in the list into the corresponding positions in list L. Thus L will be a copy of the current list.
Answer:
template <class T>
bool List<T>::MakeCopy(List &L){
Node * temp;
temp=front;
while(temp!=NULL){
L .AddtoFront(temp>data);
temp=temp>next;
}
}
3. Modify the template class List to create a bi-directional list. Each node then has a next pointer and a previous pointer and the list requires a front pointer and a rear pointer. This will then allow a programmer to move up or down the list in either direction.
Add a suitable method to the class called PreviousItem(), which will get the item before the current pointer.
Answer:
template <class T>
class List {
private:
struct Node {
T data;
Node *next;
Node *previous;
};
Node *front, *current, *rear;
…
}
…
template <class T>
bool List<T>::PreviousItem(T & item) {
if (current == NULL) { return false; }
current = current>previous;
if (current == NULL) { return false; }
item = current>data;
return true;
}
4. Discuss the implications of implementing code to solve assignment 4 using one digit per node of the linked-list of the class List, when the data on the node it type char. Discuss also what happens if you change the type to: unsigned char, int .
Answer:
With any C/C++ type there is some waste of memory. Every node contains a value between 0 to 9 (base 10), so even with a type of one byte some waste occur. In practice libraries for arbitrary size numbers use base 232 or 264, so every single bit of the data structure is used.
5. Write the declaration of the class BigNumber. You need to include a list (private) , and declare the methods (public) for the class.
Answer:
class BigNumber {
private:
List<int> listofdigits;
public:
BigNumber();
~BigNumber();
void ReadFromString(string decstring );
void PrintBigNumber();
void AddBigNumbers(BigNumber B1,BigNumber B2);
};
6. Consider that you have two bignumbers in the form of a List. Write an algorithm to add the two big numbers (pseudo-code). Answer:
Create Number1, Number2, Number3;
Store digits into Number1, Number2;
AddBigNumbers{
carry=0;
digit1 = FirstItem of Number1;
digit2 = FirstItem of Number2;
while( digit1 is valid OR digit2 is valid){
partialres = digit1 + digit2 + carry;
AddtoFront(partialres%10) to Number3
if (partialres <= 9) carry=0;
else carry = integer part of (partialres/10);
digit1 = NextItem of Number1;
digit2 = NextItem of Number2;
}
if (carry!=0) AddtoFront(carry) to List3;
}
7. Discuss how this algorithm would be implemented as a function or as a method of the big number class.
Answer: As a function, the List methods should be used. Therefore the function should pass three arguments, Number1, Number2 and Number3, and then call Number .listofdigits .AddtoFront()or
Number .listofdigits .NextItem().
e.g., AddBigNumbersFunction( BigNumber Number1, BigNumber Number2, BigNumber Number3){}
If the algorithm is implemented as a method of the bignumber, then the list of at least one of them is accessible internally. The method could, for example, accept two arguments (Number 1 and Number 2) and add nodes directly accessing the private listofdigits on Number 3.
e.g., BigNumber::AddBigNumbersMethod( BigNumber Number1, BigNumber Number2){
…
//at some point, get next digits from Number2:
Number2 .listofdigits .NextItem();
//at some point, add digits to Number3:
listofdigits .NextItem(); //No explicit reference to number 3 in the method
…
}
2023-04-13