|
|
几天前的东西，现在没有大兴趣了
|
过重复代码过多,比如二叉树的建立等等! U3 o5 m8 U: E/ n9 G% ?
- k9 N# d* I1 i: Q& |3 E#include ; A' z7 W) o* g) F% M" N1 y
#include 7 _& `, L6 U) F& Q9 Y% }( c
, s. D5 z" A; h$ u' }typedef struct node
* _" B9 n& q, \' R' ~{
6 U. p. s* f' e2 \+ f# X; c) M5 I float Data;
* n; A/ Q7 r( K$ B. r7 K char Formula[100];
, m1 Z) D, \9 c9 Y4 I9 X int frist; //优先级
: [8 G* a: ~) c& a7 F struct node *Lchild;) Z4 k0 D8 Q$ n
struct node *Rchild;
/ d/ A; `" {# u. N' H0 `} BinTree;
2 w# @& P* _; Jvoid CreatBinTree(BinTree *Tree,int *nArray);) e5 |" N5 K( k7 ~9 [
void FreeBinTree(BinTree *Tree);( }6 t- ]4 \# k$ m: l8 @+ L6 W. y$ G
void AfterBinTree(BinTree *Tree,void func(BinTree*));
$ Z! W, P" L7 S7 |" afloat CalcBinTree(BinTree *Tree);
: p$ F" w) j% ?float GetFormulaVal(int *Formula,int count);
v# e- M- u) c& \) K' l* h2 S* f! Avoid ShowFormula(int *Formula,int count);
) o) s1 K1 p4 S" M( J: pvoid AfterNode(BinTree *Tree);
% t" k5 v" g3 \; ]void GetFormula(BinTree *Tree);8 H- V' E# {$ Q. L& f2 L
void Myitoa(BinTree *Tree);
+ d* h7 h$ Z7 j- |, \int EnumFormula(int *FormulaNum,int num,int sum);: W' D( R/ }" f$ n
void Restore(int *Formula,int *NumSym,int *temp,int count);' S2 [+ _3 d: t4 a
int IsOK(int *Formula,int count);, z% `7 X! P! z
int FindInt(int *nArray,int n,int len);8 `+ v$ Z; z5 w$ L8 c% W
int UpZero(int *nArray,int n);
; U' [2 v9 ?1 ?* K8 fint IsDownNumSame(int *temp,int count,int num);
4 c+ O7 J. f) o2 P5 R" k, c6 P$ I, z- G* ^
const char cSym[5][2] = {"","+","-","*","/"};9 t5 e; v+ [8 D) l# Z% S
; A- A% D5 I- r
int main(int argc, char *argv[])$ T+ b O1 N4 R$ t6 U# w" H
{/ M2 ]* y* U+ O9 S$ i
int i,n,*Array;
3 r# V% u# N" C. H! d5 e 3 N0 O3 I) y6 B' j) f* ^2 Q4 R
//printf("几个数？");
( _" G% [/ b [ //scanf("%d",&n);
6 o! t% c7 q$ k& O, g4 E n =4;
7 a0 ~* \6 n2 S6 H" h# S Array = (int*)calloc(n,sizeof(int));# Q3 [& ]0 O1 U# n1 {% S
printf("请输入%d个数（用回车或者空格分开）：",n);! G+ S- e$ H8 u t/ h# P e6 U% h
for(i=0;i+ l3 [' {) ^/ Q- R0 l# @9 @6 Y4 f
scanf("%d",&Array);
, W" Q0 V( J& k1 G printf("总计%d个式子\n",EnumFormula(Array,n,24));8 R9 v! B3 X, S H- `
free(Array);
' b# G4 w' q5 f
p1 C N' r2 G" @2 q system("PAUSE");4 E' {$ G9 l' Q; ~1 c$ r
return 0;9 o! g0 J' \2 Z0 `
}6 K% v2 @" D. B( x8 `( c' d
4 p& [5 U* U0 x1 o' v/ R, Kint EnumFormula(int *FormulaNum,int num,int sum)7 R* T- `$ ~8 }3 A7 s. W6 s
{7 V# [, z1 ~5 s) o6 p
int result = 0;$ e* h, i k. T( ?
int *NumSym = (int*)calloc(num+4,sizeof(int)); //操作数运算符组成的可枚举组
/ r5 r) E) u$ S) Q" k, B! D int *Formula = (int*)calloc(num*2-1,sizeof(int)); //波兰表达式储存空间4 t* |! i: @6 S! K, F
int *temp = (int*)calloc(num*2,sizeof(int)); //波兰表达式的代号表示空间
% u. [+ S9 _1 ^* s int i,j;6 c( ~: }- F# \# S- `
for(i=0;i = FormulaNum; //载入进行穷举的操作数1 c6 R. k/ H! J+ \
for(j=0;j<5;j++) NumSym[i+j] = -j-1; //载入进行穷举的运算符号1 \% _0 j3 d H: }( ], e i. a
2 z6 v! ~; W3 d
for(i=0;i = 0;. {8 z. Y9 }* B+ Y$ o W
// 穷举开始，结束的标志为波兰表达式代号空间最后一位已进位，即前面各位已穷举完成* C6 H( P7 d' V8 U# Y9 E
while(temp[num*2-1] == 0)5 W& d; e0 ]& ?6 d6 u
{2 p4 Z! e; u$ h" f. U t% u, d
if(!IsDownNumSame(temp,num*2-1,num)). w8 b3 j. I$ u. i3 v% m$ r
{
9 o0 d9 s& v" _, z3 P& F Restore(Formula,NumSym,temp,num*2-1); //还原波兰表达式
% D" c3 A6 m D3 A& w if(IsOK(Formula,num*2-1))4 _! L/ W7 F: x9 H) f. i* h
{ Q1 h1 Q4 S3 B
float t; //结果偏差
$ ?/ T& I) g3 Q t= GetFormulaVal(Formula,num*2-1) -sum;
+ H% A O5 ^8 V3 M: O8 B0 E if(t>-0.01 && t <0.01) //结果为浮点数，只能进行近似比较 T5 Q1 c3 [, p4 M. b
{
. a( S( D) i T9 ~/ h result++;4 P1 Y& |0 R) m4 K7 E
ShowFormula(Formula,num*2-1);
$ Q# f0 m1 A X4 {: s0 u }
- X! B0 t1 d { }9 I" c/ D5 l* b. E0 U! c& B7 @: Q
}& e) X, p7 x9 V" H
temp[0]++; //穷举动力9 B9 `5 b* E6 ?! }
for(i=0;temp > num+3 && i//代码空间类进位
: [8 ~9 r* P0 e, d4 o; f/ V {7 d o# g4 [9 f$ C
temp =0;
! o, ~# V4 x9 [4 q: G temp[i+1]++;
! D- [# } G" J: B* ^ }! ^) j# h) ~7 o7 s1 Z. y; S0 p
}
4 l: I! k- s1 H( D+ @7 D1 l // 释放内存! O+ f) U% a, ?/ H& Q
free(temp);
" Z* z0 L* _+ o( p7 a/ B: B* a2 O$ b* L5 O+ _4 e
//free(Formula); //？？此处不知为什么会出现错误
: v& [( l- Z. j$ f, U free(NumSym);6 x6 d# p' ?" X- V- l# \7 ?4 A4 ] N+ d
return result;
+ M5 T- c1 y4 U0 y0 M}2 `* r0 p3 w+ c. ^$ B/ R& w4 O
// 由代码表还原为波兰表达式$ X4 i! I: e8 a b) z8 H7 B6 p
void Restore(int *Formula,int *NumSym,int *temp,int count)
4 ?& h3 G% `4 K; [{; C7 O6 {' f/ A
int i;
0 g. ^- e* o p1 [ for(i=0;i = NumSym[temp];8 p2 P5 N% ?+ y2 c
}
) P5 X+ P( x" s2 J+ ]& [- d// 判断是否符合波兰表达式7 _9 @+ i" q1 }6 m$ q C4 T" Y
// 符合的条件是每个运算符号前必须是操作数个数多了运算符个数
0 W3 _! q+ f c// 且运算符个数为总数减一的一半. p) Z4 g7 v# T7 u
int IsOK(int *Formula,int count)7 ]( I7 M: a# c+ W4 y2 n) ]
{. u. z5 `% C9 `: }" E2 Q
int i,j;
, s$ ^1 G0 L, v for(i=0,j=1;i& }& V+ e# w. Z if(Formula<0)
3 D& ~- ]' w7 r: ]- Q/ }& I6 v9 k if(UpZero(Formula,i)>j) j++;& j* Q8 m# s- N" |5 h$ j3 E6 ^9 p# z
else break;
9 y( g+ M/ U1 k( _- C if(iint)count/2+1) return 0;2 z1 n5 K" P* S- L+ D9 a3 [* l3 d% F
else return 1;$ d) _9 n5 `- i( v% a* }* F* X& V
}
, _. d2 }& Y2 |7 P9 x// 查找数组大于0的个数
6 s+ s8 ^( |/ ~& [7 W% gint UpZero(int *nArray,int n)1 y4 p( t U% X2 w8 H s
{& |+ ~1 y! F; Z
int i,result=0;
4 k. e+ C& @1 ~4 A* q7 Z for(i=0;iif(nArray>=0) result++; y3 t- h, J- d% u6 a! @3 z* M& i# g
return result;
- c1 I: H1 ?( `, w2 s5 v3 k( D% j}
- @$ w# i z7 K6 @& Z// 查找数组中，小于Num的数是否有重复9 n1 }1 R$ F0 y8 f) E- ]. J E3 e
int IsDownNumSame(int *temp,int count,int num)2 d+ M8 @+ @. w* J
{
6 b7 \2 p# E, y* ]* U int i;
! \/ Y1 g/ p- n for(i=0;i. T6 C+ S/ T. B P& S2 C {& D: j) W- G. c% m* |! K1 Y( ~; `. G, f% i
if(temp < num)
* X4 Z- t$ s/ r2 W5 z" @# u M if(FindInt(temp,temp,i) != 0) return 1;
5 d+ {5 b* z) k8 O5 F; z }% B0 \) V8 |0 t i# @% b7 w; R
return 0;
& `, d! g+ z4 E" J. a}
4 a% n4 K5 d4 [* Y8 b// 查找数所在数组的位置，返回0为未找到
) _6 C8 U$ N5 s" e" _- ?int FindInt(int *nArray,int n,int len)$ S* I- [4 \( }3 D6 x
{
! U Z( V/ ~/ r8 B7 O3 V z int i;
8 z, N# f% O* s/ D1 i: X | for(i=0;nArray != n && i' b: b W* B) |! m" z8 v" {
if(i>=len) i=0;
' q" o" ^- e3 x- h" Y0 P else i++;
+ O+ T& n) F) Z; a( V: g0 R" B/ { return i;, z3 T0 O" v, v) ^1 u$ B5 K/ D3 z
}/ A% \4 e# R$ f
9 V2 s) r8 N+ U* f, d+ x// 计算算式结果5 |) B! q- ?+ q' U# D3 h+ I* Y& m
float GetFormulaVal(int *Formula,int count)! M. v9 k' E% \9 o
{
( g9 g# t; Z8 \$ M; ~ float result;
0 N' N6 `/ U0 y1 h- t+ W8 r BinTree *head = (BinTree*)malloc(sizeof(BinTree)); //二叉树头节点6 @, z+ o3 m9 ^
int *nArray = (int*)calloc(count+1,sizeof(int)); //波兰表达式储存数组，首位表示数组有效长度; |: h% w2 u! I' H( Q9 i: S
4 T' L; w0 h1 Y, S" k" k int i;% p& I$ H2 O# B1 g0 R% Y
for(i=1;i<=count;i++) nArray = Formula[i-1]; //复制波兰表达式3 m3 v% r4 N S `9 }
nArray[0] = count;
6 u' t7 _8 z w! N- K# m; \ CreatBinTree(head,nArray); //建立二叉树# Z% J# |- ~2 z8 ]7 h/ p
( _" U0 l7 \/ W: F8 ?
result = CalcBinTree(head); //计算二叉树算式
8 _* N- _0 J d. @! a3 O, u, V AfterBinTree(head,&FreeBinTree); //释放二叉树空间2 U4 u; Q2 p& y2 |$ w# y( j8 [& z2 _
. y+ }5 O# H q3 m' `+ q free(nArray);+ K9 Q% d- M1 _, M: k8 k
return result;+ ^) o+ F! f: M$ m0 Y9 Z
}
& U$ ^/ K6 ^& rfloat CalcBinTree(BinTree *Tree)8 a! N- K7 {5 M8 Y
{
5 g( p8 Z e5 c: [, D+ e / U; q. q; c, h) d7 N7 F$ I
AfterBinTree(Tree,&AfterNode);& T! N2 I/ ?1 F
return Tree->Data;
- I* d0 U! s# s$ c e}0 B6 A2 |5 J9 W* ] K: h
% k3 E4 v: {: B2 J h; q
// 后序遍历二叉树进行计算,但会破坏二叉树本身
& L1 }0 N0 v8 Y$ }, i6 _// 一个结点的结果为左子树 （运算符） 右子树
! W" S; l p0 t9 G+ m& B4 H3 ?) a! `void AfterNode(BinTree *Tree)
6 b9 g& `& {8 E7 \! h{
+ x+ @# m& P1 ^2 l8 P switch((int)Tree->Data)
% k$ E/ p) Z3 s* u4 k9 [' j {/ F) @' r/ m2 W1 E% c
case -1:% c5 H" q o2 W1 p7 g2 P
Tree->Data = Tree->Lchild->Data + Tree->Rchild->Data;
1 V% n$ a( | d0 T7 A; h break;
' h; Q3 z; ]6 ], \4 ? case -2:
3 Z& y# Z) H1 I! _% ]4 D+ F0 m Tree->Data = Tree->Lchild->Data - Tree->Rchild->Data;
0 v/ m" B5 b! Q4 ~ break;
8 B1 v5 r3 R5 E* _1 Z, F case -3: V) C1 o0 t, e0 a4 P
Tree->Data = Tree->Lchild->Data * Tree->Rchild->Data;
2 }! ^) W: ~# h0 F1 m break;$ a/ }$ E. r; f: Q$ V6 h1 T* \
case -4:; M4 D {1 p; Z6 M
Tree->Data = Tree->Lchild->Data / Tree->Rchild->Data;! z, ^: v1 Q$ v! `7 A2 ? S# a% z
break;' |, e8 L- o- m
}' C" y0 x- z0 v9 g7 V; M
}2 Y @- c& |' k
// 打印算式
; n" L1 R& I \7 U; V: H7 T" Y# X3 H. r6 u. [5 w
void ShowFormula(int *Formula,int count) B$ I0 P8 _5 u8 |
{
X% l3 ]# H) w- Q5 j BinTree *head = (BinTree*)malloc(sizeof(BinTree)); //二叉树头节点/ C% \- U1 `) Q! ~
int *nArray = (int*)calloc(count+1,sizeof(int)); //波兰表达式储存数组，首位表示数组有效长度
. q+ M2 v$ ]9 Q0 c int i;
+ ?, h3 t: d; l, @ for(i=1;i<=count;i++) nArray = Formula[i-1]; //复制波兰表达式
9 U3 ~( \) ^ x( H% o nArray[0] = count;0 v/ X E9 c! r" ?& j' C
CreatBinTree(head,nArray);
# ?: s1 j* [& @: G5 x0 ~* Z5 o% Q AfterBinTree(head,&Myitoa); //初始化二叉树字符窜部分1 X1 r" C* j8 t3 x$ i$ d5 @# B
AfterBinTree(head,&GetFormula); //转化为普通表达式
) w0 O7 F' _0 x1 G7 P printf("%s\n",head->Formula);. T/ H* g9 W+ e& W# [) x7 u' O9 F" I
AfterBinTree(head,&FreeBinTree); //释放二叉树空间. E2 v& z7 s3 c6 I9 m6 o7 D
free(nArray);
4 n' l" U3 z9 [5 E1 q 0 v" c8 M2 W6 H) l& _1 ^# ]
}% Y: g# T% b$ C ]# \
// 类似计算二叉树 n, o% U1 z! S& U" ]; \
// 会破坏二叉树本身
( O: f0 r0 U' P2 |9 rvoid GetFormula(BinTree *Tree)
7 y7 N' |- u! c- F{
" m/ ^6 P# e3 u" a% P" h) v. f // printf(Tree->Formula);
t5 r3 R. U% }8 `3 S if(Tree->Data <0); o5 O2 L: o( J2 F- U" r- O
{
5 c* x9 d' E3 Q( \0 S$ o+ M) h char temp[100];, @* n4 C, w- |& y, D6 u
if(Tree->Lchild->frist < Tree->frist)( d% q- _) ]3 w$ i# p8 A- v
{
/ ^) Q0 _ [3 L6 Z% J3 j9 u strcpy(temp,Tree->Lchild->Formula);
: Z) R$ I& B: F0 X1 [ strcpy(Tree->Lchild->Formula,"(");7 N$ k }) n4 B+ m% Y. E
strcat(Tree->Lchild->Formula,temp);0 @! x( I! S- |( w4 Y# y7 C
strcat(Tree->Lchild->Formula,")");
- n+ g9 G7 }9 X& ]* _ }
H- ?. x; q' W, ^5 |5 _ if(Tree->Rchild->frist < Tree->frist# c# ^& F4 B* m5 P) s& L
|| (int)Tree->Data == -2 && Tree->Rchild->frist == 0
9 m: b& ^; W0 y9 W H3 o: o8 @' S || (int)Tree->Data == -4 && Tree->Rchild->frist != 2)
9 {+ E0 \$ B* r. A" i {
0 W' U N. |% x5 }4 k strcpy(temp,Tree->Rchild->Formula);# N) y* n0 ~" ?& N& E& m' o
strcpy(Tree->Rchild->Formula,"(");( Z6 C& s& X; W, t( N$ B& o$ ^# I
strcat(Tree->Rchild->Formula,temp);4 T$ F7 T# }3 E) L$ H( _
strcat(Tree->Rchild->Formula,")");
' l* g4 J r: S. }' \7 I }
8 p, N, d F, {2 F strcpy(temp,Tree->Formula);
1 U1 I9 U/ ]$ [$ F strcpy(Tree->Formula,Tree->Lchild->Formula);
# l* F' u6 \# M4 A. s1 _2 F strcat(Tree->Formula,cSym[-(int)Tree->Data]);2 f! f5 c7 E$ P- D0 E
strcat(Tree->Formula,Tree->Rchild->Formula);
8 n* _0 `2 p% t4 D7 O6 d }7 _! r/ |8 s/ g3 B! D2 c
}
& e+ z6 _/ f1 a9 ?5 _// 对二叉树字符串部分赋值/ Z; |7 _ F% b; @% N" {8 L$ b$ j
void Myitoa(BinTree *Tree)
9 L( b! M) k! r1 S- c0 Y{ S: i! |1 \% t; ?2 o4 O
if(Tree->Data>=0)! z5 n! \$ X& [, B2 j+ b
{
5 G5 g i% k$ `% A itoa((int)Tree->Data,Tree->Formula,10);: s$ \5 H# f$ Q( h6 N; t
Tree->frist = 2;
1 n. f7 T" y0 E/ i2 C) y }4 x+ h8 i- M( Y
else0 G0 b' V1 h+ y9 N
{
+ E, i7 U- \$ X* o2 Z( X: ?/ T. V Tree->frist=Tree->Data < -2 ? 1:0;
2 Y' @" l) I/ N; R. G! V8 S strcpy(Tree->Formula, cSym[-(int)Tree->Data]);% g6 {+ q7 u' L0 [$ b- [# y
//Tree->Formula[1] = 0;( B" X$ V* {) M: _' l, @1 h/ h6 H
}: W6 t. V; [* d4 U3 v# `1 v) D
}# ?' ~6 p. {) b+ N, e3 y5 m/ s% H
//从一个波兰表达式建立一个二叉树链表，需指定一个头节点9 A1 J7 ^' D$ O+ H- W5 d
void CreatBinTree(BinTree *Tree,int *nArray)
T9 h: X* ?, @; f* F5 T0 f{4 B; R( k7 h3 M2 m0 B; F) b' L
Tree->Data = nArray[nArray[0]--]; n. V# s2 v; t2 S6 v- B# j2 N
if(Tree->Data < 0)6 q! i9 g l6 p6 L9 L
{+ D% `! ?+ y5 a& g3 f
Tree->Rchild = (BinTree*)malloc(sizeof(BinTree));
8 t, j k$ h# P2 A- j CreatBinTree(Tree->Rchild,nArray);# ]' k# Z; d L) }
Tree->Lchild = (BinTree*)malloc(sizeof(BinTree));
' i8 d9 D/ r8 U! G! L% C0 E3 A% K CreatBinTree(Tree->Lchild,nArray);
9 r; p% ]$ D5 g }: n3 ]7 N2 D& b4 e! _% \6 `
else4 l2 h8 M1 K9 F: e" R. h1 d j
{% e2 b2 y g& {4 U% m" e
Tree->Lchild = 0;: w0 {! [, l1 y5 b( `5 I. e4 r
Tree->Rchild = 0;* T( i2 N+ {/ r# W D+ D, M
}
, V9 X2 o6 g' u$ S) s
" Z& M; s. P6 ^9 t8 }}
5 j) t; N7 N7 X% n5 o5 N t) A, \$ F+ X1 l$ I+ L
// 释放二叉树空间9 P8 Y! F# _6 {% L ?* a' U- h
void FreeBinTree(BinTree *Tree)
9 R- i9 |! j O8 A& ^6 P! j1 ^{
8 D- x7 ?: ^/ K# f [* B free(Tree);
0 q% a& T. `& Q5 M! A}9 i7 m; X2 K% E( i9 H1 o) b
// 后序遍历二叉树! G$ k+ v F+ _ y3 W$ X
// 方便其他函数调用，func为要对各个结点进行操作的函数指针
0 x/ `3 ?6 \, Q9 H& J1 d6 |void AfterBinTree(BinTree *Tree,void func(BinTree*))
+ S$ a) I' J7 {7 I{: @6 a) B8 C# ]+ I% `
if(Tree)
- _5 l0 K7 z4 k$ L {
& A5 B7 X$ ?2 k: | Z: ] AfterBinTree(Tree->Lchild,func);
$ e% G% i/ B) M9 Y& o9 s AfterBinTree(Tree->Rchild,func);3 v8 j8 c1 X5 |7 |! h+ @
func(Tree);
" v" b9 @8 U2 o" _ }! S! S0 J! N* D$ f: k' N
}
0 z$ \7 ]6 B: j. _" W! \ |
|
楼主: 考拉
/1 
IP卡
狗仔卡
发表于 2004-5-2 15:40:00
显身卡
发表于 2004-5-2 15:50:00
, Y5 X; H5 t7 Y" a, d' w5 W