|
|
cout.setf(ios::fixed); //以定點形式顯示浮點數(shù)
cout.precision(4); //設(shè)置小數(shù)部分的4位有效數(shù)字
設(shè)序列X={x1,x2,x3......xm}和Y={y1,y2,y3,....yn}，要求最長公共子序列，可以按照下面方式遞歸計算，：當(dāng)xm=yn時，找出Xm-1和Yn-1的最長公共子序列，然后在其尾部加上xm即可得到X和Y的最長公共子序列，當(dāng)xm不等于yn的時候，必須解決兩個子問題即找出Xm-1和Y的最長公共子序列和Yn-1和X的最長工公共子序列，然后這兩個里面較長者為X和Y的最長公共子序列！ 首先建立子問題的最優(yōu)值遞歸關(guān)系。用C[i][j]表示Xi和Yj的最長公共子序列的長度。其中，Xi={x1,x2,x3......xi},Yj={y1,y2,y3,....yn}，當(dāng)i=0或者j=0時空序列是Xi和Yj的最長公共子序列，故因此，C[i][j]=0，即有 代碼如下： C[i][j]=0，（i=0,j=0) C[i][j]=c[i-1][j-1]+1,xi=yj C[i][j]=max(C[i][j-1],C[i-1][j]),i,j>0,xi不等于yj述
最長公共子串（Longest common substring, 簡稱LCS）問題指的是求出給定的一組 字符串的長度最大的共有的子字符串。 舉例說明，以下三個字符串的LCS就是 cde： abcde cdef ccde
現(xiàn)在的情況是給你2個字符串，請找到他們的LCS
請注意：字符可以不相鄰；
輸入
輸入第一行包含一個整數(shù)T，表示有T組數(shù)據(jù)；
對于每組數(shù)據(jù)包含2行，每行包含一個非空字符串，長度不超過1000個字符
輸出
對于每組數(shù)據(jù)輸出他們的LCS的長度，保證每組數(shù)據(jù)存在LCS；
樣例輸入
2 abcde cdef aaaaaaa aaabaaa
樣例輸出 3 6
分析：
設(shè)序列X={x1,x2,x3......xm}和Y={y1,y2,y3,....yn}，要求最長公共子序列，可以按照下面方式遞歸計算，：當(dāng)xm=yn時，找出Xm-1和Yn-1的最長公共子序列，然后在其尾部加上xm即可得到X和Y的最長公共子序列，當(dāng)xm不等于yn的時候，必須解決兩個子問題即找出Xm-1和Y的最長公共子序列和Yn-1和X的最長工公共子序列，然后這兩個里面較長者為X和Y的最長公共子序列！ 首先建立子問題的最優(yōu)值遞歸關(guān)系。用C[i][j]表示Xi和Yj的最長公共子序列的長度。其中，Xi={x1,x2,x3......xi},Yj={y1,y2,y3,....yn}，當(dāng)i=0或者j=0時空序列是Xi和Yj的最長公共子序列，故因此，C[i][j]=0，即有 C[i][j]=0，（i=0,j=0)
C[i][j]=c[i-1][j-1]+1,xi=yj
C[i][j]=max(C[i][j-1],C[i-1][j]),i,j>0,xi不等于yj 實現(xiàn)代碼如下： #include<stdio.h>
#include<string.h>
int c[1002][1002]={0};
int main()
{
int N,m,n,i,j;
char x[1002],y[1002];
scanf("%d",&N);
while(N--)
{
scanf("%s",x);
scanf("%s",y);
m=strlen(x);
n=strlen(y);
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
{
if(x[i-1]==y[j-1])
{
c[i][j]=c[i-1][j-1]+1;
}
else if(c[i-1][j]>=c[i][j-1])
{
c[i][j]=c[i-1][j];
}
else
{
c[i][j]=c[i][j-1];
}
}
printf("%d\n",c[m][n]);
}
return 0;
} 參考自： http://yangchuanhuahpu.blog.163.com/blog/static/18631884020125272205862/
轉(zhuǎn)。
// %.*s 其中的.*表示顯示的精度 對字符串輸出(s)類型來說就是寬度
// 這個*代表的值由后面的參數(shù)列表中的整數(shù)型(int)值給出
// 例如：
printf("%.*s\n", 1, "abc"); // 輸出a
printf("%.*s\n", 2, "abc"); // 輸出ab
printf("%.*s\n", 3, "abc"); // 輸出abc >3是一樣的效果 因為輸出類型type = s，遇到'\0'會結(jié)束
描述 對于一個字符串S1，其中S2是他的一個子串（長度嚴(yán)格小于S1長度），如果S2在S1中出現(xiàn)次數(shù)超過1次，那么S2就是一個重復(fù)子串，現(xiàn)在的要求是給定S1，請求出他的最長重復(fù)子串；
如果有多個長度一樣的最長子串，請輸入字典序最小那個串；
比如bbbaaaccc
那么最長子串就是aa
輸入 第一行包含一個整數(shù)T，表示有T組數(shù)據(jù)
對于每組數(shù)據(jù)包含一行，該行有一個字符串，長度小于10,000
輸出 對于每組數(shù)據(jù)請輸出他的最長重復(fù)子串，保證每組數(shù)據(jù)都有；
樣例輸入 2 abacabac abacabbac
樣例輸出 abac bac
代碼測試通過（普通版）：
#include<stdio.h> #include< string.h> #define N 10000 int main() { char a[N]; int i,j,n,t,p,max,t1; scanf("%d",&t1); while(t1--) { max = 0; scanf("%s",a); n=strlen(a); for(i=0;i<n;i++) { for(j=i+1;j<n;j++) { t=0; while(a[i+t]==a[j+t]&&(j+t)<n) t++; if(t>max) { max=t; p=i; } else if(t == max) //如果有長度一樣的最長重復(fù)子串，那么比較它們的字典序
{ if(a[i]<a[p]) { max = t; p = i; } } } } for(i=p;i<p+max;i++) printf("%c",a[i]); printf("\n"); } return 0; } ²）。
第二種方法是用后綴數(shù)組實現(xiàn)。轉(zhuǎn)自：http://hi.baidu.com/qwertlooker/item/44f3fe52ad772cdbd58bacfd
如果程序至多可以處理MAXN個字符，這些字符被存儲在數(shù)組c中： #define MAXN 5000000
char c[MAXN], *a[MAXN]; 在讀取輸入時，首先初始化a,這樣，每個元素就都指向輸入字符串中的相應(yīng)字符： while (ch = getchar()) != EOF
a[n] = &c[n];
c[n++] = ch;
c[n] = 0 //將數(shù)組c中的最后一個元素設(shè)為空字符，以終止所有字符串 這樣，元素a[0]指向整個字符串，下一個元素指向以第二個字符開始的數(shù)組的后綴，等等。如若輸入字符串為"banana",該數(shù)組將表示這些后綴：
a[0]:banana a[1]:anana a[2]:nana a[3]:ana a[4]:na a[5]:a 由于數(shù)組a中的指針分別指向字符串中的每個后綴，所以將數(shù)組a命名為"后綴數(shù)組"
第二，對后綴數(shù)組進(jìn)行快速排序，以將后綴相近的（變位詞）子串集中在一起 qsort(a, n, sizeof(char*), pstrcmp)后 a[0]:a a[1]:ana a[2]:anana a[3]:banana a[4]:na a[5]:nana
第三，使用以下comlen函數(shù)對數(shù)組進(jìn)行掃描比較鄰接元素，以找出最長重復(fù)的字符串： for i = [0, n)
if comlen(a[i], a[i+1]) > maxlen
maxlen = comlen(a[i], a[i+1])
maxi = i
printf("%.*s\n", maxlen, a[maxi]) 由于少了內(nèi)層循環(huán)，只是多了一次排序，因此該算法的運行時間為O(n logn). （nlogn比n大，取nlogn） 實現(xiàn)代碼如下： #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXCHAR 10000 //最長處理10000個字符
char c[MAXCHAR], *a[MAXCHAR];
int comlen( char *p, char *q ){ //計算最長重復(fù)子串的長度
int i = 0;
while( *p && (*p++ == *q++) )
++i;
return i;
}
int pstrcmp( const void *p1, const void *p2 ){
return strcmp( *(char* const *)p1, *(char* const*)p2 );
}
int main( ){
int t;
char ch;
int i, temp;
scanf("%d\n",&t);
while(t--)
{
int n=0;
int maxlen=0, maxi=0;
while( (ch=getchar())!='\n' ){
a[n]=&c[n];
c[n++]=ch;
}
c[n]='\0';
qsort( a, n, sizeof(char*), pstrcmp ); //快速排序?qū)缶Y數(shù)組進(jìn)行排序，以使后綴相同的子串集中在一起，
//以便接下來comlen函數(shù)對這些子串進(jìn)行計算其最長重復(fù)子串
for(i=0; i<n-1; ++i ){
temp=comlen( a[i], a[i+1] );
if( temp>maxlen )
{
maxlen=temp;
maxi=i;
}
}
printf("%.*s\n",maxlen, a[maxi]); //輸出最長重復(fù)子串
}
return 0;
}
第三種方法似乎可以用后綴樹實現(xiàn)，效率可以提高到O(n)，具體的后綴樹講解可以參照這篇文章：
http://blog.csdn.net/v_july_v/article/details/6897097（PS:智商有限，后面部分講解理解不了）
歸并排序法是將兩個（或兩個以上）有序表合并成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。然后再把有序子序列合并為整體有序序列。 例如，有數(shù)列{6，202，100，301，38，8，1} 1. 剛開始的分組如下： i=1 [6 202 ] [ 100 301] [ 8 38] [ 1 ] 比較次數(shù)為3次 2. 第二次，兩兩分組合并 i=2 [ 6 100 202 301 ] [ 1 8 38 ] 比較次數(shù)為4 3. 第三次，繼續(xù)合并 i=3 [ 1 6 8 38 100 202 301 ] 比較次數(shù)為4 總計的比較次數(shù)為11次 歸并排序具體工作原理如下（假設(shè)序列共有n個元素）： 1. 將序列每相鄰兩個數(shù)字進(jìn)行歸并操作，形成floor(n / 2)個序列，排序后每個序列包含兩個元素 2. 將上述序列再次歸并，形成floor(n / 4)個序列，每個序列包含四個元素 3. 重復(fù)步驟2，直到所有元素排序完畢 歸并操作的過程如下： 1. 申請空間，使其大小為兩個已經(jīng)排序序列之和，該空間用來存放合并后的序列 2. 設(shè)定兩個指針，最初位置分別為兩個已經(jīng)排序序列的起始位置 3. 比較兩個指針?biāo)赶虻脑兀x擇相對小的元素放入到合并空間，并移動指針到下一位置 4. 重復(fù)步驟3直到某一指針達(dá)到序列尾 5. 將另一序列剩下的所有元素直接復(fù)制到合并序列尾 自底向上歸并，如圖所示：  遞歸實現(xiàn)代碼： #include <iostream>
using namespace std;
void merge(int*arr, int p, int q, int r)
{
int n1 = q - p + 1;
int n2 = r - q;
int* L = new int[n1];
int* R = new int[n2];
for(int i = 0; i < n1; i++)
{
L[i] = arr[p + i];
}
for(int j = 0; j < n2; j++)
{
R[j] = arr[q + j + 1];
}
int i = 0;
int j = 0;
int k = p;
while((i < n1) && (j < n2))
{
if(L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
if (i < n1)
{
for(; i < n1; i++, k++)
{
arr[k] = L[i];
}
}
if (j < n2)
{
for(; j < n2; j++, k++)
{
arr[k] = R[j];
}
}
}
void mergesort(int* arr, int p, int r)
{
int q = 0;
if(p < r)
{
q = (p + r) / 2;
mergesort(arr, p, q);
mergesort(arr, q + 1, r);
merge(arr, p, q, r);
}
}
int main()
{
int a[] = {5, 2, 4, 7, 1, 3, 2, 6};
mergesort(a, 0, 7);
for(int i = 0; i < 8; i++)
{
cout << a[i] << " ";
}
cout << endl;
return 0;
} 非遞歸代碼實現(xiàn)： /**
* merge_sort: 非遞歸實現(xiàn) --迭代
* 非遞歸思想: 將數(shù)組中的相鄰元素兩兩配對。用merge函數(shù)將他們排序，
* 構(gòu)成n/2組長度為2的排序好的子數(shù)組段，然后再將他們排序成長度為4的子數(shù)組段，
* 如此繼續(xù)下去，直至整個數(shù)組排好序。
**/ #include <stdio.h> #include <stdlib.h> // merge_sort(): 非遞歸實現(xiàn)-自底向上
// 將原數(shù)組劃分為left[min max] 和 right[minmax]兩部分
void merge_sort( int *list, int length) { int i, left_min, left_max, right_min, right_max, next; int *tmp = ( int*)malloc( sizeof( int) * length); if (tmp == NULL) { fputs("Error: out of memory\n", stderr); abort(); } for (i = 1; i < length; i *= 2) // i為步長，1,2,4,8……
{ for (left_min = 0; left_min < length - i; left_min = right_max) { right_min = left_max = left_min + i; //right_min取left_max的值，以下要用到left_max的值才不會改變left_max原先值
right_max = left_max + i; if (right_max > length) //如果right_max超出了數(shù)組長度，則right_max等于數(shù)組長度
right_max = length; next = 0; while (left_min < left_max && right_min < right_max) //tmp[next]存儲子數(shù)組中的最小值
tmp[next++] = list[left_min] > list[right_min] ? list[right_min++] : list[left_min++]; while (left_min < left_max) //如果left_min小于left_max，則將最小值原封不動地賦給list[--right_min]，right_min 要先減1
list[--right_min] = list[--left_max]; while (next > 0) //將tmp[next]存儲的最小值放入list[--right_min]中
list[--right_min] = tmp[--next]; } if(i == 1) //打印第一次歸并后的數(shù)字排列
{ for( int j=0;j<length;j++) printf("%d ",list[j]); printf("\n"); } } free(tmp); } int main() { int a[1000],t,i; scanf("%d",&t); for(i=0;i<t;i++) { scanf("%d",&a[i]); } merge_sort(a, t); // print array
for (i = 0; i < t; i++) printf("%d ", a[i]); return 0; }
動態(tài)規(guī)劃解決01背包問題！ 代碼
#include<stdio.h> int c[10][100];/*對應(yīng)每種情況的最大價值*/int w[10],p[10];int knapsack(int m,int n){ int i,j,x[10]; //w為物品重量，p為價值
for(i=1;i<n+1;i++) scanf("\n%d%d",&w[i],&p[i]); for(i=0;i<10;i++) for(j=0;j<100;j++) c[i][j]=0;/*初始化數(shù)組*/ for(i=1;i<n+1;i++) for(j=1;j<m+1;j++) { if(w[i]<=j) /*如果當(dāng)前物品的重量小于背包所能承載的重量*/ { if(p[i]+c[i-1][j-w[i]]>c[i-1][j]) /*如果本物品的價值加上背包剩下的空間能放的物品的價值*/ /*大于上一次選擇的最佳方案則更新c[i][j]*/ c[i][j]=p[i]+c[i-1][j-w[i]]; else c[i][j]=c[i-1][j]; } else c[i][j]=c[i-1][j]; } printf("\n"); int contain = m; for(int i=n;i>0;--i) { if(c[i][contain] == c[i-1][contain])//未放入第i個物品，contain表示當(dāng)前背包的承受重量
x[i-1] = 0; //考慮：f[i][j] = max{ f[i-1][j] 和 f[i-1][j - w[i]] + v[i] }, if ( f[i][j] == f[i-1][j] )
else //則說明物品i未放入；否則物品i 放入了背包中，最大承重量也相應(yīng)減去w[i]
{ x[i-1] = 1; contain -= w[i]; // 放上了第i個物品，當(dāng)前背包的重量要減去相應(yīng)的物品i的重量，回溯
} } for(i=0;i<n;i++) { printf("%d ",x[i]); //1表示放入，0表示未放入
} printf("\n"); return(c[n][m]);}int main() { int m,n,i,j; scanf("%d %d",&m,&n); printf("Input the weight and value:\n"); printf("%d\n",knapsack(m,n)); return 0;}//測試數(shù)據(jù)：5 4
//2 12
//1 10
//3 20
//2 15
//結(jié)果：1 1 0 1 最大價值：37
給定一顆二叉樹的邏輯結(jié)構(gòu)如下圖，（先序遍歷的結(jié)果，空樹用字符‘0’表示，例如AB0C00D00），建立該二叉樹的二叉鏈?zhǔn)酱鎯Y(jié)構(gòu)。
編寫程序輸出該樹的所有葉子結(jié)點和它們的父親結(jié)點
Input
第一行輸入一個整數(shù)t，表示有t個二叉樹
第二行起，按照題目表示的輸入方法，輸入每個二叉樹的先序遍歷，連續(xù)輸入t行
Output
第一行按先序遍歷，輸出第1個示例的葉子節(jié)點
第二行輸出第1個示例中與葉子相對應(yīng)的父親節(jié)點
以此類推輸出其它示例的結(jié)果
Sample Input
3 AB0C00D00 AB00C00 ABCD0000EF000 Sample Output
C D B A B C A A D F C E
代碼：
#include <iostream>
using namespace std;
class BiTreeNode
{
private:
BiTreeNode *leftChild; //左子樹指針
BiTreeNode *rightChild; //右子樹指針
public:
char data; //數(shù)據(jù)域
char father;
//構(gòu)造函數(shù)和析構(gòu)函數(shù)
BiTreeNode():leftChild(NULL), rightChild(NULL){}
BiTreeNode(char item, char father, BiTreeNode *left = NULL,
BiTreeNode *right = NULL):
data(item), father(father), leftChild(left), rightChild(right){}
~BiTreeNode(){}
BiTreeNode * &Left(void) //注意返回值類型為指針的引用類型
{return leftChild;}
BiTreeNode * &Right(void) //注意返回值類型為指針的引用類型
{return rightChild;}
};
class BiTree
{
private:
BiTreeNode *root; //根結(jié)點指針
int i;
void Destroy(BiTreeNode * &t);
void PreLeave(BiTreeNode * &t);
void Prefather(BiTreeNode * &t);
void CreateBiTree(BiTreeNode * &T,const char strTree[],char father);
public:
//構(gòu)造函數(shù)和析構(gòu)函數(shù)
BiTree(void):root(NULL),i(0){}; //構(gòu)造函數(shù)
~BiTree(void){}; //析構(gòu)函數(shù)
//構(gòu)造二叉樹
void MakeTree(const char item,char father, BiTree &left, BiTree &right); //構(gòu)造二叉樹
void MakeTree(const char strTree[]); //構(gòu)造二叉樹，利用先序遍歷結(jié)果建樹
void Destroy(void); //銷毀二叉樹
void PreLeave(); //前序遍歷
void Prefather();
};
//2、定義銷毀函數(shù)
void BiTree ::Destroy(void) //銷毀二叉樹，公有函數(shù)
{
Destroy(root);
}
void BiTree ::Destroy(BiTreeNode * &t)
//銷毀二叉樹，私有函數(shù)供共有函數(shù)調(diào)用
{
if(t != NULL && t->Left() != NULL)
Destroy(t->Left());
if(t != NULL && t->Right() != NULL)
Destroy(t->Right());
if(t != NULL)
{
// cout << t->data << " "; //此語句只是為了方便測試
delete t;
}
}
//3、定義建樹函數(shù)
void BiTree::MakeTree(const char item, char father,BiTree &left, BiTree &right)
//構(gòu)造數(shù)據(jù)域為item，左子樹為left，右子樹為right的二叉樹
{
root = new BiTreeNode(item,father, left.root, right.root);
}
void BiTree::MakeTree(const char strTree[])
//構(gòu)造二叉樹，利用先序遍歷結(jié)果建樹，公有函數(shù)
{
i=0;
char rootfather = '0';
CreateBiTree(root,strTree,rootfather);
}
void BiTree::CreateBiTree(BiTreeNode * &T, const char strTree[],char father) //遞歸建樹私有函數(shù)
{
char ch;
ch=strTree[i++];
if (ch=='0') T = NULL;
else
{
T=new BiTreeNode();
T->data = ch; // 生成根結(jié)點
T->father = father;
father = ch;
CreateBiTree(T->Left(), strTree,father); // 構(gòu)造左子樹
CreateBiTree(T->Right(), strTree,father); // 構(gòu)造右子樹
}
}
//4、定義先序遍歷函數(shù)
void BiTree::PreLeave()
//前序遍歷訪問二叉樹，公有函數(shù)
{
PreLeave(root);
}
void BiTree::PreLeave(BiTreeNode* &t)
//前序遍歷訪問二叉樹，私有函數(shù)t
{
if(t)//若二叉樹結(jié)點不為空，執(zhí)行如下操作：
{
if(!t->Left() && !t->Right()) //如果當(dāng)前結(jié)點是葉子
cout<<t->data<<" ";
PreLeave(t->Left());//2、先序遍歷該結(jié)點的左孩子
PreLeave(t->Right());//3、先序遍歷該結(jié)點的右孩子
}
}
//5、定義遍歷父節(jié)點函數(shù)
void BiTree::Prefather()
{
Prefather(root);
}
void BiTree:: Prefather(BiTreeNode* &t)
//中序遍歷訪問二叉樹，私有函數(shù)t
{
if(t)//若二叉樹結(jié)點不為空，執(zhí)行如下操作：
{
if(!t->Left() && !t->Right())//如果當(dāng)前結(jié)點是葉子，輸出它的父親
cout<<t->father<<" ";
Prefather(t->Left());
Prefather(t->Right());
}
}
int main(void)
{
int n,i;
char strTree[800];
BiTree myTree;
cin>>n;
cin.get();
for(i=0;i<n;i++)
{
cin>>strTree;
myTree.MakeTree(strTree);
myTree.PreLeave();
cout<<endl;
myTree.Prefather();
cout<<endl;
myTree.Destroy();
}
return 0;
}
二叉樹可以采用數(shù)組的方法進(jìn)行存儲，把數(shù)組中的數(shù)據(jù)依次自上而下,自左至右存儲到二叉樹結(jié)點中，一般二叉樹與完全二叉樹對比，比完全二叉樹缺少的結(jié)點就在數(shù)組中用0來表示
結(jié)點存儲的數(shù)據(jù)均為非負(fù)整數(shù)
Input
第一行輸入一個整數(shù)t，表示有t個二叉樹
第二行起，每行輸入一個數(shù)組，先輸入數(shù)組長度，再輸入數(shù)組內(nèi)數(shù)據(jù)，每個數(shù)據(jù)之間用空格隔開，輸入的數(shù)據(jù)都是非負(fù)整數(shù)
連續(xù)輸入t行
Output
每行輸出一個示例的先序遍歷結(jié)果，每個結(jié)點之間用空格隔開
Sample Input
3 3 1 2 3 5 1 2 3 0 4 13 1 2 3 4 0 5 6 7 8 0 0 9 10 Sample Output
1 2 3 1 2 4 3 1 2 4 7 8 3 5 9 10 6
分析：這道題的關(guān)鍵在于：設(shè)定數(shù)組位置從1開始編號，那么位置為i的結(jié)點，它的左孩子在數(shù)組的位置是2i，右孩子在數(shù)組的位置是2i+1
這道題的難點在把樹建立起來，其他都容易。
代碼：
#include <iostream>
using namespace std;
class BiTreeNode
{
private:
BiTreeNode *leftChild; //左子樹指針
BiTreeNode *rightChild; //右子樹指針
public:
int data; //數(shù)據(jù)域
//構(gòu)造函數(shù)和析構(gòu)函數(shù)
BiTreeNode():leftChild(NULL), rightChild(NULL){}
BiTreeNode(int item, BiTreeNode *left = NULL,
BiTreeNode *right = NULL):
data(item), leftChild(left), rightChild(right){}
~BiTreeNode(){}
BiTreeNode * &Left(void) //注意返回值類型為指針的引用類型
{return leftChild;}
BiTreeNode * &Right(void) //注意返回值類型為指針的引用類型
{return rightChild;}
};
class BiTree
{
private:
BiTreeNode *root; //根結(jié)點指針
int i,len; //len是樹結(jié)點的數(shù)量
void Destroy(BiTreeNode * &t);
void PreOrder(BiTreeNode * &t);
void CreateBiTree(BiTreeNode * &T,const int arrTree[],int pos);
public:
//構(gòu)造函數(shù)和析構(gòu)函數(shù)
BiTree(void):root(NULL),i(0){}; //構(gòu)造函數(shù)
~BiTree(void){}; //析構(gòu)函數(shù)
//構(gòu)造二叉樹
void MakeTree(const int arrTree[],int num); //構(gòu)造二叉樹，利用先序遍歷結(jié)果建樹
void Destroy(void); //銷毀二叉樹
void PreOrder(); //前序遍歷
};
//2、定義銷毀函數(shù)
void BiTree ::Destroy(void) //銷毀二叉樹，公有函數(shù)
{
Destroy(root);
}
void BiTree ::Destroy(BiTreeNode * &t)
//銷毀二叉樹，私有函數(shù)供共有函數(shù)調(diào)用
{
if(t != NULL && t->Left() != NULL)
Destroy(t->Left());
if(t != NULL && t->Right() != NULL)
Destroy(t->Right());
if(t != NULL)
{
delete t;
}
}
//3、定義建樹函數(shù)
void BiTree::MakeTree(const int arrTree[],int num)
//構(gòu)造二叉樹，利用先序遍歷結(jié)果建樹，公有函數(shù)
{
i=0;
len = num;
CreateBiTree(root,arrTree,1);//數(shù)組位置從1開始
}
void BiTree::CreateBiTree(BiTreeNode * &T, const int arrTree[],int pos) //遞歸建樹私有函數(shù)
{
int ch;
ch=arrTree[pos];
if (ch == 0 || pos > len) T = NULL;
else
{
T=new BiTreeNode();
T->data = ch; // 生成根結(jié)點
i++;
if(i>len) return;
CreateBiTree(T->Left(), arrTree,2*pos); // 構(gòu)造左子樹
CreateBiTree(T->Right(), arrTree,2*pos+1); // 構(gòu)造右子樹
}
}
//4、定義先序遍歷函數(shù)
void BiTree::PreOrder()
//前序遍歷訪問二叉樹，公有函數(shù)
{
PreOrder(root);
}
void BiTree::PreOrder(BiTreeNode* &t)
//前序遍歷訪問二叉樹，私有函數(shù)t
{
if(t!=NULL)//若二叉樹結(jié)點不為空，執(zhí)行如下操作：
{
cout<<t->data<<" ";//1、輸出當(dāng)前結(jié)點的數(shù)據(jù)，表示該結(jié)點被訪問了
PreOrder(t->Left());//2、先序遍歷該結(jié)點的左孩子
PreOrder(t->Right());//3、先序遍歷該結(jié)點的右孩子
}
}
int main()
{
int m,i,j,k;
int *arrTree;
BiTree myTree;
cin>>m;
for(i=0;i<m;i++)
{
arrTree = new int[800];
cin>>k;
for(j=1;j<=k;j++)
cin>>arrTree[j];
myTree.MakeTree(arrTree,k);
myTree.PreOrder();
cout<<endl;
delete []arrTree;
myTree.Destroy();
}
return 0;
}
描述 給一些包含加減號和小括號的表達(dá)式，求出該表達(dá)式的值。表達(dá)式中的數(shù)值均為絕對值小于 10 的整數(shù)。
輸入 第一行為表達(dá)式的個數(shù) n，以下 n 行每行有一個表達(dá)式。每個表達(dá)式的長度不超過 20 個字符。
輸出 對每個表達(dá)式，輸出它的值。
樣例輸入 3 3-(2+3) -9+8+(2+3)-(-1+4) 0-0 樣例輸出 -2 1 0
//對每種情況都要考慮清楚
#include <cctype>
#include <iostream>
#include <string>
#include <stack>
#include <map>
using namespace std;
int getPrecedence(const char optr) //給各個操作符定義優(yōu)先級順序，利用map容器
{
map<char, int> precedTable;
precedTable['#'] = 0;
precedTable[')'] = 1;
precedTable['+'] = 2;
precedTable['-'] = 2;
precedTable['*'] = 3;
precedTable['/'] = 3;
precedTable['('] = 10;
return precedTable[optr];
}
int calculate(int a, char optr, int b)
{
switch (optr) {
case '+': return a + b;
case '-': return a - b;
case '*': return a * b;
case '/': return a / b;
default: return 0;
}
}
int evaluate(const string& expr)
{
stack<int> opnd;
stack<char> optr;
char last_ch = '\0'; //每次檢查字符時的前一個字符
for (size_t i = 0; i != expr.size(); ++i) {
const char ch = expr[i];
if (isspace(ch)) { //如果是空格，即跳過
continue;
} else if (isdigit(ch)) { //如果是數(shù)字，則壓入操作數(shù)棧
opnd.push(ch - '0');
} else {
if ((ch == '-' || ch == '+') && (last_ch == '\0' || last_ch == '(')) //遇到 '+'、'-'，則壓入0進(jìn)操作數(shù)棧
opnd.push(0); //如 7-1，遇'-'則壓入0進(jìn)棧，，'-'則進(jìn)操作符棧，遇到下一個數(shù)1，計算0-1得-1
if (optr.empty() || ch == '(' || (optr.top() == '(' && ch != ')') || getPrecedence(ch) > getPrecedence(optr.top())) {
optr.push(ch);
}
else
{
while (!optr.empty() && optr.top() != '(' && getPrecedence(ch) <= getPrecedence(optr.top()))
{
int b = opnd.top(); opnd.pop();
int a = opnd.top(); opnd.pop();
opnd.push(calculate(a, optr.top(), b));
optr.pop();
}
if (ch == ')')
optr.pop();
else
optr.push(ch);
}
}
last_ch = ch;
}
while (!optr.empty()) {
int b = opnd.top(); opnd.pop();
int a = opnd.top(); opnd.pop();
opnd.push(calculate(a, optr.top(), b));
optr.pop();
}
int result = opnd.top(); opnd.pop();
return result;
}
int main()
{
int n;
cin >> n;
while (n-- > 0) {
string expr;
cin>>expr;
cout << evaluate(expr) << endl;
}
return 0;
}
#include<iostream>
#include<string>
using namespace std;
char a[100];
int i;
int eval()
{
int x=0;
while(a[i] == ' ') i++;
if(a[i] == '+')
{
i++;
return eval()+eval();
}
if(a[i] == '*')
{
i++;
return eval()*eval();
}
while((a[i] >= '0')&&(a[i]<= '9'))
x = 10*x +a[i++]-'0';
return x;
}
int main()
{
gets(a);
cout<< eval()<<endl;
return 0;
}
|