 该用户从未签到
|
几天前的东西，现在没有大兴趣了
|
过重复代码过多,比如二叉树的建立等等
: w, ^+ o. {" v( J+ B, K# {# f- `- X0 j4 W
#include
' U% e5 k5 [, ]* b% P#include : [& {9 s1 K7 T4 Y/ T/ u
, `* R( n" P# r! |( e( e
typedef struct node
" c" I) `' L0 z{
8 o. V' \: f9 \5 |/ W/ A$ Z9 S1 x* R float Data;9 Y f/ }7 r, S( u. q
char Formula[100];
+ ~! Y1 X- b- E1 m! G$ \' F int frist; //优先级$ D6 W. A) q2 r+ F% F* c4 V
struct node *Lchild;0 N- y3 C1 r! z3 W
struct node *Rchild;
! j; C& v3 c7 O( U% z" _( F8 Y+ Q2 j} BinTree;
- ]. [8 q" B$ Uvoid CreatBinTree(BinTree *Tree,int *nArray);
3 i! E! m9 L7 }: [6 {: u7 q, E! \- evoid FreeBinTree(BinTree *Tree);
& u, ^$ y+ A& `% q' Evoid AfterBinTree(BinTree *Tree,void func(BinTree*));
/ e( l; h; i( O# a* w4 q! B' lfloat CalcBinTree(BinTree *Tree);+ }, j& g6 E9 {* N6 v# H' ?
float GetFormulaVal(int *Formula,int count);
5 C& L% n3 f% m% tvoid ShowFormula(int *Formula,int count);
7 c/ e: S6 J: m. E# B1 X8 vvoid AfterNode(BinTree *Tree);8 e$ c% ?* V2 S& h! }4 x
void GetFormula(BinTree *Tree);* D0 d' c$ \0 q
void Myitoa(BinTree *Tree);
- J/ W7 W5 g, T4 Q8 J- Vint EnumFormula(int *FormulaNum,int num,int sum);# u# j: c" ]+ P
void Restore(int *Formula,int *NumSym,int *temp,int count);& J* T" S, |7 k2 x7 q$ F$ _; v
int IsOK(int *Formula,int count);
4 T: e; A" d% b7 E1 f: p4 J& Gint FindInt(int *nArray,int n,int len);* Z2 v5 K0 A& q6 c4 M8 \: {
int UpZero(int *nArray,int n);
+ E5 Z% h2 p* [5 iint IsDownNumSame(int *temp,int count,int num);
" {* m7 C% }5 G3 } m) O/ C5 C. z6 |% K
const char cSym[5][2] = {"","+","-","*","/"};
, I, \4 L5 S" B$ @( y* w
( f4 v8 d6 j9 t) i3 Nint main(int argc, char *argv[])9 ^# f6 d) z' S( a/ w
{' F; Y( S" }# `7 U9 f4 P7 L* W
int i,n,*Array;# ~. } H& r5 z! d( {0 Z
! |$ h: e8 d0 o' y- S
//printf("几个数？");" H" O$ h" R) N' I$ m1 Q0 u% @5 ?
//scanf("%d",&n);* \* C/ d7 I. n( G2 f/ V) b
n =4; ?+ s+ X& L, }9 D) i4 G
Array = (int*)calloc(n,sizeof(int));4 _; Z4 o! i6 j0 Z5 c( ]- m# H
printf("请输入%d个数（用回车或者空格分开）：",n);; M1 w- v# S4 _+ O6 M" P0 ]) Y
for(i=0;i7 A0 Y, J: k+ b5 p$ ]) t
scanf("%d",&Array);
- N! F: I0 q( x printf("总计%d个式子\n",EnumFormula(Array,n,24));
: h3 O8 c( V$ P/ B! J4 Y" C p% s free(Array);
2 K# G" u4 q0 ^9 J# z+ o
" L" p. t( ^' k/ f system("PAUSE");
+ T, N( F3 E$ ~- D1 H return 0;5 _. E/ ]( p( E
}( v: t1 _' ] M- \5 Q6 t/ ?
' D* L) G! _6 L$ R! ^( v' K
int EnumFormula(int *FormulaNum,int num,int sum)
V- B) x- S! S2 S! N{9 F3 x; l, c% o+ x, {
int result = 0;: o2 P+ q; S; r
int *NumSym = (int*)calloc(num+4,sizeof(int)); //操作数运算符组成的可枚举组
$ l* O/ j+ X# M int *Formula = (int*)calloc(num*2-1,sizeof(int)); //波兰表达式储存空间' Y3 M, q% F3 [
int *temp = (int*)calloc(num*2,sizeof(int)); //波兰表达式的代号表示空间
* s Y$ ~: ]7 b+ _- B* Q1 O E' t int i,j;
' N8 u- ]" b, R2 \" g for(i=0;i = FormulaNum; //载入进行穷举的操作数
- {# A7 k& W) d. H7 Z for(j=0;j<5;j++) NumSym[i+j] = -j-1; //载入进行穷举的运算符号. `, o8 ]0 F' |5 b/ w I% ~
4 V2 s% E& S0 \- |3 G0 s; B! r9 z5 F for(i=0;i = 0;4 x& B3 T* J$ i- N6 \
// 穷举开始，结束的标志为波兰表达式代号空间最后一位已进位，即前面各位已穷举完成
0 q/ g- D7 Y* V6 M' ]9 X6 |( M5 Z while(temp[num*2-1] == 0)
! U: [- z( o) M5 |8 m5 \. x- a {
) }$ J5 h' u& C; C5 b5 q, R if(!IsDownNumSame(temp,num*2-1,num)), Z6 |; i* y B/ R! l: ], M4 n
{# K. a* Q% f2 C5 F
Restore(Formula,NumSym,temp,num*2-1); //还原波兰表达式7 o( e; e' m7 w9 D6 }
if(IsOK(Formula,num*2-1))9 C) O3 W: N% n( O* V
{
( Z, }1 w9 g4 d" O5 j$ U6 m float t; //结果偏差( u& K' g( ^5 F# | u
t= GetFormulaVal(Formula,num*2-1) -sum;+ y* Z6 x! v, C/ v i! h$ R' \ r
if(t>-0.01 && t <0.01) //结果为浮点数，只能进行近似比较3 t5 W5 a2 Z4 A4 X4 F" |1 M
{% k& K7 H8 ~" B
result++; k6 I& Z. o) u; b' K) _4 y
ShowFormula(Formula,num*2-1);# {7 J. \; a' U; E# P
}+ K. ^' ~; m# {# } A& b: `
}
; }) Y. _2 V( u; I9 r }
7 C' G# w& }8 k r temp[0]++; //穷举动力 P- g- x0 R# e O0 z
for(i=0;temp > num+3 && i//代码空间类进位4 j3 Y$ k; r; e7 o' n
{# v8 x7 q. P# b1 I0 s9 L8 n
temp =0;
- q) ?; _7 P4 x! `) X& d1 V temp[i+1]++;
1 ~5 |2 m3 O" M" g8 L+ V0 O }
0 U: z2 m! q2 S) M( G }
! c. t# ?% G7 B9 w% k% A7 t$ V // 释放内存+ Z$ O s \9 q2 h! }
free(temp);
0 [' t D0 c% N/ p
% h Q4 p" `/ a, Y, U //free(Formula); //？？此处不知为什么会出现错误' y5 L4 _6 \; o5 o) i
free(NumSym);
; W0 g" _. Z$ p return result;
" ^8 Q( d6 R$ M$ W: u7 X! T- j}7 S' S, a. I' ?, x6 \+ j1 g
// 由代码表还原为波兰表达式, l. l- ^' p- X. e0 i
void Restore(int *Formula,int *NumSym,int *temp,int count)
7 F7 }8 a h G' M$ i3 J9 M{
F6 G- A9 |+ X# v* Y+ y& b0 W int i;# n n/ N4 d5 L0 I, L
for(i=0;i = NumSym[temp];
2 V" I3 q v( [1 D2 _ X8 l' G}* A$ c. d- o9 M" j% S- r* e8 a
// 判断是否符合波兰表达式
% h$ m3 ^ }& W& v// 符合的条件是每个运算符号前必须是操作数个数多了运算符个数
3 [# J+ b' R2 t4 z8 `% E. r' s* o// 且运算符个数为总数减一的一半, {2 {* h) q+ N, U- `6 s7 }
int IsOK(int *Formula,int count)
4 d, ^# R* |* Z {8 x; `{
H6 L! |- G! S int i,j;6 Z: y8 ^1 s/ X# l
for(i=0,j=1;i) U6 z) `5 \ s5 }" Q$ F! S6 p if(Formula<0)
1 r- n A' T g if(UpZero(Formula,i)>j) j++;
- G$ c# i3 ^+ ^2 X" L' C else break;7 d0 B0 G/ h. x4 G8 b( Q: ^
if(iint)count/2+1) return 0;
9 z7 K6 ~" e; s, N3 F0 K else return 1;, Z& E& o3 f, H0 E4 H
}3 Z) S# d y( b! D2 x
// 查找数组大于0的个数
% e% y9 M6 s. _! e% a" Z' Kint UpZero(int *nArray,int n)) e0 t0 ~4 _( T8 U" [
{, F: ?, n; N1 C9 u9 _ l
int i,result=0;
G; r( |+ v/ i3 R5 S6 m: c for(i=0;iif(nArray>=0) result++;- C0 X! }: Y# k4 ~# n) ]4 K
return result;' Y& x/ |- N9 V. Q; K8 o4 v
} M; G# d" H) a6 d9 d
// 查找数组中，小于Num的数是否有重复5 y0 G- G) n# Q T! D
int IsDownNumSame(int *temp,int count,int num)9 K8 @( R; \$ X. W3 h
{
4 g2 x; g5 h. l/ J int i;9 [2 R: X# J0 F" R! g8 W
for(i=0;i+ w i# Q+ }8 g* [) x# _# o: S
{
: U' y6 n( r! j/ J1 u0 d if(temp < num)( l# O) L" E; {
if(FindInt(temp,temp,i) != 0) return 1;# O# m: T' R, V! T$ [! J5 `# I
}( {2 C* M( _" d* B0 i5 h% i
return 0;
; b4 z/ v, l& w1 S( K}
0 H5 {% n: z0 i; L+ j6 A& t// 查找数所在数组的位置，返回0为未找到6 t+ b3 Q7 u) y9 }) C
int FindInt(int *nArray,int n,int len). q, w& U+ q9 H
{
9 O/ k- G! n4 P$ Z! Q int i;9 U4 C# t' v3 V6 c1 @
for(i=0;nArray != n && i8 B' m) q! I0 Q) q \" }
if(i>=len) i=0;5 ?( s7 F8 _% p6 Y/ q+ y9 x
else i++;
0 R( _3 k+ @6 N* ~6 X. r% c" l' y; X return i;
% t8 x( n7 {+ e+ G9 Z7 P0 K% n1 c}7 v+ W1 x: H* a
: E) ? g# [/ P6 d# @
// 计算算式结果
0 Y$ n8 a! n ]0 ~float GetFormulaVal(int *Formula,int count)
- o# O2 G1 B. O: A6 N ~% u{; H/ B. i( y" b$ _5 I2 m3 G
float result;
) X9 F+ \' N" S8 W BinTree *head = (BinTree*)malloc(sizeof(BinTree)); //二叉树头节点- M3 T% {# M% u7 a
int *nArray = (int*)calloc(count+1,sizeof(int)); //波兰表达式储存数组，首位表示数组有效长度
" i: j- |, E& d6 S( M& z+ `
/ L0 y2 \ V4 u0 G- d1 u; h8 f int i;9 H) h4 G& T& _8 \. K8 v8 s' s0 w* ^
for(i=1;i<=count;i++) nArray = Formula[i-1]; //复制波兰表达式* T8 m0 G( X& [& q& {
nArray[0] = count;
* l, G( H8 O6 ~ CreatBinTree(head,nArray); //建立二叉树$ o$ b/ r, W& M( _9 {% ?( A
* w( a% R Z/ }& }- y1 }
result = CalcBinTree(head); //计算二叉树算式
9 V$ t0 l' y4 {2 x1 b AfterBinTree(head,&FreeBinTree); //释放二叉树空间% U Y; r F# ]! S% }3 l
" k# K$ H" w* f5 X; X- h9 Y0 ]
free(nArray);, f5 I+ J$ a' v" Y) ]# J- X: e3 r8 A
return result;
# {) e' m# T. R0 X4 L}, Q' G1 n! U" C+ x) ?- |' E
float CalcBinTree(BinTree *Tree)
' L, ?- r7 K; W" Y9 v' k. R{
; G8 v% f- M W/ k2 [ " L3 F$ I0 \: g; x# Z( r; g
AfterBinTree(Tree,&AfterNode);
7 U( ~" R" t& W7 Z; n5 C8 p return Tree->Data;" I& }6 O2 @7 N, M+ W
}( g! S# C+ ~0 i" s, X: Q8 [3 i2 i
9 k# V/ X8 s: T X
// 后序遍历二叉树进行计算,但会破坏二叉树本身& }; a& s3 G' h1 Z* Q+ |
// 一个结点的结果为左子树 （运算符） 右子树
9 O, Y* Q/ `0 f, `void AfterNode(BinTree *Tree) R' l7 h5 Q' \
{" }6 i2 u! X9 R1 g
switch((int)Tree->Data)9 _9 _8 O5 b! ]' O, i
{
; Y# Z! D, t- a/ Q; s case -1:2 s: n3 M5 j8 B6 ]3 v* A
Tree->Data = Tree->Lchild->Data + Tree->Rchild->Data;
0 o% }, H- J& W$ j break;
" y( A5 b' b# r3 W+ @/ z case -2:% U8 K' F5 i( P" s5 p
Tree->Data = Tree->Lchild->Data - Tree->Rchild->Data;
$ U8 { `/ r7 m j2 C break;! `" j# B. f* d, n
case -3:
! R9 C: T8 X# O2 @: X; B Tree->Data = Tree->Lchild->Data * Tree->Rchild->Data;3 W) C8 L* l" }3 t+ ?# [3 D
break;3 F" W8 w) e1 w/ I0 N, R* V* D- b% k
case -4:; @. z1 a4 ~: r9 A) v( y& o6 a" q
Tree->Data = Tree->Lchild->Data / Tree->Rchild->Data;
$ X- G1 s! n2 Q& U break;4 t j2 Q$ c# h7 i
}
) a- }7 x& e! Z! t( I}
6 e/ O# q0 @- b- k' {# L; v// 打印算式9 U0 B" x3 j& x/ Y2 M
2 L" e! J: ^3 P6 c* B/ x. mvoid ShowFormula(int *Formula,int count)$ L: I1 u! v, ?) x1 V6 o1 X
{
* T% R8 H- f, Y3 m7 s4 w BinTree *head = (BinTree*)malloc(sizeof(BinTree)); //二叉树头节点
9 G; K; Q" [ X* J8 G int *nArray = (int*)calloc(count+1,sizeof(int)); //波兰表达式储存数组，首位表示数组有效长度( p$ ]! D, N1 \, O
int i;$ L) p, e5 ~+ f% j7 O
for(i=1;i<=count;i++) nArray = Formula[i-1]; //复制波兰表达式$ d; V1 j0 {8 i4 @1 O% U0 X. r5 E
nArray[0] = count;+ N0 G s; A9 V9 ~3 a7 q
CreatBinTree(head,nArray);
. h' m. }% ]: n* L @# ? AfterBinTree(head,&Myitoa); //初始化二叉树字符窜部分
' x4 p! S3 Q2 H" P3 y- P0 r0 Z AfterBinTree(head,&GetFormula); //转化为普通表达式8 C; C$ ]4 U) W, G. s& t
printf("%s\n",head->Formula);1 E! Z$ g. p; z/ V/ [$ p; }
AfterBinTree(head,&FreeBinTree); //释放二叉树空间
! Y4 C# a6 m0 c7 G) ]$ w free(nArray);
% u. _5 P" A! n( f7 t ; q4 G2 A! n4 e4 F: b, C% j8 @' B- B, S
}
4 k. f& i- k0 k: ~# f( p// 类似计算二叉树! s7 j! p, V7 r3 C
// 会破坏二叉树本身
% Z1 y6 x4 g9 g( @3 Dvoid GetFormula(BinTree *Tree)
7 {8 H+ c& A$ c4 B# Z{3 {, {# z$ v0 z1 y2 Y1 V1 v7 L5 A; x
// printf(Tree->Formula);# E. Z9 @/ \6 Y
if(Tree->Data <0) O# B8 |8 |7 M4 r; B% Z* `" C
{6 h- R N( `9 a, `4 |/ N0 G! p
char temp[100];# _& A4 \: D+ i$ q
if(Tree->Lchild->frist < Tree->frist)8 l! d: e$ o7 h+ }
{
w& g- k+ |2 Q) h strcpy(temp,Tree->Lchild->Formula);( y: L6 P8 F4 o0 L
strcpy(Tree->Lchild->Formula,"(");- K2 b% I% {. w# `( @& M
strcat(Tree->Lchild->Formula,temp);5 N5 z: W# b: l
strcat(Tree->Lchild->Formula,")");3 Z- }+ v8 D" }: X4 T% S
}
3 R0 t* ?2 Y2 V% s d( @- f* [ if(Tree->Rchild->frist < Tree->frist
2 _# m. ?0 Z. l6 ~8 u5 t* Y || (int)Tree->Data == -2 && Tree->Rchild->frist == 0
Z1 @0 | a9 ~ || (int)Tree->Data == -4 && Tree->Rchild->frist != 2)
" J" B$ \- w$ ? {
* U% I, ?, t# I j8 W# d5 L' J strcpy(temp,Tree->Rchild->Formula);' s; K# k! K5 R4 I
strcpy(Tree->Rchild->Formula,"(");: K! E* _5 I X# r. j! v9 `
strcat(Tree->Rchild->Formula,temp);9 L1 g1 d" z2 B- t5 c
strcat(Tree->Rchild->Formula,")");
2 x& w- f' H/ ]8 O }) `# F$ x l7 Z* Z
strcpy(temp,Tree->Formula);
7 k7 b* J. t+ B V* [" J strcpy(Tree->Formula,Tree->Lchild->Formula); n3 h; _- N$ b- M# z
strcat(Tree->Formula,cSym[-(int)Tree->Data]);
" B8 c8 n# |% P. ? k( Q strcat(Tree->Formula,Tree->Rchild->Formula);) m$ E2 S- m2 M5 {" d" Q' ^
}4 ~4 ]7 i- B" |1 d) V/ H" ?
}
0 E( b; h7 o2 v7 [8 y// 对二叉树字符串部分赋值
1 W; a" J9 L0 L- F: j0 Z! Z; o( Lvoid Myitoa(BinTree *Tree)
! a/ t0 t0 f! B7 j) s{! g; i/ n8 L. b1 I7 W
if(Tree->Data>=0)
3 |- N8 l; k) P+ L2 X' S7 L4 M {$ O/ k+ g8 T0 G8 G
itoa((int)Tree->Data,Tree->Formula,10);
( R8 s" d; s | Tree->frist = 2;
. O8 N9 p8 c" C4 p% q/ u2 N }
, D, O$ v0 A% D/ c else
6 B1 T) a# V1 f2 V7 ]( L- Q5 K {2 p. k6 C: I& s
Tree->frist=Tree->Data < -2 ? 1:0;2 L! U. S7 g0 \' L9 ^/ m+ q
strcpy(Tree->Formula, cSym[-(int)Tree->Data]); S0 p& ]+ J( C5 U1 ^
//Tree->Formula[1] = 0;
2 J% S+ A" Y! N- k0 o2 W }) x9 f `' \8 _- i
}
. x$ ]# J* C6 u2 i//从一个波兰表达式建立一个二叉树链表，需指定一个头节点
+ U: J- c! w6 r0 C$ f- M8 q% @9 {void CreatBinTree(BinTree *Tree,int *nArray)
. J" F8 e+ R+ w6 ^& y6 r{6 a# P" }0 u; b2 K' t
Tree->Data = nArray[nArray[0]--];
% i/ ?/ q* X% n1 ~: P- t if(Tree->Data < 0)( X" k! e- }- `2 K' r
{
6 E' f& n9 r5 W4 s2 B7 S Tree->Rchild = (BinTree*)malloc(sizeof(BinTree));9 y1 z1 f7 h# g
CreatBinTree(Tree->Rchild,nArray);! _4 c2 Z: n. H! i. s. `" r
Tree->Lchild = (BinTree*)malloc(sizeof(BinTree));4 i3 h+ O5 q# l z( i3 v
CreatBinTree(Tree->Lchild,nArray);
5 U6 z4 E, V/ e0 E8 Y }+ c4 a/ m1 u1 W7 L, Z
else
$ W! z0 b6 y1 \$ H6 U# m {+ U& J$ [# r+ b- C; X4 u8 K7 q
Tree->Lchild = 0;7 f! B$ j+ }0 |, y- j3 |' K
Tree->Rchild = 0;
1 I$ |6 G% U8 y3 d: d& C, W5 P% M3 j }: U3 s3 o" F+ H3 w% t. S5 h. ^) F# S" q
' K+ l: O2 P2 D
}
' |$ l, ]' }+ E2 ^: K3 V4 w
/ \2 [1 v+ C- ~! f& u1 Q, Z// 释放二叉树空间3 M z# @7 J, U- I9 c
void FreeBinTree(BinTree *Tree)# O# G u$ i4 z2 _) K$ W
{3 s- O6 t2 R/ n1 Z- ^$ m; [
free(Tree);
, u E* x, X1 P1 \9 _. f! m( d# c}
7 V' Y1 w6 p, |3 `. D4 ]# o// 后序遍历二叉树: J! ^+ B$ m) S
// 方便其他函数调用，func为要对各个结点进行操作的函数指针9 R4 R2 ?/ @+ E. o
void AfterBinTree(BinTree *Tree,void func(BinTree*))
! c# u4 w8 N/ D- R: ~! _# K; n{
' d) O+ v9 b M8 r; D5 [ if(Tree) ~4 V# s6 O1 c
{
# e" ?6 |- y( P3 C AfterBinTree(Tree->Lchild,func);& s* W+ D6 w( V3 ?7 L2 G" n: N! [
AfterBinTree(Tree->Rchild,func);
: o& O. H9 A. Z! v0 w func(Tree);7 A9 r4 E( |% P; `# @; R
}' q) E0 u% t7 a8 g: S( F
}+ P8 @$ ?* l" ~3 G8 i
|
|
IP卡
狗仔卡
发表于 2004-4-27 17:53:00
QQ好友和群
QQ空间
腾讯微博
腾讯朋友
收藏
分享
顶
踩
转发到微博
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
抢沙发
千斤顶
显身卡
发表于 2004-5-12 19:03:00
x,o1,o2,o3,ox 进行的计算" Z1 K$ Q, x0 U( |* |7 a
操作数串: s1,s2,s3,s4# ]# k4 K- J6 i
特征马: v1-o1-v2-v12-o2-v3-v123-o3-v4 这是按照p1,p2,p3的次序且v1>v2,v12>v3,v123>v4 Y' B+ N3 \2 U" ?
0 c& a3 f. j4 j& D4 P0 Z
/ K$ P6 @! s4 R- k( f% }+ d
/1 
