Ccac C++ 017 Linked Data Structures (Rq And Sum)

Front 1

1

Back 1

1

Front 2

1. Suppose your program contains the following type definitions:
struct Box
{
string name;
int number;
Box *next;
};
typedef Box* BoxPtr;
What is the output produced by the following code?
BoxPtr head;
head = new Box;
head->name = "Sally";
head->number = 18;
cout << (*head).name << endl;
cout << head->name << endl;
cout << (*head).number << endl;
cout << head->number << endl;

Back 2

1. Sally
Sally
18
18
Note that (*head).name and head->name mean the same thing. Similarly,
(*head).number and head->number mean the same thing.

Front 3

2. Suppose that your program contains the type definitions and code given in Self-Test
Exercise 1. That code creates a node that contains the string "Sally" and the number
18. What code would you add to set the value of the member variable next of this
node equal to NULL?

Back 3

2. The best answer is
head->next = NULL;
However, the following is also correct:
(*head).next = NULL;

Front 4

3. Given the following structure definition:
struct ListNode
{
string item;
int count;
ListNode *link;
};
ListNode *head = new ListNode;
Give code to assign the string "Wilbur's brother Orville" to the member variable
item of the variable to which head points.

Back 4

3. head->item = "Wilbur's brother Orville";

Front 5

4. Write type definitions for the nodes and pointers in a linked list. Call the node type
NodeType and call the pointer type PointerType. The linked lists will be lists of
letters.

Back 5

4. class NodeType
{
public:
NodeType( ){}
NodeType(char theData, NodeType* theLink)
: data(theData), link(theLink){}
NodeType* getLink( ) const { return link; }
char getData( ) const { return data; }
void setData(char theData) { data = theData; }
void setLink(NodeType* pointer) { link = pointer; }
private:
char data;
NodeType *link;
};
typedef NodeType* PointerType;

Front 6

5. A linked list is normally referred to via a pointer that points to the first node in the
list, but an empty list has no first node. What pointer value is normally used to represent
an empty list?

Back 6

5. The value NULL is used to indicate an empty list.

Front 7

6. Suppose your program contains the following type definitions and pointer variable
declarations:
struct Node
{
double data;
Node *next;
};
typedef Node* Pointer;
Pointer p1, p2;
Suppose p1 points to a node of the above type that is in a linked list. Write code
that will make p1 point to the next node in this linked list. (The pointer p2 is for
the next exercise and has nothing to do with this exercise.)

Back 7

6. p1 = p1-> next;

Front 8

7. Suppose your program contains type definitions and pointer variable declarations as
in Self-Test Exercise 6. Suppose further that p2 points to a node of the above type
that is in a linked list and which is not the last node on the list. Write code that will
delete the node after the node pointed to by p2. After this code is executed, the linked
list should be the same, except that there will be one less node in the linked list.
(Hint: You may want to declare another pointer variable to use.)

Back 8

7. Pointer discard;
discard = p2->next;//discard points to the node to be deleted.
p2->next = discard->next;
This is sufficient to delete the node from the linked list. However, if you are not using
this node for something else, you should destroy the node with a call to delete as
follows:
delete discard;

Front 9

8. Suppose your program contains the following type definitions and pointer variable
declarations:
class Node
{
public:
Node(double theData, Node* theLink)
: data(theData), next(theLink){}
Node* getLink( ) const { return next; }
double getData( ) const { return data; }
void setData(double theData) { data = theData; }
void setLink(Node* pointer) { next = pointer; }
private:
double data;
Node *next;
};
typedef Node* Pointer;
Pointer p1, p2;
Suppose p1 points to a node of the above type that is in a linked list. Write code
that will make p1 point to the next node in this linked list. (The pointer p2 is for
the next exercise and has nothing to do with this exercise.)

Back 9

8. p1 = p1->getLink( );

Front 10

9. Suppose your program contains type definitions and pointer variable declarations as in
Self-Test Exercise 8. Suppose further that p2 points to a node of the above type that is
in a linked list and which is not the last node on the list. Write code that will delete the
node after the node pointed to by p2. After this code is executed, the linked list should
be the same, except that there will be one less node in the linked list. (Hint: You may
want to declare another pointer variable to use.)

Back 10

9. Pointer discard;
discard = p2->getLink( );//points to node to be deleted.
p2->setLink(discard->getLink( ));
This is sufficient to delete the node from the linked list. However, if you are not using
this node for something else, you should destroy the node with a call to delete as
follows:
delete discard;

Front 11

10. Choose an ending to the following statement, and explain:
For a large array and a large list holding the same type objects, inserting a new
object at a known location into the middle of a linked list compared to insertion in
an array is
a. more efficient.
b. less efficient.
c. about the same.

Back 11

10. a. Inserting a new item at a known location into a large linked list is more efficient
than inserting into a large array. If you are inserting into a list, you have about five operations,
most of which are pointer assignments, regardless of the list size. If you insert
into an array, on the average you have to move about half the array entries to insert a
data item.
For small lists, the answer is c, about the same.

Front 12

11. Give the definition of the member function push of the template class Stack
described in Displays 17.13 and 17.15.

Back 12

11. Note that this function is essentially the same as
headInsert
in Display 17.11.
template<class T>
void Stack<T>::push(T stackFrame)
{
top = new Node<T>(stackFrame, top);
}

Front 13

12. Give the definition of the copy constructor for the template class Stack described in
Displays 17.13 and 17.15.

Back 13

12.
//Uses cstddef:
template<class T>
Stack<T>::Stack(const Stack<T>& aStack)
{
if (aStack.isEmpty( ))
top = NULL;
else
{
Node<T> *temp = aStack.top;//temp moves
//through the nodes from top to bottom of aStack.
Node<T> *end;//Points to end of the new stack.
end = new Node<T>(temp->getData( ), NULL);
top = end;
//First node created and filled with data.
//New nodes are now added AFTER this first node.
temp = temp->getLink( );//move temp to second node
//or NULL if there is no second node.
while (temp != NULL)
{
end->setLink(
new Node<T>(temp->getData( ), NULL));
temp = temp->getLink( );
end = end->getLink( );
}
//end->link == NULL;
}
}

Front 14

13. Give the definition of the overloaded assignment operator for the template class
Stack described in Displays 17.13 and 17.15.

Back 14

13. template<class T>
Stack<T>& Stack<T>::operator =(const Stack<T>& rightSide)
{
if (top == rightSide.top) //if two stacks are the same
return *this;
else //send left side back to freestore
{
T next;
while (! isEmpty( ))
next = pop( );//remove calls delete.
}
if (rightSide.isEmpty())
{
top = NULL;
return *this;
}
else
{
Node<T> *temp = rightSide.top;//temp moves through
//the nodes from front top to bottom of rightSide.
Node<T> *end;//Points to end of the left-side stack.
end = new Node<T>(temp->getData( ), NULL);
top = end;;
//First node created and filled with data.
//New nodes are now added AFTER this first node.
temp = temp->getLink();//Move temp to second node
//or set to NULL if there is no second node.
while (temp != NULL)
{
end->setLink(
new Node<T>(temp->getData(), NULL));
temp = temp->getLink();
end = end->getLink();
}
//end->link == NULL;
return *this;
}
}

Front 15

14. Give the definitions for the default (zero-argument) constructor and the member
functions Queue<T>::isEmpty for the template class Queue (Display 17.16).

Back 15

14. The following should be placed in the namespace QueueSavitch:
//Uses cstddef:
template<class T>
Queue<T>::Queue( ) : front(NULL), back(NULL)
{
//Intentionally empty.
}
//Uses cstddef:
template<class T>
bool Queue<T>::isEmpty( ) const
{
return (back == NULL);//front == NULL would also work
}

Front 16

15. Give the definitions for the member functions Queue<T>::add and
Queue<T>::remove for the template class Queue (Display 17.16).

Back 16

15. The following should be placed in the namespace QueueSavitch:
//Uses cstddef:
template<class T>
void Queue<T>::add(T item)
{
if (isEmpty( ))
front = back = new Node<T>(item, NULL);//Sets both
//front and back to point to the only node
else
{
back->setLink(new Node<T>(item, NULL));
back = back->getLink( );
}
}
//Uses cstdlib and iostream:
template<class T>
T Queue<T>::remove( )
{
if (isEmpty( ))
{
cout << "Error: Removing an item from an empty queue.\n";
exit(1);
}
T result = front->getData( );
Node<T> *discard;
discard = front;
front = front->getLink( );
if (front == NULL) //if you removed the last node
back = NULL;
delete discard;
return result;
}

Front 17

16. Give the definition for the destructor for the template class Queue (Display 17.16).

Back 17

16. The following should be placed in the namespace QueueSavitch:
template<class T>
Queue<T>::~Queue( )
{
T next;
while (! isEmpty( ))
next = remove( );//remove calls delete.
}

Front 18

17. Give the definition for the copy constructor for the template class Queue (Display
17.16).

Back 18

17. The following should be placed in the namespace QueueSavitch:
//Uses cstddef:
template<class T>
Queue<T>::Queue(const Queue<T>& aQueue)
{
if (aQueue.isEmpty( ))
front = back = NULL;
else
{
Node<T> *temp = aQueue.front;//temp moves
//through the nodes from front to back of aQueue.
back = new Node<T>(temp->getData( ), NULL);
front = back;
//First node created and filled with data.
//New nodes are now added AFTER this first node.
temp = temp->getLink( );//temp now points to second
//node or NULL if there is no second node.
while (temp != NULL)
{
back->setLink(new Node<T>(temp->getData( ), NULL));
back = back->getLink( );
temp = temp->getLink( );
}
//back->link == NULL
}
}

Front 19

18. Give the definition for the overloaded assignment operator for the template class
Queue (Display 17.16).

Back 19

18. The following should be placed in the namespace QueueSavitch:
//Uses cstddef:
template<class T>
Queue<T>& Queue<T>::operator =(const Queue<T>& rightSide)
{
if (front == rightSide.front)//if the queues are the same
return *this;
else //send left side back to freestore
{
T next;
while (! isEmpty( ))
next = remove( );//remove calls delete.
}
if (rightSide.isEmpty( ))
{
front = back = NULL;
return *this;
}
else
{
Node<T> *temp = rightSide.front;//temp moves
//through the nodes from front to back of rightSide.
back = new Node<T>(temp->getData( ), NULL);
front = back;
//First node created and filled with data.
//New nodes are now added AFTER this first node.
temp = temp->getLink( );//temp now points to second
//node or NULL if there is no second node.
while (temp != NULL)
{
back->setLink(
new Node<T>(temp->getData( ), NULL));
back = back->getLink( );
temp = temp->getLink( );
}
//back->link == NULL;
return *this;
}
}

Front 20

19. Write the definition of the template function inQ shown below. Use iterators. Use
the definition of Queue given in Display 17.20.
template<class T>
bool inQ(Queue<T> q, T target);
//Returns true if target is in the queue q;
//otherwise, returns false.

Back 20

19. using namespace ListNodeSavitch;
using namespace QueueSavitch;
template<class T>
bool inQ(Queue<T> q, T target)
{
Queue<T>::Iterator i;
i = q.begin( );
while ((i != q.end( )) && (*i != target))
i++;
return (i != q.end());
}
Note that the following return statement does not work, since it can cause a
dereferencing of NULL, which is illegal. The error would be a runtime error, not a
compiler error.
return (*i == target);

Front 21

20. Define the following member functions, which could be added to the class
SearchTree in Display 17.24. These functions display the data encountered in a
preorder and postorder traversal of the tree, respectively. Define a private helping
function for each function, as we did for SearchTree<T>::inorderShow.
void SearchTree<T>::preorderShow( ) const
void SearchTree<T>::postorderShow( ) const

Back 21

20. The template class SearchTree needs function declarations added. These are just the
definitions.
template<class T> //uses iostream:
void SearchTree<T>::preorderShow( ) const
{
preorderShow(root);
}
template<class T> //uses iostream:
void SearchTree<T>::preorderShow(
TreeNode<T>* subTreeRoot) const
{
if (subTreeRoot != NULL)
{
cout << subTreeRoot->data << " ";
preorderShow(subTreeRoot->leftLink);
preorderShow(subTreeRoot->rightLink);
}
}
template<class T> //uses iostream:
void SearchTree<T>::postorderShow( ) const
{
postorderShow(root);
}
template<class T> //uses iostream:
void SearchTree<T>::postorderShow(
TreeNode<T>* subTreeRoot) const
{
if (subTreeRoot != NULL)
{
postorderShow(subTreeRoot->leftLink);
postorderShow(subTreeRoot->rightLink);
cout << subTreeRoot->data << " ";
}
}

Front 22

A ___ is a struct or class object that has one or more member variables that are
pointer variables. These nodes can be connected by their member pointer variables
to produce data structures that can grow and shrink in size while your program is
running.

Back 22

node

Front 23

A ___ ___ is a list of nodes in which each node contains a pointer to the next
node in the list.

Back 23

linked list

Front 24

The end of a linked list (or other linked data structure) is indicated by setting the
pointer member variable equal to ___.

Back 24

NULL

Front 25

A ___ is a first-in/last-out data structure. A ___ is a first-in/first-out data structure.
Both can be implemented using a linked list.

Back 25

stack
queue

Front 26

An ___ is a construct (typically an object of some iterator class) that allows you
to cycle through data items stored in a data structure.

Back 26

iterator

Front 27

A ___ is a data structure whose nodes have two (or more) member variables for
pointers to other nodes. If a tree satisfies the Binary Search Tree Storage Rule, then
a function can be designed to rapidly find data in the tree.

Back 27

tree