数据结构

一、堆栈的应用：

　　1、c++模板库：

　　　　　　stack<int>s;

　　　　　　在头文件#include<stack>,需要声明并且使用标准命名空间。

　　2、括号匹配问题：

　　　　　　

　　3、计算表达式的值：

　　　　其一般方法：

　　　　　　（1）设立两个堆栈，一个用来保存运算符，一个用来保存数字。

　　　　　　（2）在表达式首尾添加标记运算符，该运算符运算优先级最低。

　　　　　　（3）从左至右依次遍历字符串，若遍历到运算符，将其与运算符栈栈顶元素进行比较，若运算符栈栈顶运算符小于该运算符　　　　　　

二、哈夫曼树：

　　1、哈夫曼树的求法：

　　　　（1）将所有的节点放入集合k。

　　　　（2）若集合k中剩余节点大于2个，则取出其中权值最小的两个节点，构造他们同时为某个新节点的左右儿子，该节点是他们共同的双亲节点，设定他的权值为两个子节点的权值和。并将该父亲节点放入集合k,重复步骤2或3.

　　　　（3）若节点中只有一个节点，则这个节点就是该树的根节点。

　　　　在该例中，为了可以更快的取出元素，需要使用c++中的堆数据结构。为了绕过对堆的实现，我们使用标准模板库的相应标准模板----优先队列。

　　　　建立一个保存元素为int 的堆q,但是特别注意建立的堆是默认为大顶堆，即我们从堆顶取得的元素为整个堆中的最大元素。而求哈夫曼树我们需要取得的元素是堆中的最小的元素，于是我们使用如下语句定义

 

一个小顶堆：

　　　　priority_queue<int,vector<int>,greater<int>> Q;

　　　　关于堆的操作：

　　　　　　Q.push(x),

　　　　　　Q.top(),

　　　　　　Q.pop()

　　　　　　其在#include<queue>库中

    

　　　　

#include
      
       #include
       
        using namespace std;priority_queue
        
         
          ,greater
          
            >Q; int main(){    int n;    while(scanf("%d",&n)==1){        while(!Q.empty()) Q.pop();        for(int i=0;i
           
            1){ int a=0; int b=0; a=Q.top(); Q.pop(); b=Q.top(); Q.pop(); ans+=a; ans+=b; Q.push(a+b); } Q.pop(); printf("%d\n",ans); }}
           
          
         
        
       
      

 

 

 

 

三、二叉排序树：

　　

#include
      
       #include
       
        int a[100];struct Tree{    int data;     Tree* left;     Tree* right;};//向树中插入元素 void insert(Tree* root,int i){        if(root->data>i){            if(root->left!=NULL){                insert(root->left,i);            }else{                root->left=(Tree*)malloc(sizeof(Tree));                root->left->data=i;                root->left->left=NULL;                root->left->right=NULL;            }        }else{            if(root->right!=NULL)            insert(root->right,i);            else{                root->right=(Tree*)malloc(sizeof(Tree));                root->right->data=i;                root->right->left=NULL;                root->right->right=NULL;            }        }}//中序打印树 void mid_print(Tree* root){    if(root!=NULL){        mid_print(root->left);        printf("%d ",root->data);        mid_print(root->right);    }}int main(){    int n;    while(scanf("%d",&n)==1){        for(int i=0;i
        
         data=a[0];        root->left=NULL;        root->right=NULL;        for(int i=1;i
        
       
      

 

　　（2）判断两棵树是否相同：

　　　　　　由树的知识可知，包括中序遍历在内的两种遍历结果可以唯一的确定一颗树，因此可以对两棵树进行两种遍历，若两种遍历结果都相同，则可以判定两棵树是完全相同的。