nullnull栈(stack)定义:只允许在一端插入和删除的线性
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
栈顶(top):
允许插入和删除的一端
特点
后进先出 (LIFO)退栈进栈使用方法使用方法1.参考网站:
http://msdn.microsoft.com/en-us/library/h9sh48d5(VS.80).aspx
2.引用头文件
#include
#include
using namespace std;
stack classstack 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.
例子例子#include
#include
using namespace std;
int main( )
{
stack s1, s2;
s1.push( 10 );
s1.push( 20 );
s1.push( 30 );
stack ::size_type i;
i = s1.size( );
cout << "The stack length is " << i << "." << endl;
i = s1.top( );
cout << "The element at the top of the stack is "
<< i << "." << endl;
s1.pop( );
i = s1.size( );
cout << "After a pop, the stack length is "
<< i << "." << endl;
i = s1.top( );
cout << "After a pop, the element at the top of the stack is "
<< i << "." << endl;
}
Output
The stack length is 3.
The element at the top of the stack is 30.
After a pop, the stack length is 2.
After a pop, the element at the top of the stack is 20.
null数制转换
十进制N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理:
N=(n / d)*d+n % d
null数制转换
例如 (1348)10=(2504)8,其运算过程如下: n n / 8 n % 8
1348 168 4
168 21 0
21 2 5
2 0 2
算法 Stackb.cpp算法 Stackb.cpp#include
#include
using namespace std;
void main()
{
int n;
stack st;
cin>>n;
while(n!=0)
{
st.push(n%2);
}
while(!st.empty())
{
cout<
#include
using namespace std;
void main()
{
int n;
stack st;
cin>>n;
while(n!=0)
{
st.push(n%2);
n=n/2;
}
while(!st.empty())
{
cout<>m;
for (i=0;i>n)!=NULL)
{
…..
}
或
while((cin>>n)!=0)
{
…..
}
输入的组织输入的组织
2.输入未给定多少block,只是给出每个block的数据. Stack2-0.cpp in2.dat
while(cin >> n && n != 0)
{
…..
}
输入的组织输入的组织
2.输入未给定多少block,只是给出每个block的数据. Stack2-1.cpp in2.dat
或
while(scanf("%d", &n) != EOF && n != 0)
{
.....
}
或
while(scanf("%d", &n)!=EOF)
{
…..
}输出的组织输出的组织
1.一个Input Block对应一个Output Block,Output Block之间没有空行
前面的例子均这样.输出的组织输出的组织
1.一个Input Block对应一个Output Block,Output Block之间没有空行
前面的例子均这样.输出的组织输出的组织 2.一个Input Block对应一个Output Block,Output Block之间有空行。
stack3.cpp 输出的组织输出的组织 3.一个Input Block对应一个Output Block,Output Block之间有空行且在output block之前有序号。
Stack4.cpp
int casenum=0;
while(cin >> n && n != 0)
{
casenum++;
cout<
#include
using namespace std;
例子例子#include
#include
using namespace std;
int main( )
{
queue q1, s2;
q1.push( 10 );
q1.push( 20 );
q1.push( 30 );
queue ::size_type i;
i = q1.size( );
cout << "The queue length is " ;
cout<<<< i << "." << endl;
i = q1.front( );
cout << "The element at the front of the queue is "<< i << "." << endl;q1.pop( );
i = q1.size( );
cout << "After a pop the queue length is "
<< i << "." << endl;
i = q1. front ( );
cout << "After a pop, the front of the queue is " << i << "." << endl;
}
Output
The queue length is 3.
The element at the front of the queue is 10.
After a pop the queue length is 2.
After a pop, the element at the front of the queue is 20.null广度优先遍历广度优先遍历Queue.cppnull#include
#include
#include
using namespace std;
void main()
{
queue qu;
int counter=0; int level=1; int x;
qu.push(1);
while(!qu.empty()&&level!=5)
{
x=qu.front();
qu.pop();
cout<data=x;
temp->child[0]=0;
temp->child[1]=0;
root=temp;
}
else if (xdata) insert(root->child[0],x);
else insert(root->child[1],x);
}建立算法建立算法Root=0;
Cin>>n;
for (i=0;i>x;
Insert(root,x);
}深度优先遍历算法深度优先遍历算法351545504025102030深度优先遍历算法深度优先遍历算法void DFS(struct node *root)
{
int i;
if (root!=0 )
{
cout<data<<" ";
for (i=0;i<2;i++)
DFS(root->child[i]);
//DFS(root->child[0]);
//DFS(root->child[1]);
}
}广度优先遍历算法广度优先遍历算法void BFS(struct node *root)
{
queue qu;
struct node *temp;
qu.push(root);
while(!qu.empty())
{
temp=qu.front();
qu.pop();
cout<data<<" ";
if (temp->child[0]!=0)
qu.push(temp->child[0]);
if (temp->child[1]!=0)
qu.push(temp->child[1]);
// 可以改写为 for 循环
}
}求树高/树深度求树高/树深度351545504025102030队列的结构队列的结构
struct node
{
int data;
struct node *child[2];
};
struct queuenode
{
struct node *treenode;
int level;
};
queue qu; 算法 level.cpp算法 level.cppint BFS(struct node *root)
{
queue qu;
struct queuenode temp,newtemp;
int maxlevel=0;
temp.treenode=root;
temp.level=1;
qu.push(temp);
while(!qu.empty())
{
temp=qu.front();
qu.pop();
if (temp.level>maxlevel) maxlevel=temp.level;
if (temp.treenode->child[0]!=0)
{
newtemp.treenode=temp.treenode->child[0]; newtemp.level=temp.level+1;
qu.push(newtemp);
}
if (temp.treenode->child[1]!=0)
{
newtemp.treenode=temp.treenode->child[1]; newtemp.level=temp.level+1;
qu.push(newtemp);
}
}
return maxlevel;
}四叉特征树四叉特征树存储结构存储结构struct node
{
int data;
struct node *child[4];
};
插入算法插入算法void insert(struct node *&root,int x)
{
struct node *temp; int i;
if (root==0)
{
temp=new struct node;
temp->data=x;
for (i=0;i<4;i++)
temp->child[i]=0; // /////////////
root=temp;
return ;
}
switch(x/root->data)
{
case 0:insert(root->child[0],x);break;
case 1:insert(root->child[1],x);break;
case 2:insert(root->child[2],x);break;
default:insert(root->child[3],x);break;
}
}深度优先搜索算法深度优先搜索算法
void DFS(struct node *root)
{
int i;
if (root!=0 )
{
cout<data<<" ";
for (i=0;i<4;i++)
DFS(root->child[i]); ////////////
}
}广度优先搜索算法广度优先搜索算法
void BFS(struct node *root)
{
int i;
queue qu;
struct node *temp;
qu.push(root);
while(!qu.empty())
{
temp=qu.front();
qu.pop();
cout<data<<" ";
for (i=0;i<4;i++)
if (temp->child[i]!=0)
qu.push(temp->child[i]);
}
}八叉特征树八叉特征树null