|
|
几天前的东西，现在没有大兴趣了
|
过重复代码过多,比如二叉树的建立等等& S6 A$ d4 f7 S* Z
$ }4 Q j9 [( B" C- [$ k5 i( m
#include
6 X) d' g$ V* l5 g- J#include % W' Q9 Y) i; A0 k% A6 B
6 i* u. w1 K1 wtypedef struct node
& E e2 r2 J3 @{
' y8 N* }3 z: a% m3 X6 V float Data;) R$ ~, @. V3 b: l: ]
char Formula[100];
# \/ x+ k! S" x! D i+ H/ w int frist; //优先级3 w% K, Q7 [( C6 B: t: E
struct node *Lchild;$ r& f% F3 C5 D! n6 `
struct node *Rchild;) ]- e2 E" y& K% w% {+ m& h
} BinTree;
2 B! L& e7 S* i# Hvoid CreatBinTree(BinTree *Tree,int *nArray);. J; \9 j3 T* U7 f% e
void FreeBinTree(BinTree *Tree);4 q" z) e7 f) w5 A+ D1 q9 d
void AfterBinTree(BinTree *Tree,void func(BinTree*)); B. f" c" Z& j4 [' _) p0 o
float CalcBinTree(BinTree *Tree);9 Y/ w' ]8 c% X. O! d
float GetFormulaVal(int *Formula,int count); B$ Q) n, F- F9 j8 i
void ShowFormula(int *Formula,int count);! n$ ?& y4 ^; w& w% ^* [1 {, R
void AfterNode(BinTree *Tree);* x9 W" c8 A2 q( {, f' n# \! G/ v
void GetFormula(BinTree *Tree);' R* ?% g# o' }' Q2 x$ I
void Myitoa(BinTree *Tree);
# W' f) {/ t; f9 w& n6 m% U1 @! zint EnumFormula(int *FormulaNum,int num,int sum); Y2 e$ e7 _" f6 B0 d: C& ^
void Restore(int *Formula,int *NumSym,int *temp,int count);+ S& l: k4 \- {! Z
int IsOK(int *Formula,int count);/ o4 I2 u/ n- {9 X" l* \
int FindInt(int *nArray,int n,int len);
' l7 d8 X. V. r! Bint UpZero(int *nArray,int n);& I; \, @$ J% w
int IsDownNumSame(int *temp,int count,int num);
* q1 n1 O/ B4 ?* L2 q' W, U# V) J4 R
const char cSym[5][2] = {"","+","-","*","/"};
0 I6 V" X0 g+ L: V! q$ }! ]- u% Y7 x) ?* c* i# V; n; V. X. S
int main(int argc, char *argv[])
. Y) n; a6 s6 P$ u, Y{7 l* W# d3 N1 a! d% Z% z
int i,n,*Array;
: Y( L9 M4 c" O& n4 P " C" {- o2 f" C Z3 I. D
//printf("几个数？");
u; m5 `9 C; r* H& U //scanf("%d",&n);% P6 a, G7 r6 T( q$ v+ V
n =4;; {0 ]: }5 S& \6 a* ?. N8 |
Array = (int*)calloc(n,sizeof(int));
. J8 Q+ a* K5 u, r2 A9 f* K' N printf("请输入%d个数（用回车或者空格分开）：",n);- U. T3 z- l9 B8 ]! w) p; b
for(i=0;i/ p! w( }. A6 W6 m7 |+ m: A
scanf("%d",&Array);) x( d+ \1 F9 ^6 j
printf("总计%d个式子\n",EnumFormula(Array,n,24));
. d+ p# }* K @% T$ U free(Array);
& t- o- q$ Q, u2 L
( @/ e5 b' E. u0 G1 d) v system("PAUSE");- b0 a: c: @6 Y9 x, z; \& P
return 0;
7 |5 b% X9 d2 c1 T. t, |0 i7 S h}
& ]+ r2 B1 s- i! n1 c9 M& `# Y
7 d" w0 `% f! [( g! ^; qint EnumFormula(int *FormulaNum,int num,int sum)
$ E& A; R& _4 n5 Y1 \{! K: K" {9 p7 z3 q% m5 K
int result = 0;' A \* J9 c) I2 P5 ]7 ^
int *NumSym = (int*)calloc(num+4,sizeof(int)); //操作数运算符组成的可枚举组, ]" L% Y" r. m! s& v
int *Formula = (int*)calloc(num*2-1,sizeof(int)); //波兰表达式储存空间, E" {6 O8 A/ t, s, T
int *temp = (int*)calloc(num*2,sizeof(int)); //波兰表达式的代号表示空间
5 U" j- z: b* Y6 v) G+ Q$ z1 l int i,j;7 W/ r$ a1 M, u& \) u# L* U0 }
for(i=0;i = FormulaNum; //载入进行穷举的操作数
: w8 M& J O1 f/ i0 K$ I" E for(j=0;j<5;j++) NumSym[i+j] = -j-1; //载入进行穷举的运算符号* d% j: ]8 t* T
7 S* W0 r% q4 Q3 t6 @
for(i=0;i = 0;4 J7 H5 }5 x8 G4 u9 X; _4 m6 d
// 穷举开始，结束的标志为波兰表达式代号空间最后一位已进位，即前面各位已穷举完成 ~( J# z5 u* d% \% Y- q
while(temp[num*2-1] == 0)0 v+ ^. c4 t' K e, r1 v4 o/ P
{
4 i( g+ g/ J( D+ j9 Q2 O, | if(!IsDownNumSame(temp,num*2-1,num)); f9 E* V2 c8 E( x
{ N% }; N3 @& ?, u
Restore(Formula,NumSym,temp,num*2-1); //还原波兰表达式
1 h: a" y9 x% N9 P: |3 { if(IsOK(Formula,num*2-1))+ r4 W' w x, r9 c, M
{/ i+ x0 c/ v) G/ [
float t; //结果偏差
0 O8 F$ E0 T3 V% R0 ] t= GetFormulaVal(Formula,num*2-1) -sum;1 `9 b% e; }0 w1 R) f6 [
if(t>-0.01 && t <0.01) //结果为浮点数，只能进行近似比较& x7 _8 U) t4 E! D
{
% B: o% x6 H7 }) F+ X result++;
# t" c" {6 J6 F: D+ v* G7 T ShowFormula(Formula,num*2-1);
7 h" M- a4 C0 j* Z$ D }* z! Y5 e1 i" v: b2 [: J
}
) F+ {1 n- H* Z }
2 ~# d2 L: m0 Z temp[0]++; //穷举动力# N# @: a1 A0 Y
for(i=0;temp > num+3 && i//代码空间类进位
7 H5 C9 u5 w% {1 C2 R {
6 a- S* j! I# @ F/ N temp =0;: F6 o+ I& n% ?$ B9 O. ^! N8 B
temp[i+1]++;
+ \# l1 {& `0 Y; n% h5 I( } }$ W1 E1 M9 r3 Q
}
* G# P2 M W' s0 w6 e1 d6 O! U5 ? // 释放内存
( G9 O$ h& X' ? free(temp);
* k3 F+ R- Z3 P2 x# p! Z, B7 D5 t! r- b }) h; V
//free(Formula); //？？此处不知为什么会出现错误
3 N# W0 m1 T+ C, f$ j free(NumSym);
# V. \- S* f/ ~ return result;
% t: e' e/ j% e: W. I# [0 W8 T}% y8 s8 ]3 ?; J: B$ L, Z7 x# i
// 由代码表还原为波兰表达式
% U: M" t7 U! x: p- }void Restore(int *Formula,int *NumSym,int *temp,int count)5 G3 Y. Y) g4 V1 s# m0 g
{$ ]0 D( a _ k9 C: H! r4 K
int i;% Z: t1 K9 M$ O
for(i=0;i = NumSym[temp];' p" t* ?7 r7 W4 Q
}5 o# _9 e* m; j3 u( `
// 判断是否符合波兰表达式/ b7 D0 F& a. j
// 符合的条件是每个运算符号前必须是操作数个数多了运算符个数3 Q# K9 Q! \ q" v( y
// 且运算符个数为总数减一的一半
# _+ a3 d0 n% D, D+ uint IsOK(int *Formula,int count)
/ X& ~" o e6 d4 q7 P{- N; C. z: C0 J: \9 [
int i,j;9 f$ K& d/ U) \
for(i=0,j=1;i/ a G( [! w$ G1 i( n% W if(Formula<0)
: ^; F7 p7 N& O) ^! V7 E if(UpZero(Formula,i)>j) j++;
" n8 V% `2 [0 }( M! F, v$ M# { else break;
$ X2 X7 q5 v9 t) N j if(iint)count/2+1) return 0;5 Z- g1 a* N# t, _" }
else return 1;6 F& C4 X( y/ u$ F$ I# N
}
8 q2 p$ V# ^" N# C// 查找数组大于0的个数
7 i% R; J% l6 H0 ~int UpZero(int *nArray,int n)
6 a& I! F7 g* Y; K' g{+ \1 Q% o3 x+ l
int i,result=0;
: I2 [( o. j% A' h7 q8 K! n9 J for(i=0;iif(nArray>=0) result++;, M9 |' R+ O' O" ]
return result;
6 E2 `4 z7 C$ F- x4 |# ~: L$ y}, W% c, b* z) L! m/ u) W2 l8 ]) x
// 查找数组中，小于Num的数是否有重复1 W6 G1 g* C- L$ R$ _
int IsDownNumSame(int *temp,int count,int num) R1 r s/ U4 a* k* K' Y4 o
{
- ]. l" i; i& R6 C; Q, n5 s( h int i;
' s' U3 t1 G& Q; I W& _ f for(i=0;i4 {4 p1 o* K' C6 ~$ I+ \ {
" \3 k5 \7 B A1 u) w% u2 C if(temp < num)" P2 R% A4 Z1 z& r
if(FindInt(temp,temp,i) != 0) return 1;
: l& A( @- b; V# @- I }
3 B7 R+ @% }5 L: ?9 G: R2 ~ return 0;' O* |$ x0 N6 D; {% \, F8 b% R
}& h8 v3 N7 y6 k- q# [+ {
// 查找数所在数组的位置，返回0为未找到 J: v v7 m1 T; Y/ U& H
int FindInt(int *nArray,int n,int len)
6 n" g7 P1 y' r# o2 Q/ C{
( c8 g" S. L' k( a7 V" R. k int i;
( t! S% ?6 v+ i1 ^ V! e" N5 M for(i=0;nArray != n && i) k$ c/ `( G6 [& k8 n if(i>=len) i=0;5 j4 v6 m2 ?+ A C( l4 d& s" n* a3 R
else i++;
) K% `& g2 n- w- C return i;
& i% F3 U: `( D( u}
, o9 b, r: v! W) e6 r: A0 y& O) E; R. o/ s
// 计算算式结果
/ m1 ]7 @! T i9 s. Z+ [2 f0 _float GetFormulaVal(int *Formula,int count)0 s, W# A7 Z* g$ k, U
{
8 ?, o% b% w* c float result;. I6 ]- S4 X: |; i$ O" M
BinTree *head = (BinTree*)malloc(sizeof(BinTree)); //二叉树头节点
1 ?+ {' G0 g- g9 i int *nArray = (int*)calloc(count+1,sizeof(int)); //波兰表达式储存数组，首位表示数组有效长度
& f9 g* u B, V" W5 K3 C; f' v; O, p0 v7 F* B
int i;
9 W/ v3 F" B: T; F' @ for(i=1;i<=count;i++) nArray = Formula[i-1]; //复制波兰表达式
! ^; g1 ?1 m% e) ?+ Z4 x nArray[0] = count;; X, x& G" J! ?: _; z
CreatBinTree(head,nArray); //建立二叉树' U7 z! C4 c1 q0 R+ [! q/ C
$ S4 d. V/ W5 M' m. T4 R! {9 y
result = CalcBinTree(head); //计算二叉树算式
3 x. R2 {: Z8 t AfterBinTree(head,&FreeBinTree); //释放二叉树空间8 G$ ?# Z D) k" S% |3 l) V# }
# c& n3 v8 t: M3 O2 Q
free(nArray);, T0 x' p: G( E/ h% ^5 j
return result;
x, A' @) {' R1 N}
! B5 d( |! O9 D0 ]5 N4 E! ofloat CalcBinTree(BinTree *Tree)
$ q4 d, o* }! m, j& i4 ^{/ [& T8 L O: s+ g% s. n
* j; @) I+ E7 u/ B2 S( C- J: [
AfterBinTree(Tree,&AfterNode);# v. H1 ^* I4 [. U
return Tree->Data;
* D# b* O$ h3 M- ]4 Y}" w4 k3 P0 C, h( D8 b9 V, X/ q
( N/ h, M) ^4 ]. S
// 后序遍历二叉树进行计算,但会破坏二叉树本身/ m* U% _6 O- n o& Q
// 一个结点的结果为左子树 （运算符） 右子树! h% @2 w" V; Y7 c0 `+ n; [
void AfterNode(BinTree *Tree)4 V3 d( `3 J) F- I
{
{# k) b* s* E switch((int)Tree->Data)% ]( a8 g( g6 [3 Q. c
{
! P5 G% F( S; z2 Q4 ` case -1:5 l2 H7 t1 E0 j
Tree->Data = Tree->Lchild->Data + Tree->Rchild->Data;
8 n# i- y9 f+ N6 l break;
7 d( }* ]6 ~% [: Q( F- N case -2:1 S$ I5 A6 y, b) [" b7 q
Tree->Data = Tree->Lchild->Data - Tree->Rchild->Data;
# \. ~7 e+ f4 K8 c break;" h- N& r1 c4 w, K. G; Z
case -3:
3 q8 n( |* Y8 Q Tree->Data = Tree->Lchild->Data * Tree->Rchild->Data;
8 D- y8 l- Q8 G) D break;
8 S- ^& M o, @+ F" b6 C9 {' P case -4:* h2 L n* G& E; f" N6 a, U
Tree->Data = Tree->Lchild->Data / Tree->Rchild->Data;
5 I$ Z7 j- {7 U6 L: @ break;
2 ?+ b* u$ C& [+ `( l3 s }
. V$ l$ U+ {( B}
, `9 C. }' t5 U1 _# `; [9 o// 打印算式: y ]7 o: H0 W4 B8 e1 | P: c4 B. Y
5 U7 ]8 `% e) @4 Yvoid ShowFormula(int *Formula,int count)
; M% q0 J* R5 Y2 c{
' V7 p) b1 t) ^/ l" I BinTree *head = (BinTree*)malloc(sizeof(BinTree)); //二叉树头节点- ]8 s) F9 _# o% N
int *nArray = (int*)calloc(count+1,sizeof(int)); //波兰表达式储存数组，首位表示数组有效长度" G1 s5 Z: d# q7 ?. N5 _% a
int i;
2 u) n. f+ L; @7 p, A8 t1 `. Q for(i=1;i<=count;i++) nArray = Formula[i-1]; //复制波兰表达式
% X8 D$ J8 X z" w4 f nArray[0] = count;
1 {/ d2 n! q9 }: x* R' R( O CreatBinTree(head,nArray);
1 E2 z/ Z+ b1 v7 u0 O2 z- M AfterBinTree(head,&Myitoa); //初始化二叉树字符窜部分
" o, E! s8 C0 ?0 A2 P( r2 C3 I AfterBinTree(head,&GetFormula); //转化为普通表达式- M1 |& I( O/ D1 i8 C/ `6 Q
printf("%s\n",head->Formula);
9 U# T; H( a3 S AfterBinTree(head,&FreeBinTree); //释放二叉树空间
8 Y0 _' ?2 a: ~ free(nArray);% r1 q# c" v, x% X
/ f L/ A0 I4 J$ o2 ~
}
7 \. G4 ?" x7 t: e5 W' W// 类似计算二叉树! a( P: P/ ~0 M7 k
// 会破坏二叉树本身, { q# R( r7 W0 O. u
void GetFormula(BinTree *Tree)4 i$ b; ]* p! {' I
{
( |7 N9 e( ^8 j% F" [2 r/ w, n // printf(Tree->Formula);: G9 }# e! ? _$ t) S5 O- ?. Q
if(Tree->Data <0)
0 i& \' P% \$ l! I: R! z {/ b: d; N2 s1 ?7 M9 x+ \1 @9 y
char temp[100];
; c% J- A( `( }. W+ G if(Tree->Lchild->frist < Tree->frist)
1 |* ]/ T' w2 s* e0 Y5 x- ~# c {
5 v# e4 Y) q) T' H strcpy(temp,Tree->Lchild->Formula);
4 c) j: ?' p* _5 g3 k8 a strcpy(Tree->Lchild->Formula,"(");
& \2 l3 R- v% f) w6 \ strcat(Tree->Lchild->Formula,temp);* @" p5 b7 i; W9 u+ t; y
strcat(Tree->Lchild->Formula,")");$ ^# T4 w5 q* Z0 a, p/ @
}
7 c6 Q8 ?* d8 V if(Tree->Rchild->frist < Tree->frist
8 y. j6 |( l. D" n5 i b$ \& f$ X || (int)Tree->Data == -2 && Tree->Rchild->frist == 0
, m2 ^; }* }2 o1 I || (int)Tree->Data == -4 && Tree->Rchild->frist != 2)8 g* m& X4 B: E% q
{
% \# E6 P! n( f4 z strcpy(temp,Tree->Rchild->Formula);! X/ N0 V) W4 ^3 C
strcpy(Tree->Rchild->Formula,"(");7 L$ u) A' |2 ?% j$ d
strcat(Tree->Rchild->Formula,temp);
- u7 m' l- Y3 \ strcat(Tree->Rchild->Formula,")");, _$ F. R" f1 I# V
}7 j$ Q* Y4 ?& b5 l* c
strcpy(temp,Tree->Formula);6 `9 t( m' X' j1 S
strcpy(Tree->Formula,Tree->Lchild->Formula);
; h/ u3 c1 z' C strcat(Tree->Formula,cSym[-(int)Tree->Data]);( I, w6 r) j! _$ p( Q3 [
strcat(Tree->Formula,Tree->Rchild->Formula);; D' K, Y* J" |4 t$ b/ v
}* e5 Q( B+ D7 C- `! w
}
+ ^* ~5 z4 W; }. v5 Z// 对二叉树字符串部分赋值
. E! s! y' B; i: x% K+ Evoid Myitoa(BinTree *Tree)# \/ {4 @, p" U1 j% `, d
{& F1 A& b0 f1 t, u3 E# D% w
if(Tree->Data>=0)
4 b+ n! i- u- ?9 U+ ^ {" G) h% X9 [) H) N/ B
itoa((int)Tree->Data,Tree->Formula,10);
/ a+ u6 s( j# I Tree->frist = 2;
0 C- v; @- u4 X: w2 T$ |7 m }! E0 l T; Q7 |
else* n1 ^$ j7 I, E( ]% K1 t" L' r3 j2 S4 x
{2 j6 W# n% f' c* k4 P3 `6 v' @$ `
Tree->frist=Tree->Data < -2 ? 1:0;$ h- p( _% Y1 c! f1 m
strcpy(Tree->Formula, cSym[-(int)Tree->Data]);% y9 h/ E _; I V
//Tree->Formula[1] = 0;6 t8 F3 W# r( F
}6 _1 d, N- p, S4 o) |4 c0 m' J; o# P
}; V, u9 v+ U* ]
//从一个波兰表达式建立一个二叉树链表，需指定一个头节点6 o/ \* \' b" [8 O5 ?8 x9 [; E: x
void CreatBinTree(BinTree *Tree,int *nArray)8 K. K& p' T6 X' F
{
6 g# j/ @% h7 R Tree->Data = nArray[nArray[0]--];
* G; {! _# T' ]0 F if(Tree->Data < 0)
( m1 j( h9 j% Y$ ? {
/ Q: ^" p: f9 k Tree->Rchild = (BinTree*)malloc(sizeof(BinTree));
% l9 ?* p) v5 w5 ~! z3 w: X CreatBinTree(Tree->Rchild,nArray);; a% ` r. {9 m* A8 C3 ^6 m1 Y9 b2 ^
Tree->Lchild = (BinTree*)malloc(sizeof(BinTree));
' O& C; o1 ~8 |' { CreatBinTree(Tree->Lchild,nArray);4 U# P3 F7 A5 [( V2 h9 n# Y# g
}
! b7 ~9 U! J$ F. P( b7 m3 c8 p1 A else
/ M" }5 b( z3 @0 k, Y, F { u1 I2 _6 a$ J- a
Tree->Lchild = 0;
3 F% n! }7 @9 ^4 f Tree->Rchild = 0;
' H3 e1 t. t- X. O* S6 i }7 [8 w0 q0 z$ p( g1 @6 |
! u- i" f8 j; |: V n' y4 l( ~}
`! l. l! W+ y6 R6 o- m
3 t+ I8 S8 J h1 \# ~* U2 g// 释放二叉树空间) j, H( ~* [2 z( Y1 h
void FreeBinTree(BinTree *Tree)0 ~: m; s7 B0 F2 t, X) c+ @3 Y/ \
{
2 i( l* f% U2 W: r1 Z free(Tree);
9 v, T* F6 c( [! g; S}
" N9 y5 v: ]1 Q' ^ P" P/ b// 后序遍历二叉树& g6 b+ \5 a+ G* k- R. V5 o, k$ F. S
// 方便其他函数调用，func为要对各个结点进行操作的函数指针+ Q# y, l2 T) C: V6 U8 T
void AfterBinTree(BinTree *Tree,void func(BinTree*))
) G1 L2 P, C& r; Q+ K{
! G& F% I7 a9 O- U# g if(Tree)) o. i8 a6 G5 \' d* U$ b
{
$ E, g, h# z" u* T AfterBinTree(Tree->Lchild,func);# V" e e$ H ~5 f
AfterBinTree(Tree->Rchild,func);4 [1 p+ D6 @- `1 |6 o3 _3 x0 p
func(Tree);
6 L" J+ D4 k; L' c7 @4 W/ o8 b: x }
# I! o! J" I( @7 a9 e}; M' M3 X7 @6 i6 x `
|
|
楼主: 考拉
/1 
IP卡
狗仔卡
发表于 2004-5-2 15:40:00
显身卡
发表于 2004-5-2 15:50:00
