|
|
几天前的东西，现在没有大兴趣了
|
过重复代码过多,比如二叉树的建立等等
$ ]1 j8 U3 [6 P
+ A; g$ Z$ D. y- ?% S6 X#include
+ y9 Z6 t4 @+ ^4 v#include
0 C3 k+ C' H+ K, i% H8 i4 ~+ F- p7 v/ T' L+ m; I3 u) H$ M. ]
typedef struct node
. \; G5 }' g l) ?4 N# P/ R. U{& ~& Z" Z; z) \+ @" ?' F
float Data;
% D& o5 _% P% Y R3 u4 O6 M char Formula[100];0 J% Y' A, ]8 f! \, y0 w$ d
int frist; //优先级, Z. c/ X" X) J2 r Y, u
struct node *Lchild;5 c# B: s: m9 ~7 U# t
struct node *Rchild;+ c: ~* K7 w+ |# N% y% s! V) V
} BinTree;# ^ r" I; V# A ?
void CreatBinTree(BinTree *Tree,int *nArray);; \% r0 h9 e4 }0 m$ ~: Q: i: X6 M ^
void FreeBinTree(BinTree *Tree);
; p. s6 V; Q" S: w6 I3 M- Z, kvoid AfterBinTree(BinTree *Tree,void func(BinTree*));8 n" V& d: g- O m5 v0 d6 Y
float CalcBinTree(BinTree *Tree);
/ n( K. K4 P3 i* xfloat GetFormulaVal(int *Formula,int count);- D i: D; ?, r
void ShowFormula(int *Formula,int count);4 E! i1 N; Y9 M! V4 E2 Y2 Y6 t
void AfterNode(BinTree *Tree);
& r' s' ]$ o A9 @5 o; Q7 k0 Uvoid GetFormula(BinTree *Tree);2 A' o: t, i7 l/ c
void Myitoa(BinTree *Tree);, D( Q5 Y9 R( M
int EnumFormula(int *FormulaNum,int num,int sum);
9 g0 D6 _( H4 e ]$ B$ f% Tvoid Restore(int *Formula,int *NumSym,int *temp,int count);4 u7 U" O& {2 g) U
int IsOK(int *Formula,int count);
3 }, \& O9 K- j8 i* z+ j/ g* t" Nint FindInt(int *nArray,int n,int len);
) r& l X7 V4 \$ }4 dint UpZero(int *nArray,int n);
+ \# L5 W* `$ c# u1 J( k- zint IsDownNumSame(int *temp,int count,int num);$ f& @' D, B4 i4 j
2 e U& P! c0 v2 ^const char cSym[5][2] = {"","+","-","*","/"};, L9 f& |. L; I
% M& p4 P u1 P! b& P) `6 a; Aint main(int argc, char *argv[])3 x7 c# l/ r4 _5 K" A+ T& S9 D( E- U0 Z2 A
{6 \$ i0 Z2 r3 m: T7 Y* W! Y
int i,n,*Array;
( s3 W& H/ ^; V
0 ~3 j2 Q' J+ Z1 S- m* ?, g; V //printf("几个数？");& z$ h) A' P9 w" y6 s
//scanf("%d",&n);! O0 v9 @ n$ i) V" c3 d" l
n =4;
- ]. V1 y) h- ?* E Array = (int*)calloc(n,sizeof(int));
- y2 W9 ?4 z+ i9 c printf("请输入%d个数（用回车或者空格分开）：",n);
, R' E# T3 w0 r% J for(i=0;i" v! T8 L" @' Z, q% a. O" \
scanf("%d",&Array);$ h n [' A1 ^. O: t5 R
printf("总计%d个式子\n",EnumFormula(Array,n,24));, q. h6 H+ s) ?6 g5 d
free(Array);' N/ v- D- ?% D# G* b
7 a0 e4 N( b. }2 U system("PAUSE");* q5 T- w# ]( ^/ T
return 0;
: I! j/ {4 _( ]}5 M5 V) E9 W5 B# l. T+ w
# P# P4 o# \, R: \3 W
int EnumFormula(int *FormulaNum,int num,int sum)- \; e* o# V5 X: a0 F8 L' [: z
{1 q$ h7 a3 k- F e) P# w4 D5 _
int result = 0;) D( l& O; }/ _/ X1 j
int *NumSym = (int*)calloc(num+4,sizeof(int)); //操作数运算符组成的可枚举组8 x% N+ U* X2 b
int *Formula = (int*)calloc(num*2-1,sizeof(int)); //波兰表达式储存空间
: S* A: N8 C) n3 c& @, V3 t int *temp = (int*)calloc(num*2,sizeof(int)); //波兰表达式的代号表示空间) d- E- p. ?9 J6 l* L' m) |" h$ a
int i,j;- U$ O8 \& M3 ^5 `2 h6 C9 t8 O
for(i=0;i = FormulaNum; //载入进行穷举的操作数& c- t, ^5 v/ l# Y# U8 Y8 @
for(j=0;j<5;j++) NumSym[i+j] = -j-1; //载入进行穷举的运算符号) N/ l1 o/ ^, E0 l* [, t$ T3 w' m
" A5 ^! v# c0 Q) I. e
for(i=0;i = 0;
- m; l. L1 d u3 E' X4 ]8 V // 穷举开始，结束的标志为波兰表达式代号空间最后一位已进位，即前面各位已穷举完成
. u$ b0 |' U1 _. q7 R5 Q while(temp[num*2-1] == 0)
! d6 n; l) B1 [) N" J/ o" Z. Q {8 h2 o, L5 d+ N2 Q; D+ A
if(!IsDownNumSame(temp,num*2-1,num))
3 }) U- }' C' g9 ~+ P& } {, W$ H3 s, s! D& {& _5 N8 E$ l5 G
Restore(Formula,NumSym,temp,num*2-1); //还原波兰表达式
+ ^/ @( x2 O; ?5 |" E; M8 U if(IsOK(Formula,num*2-1))3 Y2 V# w. f! W* |, _ @
{
& x+ ~! E* l! Z) P$ S: N( P float t; //结果偏差
! d+ `6 g. P7 a7 n) ~ t= GetFormulaVal(Formula,num*2-1) -sum;
; W- ?4 ]# k! W* _8 O: \; x if(t>-0.01 && t <0.01) //结果为浮点数，只能进行近似比较
7 J' f2 J2 _: t { @$ B& ~5 ~8 l4 E+ _7 E) B: x
result++;
7 s" h: Z: H3 u ShowFormula(Formula,num*2-1);. q7 H6 V7 R! O2 h+ Z# m, W
}
% e6 e# u1 f- u }
. h2 a/ d" f0 t }
* V, ? e9 ~/ r2 t) D temp[0]++; //穷举动力
$ X, F8 c! G- R; r( A( o for(i=0;temp > num+3 && i//代码空间类进位
6 b: j- G9 w6 }5 t6 ]6 ` {
7 N3 ~! o9 F* Y5 t temp =0;5 y) B l/ r: Q4 P3 B
temp[i+1]++;, m0 M: E/ K2 q' b J
}
" s {' V2 x! U$ I( U }8 f+ C' h0 Q0 O1 S/ K- P
// 释放内存" T G, H: t2 E3 Y' O- X8 H
free(temp);
; X% z) `, ^; B0 T% s1 [' y# m+ H. K/ Q/ w2 `# d% j1 C% R4 ~* L! r
//free(Formula); //？？此处不知为什么会出现错误! f9 y0 ?% ~ s/ K
free(NumSym);" }* K( a( C' U9 s, r- ~
return result;$ i6 W }; p+ b& R# P; B {7 u
}4 p: x/ @* g8 K1 _( z
// 由代码表还原为波兰表达式
4 _+ P* r- b0 _2 o3 cvoid Restore(int *Formula,int *NumSym,int *temp,int count)
9 X3 H8 r8 N$ D/ v2 L# w. e$ ~' O{
/ M( I1 t2 D; v int i;
+ K! H: [" K7 n) Z for(i=0;i = NumSym[temp];8 V8 |- x2 T8 q! X
}7 b: M% R& }. d5 w
// 判断是否符合波兰表达式
9 I8 b$ h8 a! P O3 P- ^// 符合的条件是每个运算符号前必须是操作数个数多了运算符个数
5 T; [8 W, u0 L D" Z0 A* [# _// 且运算符个数为总数减一的一半
9 o- y2 c; G2 k. H; @. r! c6 dint IsOK(int *Formula,int count)
% s; L# ~. b5 ^; n( L4 U{9 H9 A- M$ v! p4 A( X
int i,j;
. J% P* N0 \2 T u for(i=0,j=1;i+ q1 ^! {8 m& q* s2 b* }
if(Formula<0)
4 u+ p) A* O6 W if(UpZero(Formula,i)>j) j++;
! h; \; d3 y' e0 T) c else break;
0 e0 Y0 ~ _9 S! n }0 C# Q/ B if(iint)count/2+1) return 0;
! e- D, Z; p2 V+ x, Y else return 1;
3 x1 N. @% p% U" |* c}& \- N3 S. [6 O% d3 z9 g4 @+ Z
// 查找数组大于0的个数4 l k5 d* Y4 p
int UpZero(int *nArray,int n)- c7 H* k; b1 b% V1 a" P
{
' m& v2 r- C) d6 j( \ int i,result=0;
; }$ Y# ]7 J4 y$ P* g for(i=0;iif(nArray>=0) result++;
# j9 b" V- x# |3 q9 ~4 e/ f) F$ [ return result;
. |; z$ n3 v: L- h l}
8 m! ]9 p2 L# n2 |// 查找数组中，小于Num的数是否有重复
0 B9 i q+ h+ z- c' F# Q" Gint IsDownNumSame(int *temp,int count,int num)
" f: ~, ?8 p" [4 t{
* }: X+ w* n; U0 T) E. S int i;
. j% z" ^2 f8 n: _! X5 w: a. | for(i=0;i: O8 N7 m3 C+ h9 V n' _8 b% b+ \
{) ?6 t# z. f+ _8 s" S, L" s' k
if(temp < num)- `6 p/ V/ {8 ~
if(FindInt(temp,temp,i) != 0) return 1;: m9 X. K6 E/ t0 N. {# f
}' d0 _/ ?/ Z* g1 U6 I- W0 p7 e
return 0;
, f9 o p/ k8 P+ t, M$ \! W% p( N}
" Y" I+ ^/ ~7 G// 查找数所在数组的位置，返回0为未找到4 ~3 }+ `$ o& b0 L( W
int FindInt(int *nArray,int n,int len)6 U- \- v9 i! z3 e" z( h5 {+ {: T, f% C9 r
{
# L7 K1 p, s% w8 A0 f int i;( r3 M& i: B7 l2 i
for(i=0;nArray != n && i/ `3 _/ X% t9 I: r; f$ Q
if(i>=len) i=0;
, l5 D% v# i8 e else i++;; p( D( B O- k0 _/ n a2 o( {- `
return i;
) k/ }# Q# C: e* j}' I" y# b( B x1 [- E
( m6 E# p7 M/ E: |+ W0 @// 计算算式结果1 Q5 p/ d1 L" h/ g5 i1 {3 y, x4 n3 Z7 G& f
float GetFormulaVal(int *Formula,int count)
$ C, g `! Q! I{
2 B" d* Z$ @. h4 \ float result;; M) _. y5 x z0 O: B( z
BinTree *head = (BinTree*)malloc(sizeof(BinTree)); //二叉树头节点3 V# `1 ~ Z/ ?6 v+ O" l
int *nArray = (int*)calloc(count+1,sizeof(int)); //波兰表达式储存数组，首位表示数组有效长度
! b A: G9 N, ?! ]2 l' ?5 ]# A$ t2 q
int i;
9 ?# |0 a1 e' a- c for(i=1;i<=count;i++) nArray = Formula[i-1]; //复制波兰表达式% t; U ?4 P8 [% C6 E
nArray[0] = count;, Z! ^ y- C" ~6 T: A
CreatBinTree(head,nArray); //建立二叉树! m5 p) `& |6 F( @0 z
. [8 |* g4 L0 U
result = CalcBinTree(head); //计算二叉树算式
6 X+ N5 o c" V3 J AfterBinTree(head,&FreeBinTree); //释放二叉树空间& @1 g, \ E3 M
& s& b( i+ Y& m. O& m/ g* r9 ^9 b/ L free(nArray);
$ p- G# b: \5 u8 C3 _ return result;
! c4 Y. s# J8 I}
+ K3 ^* R3 s' ~# F+ o- i/ Vfloat CalcBinTree(BinTree *Tree)1 Y7 j7 M1 @# `1 T9 {7 x
{
0 Q- X0 h; w0 m% @# I- @
% p, N9 z3 j/ t+ T& g. X AfterBinTree(Tree,&AfterNode);1 I* Z0 r, ]6 @2 R1 N3 A
return Tree->Data;
% @. Q* Y4 W M! W3 s}* q" `# x' n! D& p- T
0 _" m1 G- o O. Y* R9 K// 后序遍历二叉树进行计算,但会破坏二叉树本身. s4 h8 h+ Z# d6 d9 x9 E5 B# ^
// 一个结点的结果为左子树 （运算符） 右子树
6 c! P4 M0 {! h5 Ivoid AfterNode(BinTree *Tree)! X' }* G$ g% D; o; G
{$ s4 w) @7 ]( a, K M3 W
switch((int)Tree->Data); l# P* p8 h3 D+ s% c
{
5 {% _/ d5 J0 [2 n9 U8 C8 v1 M case -1:
$ G8 V$ H* o8 a9 Y7 }! p Tree->Data = Tree->Lchild->Data + Tree->Rchild->Data;* Q! K# Q# f: Z1 I+ g+ A& ]# X
break;. h; f3 u0 d! @# ?
case -2:
) ?6 G$ p$ W$ s; R! ? Tree->Data = Tree->Lchild->Data - Tree->Rchild->Data;
/ C7 W6 U* z p) R) ]9 C break;
0 l. ^; J3 R4 _ case -3:
0 r) H- k/ m4 T" |: h. F Tree->Data = Tree->Lchild->Data * Tree->Rchild->Data;
5 Y" m1 B: k* V, F break;
: c% S( Z' [6 d; q% T2 T; e case -4:& D6 {' P, ]- p3 h
Tree->Data = Tree->Lchild->Data / Tree->Rchild->Data;
7 O" l$ k3 e* I) V. J7 A S break;
: N; ]6 M6 }$ q }
1 l% f( j6 R. X( s}
: H# p. H& E1 O// 打印算式/ S# ^$ D1 b; o! z+ j8 J
: I" c& M$ }$ [: l$ D) n4 f0 R+ h! f
void ShowFormula(int *Formula,int count). @$ K4 i; J! x; ]- U
{+ \$ P9 o$ G2 i% ?- o( h; M) F \
BinTree *head = (BinTree*)malloc(sizeof(BinTree)); //二叉树头节点
* X, N9 @( j+ }9 T; Y* P: v/ w; j int *nArray = (int*)calloc(count+1,sizeof(int)); //波兰表达式储存数组，首位表示数组有效长度
3 F7 u) z. Q( a- `( | int i;6 `; X7 v4 @+ G, T4 _
for(i=1;i<=count;i++) nArray = Formula[i-1]; //复制波兰表达式3 X% J/ M1 m6 B' S% `+ @& B6 G; T% A
nArray[0] = count;3 T( Q% M/ \0 K) P- M: d
CreatBinTree(head,nArray); ( B1 y! w2 v# v% F
AfterBinTree(head,&Myitoa); //初始化二叉树字符窜部分5 x" s/ [' \+ p
AfterBinTree(head,&GetFormula); //转化为普通表达式
' }- I! f' J E( k5 r, a6 P& }- k$ @ printf("%s\n",head->Formula);% \: F% Y3 ` h8 D! y% y' m$ f
AfterBinTree(head,&FreeBinTree); //释放二叉树空间( w8 O6 l0 Q: f$ S* b: u
free(nArray);* L9 H7 q' X/ j2 q
6 F2 u1 D- v' T) k& B ~9 d, p
}+ T* A' {* U* \4 J
// 类似计算二叉树
. T q7 f, O$ u( [3 Z// 会破坏二叉树本身. S# ^# U; ?5 ~0 g8 S7 S0 P
void GetFormula(BinTree *Tree)5 C2 N& S& _$ V& c* [* U) u
{6 ]: J. y6 ]5 V+ H
// printf(Tree->Formula);
1 _/ `( ?/ E! \; B! M% J if(Tree->Data <0)
/ _# V, T, \( z" l$ D9 x1 x" q' C( R { K' Z; Z. C2 y' \4 m
char temp[100];
0 L: }& x% Z' ?9 s9 Q2 d' E! ^7 w if(Tree->Lchild->frist < Tree->frist), c8 k2 B! \- l
{9 R7 N$ q8 ^ P% }5 ?
strcpy(temp,Tree->Lchild->Formula);1 X9 ~$ F0 n! V1 X
strcpy(Tree->Lchild->Formula,"(");: _4 I: K* \2 S* l1 H
strcat(Tree->Lchild->Formula,temp);
, P; X* B; X" ~; n strcat(Tree->Lchild->Formula,")");$ [4 q7 b6 `- T
}* k+ N9 L0 H( _, {: ]
if(Tree->Rchild->frist < Tree->frist; e3 [, Y$ b+ v% Y l$ k2 O
|| (int)Tree->Data == -2 && Tree->Rchild->frist == 0
% a8 y d+ D5 K5 Z, w `5 { || (int)Tree->Data == -4 && Tree->Rchild->frist != 2)7 A* ?# W* C% W; W
{5 v: B) a* P% H% m
strcpy(temp,Tree->Rchild->Formula);
2 }1 t8 R) l- N strcpy(Tree->Rchild->Formula,"(");
7 b7 m" I8 J9 |+ | strcat(Tree->Rchild->Formula,temp);
8 D$ y9 d" `4 D6 @ strcat(Tree->Rchild->Formula,")");9 F& o4 V( h. ]$ t& c) T& _# F
}
( Z- S; C, Z: K! g2 y6 O( j strcpy(temp,Tree->Formula);! U0 U5 s1 I" U2 f
strcpy(Tree->Formula,Tree->Lchild->Formula);
' ]$ `3 D& T( n* r" | strcat(Tree->Formula,cSym[-(int)Tree->Data]);
2 S( }& x( U& w) r1 ^ strcat(Tree->Formula,Tree->Rchild->Formula);4 Y' M: K, b2 m
}
* a6 x2 Z% ?1 r w6 F& M}/ P' L( E6 d* x5 G1 y5 p; w
// 对二叉树字符串部分赋值
0 ~$ `% U% Q, w. A$ _: w. ?void Myitoa(BinTree *Tree); k7 s4 o' t' r7 P3 R1 K
{
/ A P0 R* F: H0 Z# L) E) m& S if(Tree->Data>=0)
. z6 N5 ^( L6 T8 j- w {
9 _( c _8 L A itoa((int)Tree->Data,Tree->Formula,10);
$ }0 A) v; o/ b) O& j- ~* S' ] Tree->frist = 2;7 \$ o9 v; Z7 V
}
- S( l9 s2 s8 ~. ~, ? else/ X: h3 z+ N8 J3 O
{
0 e0 E* U9 S- K+ L7 { Tree->frist=Tree->Data < -2 ? 1:0;
7 b9 z; @# j2 G8 E strcpy(Tree->Formula, cSym[-(int)Tree->Data]);; l. f/ j [4 f7 Z3 D: q
//Tree->Formula[1] = 0;6 ]' R: ~7 G9 Z7 r {2 S+ X
}+ x" J* G; G' V( |
}
& `! i, v0 X* d7 V! a//从一个波兰表达式建立一个二叉树链表，需指定一个头节点
k1 v: K( w' y8 B( |void CreatBinTree(BinTree *Tree,int *nArray)/ t. I) S! C( I$ n; l
{
7 l2 G- R* B# R! `$ \ Tree->Data = nArray[nArray[0]--];" P6 O: N C( N' m% C& t. @+ i D) t
if(Tree->Data < 0)
" ~# O8 L$ t( ~" F! s {
# X/ ~( M' W" N e. m/ Q Tree->Rchild = (BinTree*)malloc(sizeof(BinTree));. f' @; C6 u( j% Z9 ] T" }
CreatBinTree(Tree->Rchild,nArray);) Y. d) g# ]3 y9 u
Tree->Lchild = (BinTree*)malloc(sizeof(BinTree));; Z' @& X" Y" c8 H. b
CreatBinTree(Tree->Lchild,nArray);
) i! v% D( z3 u$ W! r8 l) x }
" \0 d; ]+ n8 i' k9 s else
1 U& Q5 K" Q+ A% f {
, K/ O, ^! q% l& h2 n5 u5 t8 y Tree->Lchild = 0;
' E! M1 P0 q4 K" Y* q Tree->Rchild = 0;
$ U9 A- I0 b8 S0 K& j- x! _ }# H6 |! q( G+ M+ I! G
- L# V7 c) Q: G" ^* A. c: l}
1 w: w0 Z5 R, q' {) P* ?& R/ s
# E( h4 h2 Z, r/ Z// 释放二叉树空间8 D; B8 o- B! S' u
void FreeBinTree(BinTree *Tree)
# U' M# H/ ?$ O! Q2 g: [; i/ Z{- M/ Y! j4 ^/ ?2 s
free(Tree);) S) _9 t% a: j& t" e0 _% I/ p
}
) _( ~; g Y7 P1 V$ \// 后序遍历二叉树5 z& e& f" I' b& }
// 方便其他函数调用，func为要对各个结点进行操作的函数指针9 L. [7 z# e1 b7 p
void AfterBinTree(BinTree *Tree,void func(BinTree*))
4 w: U2 q& `3 s* t. t) h{
; ^1 f6 N4 z% ~( o" [2 z/ X* n if(Tree)6 n4 |0 ?' d5 f/ Q
{! G! ?) A d. t% i w. c; g
AfterBinTree(Tree->Lchild,func);
5 K, _9 s$ ?: R# {: ^ AfterBinTree(Tree->Rchild,func);
^" Z; @( C4 q @ func(Tree);8 P' M3 f9 `7 F) k: l1 d. w$ h
}& x6 X1 P) v) O0 @; {+ C$ s
}
; r' R8 t; U, u8 J, a6 m |
|
楼主: 考拉
/1 
IP卡
狗仔卡
发表于 2004-5-2 15:40:00
显身卡
发表于 2004-5-2 15:50:00
