|
|
几天前的东西，现在没有大兴趣了
|
过重复代码过多,比如二叉树的建立等等/ q, m9 q" y0 u) q7 L R
, }# y6 H y+ A+ w; o" ]' P/ o: }1 M( b
#include 2 i) S2 S) d2 I6 k
#include # {' }3 W7 B- F7 b$ v" {- c2 D. Z
7 P$ T" r7 r' D! V% q) q( u9 S
typedef struct node8 u$ L, Z# d u9 k8 M
{
8 V" U# |3 D; n$ m R9 R9 V float Data;
$ c) ?: V/ f& n5 C char Formula[100];5 W/ X" a! J2 z5 F
int frist; //优先级
- w# Y' u, ~/ Q: ~% w struct node *Lchild;) h/ p9 H% j: }
struct node *Rchild;
! d* Q }) m! b+ k r5 u/ f} BinTree;
4 ~$ T# ]. m* y! rvoid CreatBinTree(BinTree *Tree,int *nArray);4 Y" J" I9 J( L- ^9 f
void FreeBinTree(BinTree *Tree);) A7 |+ a$ V- h1 d( [: Z7 `
void AfterBinTree(BinTree *Tree,void func(BinTree*));3 H* y& x8 ^+ m, _( q; |% \7 G& m
float CalcBinTree(BinTree *Tree);
, o3 J# R9 T; l4 X) L+ y% @float GetFormulaVal(int *Formula,int count);
$ _* o$ i3 s/ p7 J( }8 \void ShowFormula(int *Formula,int count);7 ^# O6 }: _, c2 }3 D# \* G
void AfterNode(BinTree *Tree);
7 ?$ ]$ I6 S R ?& Zvoid GetFormula(BinTree *Tree);
8 j- Y. C! t' Evoid Myitoa(BinTree *Tree);
" ~' U" s( B5 T3 b9 F0 W pint EnumFormula(int *FormulaNum,int num,int sum);
$ l# X& \8 Z8 T6 _+ L7 j* |5 Avoid Restore(int *Formula,int *NumSym,int *temp,int count);
0 h( _+ u8 S2 M8 F# A \: Gint IsOK(int *Formula,int count);" V$ K. k- a# p* Z. Q
int FindInt(int *nArray,int n,int len);
' U! O/ Y" r+ ]- Iint UpZero(int *nArray,int n);& T9 \7 O: P- b
int IsDownNumSame(int *temp,int count,int num);: p! d9 R0 {7 }/ d4 Z
, X2 F; ~. j2 Q( F
const char cSym[5][2] = {"","+","-","*","/"};
8 _4 ^: e$ v* u. _% X2 h/ u- z: \# Q
int main(int argc, char *argv[])" ?8 i. Y% Y) D2 T" D& |$ B0 B
{
/ f2 X H& V1 Y; w6 p3 M int i,n,*Array;% ]; T ~5 a# W1 k* o( J0 x( [- W# ?% D
' f" f9 P: x( r0 A" |! t- h, \
//printf("几个数？");& Y" T7 l0 b5 I0 t) J' a
//scanf("%d",&n);
; \, _$ o2 z |4 u' o5 J3 t( \/ u n =4;
* Y p4 @8 L* n& \/ { Array = (int*)calloc(n,sizeof(int));7 g- D V2 X* u
printf("请输入%d个数（用回车或者空格分开）：",n);
8 f7 Q+ D* y( k+ s6 e9 @4 P z; z for(i=0;i: z+ y! f4 R) F" N
scanf("%d",&Array);
' `, m, A3 f3 E7 G% S printf("总计%d个式子\n",EnumFormula(Array,n,24));
: v/ ]% r+ H; D F free(Array);/ m& ^' w' v" ]' @0 t0 e# ]
: D. N. S/ s$ G
system("PAUSE");
( N, \$ d; y6 D9 l3 A' r0 _ return 0;
3 p% h8 u+ v" d T}6 e$ n' c9 @( i! e
- w0 I( X4 G) J4 v+ rint EnumFormula(int *FormulaNum,int num,int sum)
/ \- I4 c! q8 h" d{
' |5 D! N2 C8 b3 o3 o int result = 0;3 ]1 m& J4 h9 C) G& }6 |
int *NumSym = (int*)calloc(num+4,sizeof(int)); //操作数运算符组成的可枚举组) M$ Z1 W& q% S7 k
int *Formula = (int*)calloc(num*2-1,sizeof(int)); //波兰表达式储存空间; C& w1 i+ s5 d, q( U# u; e, ?
int *temp = (int*)calloc(num*2,sizeof(int)); //波兰表达式的代号表示空间) ], {3 R- `) s& C* K; t
int i,j;
4 g' R$ v% H1 b# u( Z9 ^* B" ~1 h6 I for(i=0;i = FormulaNum; //载入进行穷举的操作数
1 q: M6 g! I5 h. Z for(j=0;j<5;j++) NumSym[i+j] = -j-1; //载入进行穷举的运算符号1 R* l& u6 T8 u9 ~% t
' L5 B4 P. v! I6 q! N for(i=0;i = 0;
4 d4 Z4 q& ` Y$ d: ]" k, o0 D/ t // 穷举开始，结束的标志为波兰表达式代号空间最后一位已进位，即前面各位已穷举完成
2 y! W/ a. b3 Q3 i: l* v while(temp[num*2-1] == 0)
" b1 c6 F, [4 Y4 C {3 R' n4 k1 K0 v8 g1 e
if(!IsDownNumSame(temp,num*2-1,num))
N2 B3 X" D$ s5 N; U1 c+ D {0 B' g* ?1 e1 t/ o2 a7 U
Restore(Formula,NumSym,temp,num*2-1); //还原波兰表达式
( r4 w* e0 H& e4 }! X if(IsOK(Formula,num*2-1))
) Z, f' U8 C* D {
: E0 W# N" k0 v; E float t; //结果偏差
+ T/ S, J0 v; p$ k' Y1 | t= GetFormulaVal(Formula,num*2-1) -sum;) X( ]2 Z- [: P( s
if(t>-0.01 && t <0.01) //结果为浮点数，只能进行近似比较
7 i" H+ _8 Y; ` {
0 G" p, U7 }& ?/ u; H result++;
% i$ N$ D0 I1 g ShowFormula(Formula,num*2-1);
$ u9 Q- P$ u- _( x }/ O& F5 ~2 |* J
}; \4 C# A) V% D" G3 E/ c, m
} ]/ x6 K" H! F7 I
temp[0]++; //穷举动力
, g; S* X7 w7 b/ i+ B for(i=0;temp > num+3 && i//代码空间类进位. t/ F, F$ S8 |$ Y5 r2 i% f0 `
{# a( L! o, N. t) P% u
temp =0;" |8 O/ E; ^" G! k* [
temp[i+1]++;
/ y$ ^& s7 g9 q# }, x* q' Y8 n9 Y }% q) x6 i7 A) c
}0 ?0 R2 q( i9 B) D" \
// 释放内存# p$ T/ q; \) d* Z) F+ D
free(temp);: s) O. S0 o8 q, F5 s! ]
9 X |5 U) I+ z; k6 Y) k
//free(Formula); //？？此处不知为什么会出现错误4 q+ p5 ~! J& @; q
free(NumSym);" f; R6 X: N! ?: A( Z
return result;
( j" g4 e: B8 W}: [0 z8 Z2 z: f4 q
// 由代码表还原为波兰表达式
) Q8 f$ e9 L) P5 ^, r% Bvoid Restore(int *Formula,int *NumSym,int *temp,int count)
. h9 m4 ]( t7 `1 ?: x( G{
: v0 H$ {. ]$ R; o3 K int i;
3 [# k9 Z; G" l4 z" ?( a for(i=0;i = NumSym[temp];: D& P% K4 J0 X- _
}
. s" J. y9 l$ N9 ?+ g// 判断是否符合波兰表达式4 K+ E# ^7 C+ p- }7 h( L
// 符合的条件是每个运算符号前必须是操作数个数多了运算符个数2 A6 ^' j% [9 ? X1 p
// 且运算符个数为总数减一的一半, h5 a. a$ K3 v! u
int IsOK(int *Formula,int count) S+ Z0 s! r6 P' M7 n& f% Z
{
( @$ k6 ?: L6 E& h( O' k" t int i,j;6 K; U; N. y/ j, U, r! s2 ? ?5 w
for(i=0,j=1;i6 N; ?0 T' H' ?3 k7 |. H- K
if(Formula<0); u8 f; j# n# r5 y' l
if(UpZero(Formula,i)>j) j++;6 J8 |0 j- B! I* b; k1 ]
else break;
3 Z% O; A% H' {' b" k if(iint)count/2+1) return 0;& I+ L u+ w F4 D% S
else return 1;/ b" w+ P+ I; G2 V
}1 l7 j; `, o$ H0 D' F+ e) c1 x) z
// 查找数组大于0的个数
7 T8 [$ F! ]1 _& U: k" Eint UpZero(int *nArray,int n)
" A. c7 @0 ~! K& K2 Z: w{
4 S) j& K! e0 L- L [' I int i,result=0;
! l/ ~/ U" m( L" b* j: r for(i=0;iif(nArray>=0) result++;
8 H# i& o( B5 ]7 {2 W0 R9 y# y+ d# M return result;# j, C/ {" m/ f" B& J
}# N" ^; M# q, _2 T. t
// 查找数组中，小于Num的数是否有重复6 Y& Q z8 |( R. b8 @. n+ l0 W
int IsDownNumSame(int *temp,int count,int num)
' g' s! Q, i( @1 C2 l2 s{+ u/ f2 h% ~7 }9 A! X
int i;% S5 Q+ e! J* A/ B' f+ A5 i
for(i=0;i, r8 Z+ M) L6 A$ `* l+ l {
0 S4 w. V9 M0 G/ H6 Z5 i. E+ U if(temp < num)' J; L( j; t5 |3 a3 Z) [
if(FindInt(temp,temp,i) != 0) return 1;
: ]$ M0 m3 J" U' T2 k7 U }
: }$ `+ |* ?; W! x( a9 Z- P4 z return 0;7 K" K! N( O. T3 R# ^. O! r( [; e
}# P) Z7 o' c/ s$ j: p
// 查找数所在数组的位置，返回0为未找到. j9 h" U& r* L4 j7 L) h
int FindInt(int *nArray,int n,int len); X' w4 n; u( g1 y- G& P5 `
{
; E# c/ j7 ], o0 X int i;
( Q: @, G5 `0 M2 {- y; |) D1 } for(i=0;nArray != n && i, y* F8 J( o1 [* U- _- | if(i>=len) i=0;5 h! O" C+ q7 {- y) m \/ V1 [& B4 S
else i++;! Z$ ]2 e' h `2 H6 C
return i;- r: L! g5 l9 m/ h& D% |
}% z6 l9 c& i% Q8 j/ f% O
% {; C/ Q7 Z' K0 y# b0 Y# a; u
// 计算算式结果% A- u! p: W/ H0 n; L+ {. r& I
float GetFormulaVal(int *Formula,int count)
) G+ b% K0 g7 A% e; Y{
; e1 H" f8 W2 w* A; L e float result;
/ O* H+ M' b8 E% [: Y BinTree *head = (BinTree*)malloc(sizeof(BinTree)); //二叉树头节点
1 t( n2 s. w% l; E4 z+ _4 s int *nArray = (int*)calloc(count+1,sizeof(int)); //波兰表达式储存数组，首位表示数组有效长度
9 w6 W2 K+ j9 O. _- A/ b+ p- ]) ~- ` K# Z
int i;$ K; W+ u+ }* M8 n! I7 ~
for(i=1;i<=count;i++) nArray = Formula[i-1]; //复制波兰表达式- |4 G ~$ y& F
nArray[0] = count;
: b1 u% R" S) {- p7 L CreatBinTree(head,nArray); //建立二叉树
5 P2 h% P* G) W; M, [7 q. t0 t* w9 |4 X
result = CalcBinTree(head); //计算二叉树算式! ^* Y3 F1 f8 g) p- V1 y
AfterBinTree(head,&FreeBinTree); //释放二叉树空间
+ Y5 c" _* l5 U5 v$ I/ p
; H/ _& J. m: L+ m, s free(nArray);" l6 R7 `+ o9 l8 V6 b
return result;8 C$ M: p A* n F+ |$ A1 n. D
}0 q, j8 y' S2 `" r/ J, K, |
float CalcBinTree(BinTree *Tree)
2 j. i9 O. g& H! I{
2 x1 B F$ B* t @5 D" Z* I7 U2 k6 L ' E8 N+ f5 s: h/ E) W& h
AfterBinTree(Tree,&AfterNode);
" w3 H0 a1 w$ w& S return Tree->Data;
) m- w3 \6 T, h( D}+ t7 _0 G3 \ B! [) A
% o" W" a- ^8 M+ i/ H& N P5 p
// 后序遍历二叉树进行计算,但会破坏二叉树本身
4 K) l1 j# u3 A* b1 G$ b6 c// 一个结点的结果为左子树 （运算符） 右子树4 g/ I! o! y& y) D1 p
void AfterNode(BinTree *Tree)" r+ M' l( c; C. j- \
{
% h: k+ C) N: m$ o8 A switch((int)Tree->Data)5 k7 @- j- u- A& ?1 O
{
% A$ a* p T: O0 c9 R6 Q5 h# {4 Q case -1:
$ ]) B2 v; x4 r Tree->Data = Tree->Lchild->Data + Tree->Rchild->Data;
0 V' G! j% D: e* x5 y break;
# R' [9 M9 K2 A' ^4 R case -2:9 D9 I: U* |& s% d8 T' e1 v! a" t! |
Tree->Data = Tree->Lchild->Data - Tree->Rchild->Data;
# E7 p( z/ v! R. [2 j break;
3 g* ]) l) I$ l" | case -3:6 x# @8 J+ p B' {7 y$ X
Tree->Data = Tree->Lchild->Data * Tree->Rchild->Data;5 J1 A4 ]! F' y C
break;
L7 S; U( `5 R1 c1 f4 x case -4:" Z o2 V! {" |: e
Tree->Data = Tree->Lchild->Data / Tree->Rchild->Data;
% I# x4 h/ Z0 m% p break;, Q( Y9 z) b# g# H" o( @2 ]
}
4 r; T, A; R9 l3 M4 ]2 F# p}
8 }5 S9 L6 ~) o// 打印算式, {$ i W$ Z: J, N, l5 I
a' C0 D; h5 q& rvoid ShowFormula(int *Formula,int count)3 @ I1 _7 r! ^1 D* }: V
{) I# S0 r. V4 H" Q7 ~
BinTree *head = (BinTree*)malloc(sizeof(BinTree)); //二叉树头节点$ D2 N3 |+ V; W7 _
int *nArray = (int*)calloc(count+1,sizeof(int)); //波兰表达式储存数组，首位表示数组有效长度
) r+ ?1 Y7 N4 k* C7 n" v int i;: l( W( v' O( }; n( d2 c+ H
for(i=1;i<=count;i++) nArray = Formula[i-1]; //复制波兰表达式
& k& j% E' Y) \. ?8 l1 S1 ` nArray[0] = count;# g! C! t7 T# p7 h$ R
CreatBinTree(head,nArray); : { d( U8 h& ?- n
AfterBinTree(head,&Myitoa); //初始化二叉树字符窜部分
, l H/ q* C& a2 U$ j/ F; t AfterBinTree(head,&GetFormula); //转化为普通表达式
, V1 r8 _+ h' r8 t( w printf("%s\n",head->Formula);8 G) m, o7 q( j3 ^
AfterBinTree(head,&FreeBinTree); //释放二叉树空间
; Y% ^2 Z* a2 r5 d: {* f4 Z! y free(nArray);" M0 @; }8 |$ z6 F; ~
9 s5 e2 ?2 b9 j% D
}5 G$ @; f! R8 c* M2 |/ d6 z
// 类似计算二叉树
5 b, G6 D6 B. n5 n// 会破坏二叉树本身
8 g6 _$ d4 q1 W5 B( K0 b# Ovoid GetFormula(BinTree *Tree)
4 x- P8 w# R9 i3 ^5 ~{
5 J6 n" F% u, X4 T& I // printf(Tree->Formula);
( K) p- i6 G. q7 f: d/ E- W7 B if(Tree->Data <0)
+ u5 d9 \ p; [7 K {
4 [/ u/ X3 V5 V0 ~& t char temp[100];
1 `+ H( O8 p2 d; g0 O0 `& B- ] if(Tree->Lchild->frist < Tree->frist)
% b9 ^ `3 a' ~! g5 V9 \% N8 q {
6 g$ O% ^5 E' | strcpy(temp,Tree->Lchild->Formula);
3 V0 n* ]. ^/ m B( B strcpy(Tree->Lchild->Formula,"(");4 @7 V+ i5 B* ?; p3 h* `, N
strcat(Tree->Lchild->Formula,temp);
; `7 n$ Z2 V5 U- g9 @ strcat(Tree->Lchild->Formula,")");
9 W% [ e$ m) D }! V8 @, \9 M5 C- [/ {. }
if(Tree->Rchild->frist < Tree->frist; S8 V/ o, @; e2 c! K3 j
|| (int)Tree->Data == -2 && Tree->Rchild->frist == 0+ ?: C8 V3 m/ S" p7 [
|| (int)Tree->Data == -4 && Tree->Rchild->frist != 2)
# Y `$ v9 Y* S6 m {4 ~! j% f4 X1 S! J0 \. Q+ P# {
strcpy(temp,Tree->Rchild->Formula);
; s9 {% V$ D- M9 K/ Q' ` strcpy(Tree->Rchild->Formula,"(");
; ?& p$ N& L1 n! u strcat(Tree->Rchild->Formula,temp);+ ^0 _/ E6 z9 v' ]3 ~6 w) D
strcat(Tree->Rchild->Formula,")");
$ G5 R0 M. n1 T( m7 i" J }' _! g* D: \7 J" b& S; h
strcpy(temp,Tree->Formula);
/ D' Z# a+ P- |" P strcpy(Tree->Formula,Tree->Lchild->Formula);
$ R! W( k, z+ k9 |1 a strcat(Tree->Formula,cSym[-(int)Tree->Data]);2 ^( G; D* L. U! s" O
strcat(Tree->Formula,Tree->Rchild->Formula);! U. N, Z+ _8 ?% z. D6 ~6 g+ w9 Z
}
3 |8 u9 @# e W}
; G; ^. i# ]! P7 w// 对二叉树字符串部分赋值 w$ Q5 g6 m/ K+ W# o/ z+ ]
void Myitoa(BinTree *Tree)8 ~# ~, `, Y% \: `( j
{; R3 `' [( G2 R J8 e6 J
if(Tree->Data>=0)5 ?1 n( ?0 D' r6 a
{3 Y% z( Z2 d7 _+ y& |0 _% s
itoa((int)Tree->Data,Tree->Formula,10);9 `# ^5 b0 X8 C5 z! o$ n# u
Tree->frist = 2;" L8 `+ E- x, u# `9 b. E
}% y' f, o7 W, t0 R/ X
else
2 e' Z2 p( N: ?9 f! f3 I2 V2 K {6 s( ~% {: `; o0 P/ l
Tree->frist=Tree->Data < -2 ? 1:0;
3 m- i& N% R: v1 M3 V strcpy(Tree->Formula, cSym[-(int)Tree->Data]);
# X( {% ^& \( b //Tree->Formula[1] = 0;7 S( u. V* d( r- }, }' X
}
- y* P" ~* t" A. z% ]0 B+ ~8 j}6 X ]7 n$ ]( E+ ?2 N: e+ @- k
//从一个波兰表达式建立一个二叉树链表，需指定一个头节点
1 F" P/ r/ J& W% A+ v, p$ ?0 ~4 Qvoid CreatBinTree(BinTree *Tree,int *nArray)! D* ?3 W! \" P: s' @; x) X- R
{
! m# j0 c9 T0 W. P6 M) U Tree->Data = nArray[nArray[0]--];
: U- o5 b, v$ ?$ O# P if(Tree->Data < 0): {1 b" @4 h1 d* Q6 _# D8 W
{
4 B9 |6 l- Q# Q& K Tree->Rchild = (BinTree*)malloc(sizeof(BinTree));0 w' K0 p3 j) o& H; N" p
CreatBinTree(Tree->Rchild,nArray);
" X, H$ D; h5 B! R5 E2 l Tree->Lchild = (BinTree*)malloc(sizeof(BinTree));
0 N/ ~) `' [4 b- [ CreatBinTree(Tree->Lchild,nArray);
$ ~# w/ N4 q* Y) M4 `1 r }
* _) V* ?; K# d else
, Y8 T4 ]1 x) i% y) S {( N- s) w0 o' n1 H2 m0 y& B* O
Tree->Lchild = 0;& \8 U+ ]* r+ v1 w
Tree->Rchild = 0;
1 L- C0 ^4 S7 o: ]' F- H }
5 G& v+ w* f2 F: P2 B7 r8 }" G; R+ K. Q, i/ o1 n8 y2 Q( ]1 D
}
4 ]0 w6 P% E& Z1 G* }, x5 m& L% y! w" C- Y8 R7 i( H
// 释放二叉树空间2 G& O9 Q, t" X: N& t( Q) @) Y
void FreeBinTree(BinTree *Tree); i3 }3 t, `% J. G' F
{6 {5 H- e7 O. D* k( n: E% P
free(Tree); ?# M2 E4 `# w5 w
}
' l. s- o4 [% L: H! z% y4 c: u// 后序遍历二叉树
1 Y* \% _. ?+ Z/ S// 方便其他函数调用，func为要对各个结点进行操作的函数指针
4 u9 w' O" M* @9 P. c/ i* X5 uvoid AfterBinTree(BinTree *Tree,void func(BinTree*))
' }* S8 Y# w$ a5 a& F{
" g* G: g- S! c# D2 \# } if(Tree)% \9 W! e- P: M
{
, V, L8 v; W1 G% Q AfterBinTree(Tree->Lchild,func);, G7 a( K) E- c4 `: r
AfterBinTree(Tree->Rchild,func);+ g) s4 y* Z4 Q: J( ]. l
func(Tree);' O- {% Z* c. V! N
}, V, @# Y. a( z1 f# e
}6 b* g/ m( `. O) ]
|
|
楼主: 考拉
/1 
IP卡
狗仔卡
发表于 2004-5-2 15:40:00
显身卡
发表于 2004-5-2 15:50:00
