|
|
几天前的东西，现在没有大兴趣了
|
过重复代码过多,比如二叉树的建立等等2 X1 Z8 X1 u* u+ W4 P2 i# Y
. g5 d3 X# M- l
#include 7 v2 I2 s) r3 a0 T7 y. Q f F3 r
#include
: w: A: V% ? t, Z
A) d) t; C, w4 Btypedef struct node- ]- r' E# K K& `7 S
{. [4 c3 d" `# M+ d- L6 z
float Data;% p. c/ R! c% p4 O
char Formula[100];
M! T& J" D- w2 E int frist; //优先级6 @# C4 z# |; V0 q# H4 {0 C) o
struct node *Lchild;/ _( r5 S1 G) |" m
struct node *Rchild;3 q/ j' A# Q8 D# ~: s
} BinTree;4 T: m9 g. H& M3 P0 g; {
void CreatBinTree(BinTree *Tree,int *nArray);6 U: B- |/ O6 o C c9 a
void FreeBinTree(BinTree *Tree);
5 ?0 g; q8 @. U! L5 O2 D# S- u: ~void AfterBinTree(BinTree *Tree,void func(BinTree*));, ?" F8 e: ^ n& |/ ~- n; E6 Z
float CalcBinTree(BinTree *Tree);, `- j9 p3 s2 _0 |
float GetFormulaVal(int *Formula,int count);
. D. F# P6 l5 `; @ p2 ovoid ShowFormula(int *Formula,int count);
5 X) ~/ R( q- u7 h9 Qvoid AfterNode(BinTree *Tree);
/ ~' ~1 }4 _- |2 g3 S2 N8 Bvoid GetFormula(BinTree *Tree);
* C# u9 J; a' f, ?' ovoid Myitoa(BinTree *Tree);! {. P/ h, e1 z, I+ C$ r
int EnumFormula(int *FormulaNum,int num,int sum);
/ d/ N' l# m+ ?2 K' u1 R0 @void Restore(int *Formula,int *NumSym,int *temp,int count);- {) e8 Y6 Q9 t m
int IsOK(int *Formula,int count);% U. e' o; M; \" Z
int FindInt(int *nArray,int n,int len);0 _: W7 _5 W( m7 W+ B
int UpZero(int *nArray,int n);9 u" [2 Y. y j4 C9 Z" ~" I
int IsDownNumSame(int *temp,int count,int num);9 K$ t7 v: m3 k2 b4 m. ]6 A$ M
: D) x; P* R2 A; J4 ?; \
const char cSym[5][2] = {"","+","-","*","/"};. M) i, s7 {* a& o: I, ^, q" B
# K" ~) W6 h- x* s7 R
int main(int argc, char *argv[])
* Z! W( q8 ^ p Q+ @+ _$ B/ {{
3 N( k$ t* e3 z7 u: s+ R int i,n,*Array;- G+ @: w" d1 z4 I+ C- ^8 v
3 T( g/ @7 s# s& ]& z0 ]# x a
//printf("几个数？");+ ~- \3 K. t3 c
//scanf("%d",&n); r3 Q$ @3 F! s* a
n =4;
9 o. I; s- y; {0 Z* {4 o* l0 y Array = (int*)calloc(n,sizeof(int));+ J$ e/ G' _# S# J4 E
printf("请输入%d个数（用回车或者空格分开）：",n);
8 X2 W: ?* _* E6 B1 a6 d for(i=0;i+ X1 h3 [; c4 r: j* p% M$ D scanf("%d",&Array);
) p2 ^3 T2 V. y# M printf("总计%d个式子\n",EnumFormula(Array,n,24));0 I! M# i9 I$ S& K6 w |
free(Array);" J6 b: E" S9 z0 t
0 e2 l1 Y8 b5 Q( @" g+ L8 M
system("PAUSE");
5 i) D. z; q; q7 [* _1 O& E return 0;
0 x* V4 M! q9 a5 U9 Q}
: ^$ y- U$ o+ T1 i8 s$ d# V/ x" x6 R X4 u; I3 \! @2 U
int EnumFormula(int *FormulaNum,int num,int sum)
* Q# A( I$ f; u2 {; l+ _ L k{, R' U5 w8 G9 k: @' c- X
int result = 0;' Q- v+ _2 U; F0 \/ v3 q% U1 z+ {
int *NumSym = (int*)calloc(num+4,sizeof(int)); //操作数运算符组成的可枚举组% H% @- k( J! x; L9 b7 O6 r
int *Formula = (int*)calloc(num*2-1,sizeof(int)); //波兰表达式储存空间
5 d" L2 q* j# E# | int *temp = (int*)calloc(num*2,sizeof(int)); //波兰表达式的代号表示空间+ \: h) z6 A' }2 l8 w( f5 i, e
int i,j;/ P: V* c4 E Q7 I0 F: K. _
for(i=0;i = FormulaNum; //载入进行穷举的操作数, O2 o$ j- b; V# _7 Q" P
for(j=0;j<5;j++) NumSym[i+j] = -j-1; //载入进行穷举的运算符号$ n5 F( Z0 h( u/ s8 D/ K
8 n* ~# E/ i! i1 W
for(i=0;i = 0;
1 G8 G+ o3 w$ R" ^; R$ F // 穷举开始，结束的标志为波兰表达式代号空间最后一位已进位，即前面各位已穷举完成3 k' C( T$ \3 G7 j/ [
while(temp[num*2-1] == 0)3 o# c) z- O6 W1 Y. `
{) \8 _& {( K6 N; `% S
if(!IsDownNumSame(temp,num*2-1,num))% {0 e9 J' l# j) j
{
! i/ p# A0 ?) {" S: ]8 l6 d# |3 \ Restore(Formula,NumSym,temp,num*2-1); //还原波兰表达式" h# U0 L& t' H) a; K) ^
if(IsOK(Formula,num*2-1))
% F' G$ u: o+ k0 e$ g- y+ j% d {0 F% s6 G+ X/ D# p; c! H
float t; //结果偏差
u# y# w, w! H3 C+ n# R t= GetFormulaVal(Formula,num*2-1) -sum;
$ K! a3 y2 y5 U if(t>-0.01 && t <0.01) //结果为浮点数，只能进行近似比较% h, v6 L% a% q' w
{
+ c% S, f6 E& d" M2 N! H* e( F1 a result++;) }6 s9 b; L0 R% N
ShowFormula(Formula,num*2-1);
2 _/ }$ ?; H9 }" h- W* F }
$ O: m# z* F6 @6 Z6 C. k2 k }- ?8 q; O/ T' ^9 V# \" p
}- [, r& B& |8 k6 n: l* k# l7 V7 R9 E: l! ]
temp[0]++; //穷举动力
( m$ q2 W- d1 \4 h2 q2 i1 r for(i=0;temp > num+3 && i//代码空间类进位# y; ~) G+ z) s! X$ U! u& O0 t
{& Q8 P7 ?. q% M$ K* {8 O) P# e
temp =0;9 {$ j. |0 ~+ a( T
temp[i+1]++;1 F3 J+ [: Z; G% J7 N
}/ V' x8 z7 X% T1 g
}
3 G' v3 h3 Q6 \$ z" [4 X, n" d // 释放内存) `+ H, a5 [& H2 O7 ^/ b5 G3 v
free(temp);
1 M6 G. p$ q: O- n6 |, \* _8 m
! {" R7 t% I8 I5 m! K //free(Formula); //？？此处不知为什么会出现错误 h. p4 D9 I& B* ]
free(NumSym);
) ~/ l. u, K- M0 x return result;6 e; a4 D; ^) y. @
}. H* C" P0 P: A+ M! f$ `+ B9 r a
// 由代码表还原为波兰表达式
1 j$ h3 }, t& cvoid Restore(int *Formula,int *NumSym,int *temp,int count)
# C9 n1 @4 O* [9 b% T( F* {# G! Y{; q8 V( a. S7 V% R$ o* _* G
int i;/ S5 Z4 W, Q- V7 L$ I1 \5 D! Z
for(i=0;i = NumSym[temp];
" k1 S( V- p( N}: h- A8 m1 q5 m: ?5 S( X
// 判断是否符合波兰表达式
: T% M/ J( }3 D' \1 ]/ R& L// 符合的条件是每个运算符号前必须是操作数个数多了运算符个数
0 w) s5 l y" R( b; w% ]" o! t// 且运算符个数为总数减一的一半0 J1 d" `; U1 U4 [& `
int IsOK(int *Formula,int count)
) {8 ]) p" s4 y7 ^{+ t) C: i. s6 ?$ z
int i,j;
0 ` G, r) z ^4 @! [( T for(i=0,j=1;i0 S8 Q% x1 g5 t7 n
if(Formula<0)- m" o, D! Q2 ~: _1 g0 A
if(UpZero(Formula,i)>j) j++;( w2 z9 Y* @( f7 L
else break;
& ?0 B! {* L" |- r; ] B if(iint)count/2+1) return 0;% T( U; c- O5 u% |/ R/ A& ?/ e
else return 1;. }; q# J# y' `( ^0 k
}5 }! d; [ f7 T" J, Z
// 查找数组大于0的个数
% t$ U, O- O# g* a: h/ h# zint UpZero(int *nArray,int n)
5 Q7 P: {; a, p- ?- s2 d* h* l{) T2 e g2 k$ @- I: Y. e* h
int i,result=0;; B w7 Q, S5 Y+ k6 d) q2 C
for(i=0;iif(nArray>=0) result++;6 E2 p# j; a* W4 R: s
return result;3 q$ Z. d' A+ c6 L @; P3 G
}1 u9 F( P/ {- c2 v! p
// 查找数组中，小于Num的数是否有重复
* a1 V* J: `' u" Sint IsDownNumSame(int *temp,int count,int num)0 @- l" O3 k( }$ t3 v8 g( m% p
{6 {6 E( L5 H8 _
int i;& A7 F+ k) t3 u, O( b. n
for(i=0;i5 Q% j5 U. k( z8 C1 A5 B {
5 i, I4 O( \* }/ e. ^* h! k if(temp < num)$ S4 Y( ~" S' o9 ^1 V6 [5 A1 W
if(FindInt(temp,temp,i) != 0) return 1;* b9 W3 K7 V% |5 Z$ V
}! k M$ A- D2 h6 E
return 0;2 C. A, U; U) b+ x, G' T+ o9 X; _
}
6 F m2 `! K' P- |7 D6 f// 查找数所在数组的位置，返回0为未找到- D' X: }1 |; p
int FindInt(int *nArray,int n,int len)% `; F! {9 H! v" L" {
{5 i, F& \7 b4 B0 J( A
int i;
! U: W3 p2 q. ~+ Z( l. N, n$ j for(i=0;nArray != n && i2 V. C7 i; O( \* g if(i>=len) i=0;
1 _- ~' D' e0 _' ` else i++; S x# N! R) ]# R2 p: Y* X
return i;- R6 w! t, f" F& `
}
' v' y% O3 A2 s& ?/ Q
7 V( f. z! `$ x1 q1 g+ y// 计算算式结果, r' m( S6 t* P! T$ F: ~; }/ f C
float GetFormulaVal(int *Formula,int count)
7 V3 D4 w2 Y- J* g2 [; m) Q2 q7 Q7 H{6 S% Q( ^# _: n# Y6 y: }" E
float result;
# A+ o2 k- j5 Q7 ?# j; l$ n BinTree *head = (BinTree*)malloc(sizeof(BinTree)); //二叉树头节点6 X7 o. y1 L! p" i" D
int *nArray = (int*)calloc(count+1,sizeof(int)); //波兰表达式储存数组，首位表示数组有效长度
[1 J9 V5 Z- ~% K2 W* k
: \+ r3 H1 i- u G int i; f8 z" T2 I( M
for(i=1;i<=count;i++) nArray = Formula[i-1]; //复制波兰表达式. N$ k% `/ G. J1 M
nArray[0] = count;3 X$ U- k; n% u' m4 }
CreatBinTree(head,nArray); //建立二叉树
+ V m; z9 ]" N+ w2 Z/ p1 C/ C* N# y
6 i S& K. R+ C8 j result = CalcBinTree(head); //计算二叉树算式
5 F: l \" A- k2 t/ t: k3 c AfterBinTree(head,&FreeBinTree); //释放二叉树空间; ?4 E+ Y* Z) c0 X( D3 I+ L6 z
]8 [: n W1 ~' x& J free(nArray);
1 P) _7 b5 X* j+ _; v7 X' C2 g return result;: f9 I U% g% E3 E& k$ ?1 J" {" R( e
}
/ O5 ?# ^# t% e6 k2 O1 [9 _float CalcBinTree(BinTree *Tree)3 T$ B7 ]3 V0 n; p
{2 p% C7 P% p5 Q( V& ~* ]2 [1 }
9 K9 \9 h% b; V# ]- s6 b& A# g
AfterBinTree(Tree,&AfterNode);
. d8 o1 ?8 Y* J. h" c/ T return Tree->Data;7 q$ o0 u5 d. c3 w) G0 u3 d
}# ~7 C# V; n; C; K! d {
* [, B" H. q4 N% p- t
// 后序遍历二叉树进行计算,但会破坏二叉树本身4 P+ s& w& b2 R: x
// 一个结点的结果为左子树 （运算符） 右子树4 ^1 l2 \- S: j$ P! O, v* f& u
void AfterNode(BinTree *Tree)
& l( S- [. x1 a v{
- d, b; V `# b" y switch((int)Tree->Data)2 Y1 |: J5 H- M0 g0 }& _
{
( [& Z5 {- c# w# a/ ]1 P2 l case -1:0 t* F% _' ~5 h( ^: F, A
Tree->Data = Tree->Lchild->Data + Tree->Rchild->Data;0 E' U8 s8 A, Z2 d S* U4 |' t$ D6 H% A
break;
! f9 C$ s- X' V% R d( v; m8 U case -2:
- j2 K$ q' |$ D e+ u E Tree->Data = Tree->Lchild->Data - Tree->Rchild->Data;
1 z9 k$ P6 \& k |! Y. J3 o break;
" u4 u+ E1 F( N; z# L0 S3 `( C case -3:# M; C5 c6 O( f# Z4 ^/ G
Tree->Data = Tree->Lchild->Data * Tree->Rchild->Data;
9 \) ^8 i3 ]- o8 U/ ?0 {6 |* ] break;! p) {5 N, x& D
case -4:
5 E2 K+ M" n' Z! i Tree->Data = Tree->Lchild->Data / Tree->Rchild->Data;
, x; t- k& L& ` break;. t$ S7 C; r+ |) X' g& s1 [2 |
}# R |/ Z- V7 g& j, Y: j7 ~; G
}
U$ e4 D7 a% P# _, a. t, ^! }// 打印算式& P6 {1 A7 x4 A
) g9 F) ?. a9 ? Dvoid ShowFormula(int *Formula,int count)
2 h4 O' x0 E9 r{8 ]. W4 W# z0 z8 `+ [
BinTree *head = (BinTree*)malloc(sizeof(BinTree)); //二叉树头节点 u/ P- L9 M0 u& W' E$ S
int *nArray = (int*)calloc(count+1,sizeof(int)); //波兰表达式储存数组，首位表示数组有效长度! }. R- n# t* [% f
int i;
! B* ~2 t4 o. l8 W1 X9 m for(i=1;i<=count;i++) nArray = Formula[i-1]; //复制波兰表达式5 g1 g. x2 \$ E! Q: J+ T
nArray[0] = count;
, f$ U) J) ~8 {9 q- o% d CreatBinTree(head,nArray); + }1 j* w' H) t( I
AfterBinTree(head,&Myitoa); //初始化二叉树字符窜部分
|, ?; N& O9 U, u4 o AfterBinTree(head,&GetFormula); //转化为普通表达式& ?$ O) V5 P$ C X4 F
printf("%s\n",head->Formula);
% y2 P: ?0 S- m- S* E6 |6 o0 b AfterBinTree(head,&FreeBinTree); //释放二叉树空间) N/ k0 k4 [. c( b0 [
free(nArray);$ y, n+ }2 P) q6 a' N
- t" D# G8 B) @$ V/ Z1 y7 d4 H' y5 P
}8 x0 o7 ~* U; B% O
// 类似计算二叉树
/ c4 i3 ?& Q% c: M// 会破坏二叉树本身2 g' h4 W7 b& {" b( ~( E/ t
void GetFormula(BinTree *Tree)
9 @0 q" y P; O- H{
e3 {1 x4 c2 l; W/ f1 L$ v3 I+ X // printf(Tree->Formula);
# \% E/ {% Q' `0 K. D( j if(Tree->Data <0): X% T' H9 K3 i. `8 |. N; M
{7 y' \$ B, g' G( t1 B- E; G
char temp[100];! W# I+ \) S2 s/ e
if(Tree->Lchild->frist < Tree->frist)
4 X& j& f7 c. x4 E4 r {
* g. `) W9 W( x& I6 u strcpy(temp,Tree->Lchild->Formula);( D7 {3 s; H6 f7 V
strcpy(Tree->Lchild->Formula,"(");
3 `' p _0 A0 b0 ^, u2 Q strcat(Tree->Lchild->Formula,temp);
1 p7 U5 c' d5 D8 h* o strcat(Tree->Lchild->Formula,")");
& g9 N4 m0 F- j9 J* T8 d }8 T" {; [% [6 f3 X. n9 X6 M
if(Tree->Rchild->frist < Tree->frist
0 B; z' g9 d! l5 L9 e1 } || (int)Tree->Data == -2 && Tree->Rchild->frist == 0
2 f. f8 o9 s% v$ X+ i; b/ e4 |: A || (int)Tree->Data == -4 && Tree->Rchild->frist != 2)/ L! c6 ^1 h) {7 j
{3 [& Z5 `1 W6 F1 A4 y3 M: w
strcpy(temp,Tree->Rchild->Formula);9 ]9 ~0 H' B$ ?! \5 B3 N3 Z
strcpy(Tree->Rchild->Formula,"(");& O, |- O; D# a
strcat(Tree->Rchild->Formula,temp);
3 z% Q' o' l( H7 a/ }3 N" o4 r strcat(Tree->Rchild->Formula,")");
: r! N+ u; U3 ?5 Q }
, w4 S, a: Y* L9 u* k' o strcpy(temp,Tree->Formula);
; x4 S% n( Y' |6 h. T strcpy(Tree->Formula,Tree->Lchild->Formula);
1 |$ r" P) X/ X strcat(Tree->Formula,cSym[-(int)Tree->Data]);! m3 d6 u! n2 A7 I
strcat(Tree->Formula,Tree->Rchild->Formula);
* G" j: X# f& Z. s6 v }8 E* D. Y9 R# c$ e" y* f
}3 N) K0 C. ^2 q* m
// 对二叉树字符串部分赋值- l8 t' f5 s# ~1 B4 q3 f+ m
void Myitoa(BinTree *Tree)
# J6 F1 n: W5 ~' x: R, E/ `{
0 a' g/ T0 b. h4 J: N if(Tree->Data>=0)
: m5 Y" ~) Q; }/ }0 C {
4 A- R$ w3 W( q- ^+ ~ itoa((int)Tree->Data,Tree->Formula,10);/ Z+ O U; K. j
Tree->frist = 2;0 U& ?" ^; Y7 A- S
}. z% x5 V. `8 H N* l
else8 \7 h+ d' C) \* V5 _
{. p4 _$ u6 N8 ?- U( c( A
Tree->frist=Tree->Data < -2 ? 1:0;+ i( `4 `! n/ W( S( q7 V/ t
strcpy(Tree->Formula, cSym[-(int)Tree->Data]);
7 f* f) b3 A, f //Tree->Formula[1] = 0;: Y+ R& k- m- |1 s& H( ~4 G. k
}% p: y; m* @" ^4 Y) D+ E" ~. Q% L. P
}9 I8 m0 b7 q, E+ [0 G+ L" q _
//从一个波兰表达式建立一个二叉树链表，需指定一个头节点
0 D8 p& C5 F. p5 ~! x9 _ ^! T+ evoid CreatBinTree(BinTree *Tree,int *nArray)
: g# y: D6 X* i{: M3 i0 c6 r+ L
Tree->Data = nArray[nArray[0]--];
* L L( t) |6 s$ ~: }/ G if(Tree->Data < 0)
$ w I2 W+ Z1 j/ B2 P {1 c4 f% f3 m* c; Q% _0 m
Tree->Rchild = (BinTree*)malloc(sizeof(BinTree));% z# A1 N7 u9 g+ K# w+ [, t4 V
CreatBinTree(Tree->Rchild,nArray);
5 `( T6 H+ K! V6 h Tree->Lchild = (BinTree*)malloc(sizeof(BinTree)); e0 g7 F. f% p; K5 y6 w; K4 Y
CreatBinTree(Tree->Lchild,nArray);/ c1 h! h$ X5 R$ |
}9 r! p# U* f/ ` _" C
else
* F; j6 o% N) ?2 \ {
: Y0 ?" f" u7 ?7 ~+ b) B6 ` Tree->Lchild = 0; e X. k9 g4 j% ]
Tree->Rchild = 0;" k/ x" [. y# n' I
}
$ u& v2 z: k" e& ?* ^* `" u2 f6 ]$ ? C
}
& U& x6 d# j' c3 a0 k: Y
& j# I1 z! S4 j5 U// 释放二叉树空间
% L% O% a; A1 ^$ Lvoid FreeBinTree(BinTree *Tree)
0 x( Y! C2 q0 l% j" ]7 m7 g{
7 X, A6 I0 k' w+ V+ K2 ?" J; h free(Tree);* F) y& U& i4 }
}5 R* k5 Q: ~( h" _5 [* M0 L; L# J
// 后序遍历二叉树, C: x0 o, G. q' ?: i8 B) s$ ^
// 方便其他函数调用，func为要对各个结点进行操作的函数指针
* S t6 L- f: E9 A, B8 I1 n2 dvoid AfterBinTree(BinTree *Tree,void func(BinTree*))
" B0 d0 B! ]' I0 U{9 E! h; D- ^& k6 i
if(Tree). M3 R" U8 X, ` V3 R
{
! u* t) o) Z+ u% P7 h AfterBinTree(Tree->Lchild,func);
# y$ Y, V9 b7 g2 B+ \ AfterBinTree(Tree->Rchild,func);
& M8 ~: d1 x; N2 [3 U6 J0 O. N func(Tree);' U: t; b% q, V* O- p8 b
}8 K( u* G9 a' F, N4 Z- C) L
}
* i8 w, `/ C- ~7 J1 L9 _$ T# D) W9 _: L |
|
楼主: 考拉
/1 
IP卡
狗仔卡
发表于 2004-5-2 15:40:00
显身卡
发表于 2004-5-2 15:50:00
4 G7 v' f0 V( z& ]) e; [2 B% c0 ^