没有合适的资源?快使用搜索试试~ 我知道了~
ACM 程序设计:STL编程及应用-6.pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 36 浏览量
2022-06-17
23:44:29
上传
评论
收藏 906KB PDF 举报
温馨提示
试读
19页
ACM 程序设计:STL编程及应用-6.pdf
资源推荐
资源详情
资源评论
2014/2/27
1
华南师大讲稿 华南师大讲稿
STL编程及应用
ACM 程序设计(二)
华南师大讲稿 华南师大讲稿
常用STL类的使用
• 栈 stack
• 队列 queue
• 优先队列 priority_queue
华南师大讲稿
栈(stack)
定义:只允许在一端插入和删除的线性表
栈顶(
top
):
允许插入和删除的一端
特点
后进先出
(LIFO
)
退栈
进栈
华南师大讲稿 华南师大讲稿
使用方法
1.参考网站:【英文】
http://msdn.microsoft.com/en-us/library/h9sh48d5(VS.80).aspx
2.引用头文件
#include <stack>
#include <iostream>
using namespace std;
华南师大讲稿 华南师大讲稿
stack class
成员函数:
empty
Tests if the stack is empty.
pop
Removes the element from the top of the stack.
push
Adds an element to the top of the stack.
size
Returns the number of elements in the stack.
top
Returns a reference to an element at the top of the stack.
华南师大讲稿 华南师大讲稿
使用方法
1.参考网站:【中文】
msdn.microsoft.com/zh-cn/library/vstudio/56fa1zk5(v=vs.110).aspx
2.引用头文件
#include <stack>
#include <iostream>
using namespace std;
2014/2/27
2
华南师大讲稿 华南师大讲稿
stack class
成员函数:
empty 测试stack是否为空。
pop 从stack的顶部移除元素。
push 将元素添加到stack顶部。
size 返回stack中的元素个数。
top 返回stack顶部元素。
华南师大讲稿 华南师大讲稿
使用例子
#include <stack>
#include <iostream>
using namespace std;
int main( )
{ stack <int> s1;
s1.push( 10 );
s1.push( 20 );
s1.push( 30 );
int i;
i = s1.top( );
cout << "The element at the top of the stack is " << i << "." << endl;
s1.pop( );
i = s1.top( );
cout << " The element at the top of the stack is "<< i << "." << endl;
}
运行结果:
The element at the top of the stack is 30.
The element at the top of the stack is 20.
华南师大讲稿 华南师大讲稿
应用例子:二叉树前序遍历
35
15 45
50 40 25 10
20
30
存储结构
struct node
{
int data;
struct node *child[2];
};
华南师大讲稿 华南师大讲稿
前序遍历(深度遍历)非递归算法
void DFS(struct node *root)
{
stack<struct node *> st;
while((!st.empty( )|| root!=0) )
{
while(root!=0)
{
cout<<root->data<<" ";
st.push(root);
root=root->child[0];
}
if(!st.empty( )) { root=st.top(); st.pop(); root=root->child[1]; }
}
}
35
15 45
50 40 25 10
20
30
华南师大讲稿 华南师大讲稿
队列 (
Queue )
• 定义
–队列是只允许在一端删除,在另一端插入的线
性表
–队头(
front
):允许删除的一端
–队尾(
rear
):允许插入的一端
• 特性
–先进先出(
FIFO
,
First In First Out
)
华南师大讲稿 华南师大讲稿
使用方法
• 1.参考网站:【英文】
http://msdn.microsoft.com/en-us/library/s1b6tszt(VS.80).aspx.
• 2.引用头文件
#include <queue>
#include <iostream>
using namespace std;
2014/2/27
3
华南师大讲稿 华南师大讲稿
Queue class
• 成员函数:
back()
Returns a reference to the last and most recently added element
at the back of the queue.
empty()
Tests if the queue is empty.
front()
Returns a reference to the first element at the front of the queue.
pop()
Removes an element from the front of the queue.
push()
Adds an element to the back of the queue.
size()
Returns the number of elements in the queue.
华南师大讲稿 华南师大讲稿
使用方法
• 1.参考网站:【中文】
http://msdn.microsoft.com/zh-cn/library/vstudio/s23s3de6%28v=vs.110%29.aspx
• 2.引用头文件
#include <queue>
#include <iostream>
using namespace std;
华南师大讲稿 华南师大讲稿
Queue class
• 成员函数:
back 返回队列中最后和最近添加的元素。
empty 测试queue是否为空。
front 返回队列中的第一个元素。
pop 从 queue的前面移除元素。
push 将元素添加到 queue中。
size 返回队列的元素个数。
华南师大讲稿 华南师大讲稿
使用例子
#include <queue>
#include <iostream>
using namespace std;
int main( )
{ queue <int> q1;
q1.push( 10 );
q1.push( 20 );
q1.push( 30 );
int i;
i = q1.front( );
cout << "The element at the front of the queue is "<< i << "." << endl;
q1.pop( );
i = q1. front ( );
cout << "After a pop, the front of the queue is " << i << "." << endl;
}
运行结果:
The element at the front of the queue is 10.
After a pop, the front of the queue is 20.
华南师大讲稿 华南师大讲稿
应用:二叉树的层次遍历
35
15 45
50 40 25 10
20
30
存储结构
struct node
{
int data;
struct node *child[2];
};
华南师大讲稿 华南师大讲稿
层次遍历(广度优先遍历)算法
void BFS(struct node *root)
{
queue<struct node *> qu;
struct node *temp;
qu.push(root);
while(!qu.empty())
{
temp=qu.front();
qu.pop();
cout<<temp->data<<" ";
if (temp->child[0]!=0)
qu.push(temp->child[0]);
if (temp->child[1]!=0)
qu.push(temp->child[1]);
// 可以改写为 for 循环
}
}
35
15 45
50 40 25 10
20
30
剩余18页未读,继续阅读
资源评论
wxg520cxl
- 粉丝: 24
- 资源: 3万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功