📄 chapter9.htm
字号:
p->right = this;<br>
left = p;<br>
}</p>
<p class="style3">// unlink the current node from the list and return its address<br>
template <class T><br>
DNode<T> *DNode<T>::DeleteNode(void)<br>
{<br>
// node to the left must be linked to current node's right<br>
left->right = right;<br>
<br>
// node to the right must be linked to current node's left<br>
right->left = left;<br>
<br>
// return the address of the current node<br>
return this;<br>
}</p>
<p class="style3">// return pointer to the next node on the right<br>
template <class T><br>
DNode<T> *DNode<T>::NextNodeRight(void) const<br>
{<br>
return right;<br>
}</p>
<p class="style3">// return pointer to the next node on the left<br>
template <class T><br>
DNode<T> *DNode<T>::NextNodeLeft(void) const<br>
{<br>
return left;<br>
}</p>
<p class="style3">#endif // DOUBLY_LINKED_NODE_CLASS<br>
</p>
<p class="style3"><strong>9-5 使用本章中的链表类定义两个整型链表A和B，分别插入5个元素，然后把B中的元素加入A的尾部。</strong><br>
</p>
<p class="style3">解： <br>
本题的解答见“实验指导” 部分“实验九”。<br>
</p>
<p class="style3"><strong>9-6 从教材第9章的链表类LinkedList中派生有序链表类OrderList，添加成员函数InsertOrder，实现链表元素的有序（递增）插入。定义两个整型有序链表A和B，分别按递增顺序插入5个元素，然后把B中的元素插入A中，保持A中递增顺序不变。</strong><br>
</p>
<p class="style3">解： <br>
#include <iostream.h><br>
#include "link.h" //参见"实验指导" 部分"实验九"</p>
<p class="style3">template <class T><br>
class Link:public LinkedList<T><br>
{<br>
public:<br>
void InsertOrder(const T& item);<br>
};</p>
<p class="style3">template <class T><br>
void Link<T>::InsertOrder(const T& item)<br>
{<br>
Reset();<br>
while (!EndOfList())<br>
{<br>
if (item < Data())<br>
break;<br>
Next();<br>
} <br>
InsertAt(item);<br>
}</p>
<p class="style3">void main(void)<br>
{<br>
Link<int> A,B;<br>
int i, item;<br>
<br>
cout << "请输入加入链表A的五个整数：";<br>
for ( i=0; i<5; i++ )<br>
{<br>
cin >> item;<br>
A.InsertOrder(item);<br>
}<br>
<br>
cout << "请输入加入链表B的五个整数：";<br>
for ( i=0; i<5; i++ )<br>
{<br>
cin >> item;<br>
B.InsertOrder(item);<br>
}<br>
<br>
cout << endl << "有序链表A中的元素为：";<br>
A.Reset();<br>
while(!A.EndOfList())<br>
{<br>
cout << A.Data() << " ";<br>
A.Next(); <br>
}<br>
<br>
cout << endl << "有序链表B中的元素为：";<br>
B.Reset();<br>
while(!B.EndOfList())<br>
{<br>
A.InsertOrder(B.Data());<br>
cout << B.Data() << " ";<br>
B.Next(); <br>
}<br>
<br>
cout << endl << "加入链表B中元素后，链表A中的元素为：";<br>
A.Reset();<br>
while(!A.EndOfList())<br>
{<br>
cout << A.Data() << " ";<br>
A.Next(); <br>
}<br>
}</p>
<p class="style3">程序运行输出：<br>
请输入加入链表A的五个整数：1 3 7 6 5<br>
请输入加入链表B的五个整数：2 6 8 5 4<br>
链表A中的元素为：1 3 5 6 7 <br>
链表B中的元素为：2 4 5 6 8 <br>
加入链表B中元素后，链表A中的元素为：1 2 3 4 5 5 6 6 7 8 <br>
</p>
<p class="style3"><strong>9-7 什么叫作栈？对栈中元素的操作有何特性？</strong><br>
</p>
<p class="style3">解： <br>
栈是只能从一端访问的线性群体，可以访问的这一端称栈顶，另一端称栈底。对栈顶位置的标记称为栈顶指针，对栈底位置的标记称为栈底指针。向栈顶添加元素称为“压入栈”，删除栈顶元素称为“弹出栈”。栈中元素的添加和删除操作具有“后进先出”（LIFO）的特性。<br>
</p>
<p class="style3"><strong>9-8 在标准C++类库中，栈类（stack）的成员函数stack::push()在栈顶端添加元素，stack::pop()从非空栈的栈顶端中删除一个元素，stack::empty()判断栈是否为空， stack::top()返回非空栈的栈顶元素，stack::size()返回栈中元素的个数，请构造一个整型栈，然后对这个栈调用以上几个函数，体会栈这种数据结构的特点和其成员函数的用法。</strong><br>
</p>
<p class="style3">解： <br>
#include <stack><br>
#include <iostream></p>
<p class="style3">using namespace std ;</p>
<p class="style3">typedef stack<int> STACK_INT;</p>
<p class="style3">void main()<br>
{<br>
STACK_INT stack1;</p>
<p class="style3">cout << "stack1.empty() returned " <<<br>
(stack1.empty()? "true": "false") << endl; // Function 3</p>
<p class="style3">cout << "stack1.push(2)" << endl;<br>
stack1.push(2);</p>
<p class="style3">if (!stack1.empty()) // Function 3<br>
cout << "stack1.top() returned " <<<br>
stack1.top() << endl; // Function 1</p>
<p class="style3">cout << "stack1.push(5)" << endl;<br>
stack1.push(5);</p>
<p class="style3">if (!stack1.empty()) // Function 3<br>
cout << "stack1.top() returned " <<<br>
stack1.top() << endl; // Function 1</p>
<p class="style3">cout << "stack1.push(11)" << endl;<br>
stack1.push(11);</p>
<p class="style3">if (!stack1.empty()) // Function 3<br>
cout << "stack1.top() returned " <<<br>
stack1.top() << endl; // Function 1</p>
<p class="style3">// Modify the top item. Set it to 6.<br>
if (!stack1.empty()) { // Function 3<br>
cout << "stack1.top()=6;" << endl;<br>
stack1.top()=6; // Function 1<br>
}</p>
<p class="style3">// Repeat until stack is empty<br>
while (!stack1.empty()) { // Function 3<br>
const int& t=stack1.top(); // Function 2<br>
cout << "stack1.size() equals " << stack1.size() << endl;<br>
cout << "stack1.top() returned " << t << endl;<br>
cout << "stack1.pop()" << endl;<br>
stack1.pop();<br>
}<br>
cout << "stack1.size() equals " << stack1.size() << endl;<br>
}</p>
<p class="style3">程序运行输出：<br>
stack1.empty() returned true<br>
stack1.push(2)<br>
stack1.top() returned 2<br>
stack1.push(5)<br>
stack1.top() returned 5<br>
stack1.push(11)<br>
stack1.top() returned 11<br>
stack1.top()=6;<br>
stack1.top() returned 6<br>
stack1.pop()<br>
stack1.top() returned 5<br>
stack1.pop()<br>
stack1.top() returned 2<br>
stack1.pop()<br>
</p>
<p class="style3"><strong>9-9 在标准C++类库中，对栈类（stack）重载了= =、! =、>、> =、<、< =等运算符，以对两个不同的栈进行算术比较运算操作，请构造一个整型栈，以 = =、< 运算为例，对两个栈进行算术比较运算，体会其比较归者规则；运行程序，观察其输出。</strong><br>
</p>
<p class="style3">解： <br>
源程序：<br>
#include <stack><br>
#include <iostream></p>
<p class="style3">using namespace std ;</p>
<p class="style3">typedef stack<double> STACK_DOUBLE;</p>
<p class="style3">void main()<br>
{<br>
STACK_DOUBLE stack1,stack2;</p>
<p class="style3">// Add item 4.0 to Stack1. Stack1 contains 4.0.<br>
cout << "stack1.push(4.0) s1=[4.0]" << endl;<br>
stack1.push(4.0);</p>
<p class="style3">// Add item 3.0 to Stack1. Stack1 contains 3.0(top) and 4.0(bottom).<br>
cout << "stack1.push(3.0) s1=[3.0 4.0]" << endl;<br>
stack1.push(3.0);</p>
<p class="style3">// Add item 4.0 to Stack2. Stack2 contains 4.0 (top=bottom).<br>
cout << "stack2.push(4.0) s2=[4.0]" << endl;<br>
stack2.push(4.0);</p>
<p class="style3">// Compare if Stack1 is smaller than Stack2. Should return False.</p>
<p class="style3">cout << "stack1==stack2 is " <<<br>
((stack1==stack2)? "True": "False") << endl;</p>
<p class="style3">cout << "stack1<stack2 is " <<<br>
((stack1<stack2)? "True": "False") << endl << endl;</p>
<p class="style3">// Add item 6.0 to Stack2. Stack2 contains 6.0(top) and 4.0(bottom).<br>
cout << "stack2.push(6.0) s2=[6.0 4.0]" << endl;<br>
stack2.push(6.0);</p>
<p class="style3">// Compare if Stack1 is smaller than Stack2. Should return True.<br>
cout << "stack1==stack2 is " <<<br>
((stack1==stack2)? "True": "False") << endl;</p>
<p class="style3">cout << "stack1<stack2 is " <<<br>
((stack1<stack2)? "True": "False") << endl << endl;</p>
<p class="style3">// Add item 8.0 to Stack2. Stack2 contains 8.0(top), 6.0 and<br>
// 4.0(bottom).<br>
cout << "stack2.push(8.0) s2=[8.0 6.0 4.0]" << endl;<br>
stack2.push(8.0);</p>
<p class="style3">// Compare if Stack1 is smaller than Stack2. Should return True.</p>
<p class="style3">cout << "stack1==stack2 is " <<<br>
((stack1==stack2)? "True": "False") << endl;<br>
cout << "stack1<stack2 is " <<<br>
((stack1<stack2)? "True": "False") << endl << endl;</p>
<p class="style3">// Delete item 8.0 from Stack2.<br>
cout << "stack2.pop() s2=[6.0 4.0]" << endl;<br>
stack2.pop();</p>
<p class="style3">// Delete item 6.0 from Stack2.<br>
cout << "stack2.pop() s2=[4.0]" << endl;<br>
stack2.pop();</p>
<p class="style3">// Add item 3.0 to Stack2. Stack2 contains 3.0(top) and 4.0(bottom).<br>
cout << "stack2.push(3.0) s2=[3.0 4.0]" << endl;<br>
stack2.push(3.0);</p>
<p class="style3">// Compare if Stack1 is smaller than Stack2. Should return False.<br>
cout << "stack1==stack2 is " <<<br>
((stack1==stack2)? "True": "False") << endl;<br>
cout << "stack1<stack2 is " <<<br>
((stack1<stack2)? "True": "False") << endl << endl;</p>
<p class="style3">// Delete item 3.0 from Stack2.<br>
cout << "stack2.pop() s2=[4.0]" << endl;<br>
stack2.pop();</p>
<p class="style3">// Delete item 4.0 from Stack2.<br>
cout << "stack2.pop() s2=[]" << endl;<br>
stack2.pop();</p>
<p class="style3">// Add item 8.0 to Stack2. Stack2 contains 8.0(top=bottom).<br>
cout << "stack2.push(8.0) s2=[8.0]" << endl;<br>
stack2.push(8.0);</p>
<p class="style3">// Compare if Stack1 is smaller than Stack2. Should return True.<br>
cout << "stack1==stack2 is " <<<br>
((stack1==stack2)? "True": "False") << endl;<br>
cout << "stack1<stack2 is " <<<br>
((stack1<stack2)? "True": "False") << endl << endl;</p>
<p class="style3">}</p>
<p class="style3">程序运行输出： <br>
stack1.push(4.0) s1=[4.0]<br>
stack1.push(3.0) s1=[3.0 4.0]<br>
stack2.push(4.0) s2=[4.0]<br>
stack1<stack2 is False</p>
<p class="style3">stack2.push(6.0) s2=[6.0 4.0]<br>
stack1<stack2 is True</p>
<p class="style3">stack2.push(8.0) s2=[8.0 6.0 4.0]<br>
stack1<stack2 is True</p>
<p class="style3">stack2.pop() s2=[6.0 4.0]<br>
stack2.pop() s2=[4.0]<br>
stack2.push(3.0) s2=[3.0 4.0]<br>
stack1<stack2 is False</p>
<p class="style3">stack2.pop() s2=[4.0]<br>
stack2.pop() s2=[]<br>
stack2.push(8.0) s2=[8.0]<br>
stack1<stack2 is True<br>
</p>
<p class="style3"><strong>9-10 什么叫作队列？对队列中元素的操作有和特性？</strong><br>
</p>
<p class="style3">解： <br>
队列是只能向一端添加元素，从另一端删除元素的线性群体，可以添加元素的一端称队尾，可以删除元素的一端称队头。对队头位置的标记称为队头指针，对队尾位置的标记称为队尾指针。向队尾添加元素称为“入队”，删除队头元素称为“出队”。队列中元素的添加和删除操作具有“先进先出”（FIFO）的特性。<br>
</p>
<p class="style3"><strong>9-11 在标准C++类库中，队列类（queue）的成员函数queue::push()在队列一端添加元素，queue::pop()从非空的队列中删除最后一个元素，queue::empty()判断队列是否为空， queue::back()返回非空队列的最后一个元素，queue::front()返回非空队列的第一个元素，queue::size()返回队列中元素的个数，请构造一个整型队列和一个字符型队列，然后对这两个队列调用以上几个函数，体会队列这种数据结构的特点和其成员函数的用法。</strong><br>
</p>
<p class="style3">解： <br>
#include <iostream><br>
#include <queue></p>
<p class="style3">using namespace std ;</p>
<p class="style3">typedef queue<int> INTQUEUE;</p>
<p class="style3">typedef queue<char*> CHARQUEUE;</p>
<p class="style3">void main(void)<br>
{<br>
int size_q;<br>
INTQUEUE q;<br>
CHARQUEUE p;</p>
<p class="style3">// Insert items in the queue(uses list)<br>
q.push(42);<br>
q.push(100);<br>
q.push(49);<br>
q.push(201);<br>
// Output the size of queue<br>
size_q = q.size();<br>
cout << "size of q is:" << size_q << endl;</p>
<p class="style3">// Output items in queue using front()<br>
// and use pop() to get to next item until<br>
// queue is empty<br>
while (!q.empty())<br>
{<br>
cout << q.front() << endl;<br>
q.pop();</p>
<p class="style3">}</p>
<p class="style3">// Insert items in the queue(uses deque)<br>
p.push("cat");<br>
p.push("ape");<br>
p.push("dog");<br>
p.push("mouse");<br>
p.push("horse");</p>
<p class="style3">// Output the item inserted last using back()<br>
cout << p.back() << endl;</p>
<p class="style3">// Output the size of queue<br>
size_q = p.size();<br>
cout << "size of p is:" << size_q << endl;</p>
<p class="style3">// Output items in queue using front()<br>
// and use pop() to get to next item until<br>
// queue is empty<br>
while (!p.empty())<br>
{<br>
cout << p.front() << endl;<br>
p.pop();</p>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -