 该用户从未签到
|
几天前的东西，现在没有大兴趣了
|
过重复代码过多,比如二叉树的建立等等
* O& [3 X% W% |
2 V6 ^8 K+ Y& F1 B& I#include ( N7 ]) D- V4 ^, ~
#include
( y: e* U# E# `8 R7 l1 b, \" |+ p, M* }) X
typedef struct node" ]0 a. c* H8 T% `
{: @0 X1 G6 P0 G: u) o" l, ^( s" \* }
float Data;' V4 C$ O! t6 t
char Formula[100];/ L! t$ b3 b) s& q, {
int frist; //优先级* g, R6 r. w" Q
struct node *Lchild; t9 S& X5 F2 l% T7 _
struct node *Rchild;0 r F1 }6 N: ^2 H0 g Y! o) g
} BinTree;$ b3 w) F+ } H* ~- s- u1 `: N1 Z0 I
void CreatBinTree(BinTree *Tree,int *nArray);
" N9 M$ \6 C2 ~+ \void FreeBinTree(BinTree *Tree);
|" N: _2 [% u& i }0 s9 _9 x% Evoid AfterBinTree(BinTree *Tree,void func(BinTree*));
4 ~- h' O; W3 I6 r3 C/ T; j1 Gfloat CalcBinTree(BinTree *Tree);7 C+ q1 d8 e- o7 C W8 _) _
float GetFormulaVal(int *Formula,int count);
: f0 X, @1 _6 z' E0 ^void ShowFormula(int *Formula,int count);7 x; Y( T4 j3 J4 M# ^# s* A/ K
void AfterNode(BinTree *Tree);
& {7 x" x, r- Y ]+ Y2 _void GetFormula(BinTree *Tree);! V5 F7 ~* `+ O& h+ {2 _/ g2 {* W/ ~
void Myitoa(BinTree *Tree);
" J8 ?2 q3 S6 Q) F. ?int EnumFormula(int *FormulaNum,int num,int sum);
3 H* ]9 E! K! Nvoid Restore(int *Formula,int *NumSym,int *temp,int count);. Q& {$ o- e! \
int IsOK(int *Formula,int count);
, |# V7 n( I7 v1 I$ Cint FindInt(int *nArray,int n,int len);
9 ]1 @" ^" z0 Bint UpZero(int *nArray,int n);; I% I# c3 @# p7 o% o
int IsDownNumSame(int *temp,int count,int num);
" e) g( h. A/ j4 g2 ^7 p: G l3 _, p; s* B$ a4 a
const char cSym[5][2] = {"","+","-","*","/"};
# r. r' q0 t" C$ \
5 ?4 I4 C0 k) z3 d0 f' \int main(int argc, char *argv[])
5 I5 ?7 t9 Q6 t3 F7 U3 Z' b{ l& _$ r; b8 V2 E4 |9 o' z
int i,n,*Array;- J; M% H0 I4 T! v# G ?. V2 e8 v
5 }8 Q6 m1 K6 `9 p
//printf("几个数？");
+ m7 L3 s+ w3 N/ ] //scanf("%d",&n);
) D8 s% X# ?. N( W( ?. F n =4;
9 A. s# R, F2 W% r5 L. B3 x& A Array = (int*)calloc(n,sizeof(int));& g& O, Z2 f; {/ @
printf("请输入%d个数（用回车或者空格分开）：",n);
# ^ W6 E7 l. E- s7 ` for(i=0;i9 ?( l: D0 j) n2 k
scanf("%d",&Array);
7 f1 b4 |' v' Y& n5 E printf("总计%d个式子\n",EnumFormula(Array,n,24));
; \" p3 ?2 I! l3 f: H/ w free(Array);: p; e9 F: r3 O; m! V6 ^' w" k
# r- D: u# h0 J& K0 N. Y: V9 R
system("PAUSE");
# F9 ~, y( @% T! ]# U& b! e" ^ return 0;" ?. I, u* Q$ E- x) N; [
}$ H1 J2 Y0 K% x( o; M' l2 U7 Q2 o
0 z3 W% \) D$ Y5 |- t
int EnumFormula(int *FormulaNum,int num,int sum)$ ?' ?; M! b4 p' C6 t3 R$ B4 X
{
5 j- K- A2 p; e* ]+ r( |; f' }2 i int result = 0;, D: z; Y9 I$ `# V" g
int *NumSym = (int*)calloc(num+4,sizeof(int)); //操作数运算符组成的可枚举组
: b2 o+ n0 [' y int *Formula = (int*)calloc(num*2-1,sizeof(int)); //波兰表达式储存空间! x! L: H- B4 f: x, W
int *temp = (int*)calloc(num*2,sizeof(int)); //波兰表达式的代号表示空间
0 D. \3 v0 _! B0 w5 |1 j4 R( y7 c int i,j;
. p" \, R# x- K' L7 a' l* i* D( H for(i=0;i = FormulaNum; //载入进行穷举的操作数! |" A. J8 F$ O
for(j=0;j<5;j++) NumSym[i+j] = -j-1; //载入进行穷举的运算符号
+ ]6 F* }9 f5 e4 `) b, w+ S# ?: C
3 [$ [2 |$ T# L" c' Y! x( N for(i=0;i = 0;3 c5 \/ W3 w6 b; ]( O+ I* _
// 穷举开始，结束的标志为波兰表达式代号空间最后一位已进位，即前面各位已穷举完成( c8 S3 Z; v9 n) L& ?. d( B# Z
while(temp[num*2-1] == 0)
. O" f$ F7 Z3 N9 T# `0 A {
, ^& P/ e. M' o1 @; X6 a2 D" k if(!IsDownNumSame(temp,num*2-1,num))
# M3 ^2 w$ o1 X1 H r( | {( t: e, n1 R+ a# b% [7 |$ [
Restore(Formula,NumSym,temp,num*2-1); //还原波兰表达式
- ]/ N0 l. x f' O$ g1 b, k if(IsOK(Formula,num*2-1))! j1 W) X! ~$ s4 N
{9 K: l' p. r+ H% K
float t; //结果偏差
- y' w' F l$ ~1 r! e2 ] t= GetFormulaVal(Formula,num*2-1) -sum;
5 W$ h$ f5 O2 L" q if(t>-0.01 && t <0.01) //结果为浮点数，只能进行近似比较9 C) U8 F* J6 h0 X9 e
{
' h: ]: c7 ]+ H5 Z result++;
9 p9 P' o ~) D+ K: {2 g ShowFormula(Formula,num*2-1);
1 J% _% K6 a8 E% z6 w* [4 w } X2 Q7 r$ Q6 T7 L$ u
}
- Y9 p- J' F" F; z }
( l7 }1 U& f8 `5 h u0 p& P temp[0]++; //穷举动力8 P2 p9 E8 S, C( B/ h i y8 E. ^1 u
for(i=0;temp > num+3 && i//代码空间类进位7 F( g# _: S/ k+ I9 P7 }# }
{
1 R* S8 T9 I' Y6 Y# c0 r temp =0;
) C1 B4 X6 d. Z8 T temp[i+1]++;( U& @5 I$ n4 K+ S& z. n# Y
}/ Z2 F3 y4 S" o# W) ^7 |
}. f4 `3 \* l3 W) i8 O0 E4 P3 v( }
// 释放内存
; p, R) u; m! `) R4 r% k( y free(temp);* q# W* [4 o! N- N6 }( B& `, V
; H) k: K; z4 }4 F' Z8 B( L //free(Formula); //？？此处不知为什么会出现错误
% N; |9 S1 _* e( A' f; C& ? free(NumSym);4 m3 P9 ?- X/ Q& d
return result;* k5 R6 L A! O/ E; u ~
}; r8 `0 S( U- T7 D7 q( B# Z' p
// 由代码表还原为波兰表达式
3 {8 ], ~3 H3 d3 G" L/ Kvoid Restore(int *Formula,int *NumSym,int *temp,int count) \, B' Y5 } N* V9 f9 M, W% m
{0 N- i0 V1 j# Q, f. y$ o8 l
int i; M; u9 C$ A8 N/ y5 A) B
for(i=0;i = NumSym[temp];- Z0 h9 g" Z! t2 j( v8 k t0 u
}: [7 ^* @, c, K& g! k' T2 R* H
// 判断是否符合波兰表达式- b; n$ H! W" i
// 符合的条件是每个运算符号前必须是操作数个数多了运算符个数
$ X; z D9 z- x$ s( l: {/ `// 且运算符个数为总数减一的一半
+ b! E* d) @* r9 T. Iint IsOK(int *Formula,int count); R Y9 k, a7 r) V
{2 z1 F+ r! z1 k1 s
int i,j;
; g, U. t- e' V8 S; A& v% g for(i=0,j=1;i9 M4 L! u8 H0 Y8 F+ i
if(Formula<0)
9 `1 r6 `+ O9 u- I2 G" B6 s if(UpZero(Formula,i)>j) j++;% q- A- Z2 i( ~5 d+ t2 _# u
else break;
. c, R$ P' ^/ D2 P; [4 U) W if(iint)count/2+1) return 0;2 f* r5 u4 Q) X
else return 1;+ k1 @% t; ]6 x) u' {+ |/ w' w& L2 c
}
9 d" j4 o; a3 p0 w: S# I0 ?; i// 查找数组大于0的个数8 }! m. a, y2 k" X5 j# ?. f+ e/ Y
int UpZero(int *nArray,int n)
: W: i) S! p4 H5 i8 g j# x{
* ?; [* m+ @) F; d int i,result=0;/ r% O {* n: y8 {+ j7 i
for(i=0;iif(nArray>=0) result++;
3 c: Y' _# R% [* D" W: d return result;# F! y. z7 m) ~
}
9 T' U' ?' N; _' `// 查找数组中，小于Num的数是否有重复
' \7 ?2 Z6 Y) b: yint IsDownNumSame(int *temp,int count,int num)
- X% N0 T ?$ x. G8 w{
% ^4 m# v9 a6 Q; A2 N1 G3 L int i;
2 r* \. U7 O+ c+ r m for(i=0;i& e* Z3 |: F/ i9 u) L0 L5 @ {
$ w# p7 m6 s, E% |6 K& W$ L if(temp < num)
9 ` b* v3 T6 F' B/ Q if(FindInt(temp,temp,i) != 0) return 1;9 Y! s" m; c# Z# k9 Y
}
+ o& C/ O9 K* u( B return 0; g0 o# E! c2 q0 v8 q2 O
}
% v" s d. [* H4 L* ^) Y// 查找数所在数组的位置，返回0为未找到
4 l- ^9 G% {: y) [# Q) s# W! I. iint FindInt(int *nArray,int n,int len)
' S; ?# B! Z8 d* x6 I{5 ]& Z9 W* Y4 H c9 I
int i; q( M6 c' l$ I% G
for(i=0;nArray != n && i0 ~" b/ S. y; o) l% \2 u if(i>=len) i=0;* G0 s, H! s! N+ M2 f7 ]/ a
else i++;
) d& Q) {: k) J# F5 e% J/ F return i;' R& e$ h. u" ]) c' { H* E6 ~5 H
}5 ]. L$ f7 r0 c
( {, S$ z* G4 u3 j// 计算算式结果
2 f" L K9 i* d G& yfloat GetFormulaVal(int *Formula,int count)) T2 t5 j$ j3 f
{
8 d7 O# `0 o2 r6 Z" _0 w$ A8 L float result;& K$ g" Y/ u, u4 ]/ K/ v
BinTree *head = (BinTree*)malloc(sizeof(BinTree)); //二叉树头节点9 S+ N; M3 u9 `2 Z; ^
int *nArray = (int*)calloc(count+1,sizeof(int)); //波兰表达式储存数组，首位表示数组有效长度. C2 H* Y3 n5 }2 p
& F* H& ]7 k4 e' ^; ^. N; j1 @ h int i;- M/ f3 T5 K) h3 g* c9 R" g9 s
for(i=1;i<=count;i++) nArray = Formula[i-1]; //复制波兰表达式# Z" T% ~8 P$ M3 w$ q. n
nArray[0] = count;7 x8 [: C A$ f. V4 I( s; _" _
CreatBinTree(head,nArray); //建立二叉树
- _* B! @& m( e" s& J& [' ?; C5 S5 @9 d8 `3 J1 W
result = CalcBinTree(head); //计算二叉树算式
8 d3 j& ?* |9 O: B8 A4 ?3 E AfterBinTree(head,&FreeBinTree); //释放二叉树空间
; B. X7 r* F- T( p+ w
7 V1 j: l. I$ m3 r5 {5 T. Q, J free(nArray);
* {$ h! Z( X1 ]- m( A H/ n6 N return result;/ \0 S& m/ `1 k
}/ J: x _ m0 m0 c& `
float CalcBinTree(BinTree *Tree)
7 u- d9 g( b. M, \$ t& o; e- \7 P. y{* |0 V. s/ A. ^. e2 W
% `9 I3 b) H( P3 g! w" b* D$ \7 X
AfterBinTree(Tree,&AfterNode);
' j/ T# N- x* p$ G6 o return Tree->Data;
# e6 D/ b- p! [3 v1 G1 A. |: V4 q}
8 K0 u- a4 j4 m3 Z3 R' }1 Z+ Z5 x% \% V+ e7 Z6 i! u: _
// 后序遍历二叉树进行计算,但会破坏二叉树本身
7 G/ I% d1 U, l' C* [8 l7 v2 K# W// 一个结点的结果为左子树 （运算符） 右子树: K7 W" b' }: ?
void AfterNode(BinTree *Tree)
6 I3 v7 K( z7 f' f2 g{: a/ b3 E" n2 O* n" c9 P# N* x0 s
switch((int)Tree->Data)1 W" P6 w" F) [
{7 P" w' A |5 _# B& B& l3 m
case -1:% N4 o7 j: ]/ `
Tree->Data = Tree->Lchild->Data + Tree->Rchild->Data;. g- ~9 _" D1 v, u' D5 D! R1 @
break;
' B' E. c; e, h$ v: M3 }9 L case -2:, e, O! K( Q" C7 S% h
Tree->Data = Tree->Lchild->Data - Tree->Rchild->Data;$ Z+ _; N3 J$ Q8 R( [
break;. r; P2 Z& n6 @
case -3:
! ^( I0 {8 u" z; N Tree->Data = Tree->Lchild->Data * Tree->Rchild->Data;
* @' N9 }) m, H6 o9 S break;
1 f7 T/ g! x2 ^- M* i9 N: L case -4:; i# t* o7 v2 I6 s% ]
Tree->Data = Tree->Lchild->Data / Tree->Rchild->Data;1 F8 D" G! i7 i" M9 \) [
break;% R! b, ]0 p/ L( d. V6 E; L+ ]
}
: S9 k' G0 A) v3 H) A; c. y}6 _. }7 P( S. N+ V; n
// 打印算式
4 ^) w, @+ ^. f4 F2 L5 b$ T4 \, s& q; W- l/ J" _
void ShowFormula(int *Formula,int count); r0 H3 x, W. a1 }. V
{: }* z4 b) N' M- s9 N
BinTree *head = (BinTree*)malloc(sizeof(BinTree)); //二叉树头节点* H n. c" C- W3 W& G5 @8 y
int *nArray = (int*)calloc(count+1,sizeof(int)); //波兰表达式储存数组，首位表示数组有效长度3 h2 g& P2 f* C8 }; b' Z
int i; }; Y) x$ o( Y
for(i=1;i<=count;i++) nArray = Formula[i-1]; //复制波兰表达式
n6 h, N6 D6 f5 g/ v1 ~1 D nArray[0] = count;' E. Q* q0 M3 N, E8 V
CreatBinTree(head,nArray); 4 n; N% Y( i, C4 [% g0 C( u* j" F
AfterBinTree(head,&Myitoa); //初始化二叉树字符窜部分4 P' H9 V9 T Y* g
AfterBinTree(head,&GetFormula); //转化为普通表达式# j0 a: P. [# f! ~9 I
printf("%s\n",head->Formula);
& q% B) o1 T9 t1 q- ~ AfterBinTree(head,&FreeBinTree); //释放二叉树空间
, m4 B ^& n/ \4 U& j( ?+ } free(nArray);
' S. m9 [2 F/ v- }- S9 W- \* } . B$ H# ?1 M+ V' K
}
, A. z) a0 H' e// 类似计算二叉树
7 {7 E! A) |/ {3 S5 J5 o9 X. l// 会破坏二叉树本身
% h/ J: L9 W! Y; c9 qvoid GetFormula(BinTree *Tree)
8 X" d: G' P5 h0 c; ?& _( b{$ ?$ a- `( u" E* P f6 ?" S
// printf(Tree->Formula);
7 M' {" ~) G0 `1 Y$ H2 ? if(Tree->Data <0)
" D! R8 X u. P* y1 ~6 d2 T+ j {
, a. g% p. C7 @ char temp[100];
8 Z4 i9 k" u' F if(Tree->Lchild->frist < Tree->frist)
4 ]& f. L9 @# n5 q& B {3 i% X @$ R- S n' I
strcpy(temp,Tree->Lchild->Formula);
( `" A# ~$ B& }* b strcpy(Tree->Lchild->Formula,"(");$ c2 m/ Q5 H9 G/ v! j
strcat(Tree->Lchild->Formula,temp);" j* i8 q4 @& S: m2 U+ [7 u
strcat(Tree->Lchild->Formula,")");& G( `, S3 y' L: `% o5 T7 T9 s I8 B
}2 u% i t8 W3 g
if(Tree->Rchild->frist < Tree->frist: Q9 F/ S' K2 e1 ~$ B
|| (int)Tree->Data == -2 && Tree->Rchild->frist == 0
) B# j0 J/ c, L: b/ U2 C' T2 s || (int)Tree->Data == -4 && Tree->Rchild->frist != 2)+ ~9 ?" H4 S) u) C0 H3 I" A
{
4 p" e2 y. N; k+ |2 D/ W strcpy(temp,Tree->Rchild->Formula);* e$ {% C2 T6 H7 p, ]7 u
strcpy(Tree->Rchild->Formula,"(");
/ \& h# J" y8 w# R strcat(Tree->Rchild->Formula,temp);
0 M* w" Q. ?$ ]3 b& c3 Y strcat(Tree->Rchild->Formula,")");; b* V1 B+ e y/ k
}. q/ F9 S- R; t, j0 _
strcpy(temp,Tree->Formula);
. B& D# U( |" c( X2 }, @7 j strcpy(Tree->Formula,Tree->Lchild->Formula);
& B2 p* _; m. z( o; ?7 P! a: P+ ?4 Z strcat(Tree->Formula,cSym[-(int)Tree->Data]);; l+ v. ?1 V8 g4 _
strcat(Tree->Formula,Tree->Rchild->Formula);* Q6 Q* g' @( D3 D0 y% u% \* H6 s
}
4 ]; ]* l3 C# k3 B+ P. \6 ^}4 T. c6 @# w7 X& ^5 H+ g0 _
// 对二叉树字符串部分赋值
5 K" c5 ~% H; m! ovoid Myitoa(BinTree *Tree)2 S9 E3 D& J+ A( D
{
1 k( \) }( a$ @ if(Tree->Data>=0)
# J6 k9 F% J8 _$ u {* Q! q H2 R4 w( q: R
itoa((int)Tree->Data,Tree->Formula,10);
$ T% p, @( G; _; f# F Tree->frist = 2;
+ ^8 I0 ]' s2 n+ v }/ G+ S3 c, ]4 V
else
% C4 |8 A% [2 F2 x) h {
_# {# g3 U9 B5 n7 | Tree->frist=Tree->Data < -2 ? 1:0;! N9 j* q6 c& T {6 n3 |% ]' r
strcpy(Tree->Formula, cSym[-(int)Tree->Data]);: x1 t& d+ z$ H" e) Q- ]
//Tree->Formula[1] = 0;0 F! Q& Y' R! l
}
% y# `& m' W8 X}( }+ d: k4 X& H3 }7 i* Y: T/ N1 b7 ~
//从一个波兰表达式建立一个二叉树链表，需指定一个头节点5 q* A/ }: M9 k+ D8 R4 _" X, \+ U
void CreatBinTree(BinTree *Tree,int *nArray)& S. `& T$ L9 y" r, b* X2 Q# P
{. J1 m6 P- C8 x K" p1 H
Tree->Data = nArray[nArray[0]--];4 Q5 D& ~8 D8 h) u" \$ Z7 U5 r: v5 m
if(Tree->Data < 0) ^7 D* m7 c0 Z" N" ~
{
+ \9 O9 Q4 A8 |6 A) M) J Tree->Rchild = (BinTree*)malloc(sizeof(BinTree));
1 ?8 }; V, V! Q7 y; U4 y CreatBinTree(Tree->Rchild,nArray);1 Q7 g, V( Z) |% g6 {
Tree->Lchild = (BinTree*)malloc(sizeof(BinTree));/ u% P# R% A1 ^# ?' [9 Q! T9 P: q
CreatBinTree(Tree->Lchild,nArray);
8 z6 B5 h& _& Q2 q }
2 J( ^8 f/ Y) n2 {8 u else8 [6 Q( O3 y# Z8 q
{! Z S* E* U2 Z2 c' V; ^
Tree->Lchild = 0;6 c7 n4 \/ Q @1 h" o
Tree->Rchild = 0;
$ e. P9 _, k' r8 ?6 G1 n4 q$ U }4 \- k; A" }3 S
) k9 m5 ~7 d0 } B9 F5 h9 n* l}
# N" h }6 b- t/ }8 O& Z& E
$ P3 g0 m7 a( u$ M* F// 释放二叉树空间: K4 A9 ~! j8 ]0 P. E- G
void FreeBinTree(BinTree *Tree), o% z* A0 U- N; ?+ z
{
. R$ y0 s) M# V( T7 m free(Tree);
: G$ u W9 C$ q; T/ f}
8 z* ]' H4 f6 P+ H0 W// 后序遍历二叉树
- ~" z g2 [) a$ j$ {6 \1 \// 方便其他函数调用，func为要对各个结点进行操作的函数指针5 r# B1 m, [/ _3 X: A6 G
void AfterBinTree(BinTree *Tree,void func(BinTree*))
5 Y/ k8 A7 l) _0 G& u3 a: n{" }5 ~4 D. s6 Z6 f+ W8 i/ F
if(Tree)) ~4 Z6 r; u: {. B+ \. c9 _# W. X
{" x+ N8 f$ C) k3 {! V* k
AfterBinTree(Tree->Lchild,func);' e, Z; f) a' l$ M0 W% v" M& U
AfterBinTree(Tree->Rchild,func);
" }' s4 E! z1 b j1 E6 J func(Tree);7 i) o( b# q1 [, O2 j
}+ L* L/ M5 z8 {' V3 ]$ D3 g' E
}
: b# j: R3 A% g |
|
楼主: 考拉
/1 
IP卡
狗仔卡
发表于 2004-5-2 15:40:00
显身卡
发表于 2004-5-2 15:50:00
/ R U/ ]" V. ?* _