|
|
几天前的东西，现在没有大兴趣了
|
过重复代码过多,比如二叉树的建立等等
8 \" T: \: X! q% P% y! Q4 E9 q2 {, x( Z3 U2 `# F: D4 K2 _
#include
, I9 l% _5 T7 q1 q$ T$ }( G/ B, z1 W#include - q' P) W- J# L2 S5 {1 W+ @0 b% Y9 y: X
6 G) @4 V7 r# J5 X( |; L) w) a+ C
typedef struct node
3 E2 ?( o; v& ]0 ]( w! e{4 F& u# X! f V8 g% p, l
float Data;
6 z7 x- S7 d3 W- ] char Formula[100];5 t% L$ Q" ]' X: w5 w2 y3 N4 x
int frist; //优先级7 i5 z0 e# L- d" {$ O
struct node *Lchild;- e" v! @8 ^- c% g
struct node *Rchild;
) O. M7 J+ A, v( y& G; X} BinTree;
) T0 ?% H( F. s) _0 J" Svoid CreatBinTree(BinTree *Tree,int *nArray);, r `( {/ S% i8 q$ J' A7 g
void FreeBinTree(BinTree *Tree);5 N- a" `: M* F
void AfterBinTree(BinTree *Tree,void func(BinTree*));
$ q, o* X5 U* X5 sfloat CalcBinTree(BinTree *Tree);
7 S! [! ~. w7 ^, i& T4 Sfloat GetFormulaVal(int *Formula,int count);' o( T, Z6 ?" T4 ^" f6 y
void ShowFormula(int *Formula,int count);
( n% B9 e9 a9 o2 M3 i0 ovoid AfterNode(BinTree *Tree);6 b: _, H& @0 d8 z i5 A( y
void GetFormula(BinTree *Tree);
# c$ V4 @0 M" `1 T" k( Pvoid Myitoa(BinTree *Tree);3 q& u% z2 c9 v0 b
int EnumFormula(int *FormulaNum,int num,int sum);
/ i2 i; q* R1 P0 S# A" Kvoid Restore(int *Formula,int *NumSym,int *temp,int count);
" {8 E/ o2 ^* ]8 G* f6 S+ oint IsOK(int *Formula,int count);; A% N/ M% e9 O' a
int FindInt(int *nArray,int n,int len);
3 d" l5 j+ M- r" c, wint UpZero(int *nArray,int n);
3 l" l0 n1 `4 l( @int IsDownNumSame(int *temp,int count,int num);/ {5 k' H% v( P1 \+ a: S2 r
`; Y4 W E5 N( fconst char cSym[5][2] = {"","+","-","*","/"};
2 X3 z+ W6 ] A2 h
0 @( y. l0 i' F X* [- W6 z- Aint main(int argc, char *argv[]): B: q3 |, ?) M/ y' X; O
{% y# O& a: l6 a2 h, H3 {" B
int i,n,*Array;
9 j$ e* h6 D( K% ]) D7 v. j
: }1 Y* |9 Y2 @8 E7 ^; _2 D. U //printf("几个数？");3 @5 i6 L- B( j+ U9 T' M! ?
//scanf("%d",&n);# A% ^2 Q# u( U4 D$ X: W, f
n =4;
( [- z) @) h) x b: Q/ w; \# v5 ? Array = (int*)calloc(n,sizeof(int));
! h2 w) S* Z4 K- z1 j* S printf("请输入%d个数（用回车或者空格分开）：",n);
* Y6 U. K" V; @ b$ a for(i=0;i' Z9 c, g3 U% _. m& {* W9 r O
scanf("%d",&Array);7 q) }3 J' l- j" s q1 m
printf("总计%d个式子\n",EnumFormula(Array,n,24));
" U( c) v: |# y" J e, J, {# i free(Array);
0 ~1 ?# ? U9 t0 G
$ v1 a# ~7 K0 N$ o. Z! a# p system("PAUSE");
: L! ]4 y$ c. O! q return 0;
) x6 Z4 l3 q' E7 |0 t# i4 e& O}0 [" C% ]1 M! Q2 g6 k0 V
% t0 Q. L4 D. M2 t; Y7 Oint EnumFormula(int *FormulaNum,int num,int sum)( |" Q; \, R8 Y% ?1 A3 b& m2 A% c
{
+ R7 H! p. M1 t* o4 m5 D int result = 0;5 R# M. A) P- O5 o1 k
int *NumSym = (int*)calloc(num+4,sizeof(int)); //操作数运算符组成的可枚举组
/ a9 W" M1 R$ S7 T' \6 o8 _+ j0 d int *Formula = (int*)calloc(num*2-1,sizeof(int)); //波兰表达式储存空间
' G* q0 i: O) s! r1 `) H. p; _ int *temp = (int*)calloc(num*2,sizeof(int)); //波兰表达式的代号表示空间
' L. r7 g( {5 c1 _! v! C$ G int i,j;$ q0 V3 @( V, v3 F6 `, o$ f1 x" N
for(i=0;i = FormulaNum; //载入进行穷举的操作数
! s; ?2 q6 Q( V9 g( B! w" X for(j=0;j<5;j++) NumSym[i+j] = -j-1; //载入进行穷举的运算符号
+ M3 S6 v$ R. m/ s6 s7 L1 ?
: n3 D# L5 l, B6 F" g for(i=0;i = 0;, a# j E ^9 ~" y1 p2 l% n
// 穷举开始，结束的标志为波兰表达式代号空间最后一位已进位，即前面各位已穷举完成
; g% }' B6 J9 E- ^2 d2 X while(temp[num*2-1] == 0)/ }, x4 K; K8 Q8 l" o9 X
{4 o9 S( R, H& ^- ^- T4 n
if(!IsDownNumSame(temp,num*2-1,num))" j9 P; c, l& z- r2 `) u. S
{
; d$ n* Q) f1 i! k1 O. q Restore(Formula,NumSym,temp,num*2-1); //还原波兰表达式- o3 y7 q7 W( y
if(IsOK(Formula,num*2-1))
9 M, C M Q6 H! s X2 h, H; x {
. q6 J7 O# _( a- f/ R1 R. O( A float t; //结果偏差7 { m* j% i! H- j* \- y
t= GetFormulaVal(Formula,num*2-1) -sum;
1 }- R/ Q# }" N8 J; X4 X+ x* F7 k& l if(t>-0.01 && t <0.01) //结果为浮点数，只能进行近似比较
4 w9 U1 A3 P0 f {
0 \) \- \. l+ i$ i result++;
( e* G( I! ] S0 V ShowFormula(Formula,num*2-1);$ F! K/ \' a) Y/ U; a5 N! o
}
7 {1 h' S, _0 L+ e }+ V. x- t: m% v. V' @2 M
}" O* I* o- h# M' s
temp[0]++; //穷举动力
j# d1 c& d* a2 V# k for(i=0;temp > num+3 && i//代码空间类进位
+ ~" U# p9 }' g: X {
1 O5 B- a: s+ R- Z temp =0;
3 `9 x$ F1 |8 B6 x! |3 X temp[i+1]++;
2 H" n6 V- A+ b4 t" o5 l }
) D+ ?8 ?' K9 l9 U* [6 U4 S }, }3 {& m& Y6 `' S$ `* E
// 释放内存$ H A2 E- D$ T' d' Y
free(temp);2 w& B. u, |! H; I+ E. h% ~( P
) y: I7 b s# M: p, v( _ //free(Formula); //？？此处不知为什么会出现错误
# c# T& y; o4 t2 M free(NumSym);
, I) \$ F9 N& Q* \$ @ return result;. r' m( p# h1 Z/ U% ^: Q
}
' g% R9 p# p; \// 由代码表还原为波兰表达式
5 j. f2 t* F3 @2 Z; E! y6 r# \void Restore(int *Formula,int *NumSym,int *temp,int count)5 o. i6 B+ C! y5 z$ m! F, P- G
{
, C! U. Q- p: k4 J int i;
9 {0 w) N* }) f6 K' W for(i=0;i = NumSym[temp];
; a" n* N: q6 s}
7 t% r' U, i$ R- A// 判断是否符合波兰表达式
. H1 Z# J3 S: b9 ^, F" m// 符合的条件是每个运算符号前必须是操作数个数多了运算符个数0 X% u5 g L9 h+ m1 [# { ] Q9 B# ?- Z8 d
// 且运算符个数为总数减一的一半
0 r9 ^. E2 f1 q; Yint IsOK(int *Formula,int count)
4 N8 T2 b( h% j6 f{
, J0 K) t$ W0 t+ k2 ^ int i,j;
1 V% a2 R6 s# B! ` for(i=0,j=1;i. F3 P9 A% j# H6 i9 l
if(Formula<0)
( f$ V! X: G, t, y$ I0 O. C$ X if(UpZero(Formula,i)>j) j++;: L) l+ S1 H1 ]8 D- O
else break;6 g; X1 }3 ]1 X+ L2 M5 B& k1 b @
if(iint)count/2+1) return 0;! S A/ [8 y& U* q% T" e- m1 R% t
else return 1;
5 z* O" I( o: }}
( |' q- }3 a# K9 u6 I9 g1 g// 查找数组大于0的个数0 n+ B' W5 m! |3 L" u9 [
int UpZero(int *nArray,int n)) d* J6 k: P3 K( g9 W! n1 A: ?
{$ ?. f) I9 }8 G4 o D( H5 n
int i,result=0;
# X0 j6 W4 G8 s y& n. [8 q' K for(i=0;iif(nArray>=0) result++;' d3 v7 Y# h' s- W
return result;* l/ W# q9 N3 c3 W/ ~8 v4 j
}
3 Y7 @( O# T2 q2 o i x// 查找数组中，小于Num的数是否有重复
9 x0 E0 c2 l0 |! p/ Qint IsDownNumSame(int *temp,int count,int num)
0 w) _! K) C! H4 w0 s" |{
: b( c' ? H. c, @" e& T% I0 r int i;7 ] Q5 H8 m1 {. f2 m2 y1 E$ \: F" ?6 @
for(i=0;i) {' A" ~- ]- ^7 f8 ?$ M, B6 l" H( e! P
{7 M: l! E# p: E4 r0 F, {
if(temp < num)9 K0 q- |4 ^, ]- E' _# ]4 q1 N
if(FindInt(temp,temp,i) != 0) return 1;8 c0 C0 S' J7 {0 |8 K1 A
}9 {8 B( M0 N% ?9 O ~- u
return 0;
$ V+ V. E6 Z4 N% x' ?}$ e, A" U7 {$ ~6 `5 A
// 查找数所在数组的位置，返回0为未找到3 p3 a0 _+ P4 F0 |; e% o
int FindInt(int *nArray,int n,int len)
( s: D) g5 S- F6 b/ N{) @+ b7 U7 v! m9 s+ Y
int i;
* ^8 I* s2 V6 _8 ~- T* h% { for(i=0;nArray != n && i- R" E7 b3 Y- E; p3 I9 L
if(i>=len) i=0;
+ e$ }4 Z/ f' ] else i++;
7 R/ W- J' V* I% c- q& @6 r return i;
$ b: W8 b: N6 f}
) q- |* s+ c: X# h. G% @
9 e7 ?6 h- t! U$ A' _// 计算算式结果
3 W4 y9 G; |0 ]: Rfloat GetFormulaVal(int *Formula,int count)& \6 p* O" [) w4 w# K
{
# k/ \& W9 C. w- ?* \1 w2 _ ~& n float result;
8 [& C7 a0 S- p1 Y6 S) | BinTree *head = (BinTree*)malloc(sizeof(BinTree)); //二叉树头节点* Z( Z8 n4 I/ T9 F
int *nArray = (int*)calloc(count+1,sizeof(int)); //波兰表达式储存数组，首位表示数组有效长度6 q2 w1 B0 q5 z/ E
# e' I' B7 r" K6 c: p# B! D% H, W, U int i;
4 [5 [3 P. A, X) C e for(i=1;i<=count;i++) nArray = Formula[i-1]; //复制波兰表达式" B! P& T y/ x% a
nArray[0] = count;
0 G. |$ z L/ x! q CreatBinTree(head,nArray); //建立二叉树- A+ L3 L4 M1 a; _3 T8 r
3 @* s+ q8 P# n, L
result = CalcBinTree(head); //计算二叉树算式4 ^( M8 I% D& V. l
AfterBinTree(head,&FreeBinTree); //释放二叉树空间8 d% q. Q$ c7 P, b6 X# }6 n1 Y
6 s) p* Y& u8 k& ]. a. k( A free(nArray);
P( i/ E: F" {" Z% p) q return result;7 B6 o- k0 U% b l2 a# P' j
}
3 D3 o% t+ V) b |% _5 D& mfloat CalcBinTree(BinTree *Tree)
2 D. V) Y: K' |/ Q3 N{1 r" c" z; R% C9 l9 O b
1 f/ P1 [4 ^( d5 p3 x- l AfterBinTree(Tree,&AfterNode);
+ U+ ?0 `0 P2 Y% \$ m4 k return Tree->Data;- T) x- l3 k+ K% N3 L8 K5 U! r% V0 E
}8 j. f/ L8 E* h. ^
4 K. \1 o0 g0 |' J1 ^- o) [
// 后序遍历二叉树进行计算,但会破坏二叉树本身
8 u6 a; @3 \! L; B {" K/ C// 一个结点的结果为左子树 （运算符） 右子树
3 z2 J& r* I$ ]+ H+ R( r+ h" R7 Kvoid AfterNode(BinTree *Tree)2 A* c5 @# @) X0 ]1 w
{) V; \! X3 f$ E. S/ V
switch((int)Tree->Data)5 n. |" O' j" [' h: {
{
$ X1 e8 C2 g( {6 C case -1:+ t+ g, J: K. C2 g
Tree->Data = Tree->Lchild->Data + Tree->Rchild->Data;
. }0 G4 T O: J6 ?- K+ n break;9 W J9 a, x6 Q8 A
case -2:
) \& K, Z6 \! h3 }0 F) V Tree->Data = Tree->Lchild->Data - Tree->Rchild->Data;" ?* o; J$ V. p! s, Y& u
break;
6 V6 s9 q/ I1 x6 Y/ b8 ~1 T% b3 j case -3:9 L' R& p% ^8 P8 p" J
Tree->Data = Tree->Lchild->Data * Tree->Rchild->Data;
& K6 \) ~* Y% y) W. ^% B0 E break;
9 ] y; l, t1 j( `' y' C2 h% g! [8 ? case -4:
% K) l8 h: l( T' T; } Tree->Data = Tree->Lchild->Data / Tree->Rchild->Data;! X, J# L" G: S: f9 S4 Z2 A4 X
break;
" y) x8 W6 z. @$ Q5 ?9 ~ }# b" O/ ~% B7 N4 k+ V# M. B
}
}/ [/ E' S! R5 R5 U// 打印算式
0 U5 V) z- K/ m1 Y; u; Y$ F2 v' [1 L2 F: e; I$ j( F" P
void ShowFormula(int *Formula,int count)
1 Z2 G0 p$ B0 _' a: y+ I) q/ B{5 u# Z T$ h1 J: L7 m
BinTree *head = (BinTree*)malloc(sizeof(BinTree)); //二叉树头节点
6 C! r) U6 T8 u( ]- E2 b* k2 e( B int *nArray = (int*)calloc(count+1,sizeof(int)); //波兰表达式储存数组，首位表示数组有效长度
3 A+ B& u5 H6 ^! Y int i;/ J& x; }& E9 a5 q
for(i=1;i<=count;i++) nArray = Formula[i-1]; //复制波兰表达式
* q) X+ k- z& b: E; u nArray[0] = count;
# d& ^! r5 e4 e+ O( F% P CreatBinTree(head,nArray);
9 T `6 z' X: G' P+ \ AfterBinTree(head,&Myitoa); //初始化二叉树字符窜部分
3 H1 _" s& d3 s) Z+ v! O- a AfterBinTree(head,&GetFormula); //转化为普通表达式
; u, T1 ^7 D" ]9 _9 l printf("%s\n",head->Formula);
) T# ?# a" U* r. c8 E% u AfterBinTree(head,&FreeBinTree); //释放二叉树空间: u. n! Q7 ]8 d" j
free(nArray);
$ x! i2 {- V2 M% Y6 A0 O6 d 8 ^) Z7 f o: h* g0 Y
}! F. d) }" S8 G5 ^/ [+ i- _
// 类似计算二叉树
: U1 t- x$ X, [* Y% ~6 i// 会破坏二叉树本身
9 C% e4 p l) o6 \0 @; ^% N0 vvoid GetFormula(BinTree *Tree)0 L9 x; k& L2 M8 k
{1 f/ r+ |) ^6 G: [4 ]
// printf(Tree->Formula);
" \" N# k2 [! C. W; N+ ^! V2 E9 K if(Tree->Data <0)
1 @2 X* L. I5 \/ ] {
# B% v9 Z x: \4 h char temp[100];
3 L7 D8 x+ f3 ^' q8 u. }& J if(Tree->Lchild->frist < Tree->frist)
7 G9 |: Y k: h* d! E! u {
6 \4 e2 x7 P z# Q8 ` strcpy(temp,Tree->Lchild->Formula);
- h# T- E% i- v! |8 Y$ p3 c strcpy(Tree->Lchild->Formula,"(");
" M5 M; _8 j( s' M strcat(Tree->Lchild->Formula,temp);
& C$ k8 s: H5 V# Q strcat(Tree->Lchild->Formula,")");: q/ N* q4 o+ m
}
( L4 m& r1 H$ b& \( [0 u if(Tree->Rchild->frist < Tree->frist
5 a- f* l5 z' f4 Q$ P || (int)Tree->Data == -2 && Tree->Rchild->frist == 0
; r5 @6 @* f. k' } || (int)Tree->Data == -4 && Tree->Rchild->frist != 2)9 V3 s4 O/ ]8 T
{
0 s) _/ U2 U7 Z+ u! d strcpy(temp,Tree->Rchild->Formula);! f9 o- j$ Y1 a
strcpy(Tree->Rchild->Formula,"(");, h: @2 n0 k9 F* a: A
strcat(Tree->Rchild->Formula,temp);7 P! w) Y p3 t9 }. q
strcat(Tree->Rchild->Formula,")");" b) C1 A2 N+ V6 a, `
}
" E8 Y& G- h! k! ]3 s N strcpy(temp,Tree->Formula);7 n9 L0 B2 G0 y5 f5 f
strcpy(Tree->Formula,Tree->Lchild->Formula);
9 X2 e: B9 \0 s6 ^% K strcat(Tree->Formula,cSym[-(int)Tree->Data]);
- @) F5 `4 \* \' [+ W. s$ h; O strcat(Tree->Formula,Tree->Rchild->Formula);
i5 S( \' e6 h. w! Q2 z+ w* V% H }
1 S0 B- ^+ l4 a9 f4 C3 t3 T}) h# l3 L5 s3 `
// 对二叉树字符串部分赋值; d* P y4 ~+ m+ ?4 S4 w$ \& \
void Myitoa(BinTree *Tree)
+ t1 U) O6 q1 X0 w/ t6 O2 m% c+ i- q{1 w: M2 p) o0 K3 v# D7 g
if(Tree->Data>=0)
) y& Q) m. k# T* r$ B {
% L6 r% X" C, j/ B- n itoa((int)Tree->Data,Tree->Formula,10);
. n0 F6 n( U0 J1 @/ E5 o( ^ Tree->frist = 2;
4 P w- ]5 s* ^9 q }% Z8 {$ I& F. a6 w( g" Y a
else) n. O( v' H T' ^4 y! ~
{ p) M7 `8 l8 c% T. J; i d4 g
Tree->frist=Tree->Data < -2 ? 1:0;
6 G- R8 z" E% W strcpy(Tree->Formula, cSym[-(int)Tree->Data]);# C% V% `8 u) P5 P1 d* p' g' U3 X' g
//Tree->Formula[1] = 0;/ \# }4 t* S# O4 `4 ^
}
0 W0 X$ s- P9 c; z5 _% f* [' x- y}2 Z# {3 i4 h+ s1 O
//从一个波兰表达式建立一个二叉树链表，需指定一个头节点4 ~% d: l$ i( q7 @
void CreatBinTree(BinTree *Tree,int *nArray)
) T: j* C- d( r: X% n1 I, {{
7 J3 d% ^- `# ]+ @9 \: I Tree->Data = nArray[nArray[0]--];- ^0 ]& D, }0 y% {/ i9 H9 i
if(Tree->Data < 0): C% i" E L. n8 ?( Q3 H, P
{
2 K- N& V+ @! S3 D4 B, C Tree->Rchild = (BinTree*)malloc(sizeof(BinTree));
1 Q2 F0 L. s. j5 I' s, ^, w CreatBinTree(Tree->Rchild,nArray);7 P2 U9 h6 m- J, x/ J- J$ |; M+ |2 a
Tree->Lchild = (BinTree*)malloc(sizeof(BinTree));4 ^' ~) N( Z+ M. A. i: w
CreatBinTree(Tree->Lchild,nArray);3 d& g4 s) y, O& j
}$ t [+ q$ e" c2 A8 {% W
else
! u; l0 k4 r- ^ {3 f5 c4 z( @9 F$ C1 p% j- z: ]" z
Tree->Lchild = 0;+ J9 c) Y; y# b0 f
Tree->Rchild = 0;* Z4 m, [' H) b* n4 P& ]6 X" v
}
+ Z9 b- M# K; k1 z
$ X8 E; z7 n" O8 i% O/ J* R}
$ }" a* O# R+ E6 Z4 d( |, H5 W$ E K' q4 [9 S3 t7 o& D: t
// 释放二叉树空间
! L( }9 k" ?1 Y$ D4 m! `" x# L9 X8 evoid FreeBinTree(BinTree *Tree)
" w/ Z7 s0 j& s6 _{
2 [* n. x% P3 _$ `2 H0 }3 { e8 R free(Tree);, X8 n$ ]# c8 |& U3 \
}) `, Y7 r1 }7 b) u5 @
// 后序遍历二叉树
5 \) {' ~/ X5 ~; F: s// 方便其他函数调用，func为要对各个结点进行操作的函数指针
' @0 `6 T1 ~0 j7 Dvoid AfterBinTree(BinTree *Tree,void func(BinTree*))
1 ]2 _% e: l9 d2 i1 G# ~# X8 a) x3 `{
, Z+ ] N7 Z( r% t! d, l if(Tree)* s$ J& o8 i2 N- u' J& N6 `3 A
{, A, g! w: s) e {& ~
AfterBinTree(Tree->Lchild,func);% U! v, T. K* L' w0 x4 v6 c! H
AfterBinTree(Tree->Rchild,func);7 j% l! O9 A% I) j: S4 v) @+ p
func(Tree);
9 c1 N0 j6 z" B) E, N7 s& P: i; F7 Y3 k4 _ }8 n& t3 ]. x: U( _, `* k! L
}
) y/ [( i3 s, B* s! ?; A) v |
|
楼主: 考拉
/1 
IP卡
狗仔卡
发表于 2004-5-2 15:40:00
显身卡
发表于 2004-5-2 15:50:00
* @3 t( C. |; b) ?# y# ~