📄 chapter9.htm
字号:
<p class="style3">}<br>
}</p>
<p class="style3">程序运行输出：<br>
size of q is:4<br>
42<br>
100<br>
49<br>
201<br>
horse<br>
size of p is:5<br>
cat<br>
ape<br>
dog<br>
mouse<br>
horse<br>
</p>
<p class="style3"><strong>9-12 实际应用中，双向队列比普通队列更加常用。在标准C++类库中，双向队列类（deque）的成员函数queue::assign ()给一个双向队列重新赋值，queue::swap()交换两个双向队列中的元素，queue::begin()返回指向双向队列中的第一个元素的指针，queue:: end()返回指向双向队列中的最后一个元素的指针，请构造一个整型双向队列，然后对这个队列调用以上几个函数，体会队列这种数据结构的特点和其成员函数的用法。</strong><br>
</p>
<p class="style3">解： <br>
#include <iostream><br>
#include <deque></p>
<p class="style3">using namespace std;</p>
<p class="style3">typedef deque<char > CHARDEQUE;<br>
void print_contents (CHARDEQUE deque, char*);</p>
<p class="style3">void main()<br>
{<br>
//create a with 3 A's<br>
CHARDEQUE a(3,'A');</p>
<p class="style3">//create b with 4 B's.<br>
CHARDEQUE b(4,'B');</p>
<p class="style3">//print out the contents<br>
print_contents (a,"a");<br>
print_contents (b,"b");</p>
<p class="style3">//swap a and b<br>
a.swap(b);<br>
print_contents (a,"a");<br>
print_contents (b,"b");</p>
<p class="style3">// let us swap it back<br>
a.swap(b);<br>
print_contents (a,"a");<br>
print_contents (b,"b");</p>
<p class="style3">//assign the contents of b to a<br>
a.assign(b.begin(),b.end());<br>
print_contents (a,"a");</p>
<p class="style3">//assign the first two items of b to a<br>
a.assign(b.begin(),b.begin()+2);<br>
print_contents (a,"a");</p>
<p class="style3">//assign 3 'Z's to a<br>
a.assign(3,'Z');<br>
print_contents (a,"a");</p>
<p class="style3">}</p>
<p class="style3">//function to print the contents of deque<br>
void print_contents (CHARDEQUE deque, char *name)<br>
{<br>
CHARDEQUE::iterator pdeque;</p>
<p class="style3">cout <<"The contents of "<< name <<" : ";</p>
<p class="style3">for(pdeque = deque.begin();<br>
pdeque != deque.end();<br>
pdeque++)<br>
{<br>
cout << *pdeque <<" " ;<br>
}<br>
cout<<endl;<br>
}</p>
<p class="style3">程序运行输出：<br>
The contents of a : A A A<br>
The contents of b : B B B B<br>
The contents of a : B B B B<br>
The contents of b : A A A<br>
The contents of a : A A A<br>
The contents of b : B B B B<br>
The contents of a : B B B B<br>
The contents of a : B B<br>
The contents of a : Z Z Z<br>
</p>
<p class="style3"><strong>9-13 在标准C++类库中，双向队列类（deque）的成员函数queue::front()返回一个非空双向队列的第一个元素，queue:: back()返回一个非空双向队列的最后一个元素，请构造一个字符型双向队列，体会这几个成员函数的用法。</strong><br>
</p>
<p class="style3">解： <br>
#include <iostream><br>
#include <deque></p>
<p class="style3">using namespace std;</p>
<p class="style3">typedef deque<char > CHARDEQUE;<br>
void print_contents (CHARDEQUE deque, char*);</p>
<p class="style3">void main()<br>
{<br>
//create a with A, B, C and D<br>
CHARDEQUE a;<br>
a.push_back('A');<br>
a.push_back('B');<br>
a.push_back('C');<br>
a.push_back('D');</p>
<p class="style3">//print out the contents<br>
print_contents (a,"a");</p>
<p class="style3">cout <<"The first element of a is " <<a.front() <<endl;</p>
<p class="style3">cout <<"The last element of a is " <<a.back() <<endl;</p>
<p class="style3">//now let us modify the first and last elements<br>
//using reference ,front() and back()</p>
<p class="style3">CHARDEQUE::reference reffront=a.front();<br>
CHARDEQUE::reference refback=a.back();</p>
<p class="style3">reffront='X';<br>
refback='Y';</p>
<p class="style3">//print out the contents<br>
print_contents (a,"a");</p>
<p class="style3">}</p>
<p class="style3">//function to print the contents of deque<br>
void print_contents (CHARDEQUE deque, char *name)<br>
{<br>
CHARDEQUE::iterator pdeque;</p>
<p class="style3">cout <<"The contents of "<< name <<" : ";</p>
<p class="style3">for(pdeque = deque.begin();<br>
pdeque != deque.end();<br>
pdeque++)<br>
{<br>
cout << *pdeque <<" " ;<br>
}<br>
cout<<endl;<br>
}</p>
<p class="style3">程序运行输出：<br>
The contents of a : A B C D</p>
<p class="style3">The first element of a is A</p>
<p class="style3">The last element of a is D</p>
<p class="style3">The contents of a : X B C Y</p>
<p class="style3"><strong>9-14 在标准C++类库中，双向队列类（deque）的成员函数queue::insert()往一个双向队列中插入元素，queue::push_front(const T& x)往一个双向队列的头端插入一个元素，queue::pop_front()从一个双向队列的头端删除一个元素，queue::push_back(const T& x)往一个双向队列的尾端插入一个元素，queue::pop_back(const T& x)从一个双向队列的尾端删除一个元素，请构造一个字符型双向队列，体会这几个成员函数的用法。</strong><br>
</p>
<p class="style3">解： <br>
#include <iostream><br>
#include <deque></p>
<p class="style3">using namespace std;</p>
<p class="style3"><br>
typedef deque<char > CHARDEQUE;<br>
void print_contents (CHARDEQUE deque);</p>
<p class="style3">void main()<br>
{<br>
//create a with 3 A's<br>
CHARDEQUE a(3,'A');</p>
<p class="style3">//create b with 2 B's.<br>
CHARDEQUE b(2,'B');</p>
<p class="style3">//print out the contents<br>
print_contents (a);<br>
print_contents (b);</p>
<p class="style3">//insert 'X' to the beginning of a<br>
a.insert(a.begin(),'X');<br>
print_contents (a);</p>
<p class="style3">//insert 'Y' to the end of a<br>
a.insert(a.end(),'Y');<br>
print_contents (a);</p>
<p class="style3">//inset 3 'Z's to one item before the end of a<br>
a.insert(a.end()-1,3,'Z');<br>
print_contents (a);</p>
<p class="style3">//insert to the end of a from b<br>
a.insert(a.end(),b.begin(),b.end());<br>
print_contents (a);</p>
<p class="style3">}</p>
<p class="style3">//function to print the contents of deque<br>
void print_contents (CHARDEQUE deque)<br>
{<br>
CHARDEQUE::iterator pdeque;</p>
<p class="style3">cout <<"The output is: ";</p>
<p class="style3">for(pdeque = deque.begin();<br>
pdeque != deque.end();<br>
pdeque++)<br>
{<br>
cout << *pdeque <<" " ;<br>
}<br>
cout<<endl;<br>
}</p>
<p class="style3">程序运行输出：<br>
The output is: A A A<br>
The output is: B B<br>
The output is: X A A A<br>
The output is: X A A A Y<br>
The output is: X A A A Z Z Z Y<br>
The output is: X A A A Z Z Z Y B B<br>
</p>
<p class="style3"><strong>9-15 在标准C++类库中，双向队列类（deque）的长度是可变的，成员函数resize( n, T x = T())可加长已有的双向队列对象，size() const返回队列长度，max_size() const返回系统可支持的最大双向队列长度，请构造一个字符型双向队列，体会这几个成员函数的用法。</strong><br>
</p>
<p class="style3">解： <br>
#include <iostream><br>
#include <deque></p>
<p class="style3">using namespace std;</p>
<p class="style3"><br>
typedef deque<char > CHARDEQUE;<br>
void print_contents (CHARDEQUE deque, char*);</p>
<p class="style3">void main()<br>
{<br>
//create a with A, B, C and D<br>
CHARDEQUE a;<br>
a.push_back('A');<br>
a.push_back('B');<br>
a.push_back('C');<br>
a.push_back('D');</p>
<p class="style3">//print out the contents</p>
<p class="style3">print_contents (a,"a");<br>
cout <<"max_size of a is " <<a.max_size() <<endl;<br>
cout <<"size of a is " <<a.size() <<endl;</p>
<p class="style3">//let us increase the size to 10<br>
// and set the new elements to be 'X'<br>
a.resize(10,'X');<br>
print_contents (a,"a");<br>
cout <<"size of a is " <<a.size() <<endl;</p>
<p class="style3">//let us resize it to 5<br>
a.resize(5);<br>
print_contents (a,"a");<br>
cout <<"size of a is " <<a.size() <<endl;<br>
cout <<"max_size of a is still " <<a.max_size() <<endl;</p>
<p class="style3">}</p>
<p class="style3">//function to print the contents of deque<br>
void print_contents (CHARDEQUE deque, char *name)<br>
{<br>
CHARDEQUE::iterator pdeque;</p>
<p class="style3">cout <<"The contents of "<< name <<" : ";</p>
<p class="style3">for(pdeque = deque.begin();<br>
pdeque != deque.end();<br>
pdeque++)<br>
{<br>
cout << *pdeque <<" " ;<br>
}<br>
cout<<endl;<br>
}</p>
<p class="style3">程序运行输出：<br>
The contents of a : A B C D<br>
max_size of a is 4294967295<br>
size of a is 4<br>
The contents of a : A B C D X X X X X X<br>
size of a is 10<br>
The contents of a : A B C D X<br>
size of a is 5<br>
max_size of a is still 4294967295</p>
<p class="style3"> </p>
<p class="style3"><strong>9-16 深度为n的二叉树的最大节点数是多少？有以下节点数的二叉树的最小深度为多少？1) 5； 2) 9； 3) 25； 4) 250。</strong><br>
</p>
<p class="style3">解： <br>
深度为n的二叉树的最大节点数为2n+1-1；<br>
以上二叉树的最小深度为：1)2； 2)3； 3) 4； 4) 7<br>
</p>
<p class="style3"><strong>9-17 请建立如图所示的一个简单的二叉树，结点数据类型为字符型。</strong><br>
<br>
解： <br>
//nodetree.h 即为教材中例程9-11，参见教材第9章<br>
#ifndef TREENODE_CLASS <br>
#define TREENODE_CLASS</p>
<p class="style3">#ifndef NULL<br>
const int NULL = 0;<br>
#endif // NULL</p>
<p class="style3">template <class T><br>
class TreeNode<br>
{<br>
private:<br>
TreeNode<T> *left; //左指针<br>
TreeNode<T> *right; //右指针</p>
<p class="style3">public:<br>
T data; //结点数据<br>
<br>
// 构造函数<br>
TreeNode (const T& item, TreeNode<T> *lptr = NULL,<br>
TreeNode<T> *rptr = NULL);<br>
<br>
// 访问指针域的函数<br>
TreeNode<T>* Left(void) const; //取得左指针<br>
TreeNode<T>* Right(void) const; //取得右指针<br>
<br>
// 删除当前结点的左右子树<br>
void release();<br>
};</p>
<p class="style3">// 构造函数，初始化数据域和指针域<br>
template <class T><br>
TreeNode<T>::TreeNode (const T& item, TreeNode<T> *lptr,<br>
TreeNode<T> *rptr): data(item), left(lptr), right(rptr)<br>
{}</p>
<p class="style3">//取得左指针<br>
template <class T><br>
TreeNode<T>* TreeNode<T>::Left(void) const<br>
{<br>
return left;<br>
}</p>
<p class="style3">//取得右指针<br>
template <class T><br>
TreeNode<T>* TreeNode<T>::Right(void) const<br>
{<br>
return right;<br>
}</p>
<p class="style3">// 删除当前结点的左右子树<br>
template <class T><br>
void TreeNode<T>::release()<br>
{<br>
if(left)<br>
{ //删除左子树<br>
left->release();<br>
delete left;<br>
left=NULL;<br>
}<br>
if(right)<br>
{ //删除右子树<br>
right->release();<br>
delete right;<br>
right=NULL;<br>
}<br>
}</p>
<p class="style3">#endif // TREENODE_CLASS</p>
<p class="style3">//test9_17.cpp<br>
#include <iostream.h><br>
#include "treenode.h"</p>
<p class="style3">void main(void)<br>
{<br>
TreeNode<char> D('D'),E('E');<br>
TreeNode<char> B('B',&D,&E),C('C');<br>
TreeNode<char> A('A',&B,&C);<br>
}</p>
<p class="style3"> </p>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -