|
|
几天前的东西，现在没有大兴趣了
|
过重复代码过多,比如二叉树的建立等等* I8 L0 O8 F; V9 ^$ {& {" Q! V
@3 j$ W0 q6 V1 A( b3 g- U
#include
# v- x9 s3 ?% ?#include ) i- q1 C# \) a% I$ ~! r
' T5 C# y5 D" P3 E; G$ Y5 [- P6 Vtypedef struct node
9 q( p( _% C$ m, h{
( c9 Q# G( D8 `" d1 t float Data;
5 S2 T* E) h! u: |5 Q; ] char Formula[100];
: O* H$ P' O; m2 ?4 ^ int frist; //优先级
+ \. ]2 B; T( w+ F$ U/ T5 P struct node *Lchild;
/ `& s, C2 b4 e1 T1 L, q( {: F struct node *Rchild;
1 q1 v/ U3 r7 U6 B) M" |" k} BinTree;
0 G: T2 m: `3 b, O4 I% ?5 G3 Ovoid CreatBinTree(BinTree *Tree,int *nArray);
" w+ }. e" a0 D; Z$ T9 `void FreeBinTree(BinTree *Tree);3 a7 m5 k9 f- |2 u# i: T
void AfterBinTree(BinTree *Tree,void func(BinTree*));
1 y: E0 O! [- R1 J: [( b1 y- nfloat CalcBinTree(BinTree *Tree);- Y; F- [" O/ R |+ ^ k
float GetFormulaVal(int *Formula,int count);
" h z/ x9 _; E/ ]' zvoid ShowFormula(int *Formula,int count);8 S/ |1 Y- E2 l% r' t7 v+ o1 T
void AfterNode(BinTree *Tree);
& _! Z+ U8 j- `3 k yvoid GetFormula(BinTree *Tree);
. S% R8 q/ M9 ovoid Myitoa(BinTree *Tree);
3 t5 A5 }3 y$ _int EnumFormula(int *FormulaNum,int num,int sum);1 P3 ?. {! ^5 r# V: ^
void Restore(int *Formula,int *NumSym,int *temp,int count);' T8 o4 Z7 ]; ` N
int IsOK(int *Formula,int count);6 p2 A1 C: |2 L% m3 I
int FindInt(int *nArray,int n,int len);, C b8 p6 j: ^
int UpZero(int *nArray,int n);+ j2 g7 L8 a [
int IsDownNumSame(int *temp,int count,int num); }: V! K5 \! d: J1 R
& _' }/ a$ n# y, g
const char cSym[5][2] = {"","+","-","*","/"};
' Z6 B! B- C: H5 K
, P" x, G! r# Z! r" i8 ^int main(int argc, char *argv[])
6 [% |5 m+ B7 f/ J m{" P+ T0 O+ s1 L0 M
int i,n,*Array;: t* h3 H; Z5 v" }
9 ]' r( Y7 Q6 D0 F- n5 p# i2 D //printf("几个数？");5 e1 j. `- _) J
//scanf("%d",&n);
/ ]3 @5 X5 Y1 o! D n =4;
) o9 ?: b) U, P# p2 J Array = (int*)calloc(n,sizeof(int));
) [8 Q: I* x- v3 q! E5 s printf("请输入%d个数（用回车或者空格分开）：",n); ^9 v3 z5 d, w
for(i=0;i9 j/ b9 J; P1 e8 f
scanf("%d",&Array);
3 v4 D/ \, v8 t printf("总计%d个式子\n",EnumFormula(Array,n,24));
* ~6 D* Y" D3 z0 Q W free(Array);
* F; g! c) X+ f$ F y8 v
4 V1 Z( f) N- }* P* c# h system("PAUSE");! i) T4 [4 B3 s- y" m# f* d
return 0;/ u7 S. H; P. o3 h$ r2 W
}5 i4 Z G4 E" P6 R6 K
4 c% }! k4 s& ^/ F7 aint EnumFormula(int *FormulaNum,int num,int sum)
/ P, W: n! Y- Y# u, [$ ^3 {* i{4 J4 t& [( s* Q! Z2 D6 M' B9 h
int result = 0;- s3 a, o2 b$ k; C: Q
int *NumSym = (int*)calloc(num+4,sizeof(int)); //操作数运算符组成的可枚举组9 N+ n- w% l0 I3 R% ^9 @" G
int *Formula = (int*)calloc(num*2-1,sizeof(int)); //波兰表达式储存空间3 p, h7 x3 D; a
int *temp = (int*)calloc(num*2,sizeof(int)); //波兰表达式的代号表示空间
( E! f2 \! V& Y int i,j;( @& F3 b2 A' Q, G' b, s
for(i=0;i = FormulaNum; //载入进行穷举的操作数2 k" H9 a' s) q+ C* R) j# U9 v
for(j=0;j<5;j++) NumSym[i+j] = -j-1; //载入进行穷举的运算符号' ~( B9 J8 g6 [; B! v( S
+ S' z8 U' Y1 o. z" O/ h for(i=0;i = 0;
5 b6 ^$ M' l* [9 U+ a // 穷举开始，结束的标志为波兰表达式代号空间最后一位已进位，即前面各位已穷举完成
7 S/ ]6 O5 j5 H( V. V7 s while(temp[num*2-1] == 0) p, C& j5 K# F' a# L1 h
{
2 C' S: L& Z; I6 y2 z$ x if(!IsDownNumSame(temp,num*2-1,num))3 x( Q7 b5 C* ~8 b% D" M( G
{/ l8 g% M; z T6 c7 I! z3 f
Restore(Formula,NumSym,temp,num*2-1); //还原波兰表达式
6 G8 q# B8 Z" Y5 f5 ^5 E( ~3 g# U if(IsOK(Formula,num*2-1))
% p: [3 z3 f- s& l2 e {
3 d1 k( K O- L" _1 r float t; //结果偏差
) K0 Y/ }/ p' A; T t= GetFormulaVal(Formula,num*2-1) -sum;
- c+ f( I3 B4 q/ c if(t>-0.01 && t <0.01) //结果为浮点数，只能进行近似比较# Z2 c6 @& v( X5 \) T2 E2 g. O
{
& _8 W; u/ W7 }( p! y2 _, L result++;7 _* b5 \. l. X) W5 i
ShowFormula(Formula,num*2-1);
1 ]; @9 O+ {( n0 s5 }, @3 ^/ C2 b* l) ~ }2 D) b4 _1 r6 w( T. C+ C7 Y; L! Z% E
}
9 d( ~4 N) ^# G( B7 ], @+ l; A }2 i$ Q/ s0 O$ o- q
temp[0]++; //穷举动力
* ?6 ?6 k$ g1 z8 m2 V/ w& U" B for(i=0;temp > num+3 && i//代码空间类进位
0 i2 _( e+ {2 C {& W+ p% G6 N* L! P9 W. g
temp =0;
: o! a3 r% W6 L# h* y: U& p temp[i+1]++;, d0 W# c" o. y* S! n: Q
}1 j: G9 }8 a5 g0 j2 \
}
8 F# j4 b" v# W( F% g // 释放内存
H( ^! [% p! c7 }! ^* g free(temp);
7 o, ?; E/ u: o# S1 M% Q4 l6 w/ J: G3 e1 b. `) d5 g
//free(Formula); //？？此处不知为什么会出现错误
$ {/ M8 i) r7 g* S4 R1 ]$ Y4 S free(NumSym);' O$ i- I- v' B1 O
return result;( v' Y) U) q& }+ }$ T* ]4 I4 D
}
- Q2 F& M0 @! {" ~1 @2 K4 n* r// 由代码表还原为波兰表达式- ?; ^7 J1 m- J& E3 a2 _5 {
void Restore(int *Formula,int *NumSym,int *temp,int count)7 h1 w1 ~" }7 e" V7 R3 [
{) |5 a- c/ S) ^, R9 z* e( {
int i;: ~2 S: ~4 |' ?/ W
for(i=0;i = NumSym[temp];
& j9 N+ g) a! M" g/ \}
) c q' l: C' }; [// 判断是否符合波兰表达式: K9 r4 y$ s2 L, H, G3 a% X4 X) I
// 符合的条件是每个运算符号前必须是操作数个数多了运算符个数/ Q8 T) U7 ~8 ~/ X
// 且运算符个数为总数减一的一半3 K; J: h4 K8 M2 t3 t- D
int IsOK(int *Formula,int count)# R, K; M( N; s* r
{& ~2 G1 I- t: E3 Q/ k J
int i,j;0 l+ w# V" V2 h" |7 E- h! ~
for(i=0,j=1;i7 R* f$ T1 {' w4 i7 \ if(Formula<0)
- N" w1 Z7 F/ C7 O u' R if(UpZero(Formula,i)>j) j++; W! F2 Q" | {1 m% n6 a
else break;5 e0 _9 r& i; g6 l6 F
if(iint)count/2+1) return 0;
+ L# x# [0 U. q+ R else return 1;5 L! U; R) e2 `% J
}7 W7 c( q5 R& o$ X. K$ D* y" K1 g
// 查找数组大于0的个数
! r) d* v% F: lint UpZero(int *nArray,int n)- H# p' H8 T$ z( j( `
{1 t3 p; }2 X! R3 ]/ S" h
int i,result=0;
; f6 S9 ^! Z3 Q. R q; ~/ [ for(i=0;iif(nArray>=0) result++;
2 B4 R% ^2 S+ P+ b& W) I return result;' U. w4 u+ V5 B( {7 X/ f! k6 ^
}
) u! R6 b/ ]* i1 O0 d// 查找数组中，小于Num的数是否有重复6 h& \$ `+ G* l" ]
int IsDownNumSame(int *temp,int count,int num)2 h5 V7 t! Z$ M
{" k8 B4 k! {$ A
int i;7 q, C8 m! r. E. H$ j
for(i=0;i# p0 D9 }6 { V }7 D. x
{3 H% S8 N9 I2 t% P: U- @
if(temp < num)+ O& W- n" x, k: C+ |. ?8 e
if(FindInt(temp,temp,i) != 0) return 1;
+ `, D' f% w& Y- t* X$ l }
, n; Z. h" v, ?8 u return 0;6 X& [1 c! [" Y- R1 U
}# J' L+ d$ ^5 F3 a7 h h; j1 ~
// 查找数所在数组的位置，返回0为未找到
4 @( j) s; K0 ?! fint FindInt(int *nArray,int n,int len)" z+ \* l0 |# i3 L( b: C6 G T& h) w
{
! Q) J [" W. I9 F int i;
, @9 C& ?9 V5 E% Y( [+ `7 d for(i=0;nArray != n && i* F( }+ i" G' N* R if(i>=len) i=0;
! ?3 e0 R3 \) i6 N5 v else i++;$ n4 s: @0 G! Z* o2 C: p
return i;4 D [5 O4 Y3 L2 d' J6 H
}
" W8 t& `3 G: \3 H* W- L4 w- M3 x# I" S+ W
// 计算算式结果
& f) J1 j3 a6 F; B1 zfloat GetFormulaVal(int *Formula,int count)1 f; i& u, e2 {7 d% ], t
{
U8 K( z$ Y% x0 K9 H" M5 W' I( O float result;
5 Z. e$ b- x8 d/ U, }7 m BinTree *head = (BinTree*)malloc(sizeof(BinTree)); //二叉树头节点
+ v5 E1 Q8 k. m1 O& m' y D int *nArray = (int*)calloc(count+1,sizeof(int)); //波兰表达式储存数组，首位表示数组有效长度$ K" j- g& d7 I' T0 G8 V
! x2 R# W& e) }5 h; j- u, ?0 H int i;
+ w, f# y- L- L* W for(i=1;i<=count;i++) nArray = Formula[i-1]; //复制波兰表达式2 {- Z; A9 m' d9 o5 C
nArray[0] = count;
2 t6 y+ d! e- J0 | CreatBinTree(head,nArray); //建立二叉树% ~ S& Q- z0 x: Z6 L' I9 J i; v+ C
P. E. j: I2 ]9 U4 `% i7 v result = CalcBinTree(head); //计算二叉树算式
, e& Y+ {5 `3 F3 C# x; J, h2 |, b AfterBinTree(head,&FreeBinTree); //释放二叉树空间: S1 @( t) W. m% Q; \7 N3 v0 `4 V
3 p0 i) ]0 r' z free(nArray);
6 D8 |% K' l5 F, {! Z return result;
6 H+ Y* A- w u- [! h}
$ T T. ~; n" e5 N- ufloat CalcBinTree(BinTree *Tree), T9 r0 Y/ W8 w1 G$ w8 R. \
{5 M- p* J y" F! c/ `- C# p$ k, c
' o2 ?7 ?9 k/ R' z$ L: Z AfterBinTree(Tree,&AfterNode);
) x1 |1 q+ x- v1 f3 ] return Tree->Data;" j0 d+ E- s% P4 t6 g7 ~
}& ~! [) t0 B9 i+ s. T9 }( [ o5 T
3 Y- [' b+ s- d8 w: |/ W
// 后序遍历二叉树进行计算,但会破坏二叉树本身$ s. H; x8 Q$ @' H
// 一个结点的结果为左子树 （运算符） 右子树( j* y/ Z; _. n
void AfterNode(BinTree *Tree)9 p9 O+ v C. \" z$ n
{
6 W6 [" r' M' E1 w) d/ j2 r4 p8 z switch((int)Tree->Data)
6 k# Y/ }6 o7 ^, g# F {
* R% K# M1 Z) R$ I6 |- n. E: q case -1:( o" t5 Y! n% S- R
Tree->Data = Tree->Lchild->Data + Tree->Rchild->Data;
+ X6 t1 I7 @, \9 _$ R break;; j0 g9 c; `. g( t7 `, p! h" n
case -2:
; x2 f: ^/ d% ^ |" m& K3 L Tree->Data = Tree->Lchild->Data - Tree->Rchild->Data;- G: Q9 f$ g2 `2 |- d
break;
# x" j% K' p, s/ | case -3:
3 g# ^0 I+ h S( W: x$ }4 w Tree->Data = Tree->Lchild->Data * Tree->Rchild->Data;
" f( b! v4 }" ]9 a& q break;1 X( [* n; `. S
case -4:
0 o% a$ D* E5 R2 m# H! A Tree->Data = Tree->Lchild->Data / Tree->Rchild->Data;
" C: c8 Q! G4 z- ` break;. Y7 {8 @& F- B7 L
}4 ?" |' U {* g& l
}4 E" x7 z$ l* z5 _& N% z
// 打印算式' }+ }3 M9 ~* C% M3 H
) e5 z( ~$ G' [, x" g9 `( U4 B3 Fvoid ShowFormula(int *Formula,int count)
# g9 D: j! F, c! h{+ w+ i+ d! q, Y
BinTree *head = (BinTree*)malloc(sizeof(BinTree)); //二叉树头节点
0 Y) E7 [2 G" ^ int *nArray = (int*)calloc(count+1,sizeof(int)); //波兰表达式储存数组，首位表示数组有效长度
/ ~2 U% X5 F9 C% M7 d3 u& z, N6 n int i;
9 G6 Q3 I9 i. h# R K) _ for(i=1;i<=count;i++) nArray = Formula[i-1]; //复制波兰表达式
1 h7 }. j3 `- o! I$ D6 y; _* r, F6 I nArray[0] = count;+ g$ t$ j1 H+ e8 V7 K
CreatBinTree(head,nArray); - Y3 W* A# A* K N
AfterBinTree(head,&Myitoa); //初始化二叉树字符窜部分2 t. L; ]7 U4 n/ g
AfterBinTree(head,&GetFormula); //转化为普通表达式
8 k V& d1 g) \2 {" m printf("%s\n",head->Formula);: V) r3 x& y4 f" U8 m
AfterBinTree(head,&FreeBinTree); //释放二叉树空间7 c- L& W' o( u& S
free(nArray);3 g1 [9 ^" C6 v9 ~
' F1 D& A$ b/ q6 q9 k
}
0 w- K2 L. _: v4 y+ S" V" n// 类似计算二叉树) r) e0 w/ o) H/ @3 z
// 会破坏二叉树本身9 D" q) x$ a) L
void GetFormula(BinTree *Tree)* `3 T' ? t0 V" P9 P8 x
{* M$ u8 j5 D7 Z6 [
// printf(Tree->Formula);9 p4 M! z- I( r3 T. T' b3 V* R
if(Tree->Data <0). g) j# e V) h+ w
{
# {3 n2 d, a8 R* Q5 ~" V4 R) v char temp[100];) p; ], U5 ^. T$ ? v- D
if(Tree->Lchild->frist < Tree->frist)/ L j0 \6 J' H' U
{
( K7 g: F* f) a& a strcpy(temp,Tree->Lchild->Formula);
" s# d3 _0 |2 j) j8 K strcpy(Tree->Lchild->Formula,"(");( e/ l) o1 c: W0 K# ^
strcat(Tree->Lchild->Formula,temp);
7 u; M& M6 J: ?: M2 l strcat(Tree->Lchild->Formula,")");
2 S4 Y! }0 }1 q }. v" m. Q6 p1 ^8 v
if(Tree->Rchild->frist < Tree->frist8 O1 ?- Y1 P1 w6 ^
|| (int)Tree->Data == -2 && Tree->Rchild->frist == 0* ^: T( D0 X2 |0 \' N
|| (int)Tree->Data == -4 && Tree->Rchild->frist != 2)
: d# b5 c1 |& L! { {2 _4 e7 N! U, v5 V+ K, W8 u
strcpy(temp,Tree->Rchild->Formula);
: }$ m8 f) k3 L8 L' h! Z9 v4 o4 F strcpy(Tree->Rchild->Formula,"(");
$ I+ I! E5 A# `9 g* A strcat(Tree->Rchild->Formula,temp);9 m( p7 W: {3 m8 Z4 D
strcat(Tree->Rchild->Formula,")");
# ]3 h R( Q# t) \+ `. @5 g }3 ~1 F8 t& |; n( X. e' m8 f$ o: A
strcpy(temp,Tree->Formula);
O7 z9 v' ?2 S# B) y# `# K+ R strcpy(Tree->Formula,Tree->Lchild->Formula);
) a0 B, ]7 C/ X! J" _ strcat(Tree->Formula,cSym[-(int)Tree->Data]);
8 d' F# ~, ?' O, Z7 O2 b( c s# W strcat(Tree->Formula,Tree->Rchild->Formula);
5 D% l9 R' s3 V& {+ g }) {; X/ k/ u) C1 r# q/ t# y
}2 i5 C" A ^9 Y! U( S9 E; P
// 对二叉树字符串部分赋值
) w2 y/ A) D4 o5 M! E4 Xvoid Myitoa(BinTree *Tree)9 g4 F, L. a" J1 s6 u6 C
{1 d8 T" S; E; m( h3 W o6 O+ M
if(Tree->Data>=0)
6 M: r1 t4 S: v7 D {6 M0 U, \. W% m$ v
itoa((int)Tree->Data,Tree->Formula,10);& X/ p) |& F$ R" V
Tree->frist = 2;# D( s' t K4 L. E A
}
6 U, k% E5 I' ^+ G+ H) N else/ L$ A$ m5 F7 `# x+ X9 K, g Q: @0 C
{
* ~2 _5 m# f- T- n$ u Tree->frist=Tree->Data < -2 ? 1:0;
: C* Q5 I+ `& G% h6 V5 ~ strcpy(Tree->Formula, cSym[-(int)Tree->Data]);
% g* m! s" f) G: E //Tree->Formula[1] = 0;: i/ u" G% i9 m8 t
}
2 r" I$ \/ ]/ H7 t}
! _8 @/ _% i6 u; i( ?//从一个波兰表达式建立一个二叉树链表，需指定一个头节点
6 N. D7 R" d% F& T3 i. R- ]5 f$ Vvoid CreatBinTree(BinTree *Tree,int *nArray). t5 r2 ^$ U7 _4 u4 H( K
{
0 y7 Y0 T2 l$ \- t4 M. C) S Tree->Data = nArray[nArray[0]--];8 u' o) [- \. g- |* g6 e" S
if(Tree->Data < 0)
$ M; `; m( z- y) U9 C) D {
' \" p# x5 Y! ]0 }, y h! w( F2 B Tree->Rchild = (BinTree*)malloc(sizeof(BinTree));
E' _' }+ a% K5 V5 q CreatBinTree(Tree->Rchild,nArray);2 R( D9 i6 b# y0 _! O8 \
Tree->Lchild = (BinTree*)malloc(sizeof(BinTree));
! S' e0 C9 B1 e9 \ CreatBinTree(Tree->Lchild,nArray);7 g" C/ H5 I0 q* c4 @' v% o; J: N
}% k/ ]5 @! \1 e) J1 `
else% P' b- v9 B# O& y( C; {
{* X) N9 ~3 f. u/ F z; H6 ^
Tree->Lchild = 0;4 W' e' s; a8 l9 z! Y& D" \' m
Tree->Rchild = 0;
5 k) u) |+ e; U7 W/ q }/ d2 t: A2 U7 m/ X
% i( B8 i- W, i- N# V, { X
}& j' v' e8 H b0 {
3 W6 u' v* C: v3 c6 O' j! X
// 释放二叉树空间7 u+ C' b6 g+ \' d9 j
void FreeBinTree(BinTree *Tree)
6 C& H% P2 ?7 M{
9 X8 D' r2 K/ N8 ?: d9 _ free(Tree);
0 ?% S9 P5 F" C7 y}
8 Y$ S; p' H" L5 Y// 后序遍历二叉树3 m- \7 U8 c4 ^! O: N
// 方便其他函数调用，func为要对各个结点进行操作的函数指针
3 Q6 f& K) P" s: Qvoid AfterBinTree(BinTree *Tree,void func(BinTree*))+ M+ ^/ b; X" }, G/ t
{
' i" Y2 C! Q, v* Z1 S, Q* [, y if(Tree)
& L# R G/ h2 O4 k+ t( q8 _" I5 Y {
( n B+ U4 g) A AfterBinTree(Tree->Lchild,func);0 x0 ^2 [8 _- ]; f @ @0 {9 d
AfterBinTree(Tree->Rchild,func);' L1 w m8 O& w# i
func(Tree);: H* _9 b2 Q2 e: p$ B
}0 V3 J% a! Z- t( c" e
}
! z; M5 W, s2 m ^# E( s2 c2 o |
|
楼主: 考拉
/1 
IP卡
狗仔卡
发表于 2004-5-2 15:40:00
显身卡
发表于 2004-5-2 15:50:00
