|
|
几天前的东西，现在没有大兴趣了
|
过重复代码过多,比如二叉树的建立等等- p! C' q& I X9 _
3 }' R, @4 X0 d
#include
( \1 l+ V9 Z0 t: q# M#include
5 F2 `$ T& F2 ]% i) E6 p
0 L' g' ^* l7 u1 E0 H: G Ltypedef struct node
3 f4 _8 C$ t/ `( C, E0 Y. g{! E# E. k: H4 N" _1 P
float Data;! d) @* t/ L- t. @$ t, p4 i
char Formula[100];
( g/ Q$ _1 \& ~- @0 v int frist; //优先级
- Y2 W' e7 M9 F8 ]* e- h struct node *Lchild;
( O& ] i4 F- w) R# z- A% V1 E struct node *Rchild;. C# y, E4 k9 s/ y) i) R
} BinTree;* d% G* Q+ E" U& q1 l0 [
void CreatBinTree(BinTree *Tree,int *nArray);
% ` W) q1 W) g) D9 y3 n! f/ l$ Evoid FreeBinTree(BinTree *Tree);: f3 g% { b9 s( {* ]) e
void AfterBinTree(BinTree *Tree,void func(BinTree*));
$ [- I" i0 t+ j# b3 V) Ffloat CalcBinTree(BinTree *Tree);
' V0 M; D/ |0 C+ cfloat GetFormulaVal(int *Formula,int count); _: k6 [( z4 ^! ]& j
void ShowFormula(int *Formula,int count);
6 `7 C; i& ^" P, b; @5 \7 L& Mvoid AfterNode(BinTree *Tree);
& u9 B+ f7 k# U- O5 N! Kvoid GetFormula(BinTree *Tree);
0 Z7 l) H, V; W" U0 E# i& E% jvoid Myitoa(BinTree *Tree);
5 Z4 T, A) _7 V& d# ~int EnumFormula(int *FormulaNum,int num,int sum);( l$ [8 \$ B% @: V5 p
void Restore(int *Formula,int *NumSym,int *temp,int count);4 N+ H' \4 Z, X& ^5 P# ?
int IsOK(int *Formula,int count);; l* t1 f2 P8 R6 m
int FindInt(int *nArray,int n,int len);
9 b( v5 |3 u' M% Oint UpZero(int *nArray,int n);' T1 ?* |$ m2 Q" @! }
int IsDownNumSame(int *temp,int count,int num);! f C( G) z" i. C1 w& ^
- C! v: V9 X3 m, f, V* O
const char cSym[5][2] = {"","+","-","*","/"};
6 F7 v8 `$ h+ b( K5 c, {, w; F
3 z+ Q5 Y$ `; \$ U8 a9 Nint main(int argc, char *argv[])
j% k/ z6 t5 T: I. ]7 e{
. `- \+ x8 L% f0 ` int i,n,*Array;
4 j6 L, Z5 f' w- [6 ?. U
+ Y0 f, n+ H- s8 a4 Q6 o) d //printf("几个数？");
9 n2 N! V; x1 i& g/ F //scanf("%d",&n);
& H7 L' c4 U T% N9 }# R: ? n =4;
9 Z7 y, C `) @( M Array = (int*)calloc(n,sizeof(int)); l" |; l1 d( X* ^8 l
printf("请输入%d个数（用回车或者空格分开）：",n);
8 m! i- j% j6 O$ t1 u4 X! Y for(i=0;i* @1 d9 R. s' h' n: S- w7 c scanf("%d",&Array);- X( |9 B* _1 z
printf("总计%d个式子\n",EnumFormula(Array,n,24));1 x6 l8 A* i* [4 T+ d
free(Array);! S, \; L& u& C) A3 |
- @; O3 b& A: J2 B. i7 E, }) \3 ] system("PAUSE");
' h' f: V u* _2 a return 0;
. w$ ^* \: I0 S5 r8 a# |- J; c}
/ w/ V; M4 ~3 G. C# ?
/ _* x7 w; c! z, N1 {int EnumFormula(int *FormulaNum,int num,int sum)
) k( ]+ k& l7 {{
1 p% P- K; c/ a+ ], Q) U7 i int result = 0;3 n' u2 A. g: u8 ~, H0 N
int *NumSym = (int*)calloc(num+4,sizeof(int)); //操作数运算符组成的可枚举组
( d/ J* W! |3 a) _- v$ G# ^4 j9 E int *Formula = (int*)calloc(num*2-1,sizeof(int)); //波兰表达式储存空间
7 \3 O& @, h% x! U int *temp = (int*)calloc(num*2,sizeof(int)); //波兰表达式的代号表示空间" Y9 J" F* Z- A9 @3 Q, T4 X
int i,j;
5 Z/ U W3 A; b8 X# {6 y for(i=0;i = FormulaNum; //载入进行穷举的操作数
% k& X5 n- w( X4 F- t& _ for(j=0;j<5;j++) NumSym[i+j] = -j-1; //载入进行穷举的运算符号
; |. n4 Z }+ j/ i! M! [* v" A! b- t3 A6 L( T- Y7 @. u
for(i=0;i = 0;( l- y, W0 q8 H4 u: j
// 穷举开始，结束的标志为波兰表达式代号空间最后一位已进位，即前面各位已穷举完成
V; x' o' p5 n/ Y( B2 z& O- H while(temp[num*2-1] == 0)
9 j6 ^+ i+ o" Q' ~8 _% L3 L+ o {
0 h% I# n' |, w; M9 i& D( Q if(!IsDownNumSame(temp,num*2-1,num))
4 c) P: v# Q, R/ ` {2 X* ^$ K0 ?( F
Restore(Formula,NumSym,temp,num*2-1); //还原波兰表达式
9 u3 _; L3 j7 T if(IsOK(Formula,num*2-1))
2 ?, g2 X e3 m' `: ]: c {
: L% |! l0 @# O: ` float t; //结果偏差/ W; `) l; r3 R* Q4 ~$ [. _
t= GetFormulaVal(Formula,num*2-1) -sum; l" a0 {+ d; Q0 j6 l+ v( q
if(t>-0.01 && t <0.01) //结果为浮点数，只能进行近似比较8 B9 Q/ h: U: L
{
- g. u$ i' l# l' m( n. l# E result++;6 W0 Q+ [' V, v5 ?) U7 o
ShowFormula(Formula,num*2-1);
( e9 [9 W3 j6 k* D }
* y0 O$ U w; l& r7 V4 y* I }7 c2 T. O6 z% o1 D6 g3 P+ s
}6 i5 ^0 c5 ]/ w0 h
temp[0]++; //穷举动力- q! ?! J0 H, Q8 ~7 N1 R9 U7 M
for(i=0;temp > num+3 && i//代码空间类进位
( {2 @8 @* j: |, m7 W5 ? C {
- T! w, n* ~! S& y) Z$ G8 T temp =0;
4 d; E+ ^7 t- r temp[i+1]++;" Y: E2 Z8 w# m: T- M6 C3 H
}
% P/ k; r% ]! h' J( { } P- F1 B8 H0 X- v. I/ M
// 释放内存
; L/ Z0 c: d5 t: a: p; z free(temp);
) [9 a$ N1 L# e6 K. T B3 y; N, T/ C: C. U0 [3 g
//free(Formula); //？？此处不知为什么会出现错误
: e1 @, E5 P5 a& N, ~7 s free(NumSym);
- h9 t ~7 f/ r% |" g6 p, s5 t return result;
( G2 T+ |, N. b+ t4 u7 i/ ^}
/ p7 s3 r2 C: M6 N! f// 由代码表还原为波兰表达式) H' M, y @$ I- j$ e
void Restore(int *Formula,int *NumSym,int *temp,int count)
$ a q- B+ |1 U( E, }& k9 S8 B; P# i{. [2 {* e+ Q- D# V
int i;
' z% O2 H% Z; x! U; G2 g# ^+ E for(i=0;i = NumSym[temp];% t& r( Y8 {9 h8 F
}8 T5 k) W' B& J" n% P
// 判断是否符合波兰表达式6 f$ ]& X J& c& ]+ x" P% b
// 符合的条件是每个运算符号前必须是操作数个数多了运算符个数. _6 h6 m% _9 C; H& s
// 且运算符个数为总数减一的一半- T3 ?( I8 R/ P5 }
int IsOK(int *Formula,int count)
: b' T# [# ~* v{" e6 X. ~! M9 B* }7 @' D: {, A! b1 R
int i,j;
9 |$ I" f' x2 W& U for(i=0,j=1;i7 P. P# E% D6 U" V# \! S1 e
if(Formula<0)+ ~' ^ O& N3 s$ t5 D+ A
if(UpZero(Formula,i)>j) j++;
8 P5 n0 \# l6 N% T' F0 d6 }# A7 n5 G- j else break;
% |9 T, Y/ ]. q+ Z. |) S3 P if(iint)count/2+1) return 0;" K8 M6 W8 `- A7 `# Y3 ^
else return 1;
6 g( D. I w8 y: v2 K$ w8 D' [}) }. M8 R" r% L- _2 \) c: V
// 查找数组大于0的个数& W# I4 E* g; b* u+ j' c8 s
int UpZero(int *nArray,int n)
! [8 b- b* @: [9 W) i8 \{
8 e2 Z( b$ V0 B% n: J3 @ | int i,result=0;
7 i( n) ?8 q6 L2 g for(i=0;iif(nArray>=0) result++;/ L* a* w. o+ Q$ l4 _8 @6 L. A
return result;' l" Y: M0 E* @. n2 L% _) \" ?: n4 B
}) f7 O2 Y8 I# a: R5 }7 V
// 查找数组中，小于Num的数是否有重复
0 C- i6 d( Y6 V. eint IsDownNumSame(int *temp,int count,int num)
- M" W/ z }; P$ I/ j \ ` W{4 {2 D# B1 k, T+ a0 Q2 n- @6 T2 q
int i;
x s8 a# N8 x( J for(i=0;i# w, B4 i% A0 O; r {+ T+ y" U3 b) y& y8 N
if(temp < num)2 E( p) r; `& ^
if(FindInt(temp,temp,i) != 0) return 1;( k9 S- V5 G7 A* L& r ]7 O
}
7 N. Z! O$ j2 o' }# ?8 f! e2 j7 K return 0; l# @+ a1 c' d, C$ X" Q: q3 ?
}
+ S- t& p7 ^( H' f// 查找数所在数组的位置，返回0为未找到% W1 @& [4 ~( `( e- ]1 V
int FindInt(int *nArray,int n,int len) e) ]" z' V% G& n
{7 f# I; ^8 x# `
int i;
, J0 a$ Q; y! x" b for(i=0;nArray != n && i8 t4 m0 @7 `' C$ ^ if(i>=len) i=0;' o8 F& m/ j- O9 w' u: p! R
else i++;$ _# Q7 {4 J3 F4 G5 H. S8 Q
return i;) U- J4 l! n; L. G6 e
}" R. c n5 R; [
' `, j9 F- l" {: Q; y7 L z
// 计算算式结果
1 H" Q) V5 H0 @: s) \; ufloat GetFormulaVal(int *Formula,int count)1 k/ i9 P. v7 F$ V3 T8 ?% X1 ]6 @
{
- E7 N$ |( s% `! |: K float result; D/ |. P- q7 j. k: t
BinTree *head = (BinTree*)malloc(sizeof(BinTree)); //二叉树头节点- \7 p0 X) T3 k' G- t! K
int *nArray = (int*)calloc(count+1,sizeof(int)); //波兰表达式储存数组，首位表示数组有效长度
; c5 x- A! x5 I! q/ W8 f# O
* A2 E0 U; F' C" Q' X# r int i;$ e3 }& z( x- f/ o
for(i=1;i<=count;i++) nArray = Formula[i-1]; //复制波兰表达式5 Z6 L( n# Q, Y2 u: J5 G5 S
nArray[0] = count;0 M+ L! C, @9 J6 M( I7 P; f1 o* h6 H
CreatBinTree(head,nArray); //建立二叉树
1 R4 Y% b, e+ }( W, R/ q
7 t6 ^. ^4 J, d. v result = CalcBinTree(head); //计算二叉树算式% C6 a9 R( Z! e1 j+ M' F
AfterBinTree(head,&FreeBinTree); //释放二叉树空间+ A. ]/ c8 U- Y4 a) `* t& R
2 ^2 G% q' [7 d% v* o free(nArray);- } ?$ i: \# o$ s8 D- j
return result;1 W3 s/ ?5 O, \" p# ^9 ]
}7 a+ m5 O: m- C m$ w
float CalcBinTree(BinTree *Tree)2 ]. ^5 F) w9 Q$ R2 k8 ?" I+ {
{* T8 n6 v T& B4 l! v
4 A; Q$ C8 U q' {* B" b/ [
AfterBinTree(Tree,&AfterNode);
* g: Z1 P9 F O return Tree->Data;7 v4 C4 `' d* @& A
}9 F: ]& E+ j5 ~0 v8 ?
3 W) O* C- A$ W3 L' {* b o// 后序遍历二叉树进行计算,但会破坏二叉树本身: T* }0 {" G' A6 ]# M
// 一个结点的结果为左子树 （运算符） 右子树
6 w2 l; x( Y: C( p- R. qvoid AfterNode(BinTree *Tree) I0 w9 W7 ~$ _) g' }) s% V8 R
{
o" B! P4 [& Z switch((int)Tree->Data)
6 S7 `3 z0 e8 z' P4 C1 [ {
' O! I; p9 {4 D; {9 ^. J* k case -1:
/ k6 T8 |. e: `& q Tree->Data = Tree->Lchild->Data + Tree->Rchild->Data;
9 e7 z+ z' P4 q2 |: i, t/ ~ break;
6 ]; R+ J. ?- E0 I( B case -2:
" K$ S, N) y! p8 y. j. T0 P Tree->Data = Tree->Lchild->Data - Tree->Rchild->Data;
( s* `8 Q; t! G1 ? break;
& P: G) r# R4 D2 J& h case -3:; r. x! o8 T* b/ G
Tree->Data = Tree->Lchild->Data * Tree->Rchild->Data;: z H7 s8 b6 i9 b, u5 q0 `
break;4 m9 n) t# O6 r8 I' m' c) B. [
case -4:
: O" c, K8 B b; e9 N# S8 Z Tree->Data = Tree->Lchild->Data / Tree->Rchild->Data;
: ~: d! l4 r4 K: q& w( o break;
9 i- _& w2 K8 q# o4 p }
+ L: n! ], U% g}, [+ J; R% K+ t* \
// 打印算式" s1 ]1 L) d- x; K4 x
, H* k& e! K* T X$ k/ }& E
void ShowFormula(int *Formula,int count)
& H1 z( ?5 G& G! H{+ L# i. ~& |# ^% o
BinTree *head = (BinTree*)malloc(sizeof(BinTree)); //二叉树头节点
) e) n( R+ u/ E% S int *nArray = (int*)calloc(count+1,sizeof(int)); //波兰表达式储存数组，首位表示数组有效长度- y! {) e! E9 X/ h" t' u7 Y: ^
int i;3 ~. V. L- e& D! Y
for(i=1;i<=count;i++) nArray = Formula[i-1]; //复制波兰表达式
5 g0 Z0 X/ V& F. z' e$ T' F2 a nArray[0] = count;
9 F. u( @7 a: y- ^ CreatBinTree(head,nArray);
0 M) i+ g* H0 U8 ~. f( Z+ n AfterBinTree(head,&Myitoa); //初始化二叉树字符窜部分1 |* g2 F: [$ A# J8 V8 ~ ~7 |) G
AfterBinTree(head,&GetFormula); //转化为普通表达式5 A# i; V( l9 v/ q3 r
printf("%s\n",head->Formula);
% C' _$ k6 J1 F/ |; X AfterBinTree(head,&FreeBinTree); //释放二叉树空间
7 C) `" ]0 H8 }' t free(nArray);
3 w, Z" X, J _9 d+ k
+ P" `9 U% J; t' z% z}+ `- f- y7 U) ?& R
// 类似计算二叉树/ H2 M. y8 W* e
// 会破坏二叉树本身
3 V4 a0 z. O& L7 ?void GetFormula(BinTree *Tree); C7 n" ^" C" G! @ `8 b" m0 f
{( g$ c" m' |( L* D0 X* j1 c% w
// printf(Tree->Formula);, m) H/ j3 v% I
if(Tree->Data <0)
0 M$ t4 k; H0 M/ N6 E8 Y8 k {
3 y$ z6 z- B5 ]3 T$ x% E! G char temp[100];& M' P/ ? X& J- S3 s
if(Tree->Lchild->frist < Tree->frist)
8 Q7 }7 Y0 N& w' V9 X0 [8 W- Z {
6 B* {2 e6 Z' P! l7 S$ m strcpy(temp,Tree->Lchild->Formula);9 L' X3 V1 @9 ]; R6 P. v z
strcpy(Tree->Lchild->Formula,"(");. o; j& j! b4 @# r' G
strcat(Tree->Lchild->Formula,temp);
3 p" t, }4 u! ^: J3 ^ strcat(Tree->Lchild->Formula,")");& `4 T4 N+ h# g
}) j7 S1 P) M2 `- i
if(Tree->Rchild->frist < Tree->frist& o7 G% W/ r" g* C( ]( j
|| (int)Tree->Data == -2 && Tree->Rchild->frist == 0
S- L4 [1 m( A% S" ~ || (int)Tree->Data == -4 && Tree->Rchild->frist != 2)
8 ?# l+ x3 H3 A# Z' Z' L4 Z6 L: g& F {
) d' K4 J' _" ~0 z" p strcpy(temp,Tree->Rchild->Formula);
, {8 y# O' l" U strcpy(Tree->Rchild->Formula,"(");
; S& W" c( S) b9 W8 a strcat(Tree->Rchild->Formula,temp);( L0 Q( {% m% w( D! P$ z
strcat(Tree->Rchild->Formula,")");3 a' a0 m9 d7 O/ X! D8 I% o
}
5 A* o- @. }6 ]0 T% R6 q+ p strcpy(temp,Tree->Formula);
B8 Z. F# u7 T# H$ E9 x strcpy(Tree->Formula,Tree->Lchild->Formula);- l$ ?$ W2 |! d/ C/ d. v
strcat(Tree->Formula,cSym[-(int)Tree->Data]);# K6 q( I$ _$ n/ U1 M6 h, ~( V6 y! V
strcat(Tree->Formula,Tree->Rchild->Formula);: r. s% H- d) o
}8 }2 w" g* [) K1 O3 {7 D' V
}7 v. M8 z" q, ?5 d8 \
// 对二叉树字符串部分赋值' i$ B6 P/ E8 F9 w0 _; p
void Myitoa(BinTree *Tree)7 `& X1 C( W5 G; R Y6 z1 N2 Q- M
{
* C1 W' ]/ D0 R if(Tree->Data>=0)& P2 p& Y9 e2 [8 Z$ U' K0 j
{+ w& Z9 L+ ~. Q( |2 f' |. G
itoa((int)Tree->Data,Tree->Formula,10);! z7 P5 u& ~4 g. L- {) n! P/ Y
Tree->frist = 2;& x% {. H; F% J/ p3 r
}! Q8 \6 h s# j% c& P+ B4 b
else
# a2 m5 b% `6 F$ ` {: u' o1 A8 C8 F+ d
Tree->frist=Tree->Data < -2 ? 1:0; M/ p; \# u' x0 t4 O
strcpy(Tree->Formula, cSym[-(int)Tree->Data]);
/ t# i6 E9 n; {- H' v: R //Tree->Formula[1] = 0;
) r6 g+ C8 w* r4 L2 w$ D' c+ C }
# M& m: t! i: S0 F5 b& S3 T& S}
7 X0 E A6 F' r" b//从一个波兰表达式建立一个二叉树链表，需指定一个头节点6 L+ }3 u7 I7 U) d3 h% P& A
void CreatBinTree(BinTree *Tree,int *nArray)
8 R5 b$ D# H/ f( @/ o{2 f- [1 V1 S: L7 H/ l1 r
Tree->Data = nArray[nArray[0]--];
- b2 z& f/ x T( @) s4 C8 }0 U" [ if(Tree->Data < 0)! ?2 a) W& \4 P* b& H$ b5 w
{: Z9 A& `7 Q# ^- j! k
Tree->Rchild = (BinTree*)malloc(sizeof(BinTree));
! P" o2 C5 b3 W CreatBinTree(Tree->Rchild,nArray);/ _9 N( o+ i" W( q ~) j2 W! y1 J
Tree->Lchild = (BinTree*)malloc(sizeof(BinTree));& R; s8 e6 p9 G$ K! f8 s( }
CreatBinTree(Tree->Lchild,nArray);
* B: E1 L, o- l' N7 ?0 P }
8 g# A* ~ ?5 f3 f else1 `, z- }* \, W3 |5 I( k4 f
{
' Z5 N7 B8 `& x. u0 o Tree->Lchild = 0;
& r0 V5 H; k8 g i+ k6 ~ Tree->Rchild = 0;
* y7 l5 K+ A% D& D }+ h3 O5 p. X; }$ E$ ~5 h/ L
6 K: X) g" _; ^# I- o4 H
}* Z3 C+ u6 f! p( K7 i: o
p% `# L( w# h* A// 释放二叉树空间6 u- G( h2 J0 o. t) `& e4 l) g
void FreeBinTree(BinTree *Tree)9 P1 L9 h( o9 ?
{4 U) d8 e9 y1 J
free(Tree);
9 Z2 J' j4 H$ h& C& a}# o) N1 U) }! B
// 后序遍历二叉树
9 H( u. L4 F& H: K0 w( e0 P" ]- L// 方便其他函数调用，func为要对各个结点进行操作的函数指针" G0 u3 q" c/ |0 g1 L& R( v( M9 K
void AfterBinTree(BinTree *Tree,void func(BinTree*))4 ?- o$ L$ y4 u2 x' y% e
{
" y* W1 U& b# y$ l j if(Tree)
6 b6 Q; K# |5 M! ~1 y {6 p) _3 |6 ^3 |9 T2 V5 b
AfterBinTree(Tree->Lchild,func);4 a- \1 J& ?+ [4 ]* r1 \0 X
AfterBinTree(Tree->Rchild,func);
- r, o# i( F7 b1 C% I; ~" o/ d* L func(Tree);
# U2 e" K' a; D, G# s6 U% _/ m5 E }) k, d, q6 V6 e9 x; m [6 y$ Y
}
# @/ U" p1 V/ f$ U Q. F7 _ |
|
楼主: 考拉
/1 
IP卡
狗仔卡
发表于 2004-5-2 15:40:00
显身卡
发表于 2004-5-2 15:50:00
( P9 B2 G4 @. E# S I# s