|
|
几天前的东西，现在没有大兴趣了
|
过重复代码过多,比如二叉树的建立等等
) z0 \1 @4 }# Y4 @0 [2 A: ~" s$ S ?9 ]2 W: `6 ~1 ~
#include
C7 W& K4 J7 G' |#include
- Y; Y1 X4 X; |5 A% n: q7 a+ q
+ k( {& e* _7 ?& |3 A1 Ftypedef struct node2 n# Z5 p& A m5 X& u
{# |2 O" F4 W+ Y
float Data;
) B/ l. o2 z, o) e7 H& f) w. y9 X/ D# ~ char Formula[100];
. l* k Q% n7 g$ b& ~* U int frist; //优先级
4 u2 B# \" \, C. [0 V- x struct node *Lchild;4 [# J' s- q/ Y! a
struct node *Rchild;' c6 [) h6 a2 y) a" v0 k, ]6 X$ n& K
} BinTree;5 |8 z' A& J: o" a) y- q
void CreatBinTree(BinTree *Tree,int *nArray);
5 S. {2 R2 |) z! Y6 [! Lvoid FreeBinTree(BinTree *Tree);$ b- c0 \' e B7 U$ h
void AfterBinTree(BinTree *Tree,void func(BinTree*));) J2 z1 o6 q% F" m" O
float CalcBinTree(BinTree *Tree);
2 Q6 S/ p" ~5 w' _float GetFormulaVal(int *Formula,int count);1 n8 F+ t2 f: W2 ]. s
void ShowFormula(int *Formula,int count);- D% A4 o( L! w5 _* h
void AfterNode(BinTree *Tree);
+ k8 ?6 O% C; q; A% Z4 m. U7 [void GetFormula(BinTree *Tree);3 x' V+ m4 M, ]" f& v7 G* V! R
void Myitoa(BinTree *Tree);6 F+ C+ H- k0 {. o& L4 w
int EnumFormula(int *FormulaNum,int num,int sum);) Q ?/ {7 V; j b) ? B
void Restore(int *Formula,int *NumSym,int *temp,int count);9 {, @; B/ o: N3 U
int IsOK(int *Formula,int count);9 Q% ~( Z/ k8 ?% q g
int FindInt(int *nArray,int n,int len);" _0 Z) b& C: D$ p
int UpZero(int *nArray,int n);
" k# Q6 ^/ ?& V8 b& V" E7 }int IsDownNumSame(int *temp,int count,int num);
6 J0 f r1 q" R' N [
. Z7 P- Y3 s. P" q; ]3 iconst char cSym[5][2] = {"","+","-","*","/"};& @4 \* k/ R, T! P
' E- M# _3 ~% P% ?2 G
int main(int argc, char *argv[])" O, F f) F9 J* k! P% V8 Q+ @+ |
{
8 n( G( k* X: i/ y; ` int i,n,*Array;3 l2 h- R3 n2 q% t
# u/ x) ^- Y; Q3 l5 |/ n0 |
//printf("几个数？");
3 x6 I% f; |8 {6 b5 ~ //scanf("%d",&n);; U1 ?/ U" q* g/ l; u% V
n =4;
/ J, F U7 X0 B* ?/ S$ t0 r. j# Y Array = (int*)calloc(n,sizeof(int));3 [: A- T" n5 `4 ^6 Y" U% k* D
printf("请输入%d个数（用回车或者空格分开）：",n);
/ `# |0 K% v' F) o for(i=0;i$ {% j7 n0 G3 d3 }7 P scanf("%d",&Array);
0 B8 N7 d8 ~' y printf("总计%d个式子\n",EnumFormula(Array,n,24));& W: P, i& z M# x8 U# ~
free(Array);5 J: P2 l6 o9 V, M0 Z( a
. q0 T% }6 a9 M# f# ~# t+ a
system("PAUSE");
7 j$ w1 b* W) i5 m9 l! @% b return 0;7 Y& v4 ]8 ?4 }! A B* f
}' g3 o: X; J+ D5 i2 s
2 `2 W9 Q, D" u9 p1 U5 ^
int EnumFormula(int *FormulaNum,int num,int sum)' J# _6 P% e" Q, d1 T4 n
{
/ i5 E9 t# A3 D. E* Z5 [ int result = 0;
: f6 Z. V* B4 Q! Y0 S! S int *NumSym = (int*)calloc(num+4,sizeof(int)); //操作数运算符组成的可枚举组
. s. Q% ]8 q! M" O0 X int *Formula = (int*)calloc(num*2-1,sizeof(int)); //波兰表达式储存空间
8 u! |1 K' h1 W" p: ]/ F2 i9 O$ S int *temp = (int*)calloc(num*2,sizeof(int)); //波兰表达式的代号表示空间# O4 o" j4 m" T/ L. U1 r- n- A3 Z
int i,j;
( |* ~# Z$ J+ @- R7 I' P! @ m for(i=0;i = FormulaNum; //载入进行穷举的操作数$ U$ @; c$ ~) ^9 r8 f$ \" k
for(j=0;j<5;j++) NumSym[i+j] = -j-1; //载入进行穷举的运算符号% B9 B4 i4 i9 n* z1 u
6 P8 A1 H8 H2 B D( ? V# J) N) `
for(i=0;i = 0;
' l5 W* f# B) a. T // 穷举开始，结束的标志为波兰表达式代号空间最后一位已进位，即前面各位已穷举完成+ m: Y. Q; I3 [* S3 m
while(temp[num*2-1] == 0)- l/ h. k( b# a; ^! {
{* M) m, l" Q& I0 N+ U, J6 A. k
if(!IsDownNumSame(temp,num*2-1,num))
0 G: b7 i4 u G* }% ] {; N2 y( o8 _. s% \8 g E" g
Restore(Formula,NumSym,temp,num*2-1); //还原波兰表达式 h: g. |8 b4 c) G# r
if(IsOK(Formula,num*2-1))/ h" q2 a5 u3 p3 r3 J/ R
{
8 e9 M3 k7 W& t: F float t; //结果偏差! c0 v7 Y% l3 `9 y+ n% h
t= GetFormulaVal(Formula,num*2-1) -sum;; d- [( v+ y7 P" q! r* _6 A
if(t>-0.01 && t <0.01) //结果为浮点数，只能进行近似比较" g. Z" s: ?& l: W m7 h
{: F1 A0 M# ~: O H
result++;2 y" W/ R4 W3 r( k
ShowFormula(Formula,num*2-1);
3 p! M7 E% v5 }" h% P4 F }8 V: ~' i' ~; _6 p1 |
}, _+ h k! t6 \
}6 r* n2 t% l+ B+ C* ~" _1 ^- w
temp[0]++; //穷举动力; Y2 }; T: @: f' P
for(i=0;temp > num+3 && i//代码空间类进位
4 T0 F( N6 {. k: Z9 d {
H9 a- ^6 u* m1 Q8 Q/ ^ temp =0;
. J8 \9 U6 R7 e7 V4 l, q ?, R/ i temp[i+1]++;& X+ L9 A1 g3 f0 E
}
& Z$ e- l2 C6 ?4 L' m, @ }' R( }/ V% v+ E' r$ M' F
// 释放内存6 Z0 t: h1 ]2 l6 O+ ^' R
free(temp);. p w3 g0 d p) \' H3 L6 u6 K# u
" c9 n! c! k8 N9 o4 U //free(Formula); //？？此处不知为什么会出现错误: e9 A" u! \0 S2 t' u! A( t2 b- H
free(NumSym);5 {6 }* y7 Q# |6 L
return result;
" h8 {1 I" Z. |. C7 N1 F}
" J+ u1 t, a$ O; z/ j// 由代码表还原为波兰表达式
' M' s7 h5 ~" }; vvoid Restore(int *Formula,int *NumSym,int *temp,int count)
: D5 Z6 X' B: G1 ]9 s1 Q I{
6 H' ^# p# ?2 W! N int i;8 t# W0 t. q1 V1 ]; ]+ m
for(i=0;i = NumSym[temp];) T- t+ X2 A- _. r% k2 F
}* }7 _3 T, t7 j$ s* ~* |
// 判断是否符合波兰表达式
4 l6 w0 @) B8 e' Z3 S- i( e) N6 p// 符合的条件是每个运算符号前必须是操作数个数多了运算符个数
' U3 I) h. |+ ]7 C, v+ O// 且运算符个数为总数减一的一半1 A, _* C/ `% @- E8 D
int IsOK(int *Formula,int count)
: T. Q1 E* A, N3 @) z; r{
& R, O7 \, @* F int i,j;
2 k$ N' T5 G2 W7 H+ V6 D) }+ C for(i=0,j=1;i' W" @7 }, Y9 d
if(Formula<0)$ Z0 v8 t ` T, c- b: A
if(UpZero(Formula,i)>j) j++;5 B" {( k9 }5 `4 L- J
else break;
% b8 r5 w( o+ ]' ~ ` if(iint)count/2+1) return 0;
' `2 q* H5 z d! q% a% o; @- r# H else return 1;# ?6 }/ l2 N* q0 J1 T L
}5 k# v+ @/ I9 a b% C
// 查找数组大于0的个数' G T4 u# {3 l1 O& S! E
int UpZero(int *nArray,int n)
$ R# N9 O) J k/ C" F- S6 W{
( n6 h8 {9 r$ I) {% Y int i,result=0;
- \ d$ d# u, U. s$ { for(i=0;iif(nArray>=0) result++;
- q! M5 M. G- \* k$ Y return result;
3 V3 l" r' X2 L& R8 h% P}/ V/ [7 q C) x w# D' p6 C3 C$ |5 D
// 查找数组中，小于Num的数是否有重复
! M. ^1 T) s4 s* E3 dint IsDownNumSame(int *temp,int count,int num)
# |3 l" G$ r$ o7 ^1 k( s4 K{
3 @ E8 S, r1 o/ @% z int i;
+ Y0 y: ~8 w& q" T; h) D for(i=0;i/ ^" C+ D( ?5 U" Z1 r {
2 a+ n) m8 f: o0 `& e4 o if(temp < num)6 |" N1 w! C y6 `- g& [
if(FindInt(temp,temp,i) != 0) return 1;
& K* F/ o: X. Y2 [5 H }' u" Q9 Y* e. N7 R3 q9 y
return 0;% r+ X8 G k( P# Y2 `
}7 C; \; q: s; R/ r( C0 A
// 查找数所在数组的位置，返回0为未找到- x& Q7 }! ^& }7 u+ W1 T2 m( O# i
int FindInt(int *nArray,int n,int len)$ D. `/ [- B8 Y' x* y
{; p- Z) p4 f' y7 P) Z
int i;# H/ i2 B1 h- L. U; B
for(i=0;nArray != n && i" P: [$ O& Y* g$ B; {
if(i>=len) i=0;- m7 L1 C, E$ m& n2 Y) a& ~
else i++;
& }) t0 ~) _* ]" S& @# K& i" l return i;
9 C# S0 w2 V4 {, F& I0 G7 p3 N- G}
7 u4 Q0 G( H# M
( |# a" e2 N. C. c; n% Z// 计算算式结果7 r( C( z! g, y0 i
float GetFormulaVal(int *Formula,int count)
3 l% I, s7 k% l6 k8 |{9 `! A/ H$ H9 f4 x1 T
float result;- Z" e( S- } N# j K* Y: `% [0 M
BinTree *head = (BinTree*)malloc(sizeof(BinTree)); //二叉树头节点8 S0 t- f- e. G* @1 ~/ @4 j+ ]
int *nArray = (int*)calloc(count+1,sizeof(int)); //波兰表达式储存数组，首位表示数组有效长度% h1 Y H9 q) T% A O$ l w
- @; q4 ~6 K+ U. x- Z' l
int i;
$ N/ U& v! b7 _5 ?! L$ m/ G0 c for(i=1;i<=count;i++) nArray = Formula[i-1]; //复制波兰表达式( V7 e; e: ?# z2 ?! ^; M4 |
nArray[0] = count;
4 Y. ?' N" H, `8 L, y+ [ _3 o CreatBinTree(head,nArray); //建立二叉树5 x! S/ |- M' I2 S; g6 |$ O
" `. }" b5 A- `3 V( v0 e" z result = CalcBinTree(head); //计算二叉树算式7 X5 S% ]0 C$ b7 y/ f
AfterBinTree(head,&FreeBinTree); //释放二叉树空间+ A! T2 J) x5 v2 v2 \0 V
1 ^- `" j" d% _" ?. @ free(nArray);
+ i/ X& _4 n4 B, J# n, L; u1 x/ L0 T return result;
: y% ~3 E: d9 J/ s( H" H}
& ~" O- E- K+ \6 a/ ]3 R5 d2 [float CalcBinTree(BinTree *Tree)
1 T( Z# l2 U+ h* H6 A{& J% |8 {5 q% P! }$ b. x
3 s: a- Z' n4 Q# H
AfterBinTree(Tree,&AfterNode);
4 j( D9 Y' F C" J return Tree->Data;
~* W& x7 P3 w/ ?1 _+ B% U0 I}
5 V3 }5 u. j& q+ v7 ^0 b' f& g; M) Y) c" t' y
// 后序遍历二叉树进行计算,但会破坏二叉树本身
4 G: b) }7 q4 S( K4 x// 一个结点的结果为左子树 （运算符） 右子树% G! C% I) l# b+ z3 V: k
void AfterNode(BinTree *Tree)% k$ L% l3 e& `0 S2 l
{
; q% |$ y/ F2 y1 Q- h& b switch((int)Tree->Data)
3 c7 a8 @( m- ]1 R {
5 v+ k. b% x- M% X/ M case -1:( n1 t- q0 D+ n. R9 V
Tree->Data = Tree->Lchild->Data + Tree->Rchild->Data;, x6 \ e+ s" C* p" H
break;- ^! j' r5 ?# w* k
case -2:+ S! e3 k% X5 w3 Z0 _) S0 g
Tree->Data = Tree->Lchild->Data - Tree->Rchild->Data;
! _# ^4 Z; B/ l. {& X: S3 B, B- b' ]% E break;' x W C q- `: w) T: X, ?
case -3:
3 F/ |2 _; w" v# d* ]5 E, g Tree->Data = Tree->Lchild->Data * Tree->Rchild->Data;
* G7 [; M- H( A1 b2 X break;- U1 @* `, G6 H* R7 w
case -4:
N4 \% S# i( W3 W0 h& l- O Tree->Data = Tree->Lchild->Data / Tree->Rchild->Data;" P, e, t+ Y! _) _1 n, o/ O
break; m$ e# p7 x! O1 U8 C% K
}
3 \. o: U0 T0 L/ S: I [( s( p}
1 E* {: `8 y ~; k8 C' ~// 打印算式) F& H4 j) ?' \4 {
3 T& b" m8 _" v3 pvoid ShowFormula(int *Formula,int count)6 \. {: i9 L/ }8 @
{. X" @9 g& Z% T/ M( a2 Y
BinTree *head = (BinTree*)malloc(sizeof(BinTree)); //二叉树头节点
) V: D0 n' P* s" R4 D int *nArray = (int*)calloc(count+1,sizeof(int)); //波兰表达式储存数组，首位表示数组有效长度$ j4 N! I; U6 r/ K* e
int i;& U7 k, J, V( U5 p
for(i=1;i<=count;i++) nArray = Formula[i-1]; //复制波兰表达式
1 a) k! O9 z# B6 B. P- o& n" C nArray[0] = count;7 Q; H+ R; v0 r4 {/ h1 n e
CreatBinTree(head,nArray);
9 H. b- P, E/ I8 k AfterBinTree(head,&Myitoa); //初始化二叉树字符窜部分0 ]2 p: S% r- O9 y& z1 q) n
AfterBinTree(head,&GetFormula); //转化为普通表达式
) d; ]9 ^ G! Z% `; F printf("%s\n",head->Formula);
/ e7 q: W2 U: O) u6 y% ^2 I( H3 I4 | AfterBinTree(head,&FreeBinTree); //释放二叉树空间5 A9 `* c: d/ A" o9 {; _
free(nArray);/ z, }" J0 I& S+ Y( M5 Q2 x
: C) S7 l/ G+ ^7 n8 M/ |! j}" U. p4 J- V& E
// 类似计算二叉树5 `: J& d z" g) K- p; N
// 会破坏二叉树本身
$ r0 n3 R, L+ u7 L# ~/ [; h9 O* |void GetFormula(BinTree *Tree)
/ L2 X" u6 d; j" P{ x6 u# g' G' X. }# u! S ?
// printf(Tree->Formula);4 ?( f) V1 a. m, O9 j
if(Tree->Data <0)$ p+ z- [- G! E1 @$ Y+ [5 w
{
7 ~9 i! B7 U/ P char temp[100];0 r! ^5 c4 Q5 X0 t" P: Y% l( a
if(Tree->Lchild->frist < Tree->frist)# C( `, ^/ X* `$ b- {% f
{+ I$ q( |! e6 L% m4 ~6 p# Q
strcpy(temp,Tree->Lchild->Formula);
/ k& G) d3 B5 s0 u strcpy(Tree->Lchild->Formula,"(");5 p- c5 a% n+ u- g0 D W* ~. i
strcat(Tree->Lchild->Formula,temp);
9 O- N, H- J6 w+ f strcat(Tree->Lchild->Formula,")");
9 [' z3 ]+ \/ r9 Q7 g$ w }
9 g3 }2 m' f; W; D$ l if(Tree->Rchild->frist < Tree->frist
6 @: `) {: P9 s! F* P- n( C7 U D || (int)Tree->Data == -2 && Tree->Rchild->frist == 0
5 \7 g# ?' Q. w6 |" ] || (int)Tree->Data == -4 && Tree->Rchild->frist != 2)
" b; a" w' D4 Z5 M& m/ T {, }" }3 |7 L5 k; F( u
strcpy(temp,Tree->Rchild->Formula);
$ T; w' Z9 V+ Y- e; D strcpy(Tree->Rchild->Formula,"(");; o% Z1 Z2 f5 j2 l) \1 i% O8 j
strcat(Tree->Rchild->Formula,temp);
* t& p7 L* ~& D9 x4 u. f1 O9 V strcat(Tree->Rchild->Formula,")");5 C B+ ?+ U1 X" g' ]) f' w
}. [. X1 }# J% q
strcpy(temp,Tree->Formula);, y) m! E: m/ q2 ]* a+ A
strcpy(Tree->Formula,Tree->Lchild->Formula);/ B, k% X& f" q+ ]1 a
strcat(Tree->Formula,cSym[-(int)Tree->Data]);
9 |1 T" |* u7 N9 k! j) x strcat(Tree->Formula,Tree->Rchild->Formula);1 e% A$ Z/ r9 K, q6 b& F
}6 h. J0 v% H- _7 h. f& ~) `
}
) c# b6 q( q* _- r' r& P/ t! c// 对二叉树字符串部分赋值! t4 g, Z6 n3 Y0 X
void Myitoa(BinTree *Tree)
# H# e* t( a+ U- o2 b{
4 f2 |& c; V# T9 D) R# f6 J if(Tree->Data>=0)
' t3 X( P* @9 Y$ g: g' O {
; B7 i& T# D1 w( }* l itoa((int)Tree->Data,Tree->Formula,10);
" b( o; Y- ^4 |7 ?8 @5 j Tree->frist = 2;% c* Q: h: _, }2 L0 K0 Q$ \, Y
}
0 r! Q2 @* Z7 [& g+ t% o4 H else
6 Z' w* U( |4 G3 p {; j& j# H! j' @( X" N4 @: u
Tree->frist=Tree->Data < -2 ? 1:0;
; {1 P: M9 q+ ]- c* K strcpy(Tree->Formula, cSym[-(int)Tree->Data]);( k0 y4 y$ l" G$ H2 `
//Tree->Formula[1] = 0;9 Z- v: {$ c1 h& S$ O+ Z
}! n: b f0 e' q0 o
}
Y6 o2 r7 Z+ g; ?' k1 |//从一个波兰表达式建立一个二叉树链表，需指定一个头节点
% c+ A0 D. F- { _! [9 rvoid CreatBinTree(BinTree *Tree,int *nArray)# Y: s1 O9 i8 b
{+ l6 V% h+ p8 a+ r7 T1 P0 [# E
Tree->Data = nArray[nArray[0]--];6 y% `7 H, i6 h# g
if(Tree->Data < 0); l' ]5 D( d) b9 B" f
{+ D8 g- N: p8 [1 _! G
Tree->Rchild = (BinTree*)malloc(sizeof(BinTree));
* O. _$ u& O) Q0 V0 J CreatBinTree(Tree->Rchild,nArray);% A* n# I c5 G/ w6 Y- P3 {5 E
Tree->Lchild = (BinTree*)malloc(sizeof(BinTree));
) k; E5 A$ q- K! a% l }$ L$ `# w9 _ B CreatBinTree(Tree->Lchild,nArray);
- o" y* X" X- F4 V1 L7 J5 l }5 l5 ~/ d2 l6 \* M3 B4 P
else
g. E) k3 C. L8 J$ j# J: `6 S {
- e, S' v2 Z, f' G9 [ Tree->Lchild = 0;; R/ D5 |! d2 f" ^* R
Tree->Rchild = 0;
4 g; X1 V8 U7 ]( Y }6 t& r. C8 b; v6 F* v
. ^3 c& H* ^6 s& R3 F+ }6 [}' ?# c, \" Y# |5 x7 j
+ Z8 D& j0 R, @% d: I// 释放二叉树空间 Y) D' j) d8 S3 Z" J1 a
void FreeBinTree(BinTree *Tree)
2 G1 k" k. p9 h2 V{5 Q- ]; x& C$ b. `2 P# G
free(Tree);6 q% v; A4 u0 ?2 k/ E2 b6 f3 {
}5 w0 i9 U* ?* j
// 后序遍历二叉树2 M% @! V2 I% [
// 方便其他函数调用，func为要对各个结点进行操作的函数指针
. b1 Q$ m: T' G0 Vvoid AfterBinTree(BinTree *Tree,void func(BinTree*))1 P( Y" X' x8 o, ^# s8 K! ^
{
; W+ D9 k, F5 x+ p2 W9 X4 M3 [/ q, F if(Tree)! _5 k! \: l' F" [
{
- \- C8 P8 \. h# h AfterBinTree(Tree->Lchild,func);
- |! P( a, ~- L AfterBinTree(Tree->Rchild,func);7 [4 M/ {/ e! \" k( g& s
func(Tree);, [8 f+ k. I7 {: t- j
}
- I5 m) {, Z$ Z- x+ N+ b$ k9 H0 t}
2 g: d) E6 l$ m5 d |
|
楼主: 考拉
/1 
IP卡
狗仔卡
发表于 2004-5-2 15:40:00
显身卡
发表于 2004-5-2 15:50:00
