, , :
( | 1 |
+ | 2 |
* / | 3 |
. S , , , , :
1) S , ;
2) S , ;
3) S , , ; ( ) ;
4) S , , , ;
5) S, , .
, .
-, , , , .
, (15.1) :
1 | AB+CD+*E | R 1=A+B |
2 | R 1CD+*E | R 2=C+D |
3 | R 1 R 2*E | R 1= R 1* R 2 |
4 | R 1 E | R 1= R 1E |
5 | R 1 |
R 1 R 2 .
a + b * c +(d * e + f)* g. . abc *+ de * f + g *+. , .
S = a + b * c +(d * e + f)* g . .
, .
a , + . b . :
= ab | |
+ |
* , .. . ,
= ab | |
* | |
+ |
S +. , * + , , , .
= ab *+ | |
+ |
S (, , d ,
|
|
= ab *+ d | |
( | |
+ |
S *. , , * . e :
= ab *+ de | |
* | |
( | |
+ |
+, .. * , , + . f :
= ab *+ de * f | |
+ | |
( | |
+ |
S , ) ( +), ( . :
= ab *+ de * f + | |
+ |
* , g :
= ab*+de*f+g | |
* | |
+ |
S , , , , :
= ab *+ de * f + g *+ |
, , .
, , :
...
struct Stack {
char c; //
Stack *Next;
};
int Prior (char);
Stack* InS(Stack*,char);
Stack* OutS(Stack*,char*);
void main ()
{
Stack *t, *Op = NULL; // Op
char a, In[50], Out[50]; // In Out
int k = 0, l = 0; //
puts(" Input formula: "); gets(In);
while (In[k]!= '\0') { // In
// ),
if (In[k] == ')') {
while ((Op -> c)!= '(') { //
Op = OutS(Op,&a); //
if (!Op) a = '\0';
Out[l++] = a; // Out.
}
t = Op; //
Op = Op -> Next;
free(t);
}
// In , Out
if (In[k] >= 'a' && In[k] <= 'z') Out[l++] = In[k];
// ,
if (In[k] == '(') Op = InS(Op,In[k]);
/* , Out */
if (In[k] == '+' || In[k] == '' || In[k] == '*' || In[k] == '/') {
while (Op!= NULL && Prior (Op -> c) >= Prior (In[k])) {
Op = OutS(Op,&a); // Out[l++] = a; // Out
}
Op = InS(Op,In[k]); //
|
|
}
k++;
} //
// ,
while (Op!=NULL) {
Op = OutS(Op,&a);
Out[l++] = a;
}
Out[l] = '\0;
printf("\n Polish = %s", Out); //
}
//======= =========
int Prior (char a) {
switch (a) {
case '*': case '/': return 3;
case '': case '+': return 2;
case '(': return 1;
}
return 0;
}
// ============== =============
Stack* InS(Stack *t, char s) {
Stack *t1 = (Stack*) malloc(sizeof(Stack));
t1 -> c = s;
t1-> Next = t;
return t1;
}
// ============== ===============
Stack* OutS(Stack *t, char *s) {
Stack *t1 = t;
*s = t -> c;
t = t->Next;
free(t1);
return t;
}
(hashing ), , , -. i = h (key), -. - , -.
() .
, , . , .. (key). .
.
N , 2 N .
- -
, ( -), , -:
i = h (key);
key , i , .. (-), .
- i . , (-), .
- , , - , :
:
;
.
-
- , -.
- , .
, h (key), . .
-
- , .. . , , - , . , - , , , . -.
|
|
. key m. . :
int h(int key, int m) {
return key % m; //
}
m = 10 - .
m = 100 - .
, . - m ( m = 256).
int h(char *key, int m) {
int s = 0;
while(*key)
s += *key++;
return s % m;
}
, , , abc cab.
, , -.
int h(char *key, int m) {
int len = strlen(key), s = 0;
if(len < 2) // 0 1,
s = key[0]; // key[0]
else
s = key[0] + key[len1];
return s % m;
}
, , abc amc.
, ( ) .
, 32- , - 10 :
int h(int key) {
key *= key;
key >>= 11; // 11
return key % 1024; // 10
}
- ( m =256). , . , Ȼ.
r [0,1), r * key [0,1]. m, 0 m 1.
int h(int key, int m) {
double r = key * rnd();
r = r (int)r; //
return r * m;
}
m , -, . , , , m .
- i = h (key) , ( ) key. , , i = h (key) .
|
|
, - . : , - , , .
:
( ), chaining with separate lists;
linear probe open addressing.
. -, , . , . , , ( ), .. , , , -.
, , i , , , , i .
. - i - , .. key i = h (key) . , key, , , , i - -. , N NULL:
.
() - , :
i;
.
, , .. .
- i = h (key), key [0, m 1], m -. , , , - i = h (key) = key % m.
() - (-), - () .