|
|
几天前的东西，现在没有大兴趣了
|
过重复代码过多,比如二叉树的建立等等
& o& e* Z2 b! a# a) z3 a/ Y
5 s j' N* A* O' r* A; T& i" b. o#include
/ f; P; \: |7 d- q#include
4 K& ]1 d7 g+ k' w: r
/ `4 _7 I' Q0 V, @typedef struct node
/ R( n! |& N) z8 K9 t{% [( K6 m# }5 [
float Data;
& ^: R% t( [4 M: Q! ^ char Formula[100];9 b1 n' m* V2 B8 j4 Q x* V7 ^7 D
int frist; //优先级 ]) V' e6 i2 P- w) H, @
struct node *Lchild;
# K3 M/ p- j; s1 B7 T" G" G struct node *Rchild;
# K" j' a. B9 V3 N% r5 O1 K9 o( X} BinTree;$ ^) z# a9 V* o# G5 P/ Y
void CreatBinTree(BinTree *Tree,int *nArray);
6 l, F; _3 }- r; x9 {" [void FreeBinTree(BinTree *Tree);: k9 m: n( b: N4 u* i
void AfterBinTree(BinTree *Tree,void func(BinTree*));
3 v4 f* ^+ u& H; o/ Q3 h7 Rfloat CalcBinTree(BinTree *Tree);) n6 g2 _ I: G% p% |& o
float GetFormulaVal(int *Formula,int count);
2 q$ \, I- J4 G% e Q" O; bvoid ShowFormula(int *Formula,int count);
3 h2 X F9 |- q Nvoid AfterNode(BinTree *Tree);' ?4 g+ o/ y/ h# J0 i# f
void GetFormula(BinTree *Tree);
, ]! @$ v S ]* Evoid Myitoa(BinTree *Tree);
8 Y# ~" g) o& m( P3 a, U% C% I0 s& |int EnumFormula(int *FormulaNum,int num,int sum);
/ O0 J- s5 o* p3 e' H6 dvoid Restore(int *Formula,int *NumSym,int *temp,int count);5 `7 ?9 d; a9 q
int IsOK(int *Formula,int count);
6 u+ n: Z; @' Kint FindInt(int *nArray,int n,int len);. J! ^3 z7 ]2 t# |7 G" E: {
int UpZero(int *nArray,int n);
! B7 M8 H! @7 Jint IsDownNumSame(int *temp,int count,int num);
( I, e3 ?2 k7 k! V% R5 s% z/ b4 J" d6 z8 g
const char cSym[5][2] = {"","+","-","*","/"};+ z. c" A, V9 _$ }, F/ V
" e S! p/ S4 W' q b/ oint main(int argc, char *argv[])
/ P$ Z. Y; b9 {7 i{
( D- m4 l4 \- E8 |- _# Q: U, T5 v int i,n,*Array;) l/ I/ R3 @6 m8 d/ ~! K
/ H8 ?3 x/ X# q+ M, n% i/ y
//printf("几个数？");
7 [6 ^" A' \) Z) Z //scanf("%d",&n);8 s! W8 q9 s. H0 h
n =4;
( ]! V: X7 _, j% B! I- `# g Array = (int*)calloc(n,sizeof(int));9 g$ p6 d* l; t$ t1 L1 v
printf("请输入%d个数（用回车或者空格分开）：",n);! o+ @$ d. O c5 ^; |9 C
for(i=0;i2 s3 L, z s5 @$ q1 R R7 Z
scanf("%d",&Array);& w" ^0 i P( j' a) w* r# u" ^
printf("总计%d个式子\n",EnumFormula(Array,n,24));
8 i& r: B$ Q/ S2 `& K1 [ free(Array);2 c% w; E* F8 }$ k: t
, e+ h4 l1 t' N% I" G9 `
system("PAUSE");2 \+ K: j5 n! [9 v0 a" Y- ]# a( ?
return 0;
! Y5 \ ~" J9 h}, F# Y% }2 A! o
2 o: k u+ o$ D4 _) c! G2 yint EnumFormula(int *FormulaNum,int num,int sum)
8 r i+ \; C! k" i5 {6 W{: `1 A8 i1 K! [+ w' M2 d
int result = 0;$ Z) `7 K# ~. G; c. C+ g
int *NumSym = (int*)calloc(num+4,sizeof(int)); //操作数运算符组成的可枚举组
+ t+ L8 o* v9 @3 h6 s& I% k8 j+ g2 b- e p int *Formula = (int*)calloc(num*2-1,sizeof(int)); //波兰表达式储存空间( B1 o* b6 T/ L2 }2 a, V
int *temp = (int*)calloc(num*2,sizeof(int)); //波兰表达式的代号表示空间( E9 c; N O$ Y- U* ?) g
int i,j;& K$ b% Q3 [3 v6 i$ X
for(i=0;i = FormulaNum; //载入进行穷举的操作数
. l9 t4 G( w. F4 I for(j=0;j<5;j++) NumSym[i+j] = -j-1; //载入进行穷举的运算符号
4 G" ?: N% r- z! O7 M% b y) B# S2 K# S. \) k# y0 U3 _+ ?' I& t4 t
for(i=0;i = 0;& p( m4 z0 P' i
// 穷举开始，结束的标志为波兰表达式代号空间最后一位已进位，即前面各位已穷举完成
+ k9 D1 i6 h9 i S9 Z$ O. v while(temp[num*2-1] == 0)1 _2 p, B* @8 ~! }: H
{7 T" j; V3 \+ l) q
if(!IsDownNumSame(temp,num*2-1,num))
+ [' `* j) Q; ~- |' G {
: b7 w! [ N; L Restore(Formula,NumSym,temp,num*2-1); //还原波兰表达式6 C( x0 N+ F- y0 k
if(IsOK(Formula,num*2-1))
7 k$ b3 [8 O D {
]0 G: z. e$ J& P7 b2 | S float t; //结果偏差
/ o0 Z& W! d8 E t= GetFormulaVal(Formula,num*2-1) -sum;
; p& _2 T1 a" X3 C# `2 N) q& S8 W if(t>-0.01 && t <0.01) //结果为浮点数，只能进行近似比较' p, r' ~/ A; T/ i2 k- S
{ A; a: t+ T9 N( }3 {" s
result++;4 C8 S& [$ ^( B4 S
ShowFormula(Formula,num*2-1);& z; a6 `* ~' |. `( c2 Y3 _
}
4 P2 P7 V* E7 w3 R+ b- e8 A }( \* [% ]% [# o) v* d5 @8 x: Y
}2 s7 O" y0 g' }; E" \
temp[0]++; //穷举动力
6 l; E% m2 \, R/ p( n- o- H for(i=0;temp > num+3 && i//代码空间类进位
+ [+ w$ r# _( f; M {
' v& d" w5 r8 I0 }- w temp =0;
9 |4 J) w3 g" K5 s temp[i+1]++;9 A* S7 t9 N0 D- P# {
}0 \, ]9 O& [( M
}/ h7 S x( w0 _: g
// 释放内存9 g) a, B5 u) @0 B) M
free(temp);
9 L+ }2 U+ w! ?8 H' x; \* t
( G; {# I( ]5 _% ` //free(Formula); //？？此处不知为什么会出现错误8 D% O5 N# f, T& O0 d
free(NumSym);
7 y9 s) F) l$ K return result;# Y) q& r' _' q2 U8 u
}! E+ X6 \: S0 P: N1 K1 K
// 由代码表还原为波兰表达式/ g {# s( c3 m9 p. e) l
void Restore(int *Formula,int *NumSym,int *temp,int count)
# ]$ D1 g* I# j{
- `. @7 l% T1 ~. j- t, N0 b( o4 T int i;
/ R% H2 z/ B* I' Y2 T4 m5 F for(i=0;i = NumSym[temp];
, {; V; O; w( N: _}& D, Y4 \ n- U: `2 n. A) h
// 判断是否符合波兰表达式! J$ F" k( ~$ z r- G
// 符合的条件是每个运算符号前必须是操作数个数多了运算符个数& O& F% I, H! F! q P/ T
// 且运算符个数为总数减一的一半. V+ q0 Q: ^! @! y' l
int IsOK(int *Formula,int count)8 j% T" F6 q& C
{
; X; w1 ?1 {% L3 o. i, u int i,j;
4 y- z8 X( }) O0 g' }' t" D8 [ for(i=0,j=1;i& n- \: c+ i* `4 O! _
if(Formula<0)0 c# {, X, v. T8 m3 Q' V, v+ P
if(UpZero(Formula,i)>j) j++;4 ~' @3 ~! |) _8 k5 V1 g9 g8 @
else break;
3 `7 j5 Z% C. g. u$ V) o if(iint)count/2+1) return 0;
3 w* n5 x. v5 C3 U. {. w else return 1;
1 ?$ n4 v Z, R8 q" H, r# u}
+ X- P _2 C) x s0 h) r+ {6 v// 查找数组大于0的个数
c+ Z' a+ ], G2 W1 h3 Z' H/ f* hint UpZero(int *nArray,int n)
, | M# b, {. \& y( c{
5 T p5 }0 H9 M" z( j$ i4 ?" p int i,result=0;
; }, \4 r% Q; q! G( r" I3 a% {+ T for(i=0;iif(nArray>=0) result++;* l; s$ s3 ?' |( I- N
return result;& L% q/ \% N; C4 s% f
}( }, {' f8 c! D |* o1 P+ e% w
// 查找数组中，小于Num的数是否有重复' g6 i/ X( _! N( o# z
int IsDownNumSame(int *temp,int count,int num)4 V7 p! S4 O; A+ k6 @+ A) L, @! w+ P
{
/ ]$ }/ \) V' o) c, B T int i;4 Z8 N* a6 A; M
for(i=0;i/ f( M. g4 h* b+ m8 u8 [% C
{
8 z; L7 m- P! v" e; i if(temp < num)& s9 T1 Y! B/ U' g6 a" E
if(FindInt(temp,temp,i) != 0) return 1;3 R U; }: Q1 `5 D: v
}" F- o$ P; Q. C' F, {2 W! ?1 r2 q
return 0;% |% d' W$ _) d8 ^1 |% `
}
- E8 p9 D) }- H// 查找数所在数组的位置，返回0为未找到; S1 \& ]# T8 A I* }6 j+ ]6 B
int FindInt(int *nArray,int n,int len)
5 @6 J# A2 T1 M2 p+ p{
/ D" t0 ^6 j- m; e int i;
6 K" u+ l9 Q5 o& r2 k1 A for(i=0;nArray != n && i- F+ n( G! y! }# |$ M
if(i>=len) i=0;* L+ E6 ^. b2 o. p& w& ]5 A1 ?
else i++;7 E8 i4 }7 t5 B
return i;
. D4 l5 m- e' Z/ r% M}
9 G. y; b& v- n7 ]6 H1 |5 f
5 a* q k* {( |3 q// 计算算式结果( }/ D* ]& z2 `) Q- ?2 ]6 B
float GetFormulaVal(int *Formula,int count)% [ a/ D2 Z: E/ d& W3 r
{
- E4 s, k; j1 S# e float result;& v" e4 M c$ I$ q; H, K/ y
BinTree *head = (BinTree*)malloc(sizeof(BinTree)); //二叉树头节点
: b% q3 n2 [1 J% Z, f6 M$ ~( \ int *nArray = (int*)calloc(count+1,sizeof(int)); //波兰表达式储存数组，首位表示数组有效长度, V1 p8 K9 D' Q4 H# c
/ Q: J9 J5 h, L7 {2 e- M int i;
' M4 p: a6 k7 B' g5 U for(i=1;i<=count;i++) nArray = Formula[i-1]; //复制波兰表达式4 {7 U! q6 D8 \' u+ }! B
nArray[0] = count;- f% X V8 m' g1 N
CreatBinTree(head,nArray); //建立二叉树1 O6 l* d; b1 B8 w2 I1 O+ T
% s" s/ s/ E& }/ j# z6 O: J result = CalcBinTree(head); //计算二叉树算式
% R1 `, }3 v( ]; G AfterBinTree(head,&FreeBinTree); //释放二叉树空间
: }; r; v8 D1 g8 m$ \% i
+ m `& P6 [% d" a3 W( Z! N free(nArray);) ]* M8 A: I3 k% ?& C
return result;
: T% m3 v+ c& Z& K4 N}
9 M: Q: _8 i% O3 r% _float CalcBinTree(BinTree *Tree)* i# v. c3 P" g9 T% @& W( U$ ?
{
$ a9 q( c) `# s. J
' P. `2 a' ?" V4 M* r. V AfterBinTree(Tree,&AfterNode);/ v+ v' ? `7 Y1 J2 ]6 y
return Tree->Data;! I, f# Y1 M7 k" L7 j* W# L
}: b5 e$ T, p: O% k, l8 L
- O6 \ z0 L i( [8 a// 后序遍历二叉树进行计算,但会破坏二叉树本身
* `3 h6 t- m0 F- K// 一个结点的结果为左子树 （运算符） 右子树5 y7 a8 z! L9 O
void AfterNode(BinTree *Tree)
; G1 u6 v2 k6 }: m1 G{
( `0 d2 {3 H, E* k switch((int)Tree->Data)1 d ]7 F/ h" ?. W
{: h. V v7 P$ `6 S
case -1:6 J/ t2 R3 u8 E9 S
Tree->Data = Tree->Lchild->Data + Tree->Rchild->Data;
. {7 \" G" ], k% k7 P break;
; }! G& @, S3 Z4 G. _ case -2:
( O- S3 r# D, R# o/ T Tree->Data = Tree->Lchild->Data - Tree->Rchild->Data;
$ X8 e' J9 L+ d break;
+ \6 t" D+ m$ l% I2 p4 x4 i& e case -3:
5 c* F, z, m9 k Tree->Data = Tree->Lchild->Data * Tree->Rchild->Data;! b+ R) v! X ^' I0 R4 `4 w
break;
, b& o2 j4 a2 L! ~8 P- v L case -4:
0 q/ _2 r# @6 ^ P M' B9 @! ? Tree->Data = Tree->Lchild->Data / Tree->Rchild->Data;8 u' M& g2 L, l" s
break;
+ S) S7 \% k; m7 I }" L1 ]- A9 Q/ h+ M, P
}
- s; d; I" T& A K: N// 打印算式
7 f/ F F7 s7 {: W7 C6 o
! S7 Y$ H1 Z" B& O% M: [4 b, tvoid ShowFormula(int *Formula,int count)0 g3 b2 {: X" c( D. Y1 K
{/ h7 H/ [8 n3 r
BinTree *head = (BinTree*)malloc(sizeof(BinTree)); //二叉树头节点' D5 R, B8 C9 } A& c% l
int *nArray = (int*)calloc(count+1,sizeof(int)); //波兰表达式储存数组，首位表示数组有效长度 V. O: d& ^# e* j, g
int i;
: p7 d, d$ F1 U( |% q for(i=1;i<=count;i++) nArray = Formula[i-1]; //复制波兰表达式; S/ k5 ?; l v6 ?2 {, m
nArray[0] = count;1 |0 ` |! u# _( ~* N- F5 m9 k
CreatBinTree(head,nArray); : H* z9 Y/ T- ?( Z" W1 |% c
AfterBinTree(head,&Myitoa); //初始化二叉树字符窜部分
' X/ E! N" W5 h: M" E, b5 ~ AfterBinTree(head,&GetFormula); //转化为普通表达式
. S9 q, A+ b! X. L' k, V g& n7 Y; P8 Y printf("%s\n",head->Formula);$ n9 V, P# ?- A8 O# @
AfterBinTree(head,&FreeBinTree); //释放二叉树空间$ _0 T5 O8 j9 u' r9 m2 I5 n! E. k
free(nArray);4 Q+ w) s4 ?/ T8 T- o# W) C( h
: b! Z5 ^; w8 C' O# w) e {}
2 n7 M" `3 D6 D; c; d( {1 f% s3 s5 s* j// 类似计算二叉树 `& G- G Y1 N! V; P% A
// 会破坏二叉树本身
( C* y& _5 n$ c/ b" c$ Rvoid GetFormula(BinTree *Tree)2 I% y8 q. t0 O: u0 _7 Y u
{# J, @. Y' V6 X1 m S
// printf(Tree->Formula);! z2 N. N4 C' [% m, y( m4 K! m
if(Tree->Data <0)$ s5 W/ e! w% e& ~+ E
{
5 Z( z$ P8 A, C: z# m0 D char temp[100];# ]$ x2 N! T' ?% _" S
if(Tree->Lchild->frist < Tree->frist)- P/ w7 K3 f3 c6 A9 H
{0 t+ n4 q1 \/ m. S$ c
strcpy(temp,Tree->Lchild->Formula);/ m+ V! @) F" J, ^
strcpy(Tree->Lchild->Formula,"(");; J y) j. Z" y. K; H4 ?6 g7 ~
strcat(Tree->Lchild->Formula,temp);
/ ]# ~! g8 z$ g, ? strcat(Tree->Lchild->Formula,")");
" D3 U8 {% [" K; X }
3 y, y9 b/ G% S$ H if(Tree->Rchild->frist < Tree->frist
9 o: P' h8 I& N; h5 {! T9 b# K || (int)Tree->Data == -2 && Tree->Rchild->frist == 05 Z9 k, v: d$ f- E7 }
|| (int)Tree->Data == -4 && Tree->Rchild->frist != 2)
7 o& I+ I4 b0 t) u6 d {
" [2 U& o- g2 P( C( t6 {. b2 G strcpy(temp,Tree->Rchild->Formula);
5 Y9 e: o3 J& f9 G6 _# Q/ g0 i strcpy(Tree->Rchild->Formula,"(");
9 F" O6 O$ s$ O/ q4 g) P strcat(Tree->Rchild->Formula,temp);0 S1 u: T T$ [# \+ P% ]7 s
strcat(Tree->Rchild->Formula,")");6 u5 z: q0 P! \9 m, P7 g
}
3 z8 N7 z+ M" K2 q+ e strcpy(temp,Tree->Formula);6 y* c4 P$ S# m( ]4 U6 }$ D
strcpy(Tree->Formula,Tree->Lchild->Formula);) u! [7 K: y ]. `8 `( N. Q
strcat(Tree->Formula,cSym[-(int)Tree->Data]);
2 E5 z, n5 l8 X4 ^* w3 z strcat(Tree->Formula,Tree->Rchild->Formula);. H! J, D2 c9 j" ?; @/ ]$ r( `* y* R
}
4 G. Q' A# s a' K4 F4 { }- M) N% [* _}6 x) |- }, H$ I; t- H9 l' d
// 对二叉树字符串部分赋值" X$ s% E7 X3 I |& J
void Myitoa(BinTree *Tree)
/ o% {" O. S& F- m" h9 B- v' T{2 W: d; \' ?4 R" F0 e. k
if(Tree->Data>=0)
. U* T" F, t s* G9 y5 P! Z( H2 \ {
% N7 D) f) k" a) M; ] itoa((int)Tree->Data,Tree->Formula,10);, }7 J3 D, {* t# G3 e5 F1 H( I
Tree->frist = 2;# l7 w- l {/ {6 q$ j7 L: `0 R
}
3 n5 Y9 H R$ l# ^$ ` b5 d else
0 O3 C: g& z3 B: _9 G! I. b {3 f. ~% s) p& k" ?$ c; P- ]
Tree->frist=Tree->Data < -2 ? 1:0;
% }$ R* J+ t2 K0 g$ v1 M2 S" U strcpy(Tree->Formula, cSym[-(int)Tree->Data]);8 @! H1 Y- p4 g! a, n0 m0 C, k
//Tree->Formula[1] = 0;
O( ~1 q. Q# M! y# V }# g, W) h* l4 c/ v. o! N- J4 R
}
0 C" |# U' |; T# T" `+ g( l% c! H//从一个波兰表达式建立一个二叉树链表，需指定一个头节点
" J: ?6 l7 l' ?: l1 l( avoid CreatBinTree(BinTree *Tree,int *nArray)
( r" P. f$ `2 q" ~) G2 J{. G4 h2 @' J9 V+ p6 V+ c
Tree->Data = nArray[nArray[0]--];
3 ^* V" V5 c+ g) ?/ a7 C if(Tree->Data < 0)& M+ W! k1 S3 H8 Q4 P8 z
{/ X8 K# o& C$ A0 L7 L
Tree->Rchild = (BinTree*)malloc(sizeof(BinTree));
p* T5 I% b, s3 P) s* U CreatBinTree(Tree->Rchild,nArray);
* f% d( M% v* d3 V Tree->Lchild = (BinTree*)malloc(sizeof(BinTree));
3 S6 S- V1 K# j1 q. | CreatBinTree(Tree->Lchild,nArray);
( M( z9 K* p6 G5 ~2 T; V }# Z5 J; I6 {7 ^- J
else8 h" I7 i) V2 B0 r4 [
{5 x: ?* @7 U1 P& x* k1 q
Tree->Lchild = 0;
y9 }# e6 D( D; y- d+ F Tree->Rchild = 0;* N5 \3 O6 Z8 p2 b# ]
}0 ?& E& v3 ]! ^' z% ~' K
) X$ e, S, ^9 y4 d. `}
* Y" f$ A7 W7 `3 V
* X! t) @6 D8 Q" P- [// 释放二叉树空间
; g8 n k( O4 A7 ivoid FreeBinTree(BinTree *Tree)
7 }/ s* \% [1 r. ^2 A& @% j* B{
+ t+ E" x* S. L c& X free(Tree);
: h, e! v+ A4 ]. C' t+ ~}
; E, v; w, m) p6 R6 }0 e$ m// 后序遍历二叉树
( V& N: }! Z6 m3 O9 l// 方便其他函数调用，func为要对各个结点进行操作的函数指针
/ P9 _1 R7 P( z1 ]$ R4 Evoid AfterBinTree(BinTree *Tree,void func(BinTree*))
5 r& i0 }. K/ H, _{! P0 p4 a0 U: e9 T" M/ X
if(Tree)/ V; O$ ^& h+ P4 B6 M: C
{ A. \! K3 Y) g8 m& p4 g+ w
AfterBinTree(Tree->Lchild,func);) x" u0 A F0 x8 U) D1 j
AfterBinTree(Tree->Rchild,func);. g. k% m6 u# W( o, _5 E
func(Tree);
) @2 w% c2 A* W2 n+ M, C7 u }
6 t. B8 w$ F, Q, |; x( @, j}
3 l1 m8 K# A: `2 A# e |
|
楼主: 考拉
/1 
IP卡
狗仔卡
发表于 2004-5-2 15:40:00
显身卡
发表于 2004-5-2 15:50:00
4 ~. T0 i3 F8 ~4 A8 ?/ Z