22Mar
Author: wktd | Category: enart.gzfn.com
I need to write a c++ program that when given a starting character and
an end character will print all possible combinations. it is based on
the concept of using a stack. it must also be based on the given
algorithm. i am including the information that i have been given for
this problem.
The Assignment:
1. You will use both array and link-list versions of stack class and
add to these classes the new method (member function) peek. The new
function differs from the top in ability to ?peek? not only the top
element but also any entry down the stack. Hence the new function is
taking positive integer parameter n between 1 and the size of the
stack and return the value of the entry n positions down the stack. If
no parameter is provided then by default the top entry is returned.
2. Using this extended version of stack class (you will have two
versions) you will write a program that will print to the screen all
strings with at most n characters in a given range first -- last.
For your convenience I am providing you with the algorithm that should
do that. Your job is to unders
tand the algorithm and correctly
translate it to the C++ language.
The algorithm you need to translate:
Push the first character onto the stack
While the stack is not empty
Print the whole content of the stack using the new peek function
If the stack contains fewer than n letters -- push first onto the stack
Else
Pop characters off the stack, until either the stack is empty or there
is a character other than last on the top. In case when the top
character is not last -- nothing is popped out
If the stack is not empty
Pop the top one (which we may call the current)
Push the next letter (current + 1) onto the stack
Sample dialogs:
1.
Please enter the first character: a
Please enter the last character: b
Please enter the n: 3
a
aa
aaa
baa
ba
aba
bba
b
ab
aab
bab
bb
abb
bbb
this is the dynamic array stack template class:
// FILE: stack1.template
// TEMPLATE CLASS IMPLEMENTED: stack
- (see stack1.h for documentation)
// This file is included in the header file, and not compiled separately.
// INVARIANT for the Stack ADT:
// 1. The number of items in the Stack is in the member variable used.
// 2. The actual items of the Stack are stored in a partially-filled
// array data[0]..data[used-1]. The stack elements appear from the
// bottom (at data[0]) to the top (at data[used-1]).
#include // Provides assert
#include // Provides size_t
template
void stack
- ::push(const Item& entry)
// Library facilities used: assert.h
{
assert(size( ) < CAPACITY);
data[used] = entry;
used++;
}
template
Item stack
- ::pop( )
// Library facilities used: assert.h
{
assert(!is_empty( ));
used--;
return data[used];
}
//Implement the peek function here
this is the linked list stack template class that i am using:
// FILE: stack2.template
// TEMPLATE CLASS IMPLEMENTED: stack
- (see stack2.h for documentation)
// This file is included in the header file, and not compiled separately.
// INVARIANT for the stack ADT:
// 1. The items in the stack are stored in a linked list, with the top of the
// stack stored at the head node, down to the bottom of the stack at the
// final node.
// 2. The member variable top_ptr is the head pointer of the linked list.
#include // Provides assert
#include // Provides size_t
#include "linkplus.h" // Linked list toolkit
template
stack
- ::stack(const stack
- & source)
// Library facilities used: link2.h
{
node
- *tail_ptr; // Needed for argument of list_copy
list_copy(source.top_ptr, top_ptr, tail_ptr);
}
template
void stack
- ::push(const Item& entry)
// Library facilities used: link2.h
{
list_head_insert(top_ptr, entry);
}
template
Item stack
- ::pop( )
// Library facilities used: assert.h, link2.h
{
Item answer;
assert(!is_empty( ));
answer = top_ptr->data();
list_head_remove(top_ptr);
return answer;
}
template
void stack
- ::operator =(const stack
- & source)
// Library facilities used: link2.h
{
node
- *tail_ptr; // Needed for argument of list_copy
if (source.top_ptr == top_ptr) // Handle self-assignment
return;
list_clear(top_ptr);
list_copy(source.top_ptr, top_ptr, tail_ptr);
}
template
Item stack
- ::top( ) const
// Library facilities used: assert.h
{
assert(!is_empty( ));
return top_ptr->data();
}
//Implement here the peek function
this is the supporting linkplus file if needed for reference:
// FILE: linkplus.cpp
// IMPLEMENTS: The 10 functions of the expanded linked list toolkit
// (see linkplus.h). The four new functions implemented at the bottom of
// the file were implemented by __________(your name and email address)____.
#include // Provides assert
#include // Provides NULL and size_t
template
node
- ::node(const Item& init_data, node
- * init_link)
{
data_field = init_data;
link_field = init_link;
}
template
void node
- ::set_data(const Item& new_data)
{
data_field = new_data;
}
template
void node
- ::set_link(node
- * new_link)
{
link_field = new_link;
}
template
Item node
- ::data() const
{
return data_field;
}
template
const node
- * node
- ::link() const
{
return link_field;
}
template
node
- * node
- ::link()
{
return link_field;
}
template
size_t list_length(const node
- * head_ptr)
// Library facilities used: stdlib.h
{
const node
- *cursor;
size_t answer;
answer = 0;
for (cursor = head_ptr; cursor != NULL; cursor = cursor->link())
answer++;
return answer;
}
template
void list_head_insert(node
- *& head_ptr, const Item& entry)
{
head_ptr = new node
- (entry, head_ptr);
}
template
void list_insert(node
- * previous_ptr, const Item& entry)
{
node
- * insert_ptr;
insert_ptr = new node
- ;
insert_ptr->set_data(entry);
insert_ptr->set_link(previous_ptr->link());
previous_ptr->set_link(insert_ptr);
}
template
node
- * list_search(node
- * head_ptr, const Item& target)
// Library facilities used: stdlib.h
{
node
- *cursor;
for (cursor = head_ptr; cursor != NULL; cursor = cursor->link())
if (target == cursor->data())
return cursor;
return NULL;
}
template
node
- * list_locate(node
- * head_ptr, int position)
// Library facilities used: assert.h, stdlib.h
{
node
- *cursor;
size_t i;
assert (0 < position);
cursor = head_ptr;
for (i = 1; (i < position) && (cursor != NULL); i++)
cursor = cursor->link();
return cursor;
}
template
const node
- * list_locate(const node
- * head_ptr, int position)
// Library facilities used: assert.h, stdlib.h
{
const node
- *cursor;
size_t i;
assert (0 < position);
cursor = head_ptr;
for (i = 1; (i < position) && (cursor != NULL); i++)
cursor = cursor->link();
return cursor;
}
template
void list_head_remove(node
- *& head_ptr)
{
node
- *remove_ptr;
remove_ptr = head_ptr;
head_ptr = head_ptr->link();
delete remove_ptr;
}
template
void list_remove(node
- * previous_ptr)
{
node
- *remove_ptr;
remove_ptr = previous_ptr->link();
previous_ptr->set_link(remove_ptr->link());
delete remove_ptr;
}
template
void list_clear(node
- *& head_ptr)
// Library facilities used: stdlib.h
{
while (head_ptr != NULL)
list_head_remove(head_ptr);
}
template
void list_copy(node
- * source_ptr, node
- *& head_ptr,
node
- *& tail_ptr)
// Library facilities used: stdlib.h
{
head_ptr = NULL;
tail_ptr = NULL;
// Handle the case of the empty list
if (source_ptr == NULL)
return;
// Make the head node for the newly created list, and put data in it
list_head_insert(head_ptr, source_ptr->data());
tail_ptr = head_ptr;
// Copy the rest of the nodes one at a time, adding at the tail of new list
source_ptr = source_ptr->link();
while(source_ptr !=NULL)
{
list_insert(tail_ptr, source_ptr->data());
tail_ptr = tail_ptr->link();
source_ptr = source_ptr->link();
}
}
template
void list_piece(const node
- * start_ptr, const node
- *
end_ptr, node
- *& head_ptr, node
- *& tail_ptr)
// Library facilities used: stdlib.h
{
head_ptr = NULL;
tail_ptr = NULL;
// Handle the case of the empty list
if (start_ptr == NULL)
return;
// Make the head node for the newly created list, and put data in it
list_head_insert(head_ptr, start_ptr->data());
tail_ptr = head_ptr;
if (start_ptr == end_ptr)
return;
// Copy the rest of the nodes one at a time, adding at the tail of new list
for (start_ptr = start_ptr->link(); start_ptr != NULL; start_ptr =
start_ptr->link())
{
list_insert(tail_ptr, start_ptr->data());
tail_ptr = tail_ptr->link();
if (start_ptr == end_ptr)
return;
}
}
#If you have any other info about this subject , Please add it free.# |
|
