栈和队列
http://www.cnblogs.com/sharpCode/archive/2011/04/07/2008841.html
背包问题
View Code
表达式求值
View Code
1 #include <stdio.h>
2 #include <stdlib.h>
3 typedef char ElemType;
4 typedef struct LNode
5 {
6 ElemType ch;
7 struct LNode *next;
8 }LNode ,*LinkList;
9 typedef struct DbLNode
10 {
11 double ch;
12 struct DbLNode *next;
13 }DbLNode ,*DbLinkList ;
14 typedef DbLinkList DbLinkStack;
15 typedef LinkList LinkStack;
16
17 void initDbStack(DbLinkStack *S)
18 {
19 *S=NULL;
20 }
21 void initStack(LinkStack *S)
22 {
23 *S=NULL;
24 }
25 void Push(LinkStack *S,ElemType e)
26 {
27 LNode *p;
28 p=(LNode *)malloc(sizeof(LNode));
29 p->ch=e;
30 p->next=*S;
31 *S=p;
32 }
33 void PushDb(DbLinkStack *S,double e)
34 {
35 DbLNode *p;
36 p=(DbLNode *)malloc(sizeof(DbLNode));
37 p->ch=e;
38 p->next=*S;
39 *S=p;
40 }
41 bool Pop(LinkStack *S,ElemType *e)
42 {
43 if(*S)
44 {
45 LNode *p;
46 p=*S;
47 *S=p->next;
48 *e=p->ch;
49 free(p);
50 return true;
51 }
52 else
53 {
54 return false;
55 }
56 }
57
58 bool PopDb(DbLinkStack *S,double *e)
59 {
60 if(*S)
61 {
62 DbLNode *p;
63 p=*S;
64 *S=p->next;
65 *e=p->ch;
66 free(p);
67 return true;
68 }
69 else
70 {
71 return false;
72 }
73 }
74 bool getTop(LinkStack S ,ElemType *e)
75 {
76 if(S)
77 {
78 *e=S->ch;
79 return true;
80 }
81 else
82 {
83 return false;
84 }
85 }
86 bool stackEmpty (LinkStack S)
87 {
88 if(S) return false;
89 else return true;
90 }
91
92 bool OpMember(ElemType ch)
93 {
94 if(ch=='(' || ch==')' || ch=='+' || ch=='-' || ch=='*' || ch=='/' || ch=='#')
95 {
96 return true;
97 }
98 else
99 {
100 return false;
101 }
102 }
103 int order(ElemType op)
104 {
105 switch (op)
106 {
107 case '#':
108 {
109 return -1;
110 }break;
111 case '(':
112 {
113 return 0;
114 }break;
115 case '+':
116 case '-':
117 {
118 return 1;
119 }break;
120 case '*':
121 case '/':
122 case ')':
123 {
124 return 2;
125 }break;
126 default :
127 {
128 return -100;
129 }
130 }
131 }
132 int precede(ElemType a,ElemType b)
133 {
134 if(order(a) >= order(b) ) return 1;
135 else return 0;
136 }
137 void transform(char * suffix,char *exp )
138 {
139 LinkStack S;
140 initStack(&S);
141 Push(&S,'#');
142 ElemType *p;
143 ElemType ch;
144 ElemType e;
145 int k=0;
146 p=exp;
147 ch=*p;
148 while(!stackEmpty(S))
149 {
150 if(!OpMember(ch)) suffix[k++]=ch;
151 else
152 {
153 switch (ch)
154 {
155 case '(': {Push(&S,ch);}break;
156 case ')':
157 {
158 Pop(&S,&e);
159 while(e!='(')
160 {
161 suffix[k++]=e;
162 Pop(&S,&e);
163 }
164 }break;
165 default :
166 {
167 while(getTop(S,&e) && precede(e,ch))
168 {
169 suffix[k++]=e;
170 Pop(&S,&e);
171 }
172 if(ch!='#') Push(&S,ch);
173 }break;
174 }
175 }
176 if(ch!='#') ch=*++p;
177 }
178 suffix[k]='/0';
179
180 }
181 void printSuffix(char *suffix)
182 {
183 printf("输出后缀式:");
184 char *p;
185 p=suffix;
186 while(*p!='/0')
187 {
188 printf("%c",*p);
189 p++;
190 }
191 printf("/n");
192 }
193 double Operate(double a,char ch,double b)
194 {
195 switch (ch)
196 {
197 case '+': return a+b;break;
198 case '-': return a-b;break;
199 case '*': return a*b;break;
200 case '/': return a/b;break;
201 default:
202 return 0;break;
203 }
204 }
205 double evaluation(char *suffix)
206 {
207 DbLinkStack S;
208 initDbStack(&S);
209 char ch;
210 double a,b;
211 double result;
212 ch=*suffix++;
213 while(ch!='#')
214 {
215 if(!OpMember(ch)) PushDb(&S,ch-48);
216 else
217 {
218 PopDb(&S,&b); PopDb(&S,&a);
219 PushDb(&S,Operate(a,ch,b));
220 }
221 ch=*suffix++;
222 }
223 PopDb(&S,&result);
224 return result;
225 }
226 void main()
227 {
228 char suffix[100];
229 char exp[100]="2+(1+(4/2-1))*3#";
230 transform(suffix,exp);
231 printSuffix(suffix);
232 printf("%f",evaluation(suffix));
233
234 }
车厢调度
View Code
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4 typedef char ElemType;
5 typedef struct LNode
6 {
7 ElemType elem;
8 struct LNode *next;
9 }LNode ,*LinkList;
10 t