|
|
几天前的东西，现在没有大兴趣了
|
过重复代码过多,比如二叉树的建立等等
8 L+ t9 v! f$ O- M4 _! }9 b9 ?3 w# |3 M( \0 ^8 Y+ H! Q
#include
, L7 q8 n1 X- r, W% \#include 7 K' |. C6 o1 h3 b! s7 X
. A4 _/ Q5 r/ Z' qtypedef struct node' E2 v* O1 e3 D! j& f7 H" M! M _
{
3 n" V& w/ I# [5 G4 Y float Data;
3 Y$ {. a* @% [+ T char Formula[100];
6 S% M& @8 l# r8 }* `$ ~ int frist; //优先级
4 Q. _. J/ b$ v' \3 e% g* H! M( ~" P struct node *Lchild;7 G) D) u2 d* L/ e) q
struct node *Rchild;
J5 K% T( `) v} BinTree;+ G4 v+ z# T# t
void CreatBinTree(BinTree *Tree,int *nArray);
$ i5 Y0 y" a7 pvoid FreeBinTree(BinTree *Tree);4 o! a0 }. A6 G
void AfterBinTree(BinTree *Tree,void func(BinTree*));
& q! w a+ W, g. P) ifloat CalcBinTree(BinTree *Tree);
0 T7 t' h& h* w4 y8 h9 rfloat GetFormulaVal(int *Formula,int count);2 R! D; l6 m! k. g# Z3 q
void ShowFormula(int *Formula,int count);5 c. Q. v' N, ? |+ J" m; m
void AfterNode(BinTree *Tree);8 I& T2 p$ @* Q
void GetFormula(BinTree *Tree);! {9 v H, S) B% |- h+ g
void Myitoa(BinTree *Tree);+ t/ f q2 T% ]# d" L' ?
int EnumFormula(int *FormulaNum,int num,int sum);
5 \7 k0 d' u, U7 n& L& ?4 Wvoid Restore(int *Formula,int *NumSym,int *temp,int count);
6 T( d! M0 K" ?/ J4 z1 Q2 ~int IsOK(int *Formula,int count);$ y3 o6 o- Y% A
int FindInt(int *nArray,int n,int len);; i3 B# Z7 Q: Z* f F( b
int UpZero(int *nArray,int n);$ J/ \' v: A7 }6 `
int IsDownNumSame(int *temp,int count,int num);# ]8 H5 b( a# H% J3 m {, J0 Y
/ C7 Z6 v5 e! r( E/ N
const char cSym[5][2] = {"","+","-","*","/"};* R; Z. m, G+ p4 V# `9 a
2 Y2 z9 \0 J) z0 L2 j3 u4 n# r
int main(int argc, char *argv[])+ W, n% P4 u- C. w) I/ k
{0 Q! }7 a( y4 J( s8 u: f
int i,n,*Array;
5 Q: M' P/ _1 F2 M1 E; x ) l3 k S N: M* Q6 ^, D
//printf("几个数？");8 U6 z! A" G- [( e2 i
//scanf("%d",&n);* v7 u' q6 p+ r) q C/ z1 {
n =4;$ M; r- H; y, T
Array = (int*)calloc(n,sizeof(int));; M# Q1 g7 f4 N
printf("请输入%d个数（用回车或者空格分开）：",n);
3 i' B# J3 X: |6 B for(i=0;i) _ E, |) P2 P" h9 S' c
scanf("%d",&Array);1 q2 z+ O0 i( A) A% k" y. u
printf("总计%d个式子\n",EnumFormula(Array,n,24));" W9 i+ e$ S7 \
free(Array);* z2 E& r4 t; H4 x" G+ E
; ~1 f# l" O. Q! s" N) ^" F9 ~5 G system("PAUSE");
! \4 D, }1 e2 d" C. [& E/ A return 0;7 w% l# y8 ?' J# G. \; x
}
) M- {7 g% I, M" M x9 `- [. b) _) _1 E* ~6 J: N
int EnumFormula(int *FormulaNum,int num,int sum)
9 r8 L+ \. ~8 m1 ~1 B{
% ?3 [4 z( K! n7 k9 } int result = 0;# M7 _, l8 ~0 s
int *NumSym = (int*)calloc(num+4,sizeof(int)); //操作数运算符组成的可枚举组
4 ~/ k6 ~/ C- g* ~( K int *Formula = (int*)calloc(num*2-1,sizeof(int)); //波兰表达式储存空间0 N7 N- y% |2 i. l4 A5 F) S, d
int *temp = (int*)calloc(num*2,sizeof(int)); //波兰表达式的代号表示空间( H5 @9 F6 P6 ?2 ^ h
int i,j;2 G$ }- ~8 {4 q' c9 l" T
for(i=0;i = FormulaNum; //载入进行穷举的操作数1 A: K( W/ b( L% X
for(j=0;j<5;j++) NumSym[i+j] = -j-1; //载入进行穷举的运算符号9 {# k/ w/ ?+ k1 x) L
6 s9 l* J: e( H6 m& _
for(i=0;i = 0;
5 [; l. V4 B; t' F' X- z1 a // 穷举开始，结束的标志为波兰表达式代号空间最后一位已进位，即前面各位已穷举完成
7 x* `% R: [3 A2 ~* D while(temp[num*2-1] == 0)
, Y8 X: h7 N* U8 s, J {2 s; [* E3 H0 ~) }+ ^( p9 u- \
if(!IsDownNumSame(temp,num*2-1,num))
5 {3 k% H( a- y1 `7 M" V {1 u' s5 |+ E) N
Restore(Formula,NumSym,temp,num*2-1); //还原波兰表达式
2 T6 v" [7 e2 o5 r( E2 |: c. r if(IsOK(Formula,num*2-1))* I. C: D9 l. w
{
. v' E& X _! a% L float t; //结果偏差/ }8 q5 R* k' z) C( [7 k' `" k
t= GetFormulaVal(Formula,num*2-1) -sum;
9 O0 n1 Q; U+ i( U; A! [ if(t>-0.01 && t <0.01) //结果为浮点数，只能进行近似比较
8 V- r% p6 P/ |/ a {
& |) S4 l* g5 {/ ^+ i- M result++;; \$ M) @0 _9 ~$ [; i) f
ShowFormula(Formula,num*2-1);% E9 _% s+ a( d1 Y$ }$ Z" Y O
}' R4 g) C) B; o! H( Y3 J
}/ c5 Y8 ?) r" z3 Y2 m2 ^
}, ]: W: G# Z7 U
temp[0]++; //穷举动力
& s- n9 T$ ]0 Y5 y+ `* H+ j for(i=0;temp > num+3 && i//代码空间类进位# A7 }. M, b, ]1 _
{
9 G) k1 X" K0 p& o( l$ ? temp =0;
& F4 l9 K; J: H- |# } temp[i+1]++;
H5 e. H1 _2 B) S }
2 h( j) F3 p- k2 l: y) G }( g: `5 {- q- ?% i
// 释放内存
o3 h* u: T8 D$ o free(temp);( U2 |* q% d6 `7 w* a, N3 I
* Q0 }* N4 g, \9 I Y) }2 _ //free(Formula); //？？此处不知为什么会出现错误
0 j" r6 J; V5 K0 U1 K4 F# s) P* |8 Y free(NumSym);! e4 y( A* g" u) R. Q9 c5 G
return result;
3 t: p* u) @7 s( o}2 y# b( W# `. e1 k& y( F
// 由代码表还原为波兰表达式6 F5 a& f" y Y
void Restore(int *Formula,int *NumSym,int *temp,int count)$ Y4 g. c5 T. z) }
{7 c4 T; `- Q1 h( |& Y6 t& L
int i;
1 X* S0 X: ^6 h$ x0 J for(i=0;i = NumSym[temp];
5 f( w2 p2 _2 _& _$ Z9 M2 ]# d# X}
+ G H! v6 D( F K// 判断是否符合波兰表达式
% a( X" p- K# m9 m// 符合的条件是每个运算符号前必须是操作数个数多了运算符个数
1 r% T$ r3 v/ g' o1 U// 且运算符个数为总数减一的一半3 L( c- P& ^5 Q m" t: r6 b( [
int IsOK(int *Formula,int count)5 l, w+ Q6 ~0 i5 R
{
% Z8 v5 o' l. v. n9 N int i,j;
; s6 c& w5 v+ o5 p! q! ^& D/ K for(i=0,j=1;i$ \- t' m# `7 M( w
if(Formula<0)! Z! q C$ U" n
if(UpZero(Formula,i)>j) j++;! r) z) ~' w$ g; Q( L
else break;7 Q1 S$ {' Y0 M5 f, F0 g
if(iint)count/2+1) return 0;
, A' A, d n. f7 Q: w else return 1;7 L: W" c- l' y3 l
}
' M3 ~' f7 L. M// 查找数组大于0的个数; J5 z3 f% Y% r* q
int UpZero(int *nArray,int n)
2 X) A' t {% E( X. s! K. r# U{, }# D" B3 x) R! s z
int i,result=0;
% t6 a4 Y3 {% G* c, M for(i=0;iif(nArray>=0) result++;# k/ d; z ^% W) ]
return result;
7 C! B$ L6 B! g0 ], J}
2 Z: p% L/ B. I. V// 查找数组中，小于Num的数是否有重复6 ~' [/ ]" F3 t1 B) T6 _ C
int IsDownNumSame(int *temp,int count,int num)
2 g$ k' L8 v% g{4 Y: f, p2 S( E. @2 V# q
int i;
2 I7 i1 f% g4 P& S9 a" v for(i=0;i* O+ {) Q J7 }
{9 ?3 T& `2 {! C
if(temp < num)
- L0 T) O O8 c1 k1 G if(FindInt(temp,temp,i) != 0) return 1;
* N4 h3 t$ @ Z" S }
n: K$ g/ P; H. n return 0;) Q6 y: F+ J! M6 w" \
}
- x: ~7 K& E$ H- _, W8 ^// 查找数所在数组的位置，返回0为未找到1 m8 \- B5 R( F- g
int FindInt(int *nArray,int n,int len)
% Y f/ ]1 d5 @% F+ }) n{
/ [' W+ i, H9 f& {7 s/ s: n int i;
+ r) g i W/ X! R6 x7 u+ L) ~ for(i=0;nArray != n && i6 ?& z# C2 V+ f6 g7 A/ h6 C0 ^, q
if(i>=len) i=0;' w g( d) m5 l% Y8 r; G0 C( x
else i++;
2 [/ n, B/ E* Q" n return i;
9 \& g( o0 s# Y! O}* E$ R$ @. |1 {% n: X3 I; m5 ?" T
" F3 a4 r6 O$ L4 @+ K
// 计算算式结果
$ O+ L9 a( q6 \- zfloat GetFormulaVal(int *Formula,int count)
7 F" K: w$ b! \4 B{
- t9 Z3 w" L9 a# ^" C/ w float result;
6 ]; [) G: j( j8 s3 c b- D! k BinTree *head = (BinTree*)malloc(sizeof(BinTree)); //二叉树头节点 | \+ ^- I8 ]& N( H
int *nArray = (int*)calloc(count+1,sizeof(int)); //波兰表达式储存数组，首位表示数组有效长度
% l0 k. p/ ]" \- x6 \1 f: J6 S7 Y0 T |2 u
int i;+ d4 G' Y* h- }" ]9 b+ |$ `% |* R% \
for(i=1;i<=count;i++) nArray = Formula[i-1]; //复制波兰表达式. y& y0 f& ?0 m4 ^' V
nArray[0] = count;0 i5 ~8 g5 P# X' W y0 l
CreatBinTree(head,nArray); //建立二叉树" n% k. m) U' D' M/ K
N& c1 D0 v9 a
result = CalcBinTree(head); //计算二叉树算式
* C# c4 I/ Y# p' S; z AfterBinTree(head,&FreeBinTree); //释放二叉树空间' w6 F# F( o. U
" Q' j; @8 h" |) w. {/ F# q' f free(nArray);7 G/ |9 d! A- G6 @9 Q
return result;
1 y; b6 [" ^& h3 M/ \# d}
' n1 `" o3 K2 n# W+ q8 l; mfloat CalcBinTree(BinTree *Tree)
. A) N0 X+ [0 W, g, M, X# @{& e. W/ G4 T+ ?" M7 D: H- }. t) Q
$ ?8 p7 o: ?1 R; K; h
AfterBinTree(Tree,&AfterNode);
( q; V$ @. k4 Z9 k3 r return Tree->Data;
) ^) D$ ]2 J! h- H( D3 l1 g}) U1 A4 H* N: G( ]0 ]# A2 P
' a3 q \5 e, m6 F" ]' E, \// 后序遍历二叉树进行计算,但会破坏二叉树本身5 A8 ^ U$ B2 @
// 一个结点的结果为左子树 （运算符） 右子树
$ a7 v7 q$ q$ q! Rvoid AfterNode(BinTree *Tree)
3 x- d$ D R4 B2 N% l{
( k# F: A, H$ @4 E) s' [* o switch((int)Tree->Data)
. @7 q0 x4 {& x! ]) Q2 x {2 g9 @$ s+ f4 f) Y! W! \6 ^5 T5 ]
case -1:
! z" r6 u$ u8 r Tree->Data = Tree->Lchild->Data + Tree->Rchild->Data;
( h% ~8 b7 {2 a3 V break;
8 q9 z' I2 l* {4 @6 [& a3 U case -2:
7 _4 ~ i9 e5 ]! M/ a _7 ? Tree->Data = Tree->Lchild->Data - Tree->Rchild->Data;
( _- a+ b0 d8 l2 ?7 B- ? break;
: M: S: M" Y" a. @* k& y case -3:
+ E- X! i; m4 |4 @7 D' g Tree->Data = Tree->Lchild->Data * Tree->Rchild->Data;
+ A F0 I* D: Z- j9 t, Q8 e break;
2 d2 j5 I h# F' d) P, b- B case -4:: F. o: n& H+ c; v
Tree->Data = Tree->Lchild->Data / Tree->Rchild->Data;" k. H1 w! R; ~! y) p% o
break;9 L& V2 ^8 p% i2 j) @0 m5 c
}: v) N$ {; v& s) u7 g- ]3 u
}
# Y" N% X$ o& q3 h// 打印算式7 p9 A8 C* E x; P: p
. T4 i# k) X V, O
void ShowFormula(int *Formula,int count)
! i) U1 A% v! O; P- j{
* o, D! ~4 S& n( u BinTree *head = (BinTree*)malloc(sizeof(BinTree)); //二叉树头节点
6 ~ g4 g }' G; z Y& T6 g' O0 i int *nArray = (int*)calloc(count+1,sizeof(int)); //波兰表达式储存数组，首位表示数组有效长度
" f& Q2 U! W; w3 V [ int i;4 O7 Y% A8 O/ X( K' H
for(i=1;i<=count;i++) nArray = Formula[i-1]; //复制波兰表达式
: G% U. C, _" o8 c# s X b* n; O nArray[0] = count;( q" I7 ~, X$ W7 S7 p
CreatBinTree(head,nArray);
/ G5 ?% @! l: f( d: a AfterBinTree(head,&Myitoa); //初始化二叉树字符窜部分
6 x7 V' U% g I AfterBinTree(head,&GetFormula); //转化为普通表达式
: q1 K( L1 F) H% j printf("%s\n",head->Formula);
1 n- h1 k1 H' n AfterBinTree(head,&FreeBinTree); //释放二叉树空间
% z+ z3 J; J. f" j8 @ free(nArray);, S4 h2 t7 B; j1 S6 b9 A1 A
# {; b+ i; q% i# ]3 q. p( _* t}
! l& c, E& x1 |8 N1 w+ R// 类似计算二叉树4 v% f9 s. v' l4 l; D' @
// 会破坏二叉树本身7 I. S; i) ^8 w6 I3 k
void GetFormula(BinTree *Tree)$ b9 t* ^9 x: N) g
{
' }" K1 b0 y" _% T ?% _ // printf(Tree->Formula);
6 h7 V$ p1 N6 |. X; q9 B if(Tree->Data <0)
+ G- x8 |' i0 C5 j+ L5 l5 z; d {/ ^. V0 z" O8 C3 z
char temp[100];5 x5 K1 M9 e: {1 h4 m( X
if(Tree->Lchild->frist < Tree->frist)
4 c) s/ P: V& G6 K% Q2 m {
/ E" j6 ^8 z; w% V, \ strcpy(temp,Tree->Lchild->Formula);
# Z! C) L' F+ z+ ?' L* u. J1 ` strcpy(Tree->Lchild->Formula,"(");
3 o) o; [/ Q, _: V2 q/ T% [( z5 v strcat(Tree->Lchild->Formula,temp);/ \+ R2 n0 c7 v% {4 R3 O
strcat(Tree->Lchild->Formula,")");9 `% s5 z# j/ Y5 r! L( ?3 K, [" r
}2 G8 b0 ^* q1 q- t# {
if(Tree->Rchild->frist < Tree->frist: i% p& ^, k5 X+ J- f
|| (int)Tree->Data == -2 && Tree->Rchild->frist == 0
! Q4 u1 V) r |) n& \% o; N || (int)Tree->Data == -4 && Tree->Rchild->frist != 2)
4 O$ U- D/ p% A {8 W6 I8 g6 A; A3 u, A
strcpy(temp,Tree->Rchild->Formula);
2 i+ Z- g, Q- d0 _( V strcpy(Tree->Rchild->Formula,"(");
6 M* @7 n. q( M1 y strcat(Tree->Rchild->Formula,temp);! C# c/ e2 V. z" w
strcat(Tree->Rchild->Formula,")");
2 P, h3 K. @9 n } j' ?- q5 Q u
strcpy(temp,Tree->Formula);
5 ?8 m3 ], p4 L/ L+ e strcpy(Tree->Formula,Tree->Lchild->Formula);, N3 x# D) T7 S, }
strcat(Tree->Formula,cSym[-(int)Tree->Data]);
# L7 t6 z/ q! e3 r5 ]; |+ Y: I8 I strcat(Tree->Formula,Tree->Rchild->Formula);
, B' I; g1 `" x8 q. e j: P2 n }
1 m p4 C& ^' b9 B) ]" v- {5 K}" @2 `. N% L6 M5 p: L
// 对二叉树字符串部分赋值# r( B: p! Z# @# \. |, [2 t
void Myitoa(BinTree *Tree)
7 F: | ]/ y# W5 n/ O- K- ?8 P0 H; b{& ~8 D9 `# K/ U& ?
if(Tree->Data>=0)
4 b2 Q P' @6 e9 a( | {' u {
% g$ z! r7 v. p; x4 x& P7 r1 M* @ itoa((int)Tree->Data,Tree->Formula,10);& I: w$ W, m- C
Tree->frist = 2;* t5 L f u4 R0 ~
}0 s+ \. w9 z# Z0 I
else
( B/ Q9 Z6 L) E+ ^ U+ v4 c {8 Z2 Z) z8 U" {6 O8 l
Tree->frist=Tree->Data < -2 ? 1:0;2 W+ D+ L2 b$ C U
strcpy(Tree->Formula, cSym[-(int)Tree->Data]);" f ~6 K, g* r& G
//Tree->Formula[1] = 0;6 }1 P; s( y5 p) _& _. r* s
}
$ x2 \0 w% }0 W1 y7 U}
# `% k2 k1 g3 x, F3 v! L2 S( W//从一个波兰表达式建立一个二叉树链表，需指定一个头节点
# d( g( S* f: m$ Z6 }2 gvoid CreatBinTree(BinTree *Tree,int *nArray)
j. V+ T) a% H- u! M+ T$ s{
p; z6 t/ y6 s# H/ l% } Tree->Data = nArray[nArray[0]--];6 B9 S; O+ D h! t
if(Tree->Data < 0)9 \1 u7 ~4 W, P; }
{5 f9 h1 f3 {4 o- T8 y k) w
Tree->Rchild = (BinTree*)malloc(sizeof(BinTree));
% V3 y, d1 F' O CreatBinTree(Tree->Rchild,nArray);
; f$ [! R; {. S2 @( D Tree->Lchild = (BinTree*)malloc(sizeof(BinTree));/ K4 S0 G# [' G2 |: S/ D% Y2 m
CreatBinTree(Tree->Lchild,nArray);& Q2 ^) f7 `' v1 J$ i9 d: r
}
; M9 x3 A3 u) K else
' r7 _% [' p9 l' t {* H7 z- h# Y9 k8 N
Tree->Lchild = 0;% n+ I/ V& D5 L& b \& ] @% O4 g
Tree->Rchild = 0;( I3 T, v9 w+ t5 P
}
' J) B: R" {: l U ]- K
+ q1 B( x- E( m% W C8 N9 R}
) E; M5 V0 y7 ~% n; Y0 L
2 B# k. H2 i% R! Q) Z7 Z9 N! _// 释放二叉树空间
/ h* p+ x1 S6 }+ [" _void FreeBinTree(BinTree *Tree)
6 P4 n2 ? t( A8 o( s: g1 T; l) V' H{
! G2 W1 d# k0 d- `1 f- `1 Y free(Tree);
8 d( e: k" ?" D I: M}
4 q% \$ P1 ]/ s c// 后序遍历二叉树
`/ K7 |: l D4 W! P// 方便其他函数调用，func为要对各个结点进行操作的函数指针
' M: B/ q# A& Q: d6 d$ g+ fvoid AfterBinTree(BinTree *Tree,void func(BinTree*))
3 A# x {8 z1 T$ l6 R8 i* s{; R) n* {& g, h1 _
if(Tree)
. B2 W' G, J1 H% b, n {/ D g+ I/ E" s( q* u
AfterBinTree(Tree->Lchild,func);. O H% i! @; g: y! x
AfterBinTree(Tree->Rchild,func);
& O- L+ l( U) N8 s1 ^ func(Tree);
# I; ?- k# C: O' S: ^5 Q) _, ~1 \ }6 o8 A& A& X, c2 K* L
}2 A$ Y$ _" P. ^" J% ]
|
|
楼主: 考拉
/1 
IP卡
狗仔卡
发表于 2004-5-2 15:40:00
显身卡
发表于 2004-5-2 15:50:00
