|
|
几天前的东西，现在没有大兴趣了
|
过重复代码过多,比如二叉树的建立等等
3 j. ^+ H5 t& y% B2 r3 t# H# M/ F+ {) {" G6 ]% l
#include
" \% n8 g% k) o. |#include 0 j a! w i: \- x; C( S0 w
7 `5 {9 d/ l: I9 ztypedef struct node
# I n9 d( [$ J, l" g+ y{
2 E1 J# c0 ?2 S) [/ M& A float Data;% g. u2 h$ H7 T8 q5 ]3 g/ J
char Formula[100];
' r" m) N3 r( X0 Z2 |4 a) W1 K int frist; //优先级/ |, Q7 b. |! g/ ^4 {3 o
struct node *Lchild;
4 \2 ^9 B9 \% k1 Y% I+ t3 r struct node *Rchild;
3 S) M S* T' U} BinTree;
; z7 T7 @( t: j+ x5 S) A/ Wvoid CreatBinTree(BinTree *Tree,int *nArray);6 F5 _* u* K- g! ~
void FreeBinTree(BinTree *Tree);
# g4 ^7 Z1 _6 u B$ \) r. Zvoid AfterBinTree(BinTree *Tree,void func(BinTree*));9 ~6 _! J( t4 b0 O" ?+ c: K
float CalcBinTree(BinTree *Tree);: Q" \) G3 F; T0 A/ f! O- }
float GetFormulaVal(int *Formula,int count);
. ?1 X0 P0 G! z6 D0 y1 @void ShowFormula(int *Formula,int count);
! w0 i& g! x0 Z* o) x( t8 Q bvoid AfterNode(BinTree *Tree);
# X0 M7 y6 R# x5 W& E, u1 nvoid GetFormula(BinTree *Tree);
/ h% S% p' m; f2 H' k: v% f! l6 i: kvoid Myitoa(BinTree *Tree);$ N5 S) V' l9 n9 C
int EnumFormula(int *FormulaNum,int num,int sum);
1 C3 I/ d$ J2 W( y dvoid Restore(int *Formula,int *NumSym,int *temp,int count);) e ?: R# J; y/ J. q/ I
int IsOK(int *Formula,int count);
$ z( T ]1 C I6 C: Oint FindInt(int *nArray,int n,int len);
* r' l% w3 i1 h* {' E3 Iint UpZero(int *nArray,int n);
" f- V2 q1 z+ E) c- R9 X0 Gint IsDownNumSame(int *temp,int count,int num);
; R) o" W/ \# B1 t" q, r, M
- m. Y* [9 P6 f9 ^9 B) X: h! _const char cSym[5][2] = {"","+","-","*","/"};1 v: t m+ R; S& G+ H7 H! I: G
* l) v5 O0 Q1 M2 t, @8 U1 [
int main(int argc, char *argv[])5 e3 V3 W+ z* ?& k: b7 |2 N. {9 ?
{* T7 ]- ~% }* R
int i,n,*Array;# L/ Q& b+ i" W3 z% y7 i2 Y# c" C
2 t9 n2 F' y& W8 }# z/ `
//printf("几个数？");( s1 J \1 Y4 U3 S6 ]7 n( p# @8 M
//scanf("%d",&n);$ `) @9 R; o$ E5 I4 E" m
n =4;
& Q* B, L0 y; @ Array = (int*)calloc(n,sizeof(int));, ?3 V- e2 A. N# w" q+ r$ S' O
printf("请输入%d个数（用回车或者空格分开）：",n);3 X# t3 ^3 T- p2 K
for(i=0;i; Z( t; d" C5 R scanf("%d",&Array);
2 k# x1 c. X) y2 i( u printf("总计%d个式子\n",EnumFormula(Array,n,24));
& R4 @# }9 @: {* K) C( n free(Array);
0 [6 Y3 n: X3 K( u) g
, Q0 f0 u2 S( M, G }0 |: [ system("PAUSE");
$ e. g, u; |3 e2 q# V% c7 n return 0; ] n; P8 g0 w3 |
}+ a8 o( q( [9 i8 V Q. G8 `
8 T# h1 Q! w: R$ |, wint EnumFormula(int *FormulaNum,int num,int sum)
* Z `9 o0 e9 T4 S" d' t{
: J( U9 |( }1 a* P6 A int result = 0;( s7 d. \" M. ?& S$ f8 @
int *NumSym = (int*)calloc(num+4,sizeof(int)); //操作数运算符组成的可枚举组( E$ ^: `" Z/ H! v7 V. j
int *Formula = (int*)calloc(num*2-1,sizeof(int)); //波兰表达式储存空间+ R4 R7 Z' s8 d( \
int *temp = (int*)calloc(num*2,sizeof(int)); //波兰表达式的代号表示空间
$ Z. ^. U0 Z9 C int i,j;
; P* `- k* A" O1 l( v1 B for(i=0;i = FormulaNum; //载入进行穷举的操作数
% B7 W% c' u( i) X+ ~# M/ D for(j=0;j<5;j++) NumSym[i+j] = -j-1; //载入进行穷举的运算符号$ c$ m) F. ]8 M) C, s* ?
5 t. ^( v7 a: y+ a) u2 f1 [- K. } for(i=0;i = 0;8 {) z+ T% F" q. M; X: G K
// 穷举开始，结束的标志为波兰表达式代号空间最后一位已进位，即前面各位已穷举完成8 _3 t" D" D0 Y( x- J& n. S; b
while(temp[num*2-1] == 0)
- ~9 N' f f' L4 Z/ [" x {
/ ~0 I! F- }% |" j& c+ C5 e if(!IsDownNumSame(temp,num*2-1,num))
* x/ c* o7 z2 a. W+ c {
- @+ ^' E( q2 L" d Restore(Formula,NumSym,temp,num*2-1); //还原波兰表达式
# }2 H- x9 E% X5 X) E# D6 J if(IsOK(Formula,num*2-1))6 G9 `. v& u; x
{: q8 m/ E* n. |+ d) G
float t; //结果偏差
/ X+ u3 P" [( ^- f7 ^ t= GetFormulaVal(Formula,num*2-1) -sum; [1 m) v2 D+ K/ {* N6 N2 x: P
if(t>-0.01 && t <0.01) //结果为浮点数，只能进行近似比较3 X/ Z: v- d" k9 M- r
{
4 ]# p; t, B8 S0 _0 v result++;! ?: S7 i2 V" b* R
ShowFormula(Formula,num*2-1);
% _; M; Y! G5 e) H }& r( F" E! s% R, i1 g: H! U, C
}
7 }. E* \2 \* C }
& H' b$ p( P- Z7 Y/ T0 l- v1 m temp[0]++; //穷举动力5 R+ E+ c \5 d% x. m$ }
for(i=0;temp > num+3 && i//代码空间类进位
7 w! s$ U: F* e$ L' w {
: C. O( x$ z$ D) M temp =0;
9 a* o6 v9 G4 f2 Z& l" i. \ temp[i+1]++;* O \ S7 i8 ?" L H
}
, O2 a, b9 }' @2 E7 K }
2 K, I9 }6 i2 S // 释放内存
; B; R/ H% T) G4 Y3 q( s free(temp);+ q. E7 X# b, k. D
: e% ]' t2 r, r+ Z# v2 u
//free(Formula); //？？此处不知为什么会出现错误8 }9 Q" c2 m) c, _9 B
free(NumSym);3 ~/ k' t! ?# h+ K, S& C- ]! y7 u
return result;. h6 R9 I$ L0 s% _1 H
}
7 d0 s+ |) m3 b; Y// 由代码表还原为波兰表达式& A# B' S- ^) }
void Restore(int *Formula,int *NumSym,int *temp,int count)
& Y8 i, [( D/ n: w& I; l% @ h{
' g* \7 u- w( a' Y% C0 p) x r int i;+ W( [' K/ K) Z) j
for(i=0;i = NumSym[temp];' l' S- O& `" [* M- M
}7 T: \% X: ~" h, G7 q
// 判断是否符合波兰表达式
" z& @" F+ \! ], \/ Y0 o5 ~// 符合的条件是每个运算符号前必须是操作数个数多了运算符个数, P" S, M$ [2 k$ g$ M4 I3 f( f3 L# [
// 且运算符个数为总数减一的一半
9 z3 I& ^7 w1 d* u x, ]int IsOK(int *Formula,int count)5 ~/ J1 g- _5 M7 i7 B, h
{6 ~2 A" z8 Q7 [: x9 \7 A
int i,j;
2 W# Y1 i2 w5 c- Z: C4 H for(i=0,j=1;i- T% S$ u. z- ~, N) q5 M& e if(Formula<0)* U( J. y, `3 r
if(UpZero(Formula,i)>j) j++;
4 |8 t: f9 l0 X6 c& O# } else break;
6 D6 z7 K/ i, P' S if(iint)count/2+1) return 0;
$ S! e0 {* I' V; _ else return 1;! V9 a9 l3 F1 i- W0 i
}; v% R" r" N# W3 y- m4 e
// 查找数组大于0的个数
/ H/ _8 G% T6 f( U3 p- Sint UpZero(int *nArray,int n)2 H' ]" c5 \0 B" H% ? H
{
7 n. r. z, d6 O" u) q3 r int i,result=0;
, }* |4 w3 N" X0 s for(i=0;iif(nArray>=0) result++;
* o0 [* S0 I+ A& _6 m2 X! x8 F return result;
8 A' J3 b2 p2 T! E: u1 K8 y! q. A}
- r- O. U) h2 D9 i8 u// 查找数组中，小于Num的数是否有重复
" X( J5 u( H! E+ a9 F; dint IsDownNumSame(int *temp,int count,int num)
; p0 I# d) A& e: L- B! ?9 a{
+ ~! j" [+ n, E9 ?) J3 i) v" a int i;; i9 ~$ a! c, q1 `* O: F- e
for(i=0;i1 {4 z6 a& p. \5 c; ^' R
{
2 b8 e1 c+ u8 l if(temp < num)7 j& ]3 w+ e6 i
if(FindInt(temp,temp,i) != 0) return 1;7 P& l+ l: J4 M. V* Y) m0 e
}
4 V* ^+ n1 T/ [/ E) N$ r return 0;9 g- Q. r% B J5 n
}/ H ?6 d; u7 X; i1 b$ i
// 查找数所在数组的位置，返回0为未找到
# K1 _$ W4 ]' O/ a. o" Cint FindInt(int *nArray,int n,int len)
! T7 \* K i E& z6 l* L4 W7 F{
3 X( e9 Z! Q! C3 i$ I# D int i;7 p. z+ Q. q+ T( x1 I; T. w- h
for(i=0;nArray != n && i. \6 B" i. }0 z/ B: P7 k( \
if(i>=len) i=0;) l0 j* P" y( m% z" o4 t" h. Y0 c5 p
else i++;
( H1 Q3 z; b3 p5 O* l return i;6 o, ~, D! e9 g, y, l6 s/ N
}4 X% M& p, h; V$ i X4 V
& R5 d9 H" v$ p0 F$ L1 H// 计算算式结果
' { J& O, b* `' X+ }float GetFormulaVal(int *Formula,int count)
+ L; X: I! ^, D1 x3 B; y3 K{
5 `* R0 |5 z: r+ j2 R float result;: H9 n6 B9 ~: E2 c6 s
BinTree *head = (BinTree*)malloc(sizeof(BinTree)); //二叉树头节点
$ R& t; z, T( ^3 N( |: D5 C' k1 M int *nArray = (int*)calloc(count+1,sizeof(int)); //波兰表达式储存数组，首位表示数组有效长度
* l6 [ B- U0 _$ H' s* C3 x, j8 d4 \
int i;
# w" d: X# R5 H: [$ F7 t% a for(i=1;i<=count;i++) nArray = Formula[i-1]; //复制波兰表达式
1 v6 W5 W6 w/ B4 n& C& I nArray[0] = count;
* m" S6 [! h9 f7 s+ W x CreatBinTree(head,nArray); //建立二叉树
. m6 ]. ^- ?8 X, a! g0 i' N- \0 D
result = CalcBinTree(head); //计算二叉树算式4 n* j# H3 Q/ }5 Z
AfterBinTree(head,&FreeBinTree); //释放二叉树空间2 X) [& m% ~3 p, J a$ `
$ i& s8 c6 C; l* A+ _# a free(nArray);2 T& ^; v/ b( ~4 G( j
return result;0 n0 ~0 m7 P$ }2 v) e: K+ h
}
" K. f- T1 i/ s4 ofloat CalcBinTree(BinTree *Tree)
9 x& O7 C, n2 o9 {4 H{8 f3 t; y S: m
- g9 J8 O; M& V2 s6 E; x AfterBinTree(Tree,&AfterNode);
q, P6 \ Z. ~" a return Tree->Data;3 t' D' \; i9 N& b9 |
}
$ `& [8 i X' r5 {/ q" V! m( v" v3 j# p _
// 后序遍历二叉树进行计算,但会破坏二叉树本身0 n$ y( D% v) ~. F6 F& P: _7 P
// 一个结点的结果为左子树 （运算符） 右子树* M5 l. W# | S% `1 M- F3 h1 ]
void AfterNode(BinTree *Tree)
5 }4 w( ^2 w" i- F$ B{
0 v$ n# `. G3 P2 ~: k; V/ K: e switch((int)Tree->Data)
6 K* Z( \ q- ]( R) D9 b! K {
1 Z$ g, I" M/ v: } case -1:
6 b7 m; k" A* B/ B3 R5 B( A$ ^ Tree->Data = Tree->Lchild->Data + Tree->Rchild->Data;6 l/ v# k6 k; u
break;
0 ?% U/ N% K, H8 P6 G$ q case -2:0 }9 A- C) r7 l) h
Tree->Data = Tree->Lchild->Data - Tree->Rchild->Data;+ b$ A1 G4 H" P4 |
break;
' o8 K5 O& S% t( c. L case -3:
q. F2 I, V' X' j Tree->Data = Tree->Lchild->Data * Tree->Rchild->Data;3 A7 L/ v; ~5 t
break;; O# T/ ?& ?* _! Z# m8 H% m/ {; R
case -4:
( Y5 Y: r9 f3 ~8 C Tree->Data = Tree->Lchild->Data / Tree->Rchild->Data;
5 F& s0 h7 i- u: ]" g( U break;4 _4 h; v: w; h1 ~- ]
}& Z2 @7 J V6 \2 s
}
& v1 r6 z1 i+ f4 j1 l1 | T// 打印算式, v) e) ~, Y$ F; G4 W+ C; ]1 x
! `5 Y& H: x' a4 r- ?void ShowFormula(int *Formula,int count)
A- c8 m4 W* o, m6 c8 x8 T{9 g* i9 m) m+ `# }' d# u0 r
BinTree *head = (BinTree*)malloc(sizeof(BinTree)); //二叉树头节点
% J$ B7 [; b$ w f; C* K: f3 c int *nArray = (int*)calloc(count+1,sizeof(int)); //波兰表达式储存数组，首位表示数组有效长度3 ~ P$ G8 H- y! T7 X) h7 }
int i;
1 N2 G* v w" n/ Z6 `/ Q- ^ for(i=1;i<=count;i++) nArray = Formula[i-1]; //复制波兰表达式 _5 k+ O' r4 V3 _5 R, C+ p
nArray[0] = count;! C9 s" Y5 r) A" L; b. i# I9 {
CreatBinTree(head,nArray); ! p& h3 P! t& l; m# t0 m9 m
AfterBinTree(head,&Myitoa); //初始化二叉树字符窜部分
- u3 n f7 l8 B h AfterBinTree(head,&GetFormula); //转化为普通表达式, L6 I; G$ `/ s, _3 c
printf("%s\n",head->Formula);
! z( M r8 R8 T. f. ]0 ^0 M AfterBinTree(head,&FreeBinTree); //释放二叉树空间
) u/ w3 N/ J% _6 [7 q5 G free(nArray);
t2 z4 N4 I5 C& v# k; g , T5 f4 f1 h7 D5 z4 m
}
& ~$ `+ |5 w1 e. N9 o9 ~3 ?; E+ l// 类似计算二叉树
+ d$ r6 V" T; L/ ]// 会破坏二叉树本身( Y/ Z. A; j$ Z+ V
void GetFormula(BinTree *Tree)2 `, l6 Q8 m- R$ J [
{% v) k: C6 `% [. g0 j) U# |
// printf(Tree->Formula);
( ], b8 f9 z3 v: O! h if(Tree->Data <0)
4 t M; l \, s, w {. O2 q1 ~9 E' {
char temp[100];# t( K5 M3 Y* b- A
if(Tree->Lchild->frist < Tree->frist)
* O! m7 d8 {. d0 M1 F+ [$ r; D {0 Z% U) s! x9 w: }0 a5 h
strcpy(temp,Tree->Lchild->Formula);/ W& z p/ d! k: B7 g
strcpy(Tree->Lchild->Formula,"(");
' ]( ]) W; S2 y- x5 J- E strcat(Tree->Lchild->Formula,temp);
/ ?( z( G p9 }1 s2 j. e7 m! A3 a( h, l strcat(Tree->Lchild->Formula,")");' n# S9 F z4 T; \
}
- d( W5 y) m9 T* X2 |6 D if(Tree->Rchild->frist < Tree->frist
- N) |- W$ z" j$ P/ l || (int)Tree->Data == -2 && Tree->Rchild->frist == 0! `( B9 o4 S- {$ a
|| (int)Tree->Data == -4 && Tree->Rchild->frist != 2)- W n1 c0 G! U9 h) b
{
: D0 P' f, b- I: I9 G strcpy(temp,Tree->Rchild->Formula);
3 ?' ^1 R6 u* b7 e: l- K" G strcpy(Tree->Rchild->Formula,"(");
- K! ~% {# q; d strcat(Tree->Rchild->Formula,temp);
1 }. v5 ^0 a4 b& } strcat(Tree->Rchild->Formula,")");
- f o3 c Q7 @ }
4 B( R2 Z! v) c# W strcpy(temp,Tree->Formula);
; ~4 s# U) \* l: J! x strcpy(Tree->Formula,Tree->Lchild->Formula);9 B5 M8 [6 U0 d, I& @& i
strcat(Tree->Formula,cSym[-(int)Tree->Data]);0 f5 s) @! ^9 l0 L/ L
strcat(Tree->Formula,Tree->Rchild->Formula);# \+ C9 E' v& b; m/ u5 b* W
}9 h$ ~" [# @6 O" m
}9 O' J/ [% |' {1 B& S
// 对二叉树字符串部分赋值3 r7 S e2 \7 F5 Y0 a! i
void Myitoa(BinTree *Tree)
- t2 y) I h, z0 j C- M' F{6 _$ \2 B: ~% [% q$ s7 R7 S# l
if(Tree->Data>=0)
2 ]' ^* K% G/ v, ~$ P( h$ o) M0 l/ A {% T6 ?) }! m) s- m( h0 x9 o) k
itoa((int)Tree->Data,Tree->Formula,10);
3 n, f, P% G. G& A H, ]) ?/ q+ b; M Tree->frist = 2;' P$ }# u) z( ^% u2 Z
}) i' o/ V, z) E) X) t
else6 S8 N$ ~& t$ k; A9 n, f, a4 j
{
3 q( A' q5 U, m7 l" j ]- v Tree->frist=Tree->Data < -2 ? 1:0;/ {! t* ~2 v5 g- c: H
strcpy(Tree->Formula, cSym[-(int)Tree->Data]);0 j$ }, Y9 b$ X, R3 V
//Tree->Formula[1] = 0;. `. z: W4 E; R5 i
}
: |8 u1 d& {4 {! Q# O; l# c* u}$ v. [# o6 {% ]
//从一个波兰表达式建立一个二叉树链表，需指定一个头节点' C% d# x, C/ `4 l
void CreatBinTree(BinTree *Tree,int *nArray)
- ]$ R/ y' D0 D# B# {{
, l* n) F$ j1 ^: E& E' V/ D Tree->Data = nArray[nArray[0]--];- g! Z' O. S9 D$ ^! r
if(Tree->Data < 0)* ^; g8 h* ~7 s$ J$ H
{) |0 d# J w2 A: f
Tree->Rchild = (BinTree*)malloc(sizeof(BinTree));8 R4 y5 o' D; ?% J8 p" G4 q
CreatBinTree(Tree->Rchild,nArray);3 A* {) r4 O0 d
Tree->Lchild = (BinTree*)malloc(sizeof(BinTree));5 k+ o( z6 f- v3 X$ p$ p& o7 D q
CreatBinTree(Tree->Lchild,nArray);3 q% e( a2 W3 [( C
}. L# E- ^3 _$ {
else9 n" D" H. N" r `
{
1 y/ f9 ]* \2 Z- C% @3 | Tree->Lchild = 0;& ^" j! D* k( O: |0 G0 i/ S
Tree->Rchild = 0;) L3 {2 `, e- M3 {0 h4 Q5 F7 o
}
6 l, `8 k8 x3 s; x6 a& M6 }3 k& k8 p
" N" `/ E& F5 \4 g4 x5 ~+ F}3 h1 S8 \5 B/ [/ a7 m
5 j9 c& R; `, Q// 释放二叉树空间
$ i% D! R3 c; B! gvoid FreeBinTree(BinTree *Tree)
% c; J" a/ i; y+ O& \* z{
3 k) B6 n3 { p6 q free(Tree);/ d2 x% O) G! F6 W9 q( a" A
}
: Y6 v& J/ G# ~; P3 V9 f// 后序遍历二叉树
9 `/ k! j& W, a8 }0 U// 方便其他函数调用，func为要对各个结点进行操作的函数指针" E; {8 {9 r, o
void AfterBinTree(BinTree *Tree,void func(BinTree*))
, y; V g, _6 @* P( L; \{$ p! P: G9 p2 Z. Y4 C& @: Q9 t
if(Tree)4 s! o# [& m0 ?" p4 ~$ X8 x
{$ @7 ]( P) D+ c& \- Q' a# P
AfterBinTree(Tree->Lchild,func);9 V P# Z8 l8 m
AfterBinTree(Tree->Rchild,func);
: I' V8 k4 ~" F& G func(Tree);
6 D. q6 n" [* c) ~) ?+ n3 e( \ }9 p) ^0 S8 s" O7 ~
}
) ^8 s5 |4 \" X. t, f% u |
|
楼主: 考拉
/1 
IP卡
狗仔卡
发表于 2004-5-2 15:40:00
显身卡
发表于 2004-5-2 15:50:00
% w9 C. s% `$ i5 S