|
|
几天前的东西，现在没有大兴趣了
|
过重复代码过多,比如二叉树的建立等等* K& n+ N8 i% h5 B( y
0 f* z" W( r! z0 \- n q
#include * |5 i8 o+ |3 U) T( E
#include 6 t, C- ? h3 D- k% O
; Z, d* D+ n0 v1 f
typedef struct node
5 f4 Q `. |$ A1 P/ P{6 {: D2 S( E6 ]* ?4 W! d
float Data;# U9 Y' U+ T E- Y% U1 L
char Formula[100];
, c% i. `9 c h1 i. I& O5 [ int frist; //优先级: \2 R9 u# P, O- u
struct node *Lchild;: P$ O* k# R7 d3 V- [. F
struct node *Rchild;: M, L, M- T* T0 }7 m- K
} BinTree;* e% Y- E P; L- Q1 T$ K* |8 {
void CreatBinTree(BinTree *Tree,int *nArray);; U X$ a' R0 l$ D& ^# w: L
void FreeBinTree(BinTree *Tree);2 l4 `8 S5 @7 Y% Q& o( g* T
void AfterBinTree(BinTree *Tree,void func(BinTree*));
; B a' s& C1 F: `% X" c: p Vfloat CalcBinTree(BinTree *Tree);. b5 C3 u6 c1 O, e% u+ o" {
float GetFormulaVal(int *Formula,int count);
, N+ V( O9 @6 \" zvoid ShowFormula(int *Formula,int count);9 y$ s, w! X+ e7 W, }
void AfterNode(BinTree *Tree);
3 j& r8 H# a( f% \! k/ p. Qvoid GetFormula(BinTree *Tree);6 S2 c; Y2 u j# i
void Myitoa(BinTree *Tree);
5 o* b$ F! \9 aint EnumFormula(int *FormulaNum,int num,int sum);
& } _7 s' V6 p9 L* cvoid Restore(int *Formula,int *NumSym,int *temp,int count);
+ J( A2 I r3 p% o ~6 Q2 Fint IsOK(int *Formula,int count);1 e8 j# j4 a' K2 M! C, i" x6 z
int FindInt(int *nArray,int n,int len);( e# [% E/ N- B a
int UpZero(int *nArray,int n);
' @% G8 D5 l8 z$ fint IsDownNumSame(int *temp,int count,int num);- K- I: p$ s) _: h/ I
9 c$ N" ~- ^* C% |: f
const char cSym[5][2] = {"","+","-","*","/"};. ?7 A5 l6 i' q8 y
3 w5 b; }# f* {' R( t& {4 gint main(int argc, char *argv[])2 t. t, z2 w# \1 \
{) f5 P0 u2 e" y0 v0 X# o
int i,n,*Array;
( U+ d3 e% n* p9 x8 y L
! c6 T6 y& T$ g. r, O6 B- X //printf("几个数？");
% _5 L9 c% q7 Q Z+ S //scanf("%d",&n);
5 Y l& d0 g9 R" M; y( Y n =4;' G+ f9 Q2 \; r& I: n6 u
Array = (int*)calloc(n,sizeof(int));
- B* ]5 F: W5 d4 e# ~3 q printf("请输入%d个数（用回车或者空格分开）：",n);
8 D0 C3 \* v9 @+ X0 h+ v: l for(i=0;i1 t" t. {% V; U' ? scanf("%d",&Array);
: y# O' X! B+ X8 d, `/ J printf("总计%d个式子\n",EnumFormula(Array,n,24));; H! {- A6 ~: k: f! p3 C+ u$ Q
free(Array);4 L7 ]* m6 J# G7 X/ p) _: P
0 i7 p2 X b: W" J1 t x system("PAUSE");
" G( K: b' [' S. d* Y( C return 0;0 C4 L4 E" ?0 F9 f
}
6 U4 F5 m5 }" _- k+ u; w
0 X F T1 u Vint EnumFormula(int *FormulaNum,int num,int sum)
, x/ @3 ~$ d/ G9 m& Y7 [{
1 u0 z: j$ e' W2 I( }* B# k5 s int result = 0;
/ U! X) z# h2 `' l int *NumSym = (int*)calloc(num+4,sizeof(int)); //操作数运算符组成的可枚举组 M% d s i, i0 R! `% ?- J
int *Formula = (int*)calloc(num*2-1,sizeof(int)); //波兰表达式储存空间3 C3 }2 V9 W, ?3 a4 `
int *temp = (int*)calloc(num*2,sizeof(int)); //波兰表达式的代号表示空间
; U- a! _" c! E% [9 ] ~8 S int i,j;" N: O' c) h ], w. ~# h' l
for(i=0;i = FormulaNum; //载入进行穷举的操作数
( R J0 a- n4 R( Z for(j=0;j<5;j++) NumSym[i+j] = -j-1; //载入进行穷举的运算符号
3 F( L- p4 X/ B* p) j
6 N ]1 d7 v3 l for(i=0;i = 0;" H% I5 t6 ^4 @ F
// 穷举开始，结束的标志为波兰表达式代号空间最后一位已进位，即前面各位已穷举完成
* d5 R2 J( ^$ h. _- w+ G while(temp[num*2-1] == 0)! a3 Y: |6 V8 ^- ? t1 V( n
{" @% F, _) D! h3 |, {; _* F5 U
if(!IsDownNumSame(temp,num*2-1,num))5 \8 i1 V( H9 ]) q
{
! f' v3 R9 }! r4 I4 |. F7 n' m Restore(Formula,NumSym,temp,num*2-1); //还原波兰表达式- o$ ?# V/ R' o, W& A# P
if(IsOK(Formula,num*2-1))- q% Q0 n5 M% m6 |1 ^
{
; x; G% ^; v$ s/ v7 i float t; //结果偏差 B0 I8 L/ n2 k
t= GetFormulaVal(Formula,num*2-1) -sum;" l) g& M+ X3 Q1 z+ i4 q+ p
if(t>-0.01 && t <0.01) //结果为浮点数，只能进行近似比较
5 i& _# l }, [' M% r) v5 ^ {/ R- w3 _( P" W9 N. N) v
result++;
- o$ y# ^; C8 e% c4 }5 D ShowFormula(Formula,num*2-1);, X5 i; U7 u5 Z& \; l5 v# K. f8 V
}
0 B: h( m# F" c: ?) z) v8 d ^ }; _2 f8 u+ E% `; J) ^ A% g
}: n2 x& g$ O) g$ x
temp[0]++; //穷举动力( @7 S# J/ v, X9 d6 l; g9 c
for(i=0;temp > num+3 && i//代码空间类进位
" @% f$ U8 T3 z5 x* W' H/ W {& l4 {+ o' R* @% q6 c
temp =0;% T, S8 g0 w' p" E9 C! e+ g
temp[i+1]++;" W5 n' i+ k7 V, L7 {+ p2 {5 K) V7 S/ w
}) b4 K( ?- c! L4 ?* m
}
9 U/ I- _. v9 G. u% Y // 释放内存8 ]5 O# K! e. v9 J/ l7 p
free(temp);6 a5 D4 C$ O m6 G3 l- }8 @8 d$ v
7 F! v- `) R8 \7 H& m% S8 I- \9 {
//free(Formula); //？？此处不知为什么会出现错误
# D$ }* v8 Z, ]% T/ U3 E free(NumSym);4 }' b" p. r9 ~) h
return result;9 L" @* o, g1 `: A
}
7 C8 e# J u" B2 q8 _1 y& ]# X// 由代码表还原为波兰表达式
/ e; G3 ^5 ^* @. X4 Fvoid Restore(int *Formula,int *NumSym,int *temp,int count)9 n. J1 v! U5 `6 O0 X
{
: m6 T6 G% R# f9 ^( d9 u( D int i;
" ~. l8 y ]. Y( e! i7 s for(i=0;i = NumSym[temp];2 J& \* ]! o1 Y# w! J6 f2 f
}
9 H: F j" K$ V6 J// 判断是否符合波兰表达式
& S# I" W5 U9 u6 S, V// 符合的条件是每个运算符号前必须是操作数个数多了运算符个数; }3 ]( Q+ m+ j! \- j9 J
// 且运算符个数为总数减一的一半, ], S9 x8 D' \' K0 }! ?3 I
int IsOK(int *Formula,int count)7 W; D, K; ]2 A" ~1 u0 S9 E
{1 o* E g5 v0 P
int i,j;
. J3 Z- v& V' j) t6 _4 e, W7 A for(i=0,j=1;i& ~2 R ~; D1 k! P L+ J if(Formula<0)
( k b% t4 E3 S2 Y6 n1 N" g if(UpZero(Formula,i)>j) j++;0 Z4 X3 G/ P( m0 F
else break;, _, ^2 w1 z% Z r
if(iint)count/2+1) return 0;# L3 l" j* s. Y5 d0 x
else return 1;' i/ t0 h8 S0 x/ P% T& G5 p
}1 T1 u1 {* C5 ?* x1 @( K& u
// 查找数组大于0的个数% Q( ^( s# Y+ t- p
int UpZero(int *nArray,int n)
) Y7 {1 ?* Z) `. D$ P4 T# s2 r; y" f$ _{ u# x& P: p, S# _ P- k' b6 x
int i,result=0;
; j& \/ C7 q- N. u for(i=0;iif(nArray>=0) result++;8 V7 q0 X3 P# M' B7 {
return result;; B {" {4 p& x; c" [
}
0 _$ t! x6 K5 Q& |' |// 查找数组中，小于Num的数是否有重复
2 p F" d) @4 R* Cint IsDownNumSame(int *temp,int count,int num). H+ f& g( L! s2 g% x
{1 f v) G- Z2 @" W4 {
int i;
8 `& m8 P6 Q0 {* E0 `+ X for(i=0;i% [% q( e1 X, {2 W& e0 Z
{5 m# _ U% a( I, }) K$ Y
if(temp < num)" [% `0 X- v: N& O+ H3 e& X. u
if(FindInt(temp,temp,i) != 0) return 1;
5 v) j7 e) k/ h: d1 j+ D: p5 Z }
# i. P) J! p4 p- A) ~" ]+ S+ t4 s return 0;7 j. R2 ?. P9 Z- L8 u7 ]3 W
}$ q% j" V- M; q1 e5 D8 n' O2 T
// 查找数所在数组的位置，返回0为未找到6 |+ h. [0 t7 W8 a+ g. H' z! }/ i
int FindInt(int *nArray,int n,int len)% c2 |$ y3 A/ l: g6 b* k6 @/ a
{' y6 c# X0 a3 _
int i;* j9 H' e3 _3 g2 `1 G4 t% r0 V! x# ^
for(i=0;nArray != n && i- W9 g$ k) n1 o2 ^5 v if(i>=len) i=0;
! g5 R4 Q3 V7 R0 c& B+ n! K# Z else i++;
9 C- g# e* G+ O3 M return i;9 `/ x% Z9 y+ s! ]: K+ _
}
+ q+ {1 U( p/ l
, `6 s. D# s8 U, e% i// 计算算式结果
& i" I7 @# B3 `float GetFormulaVal(int *Formula,int count); j5 U9 Q5 l1 F6 l
{
& u2 E, p6 `7 p float result;0 F5 J+ B0 r- q$ i- \4 z3 M
BinTree *head = (BinTree*)malloc(sizeof(BinTree)); //二叉树头节点/ v/ I* ?+ d+ e( R7 Z: R+ V/ G
int *nArray = (int*)calloc(count+1,sizeof(int)); //波兰表达式储存数组，首位表示数组有效长度- ^, \5 f* _, b1 t
0 i& Q* Z9 z2 K+ B int i;
6 n, E8 r7 T+ m6 ?5 I5 G for(i=1;i<=count;i++) nArray = Formula[i-1]; //复制波兰表达式6 L7 ~5 I1 n6 M* N
nArray[0] = count;7 B& b% z; K( J3 w& U8 U% z
CreatBinTree(head,nArray); //建立二叉树
1 k, O& R( x) n$ `$ X' o, ?; s
% I) P: m6 k' d( ^; ~* ?8 ] result = CalcBinTree(head); //计算二叉树算式
4 m- ~( C& b# u' Q- _: Q AfterBinTree(head,&FreeBinTree); //释放二叉树空间
* r6 Z" n9 @0 [- A: p8 a. q# t0 _6 l% p" T. ~9 h* i. R4 a
free(nArray);
+ _5 P ?3 I/ W9 a! d, z return result;, n J. S- Q H. P
}
5 M3 e% w3 M1 l# nfloat CalcBinTree(BinTree *Tree)
$ _7 z* K! R' R% H) F{
1 b. L7 ~! ] P1 w @1 p0 d& \) w
6 P4 w1 [" W' v# a. `' F0 u AfterBinTree(Tree,&AfterNode);( O3 f; B2 g% m+ [# [1 |+ l
return Tree->Data;5 s. n: a/ O- B7 f% \0 i9 U% X' U3 J
}
$ H/ Y8 l, E% U! E& j5 `! x6 r/ O- k/ I9 Z7 ]# }
// 后序遍历二叉树进行计算,但会破坏二叉树本身
* f" }# w9 U$ D: q// 一个结点的结果为左子树 （运算符） 右子树' s" k0 ?3 i/ z$ a5 q
void AfterNode(BinTree *Tree)
& Z& k* v/ k* O! u* ~# f2 y{: t, ?' i1 e# l
switch((int)Tree->Data)
6 K- ?: d, h& ^ {
& a9 B$ `( P+ s/ n' c6 K case -1:
% F! R4 v" O# v2 k Tree->Data = Tree->Lchild->Data + Tree->Rchild->Data;
$ b8 [8 ]0 l/ L" o; f6 F+ P4 P break;* K" W1 x* D* ^6 Y! M
case -2:+ I4 z8 J9 @2 e$ t% E R: \+ x/ x& B/ Y: X
Tree->Data = Tree->Lchild->Data - Tree->Rchild->Data;/ J1 l; `3 ~ E* m
break;2 m5 k; q; P' E6 \: z
case -3:0 k! Z H3 k% x/ u) a1 a
Tree->Data = Tree->Lchild->Data * Tree->Rchild->Data;
( B$ \5 i# E6 X% D break;
# J! e/ @+ s9 l" E5 Z |# P$ E case -4:, K; \% O/ j2 p% }" B
Tree->Data = Tree->Lchild->Data / Tree->Rchild->Data;
3 Y! D8 A0 }7 S' ? break;7 q' `4 M: N" |' P. O$ W, x* E# N
}
. ^' _2 K# e7 [2 ]; P2 u}! c8 t3 q5 k+ |, g0 S
// 打印算式
2 b& z. D( }; U
% k( Z0 `; K+ `' C jvoid ShowFormula(int *Formula,int count)# P; J; e \- I
{
/ C. F) o. l1 i0 ^) T3 X BinTree *head = (BinTree*)malloc(sizeof(BinTree)); //二叉树头节点/ U9 f6 J7 _- h
int *nArray = (int*)calloc(count+1,sizeof(int)); //波兰表达式储存数组，首位表示数组有效长度
2 q& O$ {; _ E7 A0 G# Z2 f int i;" k5 R; f) v. A9 k, x
for(i=1;i<=count;i++) nArray = Formula[i-1]; //复制波兰表达式* Z# ~$ I" k5 X% \
nArray[0] = count;. a6 n9 V' J) f/ H+ r, l5 W
CreatBinTree(head,nArray);
( ?2 g2 Q" w6 J# f8 I! s* Q1 L& T AfterBinTree(head,&Myitoa); //初始化二叉树字符窜部分
& F+ A5 n+ H( t& e2 c AfterBinTree(head,&GetFormula); //转化为普通表达式3 h: \5 C5 V& {- T; L, i/ R/ }
printf("%s\n",head->Formula);6 z2 s/ R# r) u' X8 f7 N8 n
AfterBinTree(head,&FreeBinTree); //释放二叉树空间
1 l- j$ S& H; {6 n! B1 U3 e* R free(nArray);
$ |6 c2 V, L: {% P% s( r
4 m8 b- a- e! e/ Y- ]1 C}
; L' H& U& R8 X' i1 g// 类似计算二叉树
0 \0 Z/ t! | E( @4 I// 会破坏二叉树本身
) T1 x- o# b' C8 P) @3 ^void GetFormula(BinTree *Tree)+ ]( Y- L9 q6 t' \
{/ @$ ^. ~& F" }6 e, v
// printf(Tree->Formula);
! f- D/ N0 x8 u if(Tree->Data <0)8 f1 D6 K6 G' q" A% D' l
{
5 ?, m( }1 R' u5 d7 R$ O( W char temp[100];
n0 z4 Q. e' L) l% ]" p if(Tree->Lchild->frist < Tree->frist)/ D$ K% Q7 B/ }/ q
{8 y# ~/ p. i2 h3 Y; u6 T( f: h
strcpy(temp,Tree->Lchild->Formula);; u! [$ q- P4 _
strcpy(Tree->Lchild->Formula,"(");
9 f9 h+ d+ T: V* |: Y" O strcat(Tree->Lchild->Formula,temp);
+ k. Y( d6 Z4 w strcat(Tree->Lchild->Formula,")");* X$ L5 P1 I3 Q' d* t1 L
}! q9 u/ Q1 [$ I f' m
if(Tree->Rchild->frist < Tree->frist
" @/ U$ I% Y7 e8 e3 G || (int)Tree->Data == -2 && Tree->Rchild->frist == 0
: I7 W, {% d# L* I6 s( c || (int)Tree->Data == -4 && Tree->Rchild->frist != 2)' A" t1 a$ S, J- d
{
" s( ]" ~4 }- i+ w9 a+ i: J( C; F strcpy(temp,Tree->Rchild->Formula);
. a8 a2 @6 e1 q# T8 i* d strcpy(Tree->Rchild->Formula,"(");
: |# ^* Y+ i( V strcat(Tree->Rchild->Formula,temp);2 Y- z% i i3 l& q
strcat(Tree->Rchild->Formula,")");
7 U+ I y4 Y3 I: P, O( M }
2 K# j( \1 C: u, s7 e strcpy(temp,Tree->Formula);
' H! f" g: t/ ^9 |8 d strcpy(Tree->Formula,Tree->Lchild->Formula);
8 v, [$ v9 z6 X strcat(Tree->Formula,cSym[-(int)Tree->Data]);
( H; y& k8 \# V; l strcat(Tree->Formula,Tree->Rchild->Formula);
. o; \' W% t& x( ~. d' H }5 k* ^( e( J% N7 _% v5 r3 ], {
}
* \* ^; ?9 |/ v9 L) ~& ~// 对二叉树字符串部分赋值
8 B% g- b* A6 R1 Ovoid Myitoa(BinTree *Tree)
3 i& A8 S: L6 z. `1 r{1 Y' k5 |$ [2 I2 B
if(Tree->Data>=0), V" D9 B- g2 ^4 R0 j+ ?
{) {5 s6 H: p6 I% m& v! m: @# F- Q
itoa((int)Tree->Data,Tree->Formula,10);
; ?' a1 Q$ w7 K% M% d- a6 y Tree->frist = 2;! D( g- e$ G' P ~$ H- g3 i
}/ ^ I2 @/ Y) _* r
else
, D) }* b' W4 r# p; @ {& y* ]% f9 V( e5 @1 {* b
Tree->frist=Tree->Data < -2 ? 1:0;
+ O4 V- r& n( S4 N strcpy(Tree->Formula, cSym[-(int)Tree->Data]);
5 C1 i+ |, Q. d; c, [0 r/ q# ^+ ? //Tree->Formula[1] = 0;
7 j) s3 d+ n4 u" _+ t7 J }
/ I/ C2 s1 m- Y* K! t0 r3 c}
4 w& H" |: }6 d0 O//从一个波兰表达式建立一个二叉树链表，需指定一个头节点8 f0 Q( R' D& N; N
void CreatBinTree(BinTree *Tree,int *nArray)
+ Y, }( s- i8 H3 ?4 }0 o6 n# h{4 Y6 ^7 o2 c v- _ a
Tree->Data = nArray[nArray[0]--];
, X2 a/ `7 x- x ~$ F if(Tree->Data < 0), `8 a9 [/ I; |
{2 O: m2 I, ]0 N$ y
Tree->Rchild = (BinTree*)malloc(sizeof(BinTree));
* J4 V3 K- s* C CreatBinTree(Tree->Rchild,nArray);
( q6 X# g1 z c: Q, D Tree->Lchild = (BinTree*)malloc(sizeof(BinTree));
" K, O/ s1 h: U2 k' a CreatBinTree(Tree->Lchild,nArray);
$ ~/ j3 B( _- i/ t9 U" [4 K }
3 m( F2 c" H$ N5 I, W1 t else
; x/ i2 J" Q, B0 T {
2 o; G z1 x1 B$ W4 f+ U+ e Tree->Lchild = 0;
) }7 V' [/ I' E4 [" g) ~ Tree->Rchild = 0;
{. v6 m! }3 P- d: a5 V# t7 H3 G% V }1 T. k& ~7 ^1 [" H4 H5 V8 y' Z0 k( x
( Z! o2 R; P( y [2 r5 g/ ]}/ v) S y2 X6 I1 q
* t% l( Q" f) m! K; p7 k) b3 x# T1 e// 释放二叉树空间
4 {$ i& U+ k& y6 qvoid FreeBinTree(BinTree *Tree)
$ j' [$ ^3 h& }' C4 ?9 P1 J{
& x: D9 ]5 N( O& v1 J free(Tree);# V# i1 G2 F6 p, M. k
}8 b0 E* n% O4 M/ k, j
// 后序遍历二叉树) N5 }. X, W$ R" W9 t
// 方便其他函数调用，func为要对各个结点进行操作的函数指针
! ~/ b& M% e6 v8 g9 s6 V4 n3 lvoid AfterBinTree(BinTree *Tree,void func(BinTree*))8 @" @& w- t; _* S2 o
{2 m3 l9 h7 F1 u5 M- x
if(Tree). D: W5 h! \, G
{
# y9 u# n& Y3 d3 l9 r3 |" t AfterBinTree(Tree->Lchild,func);* s8 i) L9 z3 x. Q/ f/ R
AfterBinTree(Tree->Rchild,func);
5 x8 }7 s: G' z: [; R$ X; x: S* J func(Tree);7 Y `/ n6 O. f$ A9 k
}) D; [8 G) ]! g' [9 E
}
5 v- C+ w( Y8 q" E7 h- ` |
|
楼主: 考拉
/1 
IP卡
狗仔卡
发表于 2004-5-2 15:40:00
显身卡
发表于 2004-5-2 15:50:00
( Y5 K6 c0 i) u- \