这一篇博客以一些OJ上的题目为载体，整理一下数据结构。会陆续的更新。
。。
我们都知道，数据结构的灵活应用有时能让简化一些题目的解答。
一、栈的应用
1、NJUPT OJ 1054(回文串的推断)
回文串的推断：将一个字符串的一半存入一个栈中。然后从栈顶開始推断这个字符串是否是回文串
/*
* NJUPTOJ_1054.cpp
*
* Created on: 2014年5月22日
* Author: pc
*/ #include <iostream>
#include <cstdio> using namespace std; const int maxn = 300; void toLower(char arr[],int len){
int i;
for(i = 0 ; i < len ; ++i){
if(!islower(arr[i])){
arr[i] += 32;
}
}
} int main(){
char a[maxn];
char s[maxn]; while(gets(a)!=NULL){ int len = strlen(a);
toLower(a,len); int mid = len/2 - 1; int top = 0;
int i;
for(i = 0 ; i <= mid ; ++i){
s[++top] = a[i];
} int next;
if(len%2 == 0){
next = mid+1;
}else{
next = mid+2;
} for(i = next ; i <= len-1 ; ++i){
if(s[top] != a[i]){
break;
} --top;
} if(top != 0){
printf("Not Palindrome.\n");
}else{
printf("Bingle! Palindrome.\n");
}
} return 0; }
下面是再次做这道题时的代码:
/*
* njupt_1054_1.cpp
*
* Created on: 2014年9月6日
* Author: pc
*/ #include <iostream>
#include <cstdio> using namespace std; const int maxn = 300; /**
* 将一个字符串转化成小写
*/
void toLower(char a[]){
int len = strlen(a);
int i;
for(i = 0 ; i < len ; ++i){
if(islower(a[i]) == false){
a[i] += 32;
}
}
} void work(char a[]){ int len = strlen(a);
int s[len]; /**
*关于mid和next额理解:
*mid: 用来标记開始比較时栈顶的第一个元素
*next: 用来比較剩下的一半的字符串中開始比較时的第一个元素的位置
*/
int mid = len/2 - 1;
int next;
if(len%2 == 0){
next = mid+1;
}else{
next = mid+2;
} int top = 0;
int i;
for(i = 0 ; i <= mid ; ++i){
s[++top] = a[i];
} for(i = next ; i <= len-1 ; ++i){
if(s[top] != a[i]){
break;
} --top;
} if(top == 0){
printf("Bingle! Palindrome.\n");
}else{
printf("Not Palindrome.\n");
} } int main(){ char s[maxn]; /**
* 不知道行数时的输入的处理方式...
*/
while(gets(s) != NULL){
toLower(s);
work(s);
} return 0; }
2、NEFU OJ 194 回文字符串
算法思想和上面的是一样的
/*
* NEFU_194.cpp
*
* Created on: 2014年5月23日
* Author: pc
*/ #include <iostream>
#include <cstdio> using namespace std; string a;
string s; int main() {
int t;
scanf("%d", &t);
while (t--) { cin >> a;
int len = a.length(); int mid = len / 2 - 1; int top = 0;
int i; for (i = 0; i <= mid; ++i) {
top += 1;
s[top] = a[i];
} int next;
if (len % 2 == 0) {
next = mid + 1;
} else {
next = mid + 2;
} for (i = next; i <= len - 1; ++i) {
if (s[top] != a[i]) {
break;
} --top;
} if (top != 0) {
printf("NO\n");
} else {
printf("YES\n");
}
} return 0;
}
3、NYOJ 1002 括号的匹配
思想：假设输入的符号是(、[则直接进栈,假设是],则推断此事最后一个是否是[，假设是[出栈,否则]进栈
/*
* NY_2_1.cpp
*
* Created on: 2014年5月25日
* Author: pc
*/ #include <iostream>
#include <cstdio>
#include <stack> using namespace std; int main(){ string a;
int t;
scanf("%d",&t);
while(t--){
stack<char> s; cin >> a;
int len = a.length();
int i;
for(i = 0 ; i < len ; ++i){
if(a[i] == '(' || a[i] == '['){
s.push(a[i]);
}else if(a[i] == ')'){
if(!s.empty() && s.top() == '('){
s.pop();
}else{
s.push(a[i]);
}
}else if(a[i] == ']'){
if(!s.empty() && s.top() == '['){
s.pop();
}else{
s.push(a[i]);
}
}
} if(s.empty()){
printf("Yes\n");
}else{
printf("No\n");
}
} return 0;
}