Implement the following function as a new function for the linked list
toolkit. (Use the usual node definition with member variables called
data and link.)
size_t count_42s(const node* head_ptr);
// Precondition: head_ptr is the head pointer of a linked list.
// The list might be empty or it might be non-empty.
// Postcondition: The return value is the number of occurrences
// of 42 in the data field of a node on the linked list.
// The list itself is unchanged.
Implement the following function as a new function for the linked list
toolkit. (Use the usual node definition with member variables called
data and link.)
bool has_42(const node* head_ptr);
// Precondition: head_ptr is the head pointer of a linked list.
// The list might be empty or it might be non-empty.
// Postcondition: The return value is true if the list has at least
// one occurrence of the number 42 in the data part of a node.
Implement the following function as a new function for the linked list
toolkit. (Use the usual node definition with member variables called
data and link.)
bool all_42s(const node* head_ptr);
// Precondition: head_ptr is the head pointer of a linked list.
// The list might be empty or it might be non-empty.
// Postcondition: The return value is true if every node in the
// list contains 42 in the data part. NOTE: If the list is empty,
// then the function returns true.
Implement the following function as a new function for the linked list
toolkit. (Use the usual node definition with member variables called
data and link. The data field is an int.)
int sum(const node* head_ptr);
// Precondition: head_ptr is the head pointer of a linked list.
// The list might be empty or it might be non-empty.
// Postcondition: The return value is the sum of all the data components
// of all the nodes. NOTE: If the list is empty, the function returns 0.
Implement the following function as a new function for the linked list
toolkit. (Use the usual node definition with member variables called
data and link. The data field is an int.)
int product(const node* head_ptr);
// Precondition: head_ptr is the head pointer of a linked list.
// The list might be empty or it might be non-empty.
// Postcondition: The return value is the product of all the data components
// of all the nodes. NOTE: If the list is empty, the function returns 1.
Implement the following function as a new function for the linked list
toolkit. (Use the usual node definition with member variables called
data and link.)
void list_tail_insert(node* head_ptr, const node::value_type& entry);
// Precondition: head_ptr is the head pointer of a non-empty
// linked list.
// Postcondition: A new node has been added at the tail end
// of the list. The data in the new node is taken from the
// parameter called entry.
Implement the following function as a new function for the linked list
toolkit. (Use the usual node definition with member variables called
data and link.)
bool data_is_on(const node* head_ptr, const node* p);
// Precondition: head_ptr is the head pointer of a linked list
// (which might be empty, or might be non-empty). The pointer p
// is a non-NULL pointer to some node on some linked list.
// Postcondition: The return value is true if the data in *p
// appears somewhere in a data field of a node in head_ptr's
// linked list. Otherwise the return value is false.
// None of the nodes on any lists are changed.
Implement the following function as a new function for the linked list
toolkit. (Use the usual node definition with member variables called
data and link.)
bool is_on(const node* head_ptr, const node* p);
// Precondition: head_ptr is the head pointer of a linked list
// (which might be empty, or might be non-empty). The pointer p
// is a non-NULL pointer to some node on some linked list.
// Postcondition: The return value is true if p actually points to
// one of the nodes in the head_ptr's linked list. For example,
// p might point to the head node of this list, or the second node,
// or the third node, and so on. Otherwise the return value is
// false. None of the nodes on any lists are changed.
Implement the following function as a new function for the linked list
toolkit. Do not call any of the other toolkit functions from
within your implementation.
(Use the usual node definition with member variables called
data and link.)
void list_insert_zero(node* previous_ptr);
// Precondition: previous_ptr is a pointer to a node on a linked list.
// Postcondition: A new node has been added to the list after
// the node that previous_ptr points to. The new node contains 0.
Suppose that p, q, and r are all pointers to nodes in a linked list with 15
nodes. The pointer p points to the first node, q points to the 8th node, and r
points to the last node. Write a few lines of code that will make a new copy of
the list. You code should set THREE new pointers called x, y, and z so that: x
points to the first node of the copy, y points to the 8th node of the copy, and
z points to the last node of the copy. Your code may NOT contain any loops,
but it can use the
toolkit functions.
Short Answers
Section 5.3
The Bag ADT
with a Linked List
|
Suppose that a_ptr and b_ptr are node pointers. Write one clear
sentence to tell me when the expression
(a_ptr==b_ptr) will be true.
Compare the worst-case big-O time analysis for these two functions:
The insert function for the bag that is implemented using a fixed-sized array,
and the insert function for the bag that is implemented using a linked list.
Compare the worst-case big-O time analysis for these two functions:
The erase_one function for the bag that is implemented using a fixed-sized array,
and the erase_one function for the bag that is implemented using a linked list.
Short Answers
Section 5.4
The Sequence ADT
with a Linked List
|
Tell me about one of the sequence operations that is more efficient
because the class keeps a tail pointer as a private member variable.
Provide a specific example showing why the operation would be
less efficient without the tail pointer.
Tell me about one of the sequence operations that is easier to program
because the class keeps a precursor (rather than just a cursor).
Provide a specific example showing why the operation would be
harder to program without the precursor.
Compare the worst-case big-O time analysis for these two functions:
The insert function for the sequence that is implemented using a fixed-sized array,
and the insert function for the sequence that is implemented using a linked list.
Compare the worst-case big-O time analysis for these two functions:
The remove function for the sequence that is implemented using a fixed-sized array,
and the remove function for the sequence that is implemented using a linked list.
Short Answer
Section 5.5
Dynamic Arrays vs.
Linked Lists vs.
Doubly Linked Lists
|
class dnode
{
public:
// CONSTRUCTOR: Creates a dnode containing a specified initial values.
dnode(
int init_data = 0,
dnode* init_fore = NULL,
dnode* init_back = NULL
)
{
data_field = init_data;
link_fore = init_fore;
link_back = init_back;
}
// Member functions to set the fields:
void set_data(int new_data)
{ data_field = new_data; }
void set_fore(dnode* new_fore)
{ link_fore = new_fore; }
void set_back(dnode* new_back)
{ link_back = new_back; }
// Const member functions to retrieve current data:
int data( ) const { return data_field; }
// Two slightly different member functions to retrieve each link:
const dnode* fore( ) const { return link_fore; }
dnode* fore( ) { return link_fore; }
const dnode* back( ) const { return link_back; }
dnode* back( ) { return link_back; }
private:
int data_field;
dnode *link_fore;
dnode *link_back;
};
|
Write one sentence to describe a situation when a
doubly linked list is appropriate.
Describe a situation where storing items in an array is clearly
better than storing items on a linked list.
Implement the following function using the dnode
class that is shown above. It is NOT a member function).
int sum_data(const dnode* head_ptr);
// PRECONDITION: head_pointer is a non-NULL head pointer for a linked list.
// POSTCONDITION: The return value is the sum of all the data fields
// of the dnodes in the linked list.
Implement the following function using the dnode
class that is shown above. It is NOT a member function.
dnode* find_data(dnode* head_ptr, int target)
// PRECONDITION: head_pointer is a non-NULL head pointer for a linked list.
// POSTCONDITION: The return value is a pointer to the first dnode in
// the linked list that contains the target as its data. If there is no
// such dnode, then the return value is NULL.
Implement the following function using the dnode
class that is shown above. It is NOT a member function. Your function
should not cause a heap leak.
void delete_dnode(dnode* p)
// PRECONDITION: p is a non-NULL pointer to a dnode in a linked list.
// It is neither the first nor the last dnode.
// POSTCONDITION: The dnode *p has been removed from the list.
Implement the following function using the dnode
class that is shown above. It is NOT a member function.
void insert_dnode(dnode* p, int new_data)
// PRECONDITION: p is a non-NULL pointer to a dnode in a linked list.
// It is neither the first nor the last dnode.
// POSTCONDITION: A new dnode with new_data has been inserted into the
// linked list after *p.
Suppose that a program has declared these three variables using the
dnode class shown above.
dnode *b;
dnode *h;
dnode *z;
After executing part of the program, the pointer b
is a head pointer for a non-empty linked list. Write some code that
can be placed in the program at this point to make a complete copy
of b's linked list. At the end of your code,
b should be unchanged, h should be the head
pointer of the new list, and z should be the tail pointer
of the new list. If necessary, you may declare other
dnode * variables to use in your algorithm.
This question is appropriate if you have implemented
the polynomial with a linked list from
www.cs.colorado.edu/~main/projects/chap05d.html.
In my dynamic polynomial, the set_recent function includes
this line:
recent_ptr = recent_ptr->fore( );
A. Describe the effect of this statement in one clear English
sentence.
B. The set_recent function is a const member
function, which means that normally it is not permitted to change any
member variables. Explain why the compiler permits
set_recent
to change the
recent_ptr member variable.