|
|
几天前的东西，现在没有大兴趣了
|
过重复代码过多,比如二叉树的建立等等. y6 Q6 b& n$ R' Z
5 u8 J* P5 l3 X
#include
" S, u& O! q* H4 e#include
# P# ?8 L! n! p2 H" ]$ Z+ ]6 M- _4 f: q% A
typedef struct node
! j7 e! C# T$ \2 o# |- H" T! }{5 A% x0 o, A+ F6 ?- v4 Y+ z
float Data;
3 D0 B1 e, K; F% @# ~ char Formula[100];
6 r$ e" e' }' H7 u) i* [ int frist; //优先级
f1 U; f) _# X* K/ V struct node *Lchild;
. g6 \1 K2 w7 ?! h% H1 h- l( G struct node *Rchild;' m1 i. H# Q! e* q- Z
} BinTree;5 d5 P( k4 }: |: |8 q8 |8 m, G2 C
void CreatBinTree(BinTree *Tree,int *nArray);) h. [4 F w* ^5 h% M
void FreeBinTree(BinTree *Tree);
8 i0 \' r( c/ H0 Pvoid AfterBinTree(BinTree *Tree,void func(BinTree*));6 W- I2 o" E! C1 u7 T
float CalcBinTree(BinTree *Tree);) _8 m5 s* }2 j0 z1 t9 e' j$ k
float GetFormulaVal(int *Formula,int count);
# @! i. o8 j' d3 `: ~9 a( t5 nvoid ShowFormula(int *Formula,int count); ]6 @7 |' h! K4 v
void AfterNode(BinTree *Tree);
W4 j g' \" V5 O! nvoid GetFormula(BinTree *Tree);
" j. P$ H! a M- P+ Z6 p& |void Myitoa(BinTree *Tree);; O- u" P8 a7 f
int EnumFormula(int *FormulaNum,int num,int sum);* e& k5 N, j1 z0 h; v6 y' a ?
void Restore(int *Formula,int *NumSym,int *temp,int count);4 ^, s) y0 a( _, _& X
int IsOK(int *Formula,int count);
, E; l- E4 g& D# o" u8 jint FindInt(int *nArray,int n,int len);" C1 @ @# ?1 D4 P
int UpZero(int *nArray,int n); j' C, @( j+ V4 i5 N
int IsDownNumSame(int *temp,int count,int num);& B6 T) t2 |$ E: U9 R3 h# J
n3 i. Q5 u- w1 c% B
const char cSym[5][2] = {"","+","-","*","/"};. }8 Y- Y$ J/ V
( ] `/ Z! \- E/ J2 c4 h2 G
int main(int argc, char *argv[])
5 |7 ~* Z( @: y3 {, t- c' g* v! p{3 E+ {: z2 `0 s% D
int i,n,*Array;. [% b) W/ {) Y- U
5 H* g/ N+ x& `) v
//printf("几个数？");
: d q# t# j7 H4 U //scanf("%d",&n);5 N/ _8 M$ y" B" l4 } t( [
n =4;
" n. q. t4 z7 n4 c: m Array = (int*)calloc(n,sizeof(int));2 S4 R% G3 \6 D$ U/ b3 m4 r8 X8 L& A
printf("请输入%d个数（用回车或者空格分开）：",n); j' [* {8 c( q
for(i=0;i L/ C# n [' ~0 o
scanf("%d",&Array);
8 K: @! E' ~1 X( Z9 j | printf("总计%d个式子\n",EnumFormula(Array,n,24));
0 V$ w/ ^. P; I; Y9 \ free(Array);& o$ R- A$ v: H7 J: x) N
8 ]) S& I( x, _- f+ [
system("PAUSE");
) A0 z W6 U% C6 |* s3 q return 0;
# }6 \" y- @7 U" I}4 ?5 D- \# F: Q. @
* S, o6 f& ?! O5 c) Nint EnumFormula(int *FormulaNum,int num,int sum)
; d( z# V& ~4 F* d4 Y0 o- l: t% e0 h{
( ^0 T: Y8 q! A/ X! o$ |( S, Q int result = 0;# x# Y( |9 e% K1 V. P
int *NumSym = (int*)calloc(num+4,sizeof(int)); //操作数运算符组成的可枚举组, p( s* G0 O# t7 B7 A, o, _7 s
int *Formula = (int*)calloc(num*2-1,sizeof(int)); //波兰表达式储存空间
1 p/ W7 r6 F' q3 y0 M. n int *temp = (int*)calloc(num*2,sizeof(int)); //波兰表达式的代号表示空间
0 U5 z+ a% G2 L5 C D; a int i,j;
9 U" a* s0 ]+ D! a for(i=0;i = FormulaNum; //载入进行穷举的操作数8 m- ^" v- R' t ]: W# f
for(j=0;j<5;j++) NumSym[i+j] = -j-1; //载入进行穷举的运算符号3 N$ q% L( m J7 v0 d8 [5 u ~/ b
" `6 r* `8 l/ V" B S1 R: J
for(i=0;i = 0;
. k5 V& J9 |4 B" c8 m* Z+ w // 穷举开始，结束的标志为波兰表达式代号空间最后一位已进位，即前面各位已穷举完成
4 Z' b) N% X u' X; F1 h while(temp[num*2-1] == 0)& F0 t4 n i4 T
{7 K$ @3 M) p8 m& l! g1 H$ B
if(!IsDownNumSame(temp,num*2-1,num))+ `: h l7 N3 o
{& l2 N J J- c" k
Restore(Formula,NumSym,temp,num*2-1); //还原波兰表达式* J2 Q# V8 c$ w. G9 u+ R+ c6 a# E
if(IsOK(Formula,num*2-1))
4 j' E$ W; R' I {- k- _. k( e7 L: C4 b; K
float t; //结果偏差! w* ~6 N, k) `1 \8 b
t= GetFormulaVal(Formula,num*2-1) -sum;7 f/ O3 N- k' o' R1 J8 l
if(t>-0.01 && t <0.01) //结果为浮点数，只能进行近似比较8 ~* ?! T+ Z: I" m
{( `; ?# A1 R% z0 G6 K
result++;
, `7 j, Q6 g) V S3 V2 v+ A# H m ShowFormula(Formula,num*2-1);# A5 W& r3 w* x- D) B
}
- [2 A) G5 p2 g U( U8 T }. a# m/ T4 Z$ X
}& ~6 C" f- {6 Y& {8 @* Z y
temp[0]++; //穷举动力
" M' g6 `( Z7 z3 P! ?- n7 R for(i=0;temp > num+3 && i//代码空间类进位
4 e5 c# r( W* D6 D/ K2 }- Q. @9 L& o {8 i9 R/ Y9 `4 W) b4 j% e" U
temp =0;/ j. Y, Z/ P) P( g+ ^
temp[i+1]++;' a7 D" _6 q+ ^& I( s+ l8 I
}; w8 U2 s& z9 @) T# d
}& ]+ K' _/ Q- m/ T
// 释放内存+ a& {5 N% F: n: T9 G
free(temp);
1 f3 q4 A; x4 d( w
* S8 {: U: g8 ~- [ //free(Formula); //？？此处不知为什么会出现错误
% `, Z- ^% T( w% h3 A4 e0 q( k. R free(NumSym);
' b; n9 ]9 l) {# \/ v2 y0 Z return result;
t+ e! ?7 p+ [5 M2 E. m}
. r- X# z& ]+ k# D// 由代码表还原为波兰表达式
8 y* x! z; |# L3 }7 C5 g* d3 N+ S# Pvoid Restore(int *Formula,int *NumSym,int *temp,int count)( s3 l: _5 B1 T
{3 {7 p4 R# D& N% k8 V. A
int i;
7 H- ?+ L: R8 n: |9 `, ~! J/ u& e for(i=0;i = NumSym[temp];
' ] _2 v% U r; L0 y; f. Q* A}
+ z# q( ?' e4 v) O// 判断是否符合波兰表达式
) F: G! Y$ d$ i F3 Z B! s% o// 符合的条件是每个运算符号前必须是操作数个数多了运算符个数
- M- V$ t% M3 s" x// 且运算符个数为总数减一的一半3 Y1 l. L% k/ x* n) Q3 |
int IsOK(int *Formula,int count)
3 P# b* g: i2 e3 x0 F{ J* {/ i. W+ F! @1 @, m, S" @
int i,j;
; I# N( `6 [; N6 Y) m- L6 b for(i=0,j=1;i1 Q7 m( d' R3 F: \
if(Formula<0)) k+ E% S* g3 f1 G! e( A
if(UpZero(Formula,i)>j) j++;
g, N4 \- e7 W* I$ H else break;
8 L+ P+ E$ E# N+ u. T, S- U if(iint)count/2+1) return 0;, T; C6 W9 P2 T1 m9 g; D
else return 1;
/ j/ _4 l0 c) N8 C" @# l3 d& C+ _}
0 k( D" V7 D+ g3 i% ~' s// 查找数组大于0的个数& ~! x: A, D0 g* S7 u# B
int UpZero(int *nArray,int n)/ Q% `3 x/ Y2 h. _4 c- C2 A
{& Y! i( ^+ Z7 Y5 f! \8 W
int i,result=0;* L+ T# E1 i: N/ x
for(i=0;iif(nArray>=0) result++;$ s3 y n6 _2 H' T
return result;
8 n, k3 h1 b2 ~, Q; P: L4 \+ E6 Y}: O) c/ ]' V; `! k% P
// 查找数组中，小于Num的数是否有重复
8 R1 i, g5 {! I3 U0 ~/ W+ Z" Aint IsDownNumSame(int *temp,int count,int num)1 f0 S: h* M7 B! N3 I
{6 ~8 ~% i; D+ D+ A2 ^+ P' Y( m
int i;
6 `0 l; E& d0 D. [" f0 u for(i=0;i, n% U4 }3 w/ z, b# \9 Z: i
{4 p( p" ]3 ^+ q) r0 v' G9 o! w
if(temp < num)
; c% \4 r$ E6 t* C& z a if(FindInt(temp,temp,i) != 0) return 1;
. c7 }) u: }" A: d" B7 m }
7 N3 J" x6 \1 s5 ~# P) S+ V! f return 0;2 L& p3 j8 S0 D. V" b' [: V
}( m$ R5 b" W) |: Z
// 查找数所在数组的位置，返回0为未找到
* | }! X& O z+ L- Eint FindInt(int *nArray,int n,int len)0 C' N7 n0 \$ ^3 R ]. n8 }
{
7 f1 \" H0 l' U# J! M: b' Z int i;
5 w" G9 C/ I3 b; `# Y for(i=0;nArray != n && i4 f8 \) f2 f- l' V$ i1 f r. s. \
if(i>=len) i=0;8 n! ]9 M( x, M
else i++;3 G# f c( G+ ~/ Y N
return i;/ z" p9 Z# K3 v; h) }
}9 `0 F% N, X( n3 C# H r: @" o
* C( S9 E C: a8 C; W. C/ g
// 计算算式结果# p8 P" t& g8 w) M6 W% u
float GetFormulaVal(int *Formula,int count)
6 U9 X. f: e6 B& o' E. [# l{ e D7 N& X% e# b
float result;0 z/ P) o$ E% p6 P% S
BinTree *head = (BinTree*)malloc(sizeof(BinTree)); //二叉树头节点2 f6 Q) z- G7 v. r$ g! V3 p9 b
int *nArray = (int*)calloc(count+1,sizeof(int)); //波兰表达式储存数组，首位表示数组有效长度5 S% L" e+ j0 M, E
7 C6 P) o3 R) o+ o! N0 v int i;
2 p4 p" `) c$ [7 U0 }$ B5 u: y e for(i=1;i<=count;i++) nArray = Formula[i-1]; //复制波兰表达式
) X( X! K2 i! | K3 f3 V* E nArray[0] = count;0 M* b' C3 Z! e5 {3 H
CreatBinTree(head,nArray); //建立二叉树
/ ?' Q7 _. E( T+ }% m" o3 b9 z/ R. V6 }2 j9 ?% m l
result = CalcBinTree(head); //计算二叉树算式
8 W- F! F5 \) v; a AfterBinTree(head,&FreeBinTree); //释放二叉树空间% b2 O1 H! w( [+ F
/ w1 d; {, v5 L0 t; @' t
free(nArray);3 C% c" t @. b( _
return result;
& {! k y1 x$ _# y7 R* @} l/ M) \2 \+ ?4 T
float CalcBinTree(BinTree *Tree)
/ a# K- O# p' k- Y! H r# }{
4 X+ U6 B1 u4 o8 \9 I* G
4 ?7 N) i9 ^' G' F; F AfterBinTree(Tree,&AfterNode);
8 Q! v* ~. i& ]0 p return Tree->Data;* o5 C9 O: h" V
}) |* S& ^0 b' d5 j
' r. a- a7 I0 l) {4 k$ U// 后序遍历二叉树进行计算,但会破坏二叉树本身" l" Y: G4 c; q% V5 d4 ~
// 一个结点的结果为左子树 （运算符） 右子树
- `+ |5 @3 O2 q& mvoid AfterNode(BinTree *Tree)
( n' D" z$ q2 j L{/ | b, E( l! s( y0 ]4 A
switch((int)Tree->Data)
0 ?* r+ v: q& u% e0 ?5 w$ p {
, s: u' q- @3 K case -1:
- h4 F# B5 r8 \; J; J Tree->Data = Tree->Lchild->Data + Tree->Rchild->Data;
L' d3 S7 n# `* f break;4 d& i+ B0 S+ @' R5 ^
case -2:
7 Y$ I( H2 t' {% n9 e Tree->Data = Tree->Lchild->Data - Tree->Rchild->Data;. |! S. o' |; G |! E7 J9 b
break;
) C4 v. H# s) |9 ?$ o case -3:, [' }% v0 m) r& o
Tree->Data = Tree->Lchild->Data * Tree->Rchild->Data;
+ i8 J9 n. p M7 ? break;3 W$ o, U0 Z: [3 g8 Z. J
case -4:
. ~( ]* Y9 w# r6 x* Q Tree->Data = Tree->Lchild->Data / Tree->Rchild->Data;+ q# M. E$ I% t1 U4 G9 N* Y
break;8 i. I, D3 b, i& f. |
} p8 C; m3 R9 E' K3 q
}6 ^) D5 |( [1 l" k
// 打印算式
8 i: D6 [. \( g0 C+ Y0 G5 J' p( \ [2 {6 l
void ShowFormula(int *Formula,int count)
; J: Z5 T1 ], J: s, w{
$ U) j I- l" w, b/ ? BinTree *head = (BinTree*)malloc(sizeof(BinTree)); //二叉树头节点
2 D6 l- m. U/ {- T% C int *nArray = (int*)calloc(count+1,sizeof(int)); //波兰表达式储存数组，首位表示数组有效长度
! ~0 I+ o/ e% R# M+ @, i8 u' G3 x& f! I int i;8 b E& y! H' k8 S- W
for(i=1;i<=count;i++) nArray = Formula[i-1]; //复制波兰表达式
! l, @) o8 D$ i2 h- i5 h6 [; }6 A* @ nArray[0] = count;- o, d4 l, L; O! @2 ~/ C
CreatBinTree(head,nArray);
/ T P8 I. V- F* d) z2 ` AfterBinTree(head,&Myitoa); //初始化二叉树字符窜部分: u! h0 }# V& |" L+ r
AfterBinTree(head,&GetFormula); //转化为普通表达式
3 e" _3 S! i; S% N( t# N; ` printf("%s\n",head->Formula);
5 {. V* z" u3 {2 m" Z. Q AfterBinTree(head,&FreeBinTree); //释放二叉树空间( U# ~: a/ z5 \4 s% B8 @
free(nArray);
# p; i" V. R g- s ' i0 R; T( v8 u: `" H4 e
}
6 v" v# C( t5 w2 x7 N+ L// 类似计算二叉树
4 v( S& {, R1 n2 t6 G// 会破坏二叉树本身1 c* N' H* P( i
void GetFormula(BinTree *Tree)
8 p' i( p; t: `4 d# n. |9 h{' q5 D. a7 ?3 r: g
// printf(Tree->Formula);
- F) Z5 m5 c+ o if(Tree->Data <0). s, V' ^7 I1 h6 W; F7 S) p4 ^
{
: y! L, \5 N' h: z# g1 L char temp[100];" ^5 I5 Z4 e3 \/ [3 m% \% C0 O1 l7 `
if(Tree->Lchild->frist < Tree->frist)/ ]6 @! {) p* x; t
{# C) q) G( @7 K
strcpy(temp,Tree->Lchild->Formula);
: W+ {4 G; ~4 p3 M, r/ _3 L; S2 y strcpy(Tree->Lchild->Formula,"(");
1 G7 h! F2 ~8 `, _, `: T strcat(Tree->Lchild->Formula,temp);( g' t" I* v0 e) m. {! u$ r% ?. }
strcat(Tree->Lchild->Formula,")");
& n) @5 q4 C; a8 _: q) n: V }. N& L* F- E# E* d% I
if(Tree->Rchild->frist < Tree->frist
# R5 h& z: v2 @6 P$ C/ \$ C. X: o || (int)Tree->Data == -2 && Tree->Rchild->frist == 0
5 y2 p' U' ?8 O; |1 q || (int)Tree->Data == -4 && Tree->Rchild->frist != 2)
+ q5 _" R# q" ]2 l) m. f {
1 F$ L- k8 c1 Z9 m( C strcpy(temp,Tree->Rchild->Formula);
0 B( X) k8 \7 B8 Y' [9 Z) X strcpy(Tree->Rchild->Formula,"(");
$ q; U8 h: D% W( n strcat(Tree->Rchild->Formula,temp);
E. S& A2 k% O# ^3 [: p strcat(Tree->Rchild->Formula,")");
9 V+ U0 z5 K v: ^+ `) J- C6 n }( U+ d& Q4 |" @* g& J
strcpy(temp,Tree->Formula);
- i/ w( D3 i# D( Q strcpy(Tree->Formula,Tree->Lchild->Formula);4 ^4 Z0 {$ n; Y2 p
strcat(Tree->Formula,cSym[-(int)Tree->Data]);
' i E1 s; n2 |) ^0 \3 } strcat(Tree->Formula,Tree->Rchild->Formula);$ D# F1 F) E( p0 E7 l- v
}* ?" f% I* m# P% Q4 J/ d
}) O0 o- L0 H8 t% C- J% q3 o. s
// 对二叉树字符串部分赋值
+ u1 x! z: j. U0 i( hvoid Myitoa(BinTree *Tree)
5 A1 D& q7 @$ J7 Z' v4 s! ^) Y{) A0 K& @0 g2 m) ~3 t4 O9 W+ o/ a
if(Tree->Data>=0)
0 R5 w: T7 w& r {# L& s# P0 H! Y" T7 R
itoa((int)Tree->Data,Tree->Formula,10);' r! @3 L/ S3 Q* m; X
Tree->frist = 2;5 q. ~4 F( c! |
}
+ i7 T- x% E% ~ else
1 J! u- v% l6 [. J4 f {
' n9 a* l g# K- _9 h$ p Tree->frist=Tree->Data < -2 ? 1:0;
' q( F7 x( X: z: U+ w0 Q strcpy(Tree->Formula, cSym[-(int)Tree->Data]);
. p! i" ~0 n6 Z4 a2 A# u //Tree->Formula[1] = 0;8 t! j, I3 c! x# e
}
$ J: q( a4 u3 Z# W. R( h+ m* o}0 U u0 ^/ E+ ?/ d0 I
//从一个波兰表达式建立一个二叉树链表，需指定一个头节点/ Q# L- j* F: L. Z; E. A
void CreatBinTree(BinTree *Tree,int *nArray)9 ?. ]" e: \( A. _) [8 P; g) E1 K! m
{
0 [* f- a" M4 _ Tree->Data = nArray[nArray[0]--];" S; f X, f( u7 d! t$ }
if(Tree->Data < 0)8 A. Q* K! K' n5 j6 N7 r1 ~
{
. t' @% P' e& T, ? Tree->Rchild = (BinTree*)malloc(sizeof(BinTree));3 x4 a4 M$ q! t% R- _( \ l
CreatBinTree(Tree->Rchild,nArray);
8 C# i% ~+ W' e' k2 y, ]; ?, y Tree->Lchild = (BinTree*)malloc(sizeof(BinTree));$ i% M$ G: s6 V7 s/ z; @- X$ a
CreatBinTree(Tree->Lchild,nArray);
; V+ }3 V. j: w }
* R" f: c6 j' n" ^, r else
" a8 |- N! O3 j$ `, I' \ {
% p5 ^" ]6 R/ y! E% {5 F$ N; M7 o Tree->Lchild = 0;
' {. |8 \ O- J& X* v Tree->Rchild = 0;
% W) K* F. b5 A* I: z7 j- h }
0 p2 N8 F: ~- p* z @9 d
7 O7 Y( D; ~) P7 Q" r: ?8 ?}) n2 K/ E4 U4 ]) s x( ~5 G. N
8 M: S$ ~* r/ L% R! H6 G- k# w
// 释放二叉树空间
" G1 ^2 n' {) n- c8 Fvoid FreeBinTree(BinTree *Tree)) w; ~0 p9 {/ [( y
{+ Z# C( z- P& o# Z4 {/ ?
free(Tree);
5 H" x3 O @' |0 A) ^. W x}8 _% k& y: P! L5 M: e
// 后序遍历二叉树
/ p. w: p2 U7 S2 n: ~& ]9 M, r% `// 方便其他函数调用，func为要对各个结点进行操作的函数指针
/ g$ {" i% S. L9 q/ kvoid AfterBinTree(BinTree *Tree,void func(BinTree*))
3 f/ r0 d& w' _0 n W, e5 |7 T/ L{/ ^% j) \ `$ G9 r- u9 t5 a
if(Tree)
4 H; T/ M0 x/ } {7 d- l3 c3 f% w- K6 o
AfterBinTree(Tree->Lchild,func);- i' C( i, \2 |/ b% C* g
AfterBinTree(Tree->Rchild,func);
# V& q0 W8 z: d( s# [ func(Tree);" o% T: R5 x( J. O
}
, }+ F# |9 k1 f/ s}
" c7 Z9 m! Q8 X6 l. C @ |
|
楼主: 考拉
/1 
IP卡
狗仔卡
发表于 2004-5-2 15:40:00
显身卡
发表于 2004-5-2 15:50:00
