个人学习编程(3-24) 数据结构

括号的匹配：

if((s[i]==')' && now=='(') || (s[i]==']' && now=='[')){

#include <bits/stdc++.h>using namespace std;int main() {char s[300];scanf("%s",&s);int i;int len = strlen(s);stack <char> st;for (i = 0; i < len; i++){if(!st.empty()){char now = st.top();if((s[i]==')' && now=='(') || (s[i]==']' && now=='[')){st.pop();}else{st.push(s[i]);}}else{st.push(s[i]);}}if (!st.empty()){printf("NO!");}else{printf("GOOD!");}return 0;
}

 哈夫曼树（果堆排序）：

有n堆果子，看看如何分类

输入包括两行：第一行是一个整数n（1<=n<=10000），表示果子的种类个数。

第二行包含了n个整数，用空格分隔，第i个整数表示整数ai（1<=ai<=20000）是第i堆果子的数目。

eg：输入 3

                1 2 9

        输出：15

解法1：

如果数量比较少，可以用sort函数来排序，每次将前面两位加完之后继续排，继续加，直到数组只有一个值。

解法2：

#include <bits/stdc++.h>
using namespace std;struct node{int x;node(int a) {x = a;} //构造函数方便赋值
};//定义优先队列的排序：
bool operator < (const node& a,const node& b){return a.x > b.x;
}int main(){priority_queue <node> q;int n,x;cin >> n;for (int i = 0; i < n; i++){cin >> x;q.push(x);}int ans = 0;while (q.size() > 1){node num1 = q.top();q.pop();node num2 = q.top();q.pop();ans += (num1.x + num2.x);q.push(node{num1.x + num2.x});}cout << ans;return 0;}

其中的q.push(node{num1.x + num2.x}) 是前面把num1 出队和num2出队之前，把他们的值保存下来再相加

二叉树的建立和遍历：

按照先序先输入 二叉树的节点，没有的按0表示。

再输出 第一行是先序 第二行是中序 第三行是后序变量 第四输出叶子结点

#include <bits/stdc++.h>
using namespace std;typedef struct node{ //注意typedef不能忽略char data;struct node *lchild,*rchild;
}*BitTree;
//先序遍历的方式创建二叉树：
void CreatBitTree(BitTree &T){char c;cin >> c;if(c == '0'){T=NULL;}else{T = new node;T->data = c;CreatBitTree(T->lchild);CreatBitTree(T->rchild);}
}//将二叉树按照先序输出：
void PreOrderTraverse(BitTree T){if(T != NULL){cout << T->data << ' ';PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);}
}//将二叉树按照中序输出：
void InOrderTraverse(BitTree T){if (T != NULL){InOrderTraverse(T->lchild);cout << T->data << ' ';InOrderTraverse(T->rchild);}
}//将二叉树按照后序输出：
void PostOrderTraverse(BitTree T){if (T != NULL){PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild);cout << T->data << ' ';}}//二叉树的叶子节点数：
int Leaf(BitTree T){if(T == NULL) return 0;if(T->rchild == NULL && T->lchild == NULL) return 1;return Leaf(T->lchild) + Leaf(T->rchild);
}//二叉树的深度：
int Deepth(BitTree T){if (T == NULL) return 0;int x = Deepth(T->lchild);int y = Deepth(T->rchild);return max(x,y) + 1;
}int main() {BitTree T;CreatBitTree(T);PreOrderTraverse(T); cout << endl;InOrderTraverse(T); cout << endl;PostOrderTraverse(T); cout << endl;cout << Leaf(T) << endl;return 0;
}