, . , C cur->next. , . . , :
3. :
4. .
5. .
6. .
34. , .
void PrintSearchList (list head, int val)
//Head , str
{
bool lfound = false; // ,
tail = &head; //
while (tail!= NULL)//
{
printf("%d\n", tail->value); //
if (tail->value = val) lfound = true; // ?
tail = tail->next; //
}
if (lfound) printf(" !");
else printf(" !");
}
list GotoNode (list head, int cnt)
//Cnt , 1,
{
int i = 1;
tail = &head;
while ((tail->next!= NULL) && (i < cnt))
{
i++;
tail = tail->next;
}
return(*tail);
}
, ,
(. stack) , : , . , LIFO (Last In First Out, ). , . ptrStack (.43). , .
:
push () ;
pop ;
isEmpty , ;
top () ( );
size ;
clear ( ).
|
, :
struct st // stack
{
char info;
struct st *ps; // ( )
|
|
} stack;
. , . .
() ( ) ( ) , .. , , , .. , , , . , . , , , .
35. (a+b)/(c/a*c e*d) :
: ab+ca/c*ed*/. , : , .
1. : R1 = ab+ = a+b, ab+ R1 : R1ca/c*ed*/.
2. : R2 = ca/ = c/a
: R1R2c*ed*/
3. : R3 = R2c* = R2*c = c/a*c
: R1R3ed*/
4. : R4 = ed* = e*d
: R1R3R4/
5. : R5 = R3R4 = R3R4 = c/a*ce*d
: R1R5/
6. : R6 = R1R5/ = R1/R5=(a+b)/(c/a*ce*d)
: R6
R6.
(́ ́ ́, 19302002, , ). :
1. , .
2. , ( ).
3. , .
4. , .
5. , . , . , .
6. (. 17). , :
17.
( | + | * | / | ||
7. , .
8. , .
|
|
9. . .
10. .
36. .
/* pp( ) */
struct st
{
char c;
struct st *next;
};
struct st *push(struct st *, char);
/* p */
char DEL(struct st **);
int PRIOR(char);
void main(void)
{
// p
struct st *OPERS = NULL;
char a[80], outstring[80];
int k, point;
do
{
puts(" ( '='): ");
fflush(stdin);
// p p
gets(a);
k = point = 0;
// p, '='
while(a[k]!= '\0' && a[k]!= '=')
{
if(a[k] == ')') // p - ')',
// p p
// p
{
while((OPERS->c)!= '(')
outstring[point++] = DEL(&OPERS);
DEL(&OPERS); // p
}
if(a[k] >= 'a' && a[k] <= 'z') // p - ,
// p p
outstring[point++] = a[k];
if(a[k] == '(') // p - '(',
//
OPERS = push(OPERS, '(');
// - p, :
if(a[k] == '+' || a[k] == '-' || a[k] == '/' || a[k] == '*')
{
if(OPERS == NULL) // p
OPERS = push(OPERS, a[k]);
else //
// pp p pp p p p
if(PRIOR(OPERS->c) < PRIOR(a[k]))
OPERS = push(OPERS, a[k]); //
else // pp p p
// p p pp
{
while((OPERS!= NULL) && (PRIOR(OPERS->c) >= PRIOR(a[k]))) //
outstring[point++] = DEL(&OPERS);
OPERS = push(OPERS, a[k]); //
// p
}
}
k++; // p p
}
// pp p p p p
while(OPERS!= NULL)
outstring[point++] = DEL(&OPERS);
outstring[point] = '\0';
printf("\n%s\n", outstring);
fflush(stdin);
puts("\ (y/n)?");
}
while(getchar()!= 'n');
}
/* push ( p p HEAD)
a. p p */
struct st *push(struct st *HEAD, char a)
{
st* PTR = new st; //
PTR->c = a; // p
PTR->next = HEAD; //
return PTR;// PTR - p
}
/* DEL p .
p . p */
char DEL(struct st **HEAD)
{
struct st *PTR;
char a;
if(*HEAD == NULL) return '\0'; // , p '\0'
PTR = *HEAD; // PTR - p p
a = PTR->c;
*HEAD = PTR->next; // p p
free(PTR); //
return a; // p p
}
// PRIOR p pp p p
int PRIOR(char a)
{
switch(a)
{
case '*':
case '/':
return 3;
case '-':
case '+':
return 2;
case '(':
return 1;
}
}
(a+b*c)*(ab)/(d(a+b*d)). , .. , 90 , (.18).
|
|
, , , , .
(a. queue) , , . , , . , FIFO (First In First Out, ). , , . , : , , , , , .
(. deque double-ended queue, ) , , . , . , , , . : ( ) ( ). : ; ; ; ; ; .
, , .. , ( , , ), .
, . : , , :
1. , .
2. , , m≥0 1, 2,.m, . 1, 2,.m () .
, (.. m=0), .
() , . : , . , . , , , , .
37. (.44), (A*B+C*D)/(B*C), .
|
. , . : , (). .45 A . B ..
|
|
| |||
.45. |
:
struct tree
{
int info; //
tree ltree,rtree; //
}
:
1. , .
2. () .
3. .
4. .
5. .
6. .
7. .
8. .
9. .
40. .
tree MakeTree(tree node, int x)
{
if(node.value == NULL)
{
tree* p = new tree;
p->value = x;
node = *p;
}
else
{
if((node).value > x) MakeTree(*node.pleft, x);
else MakeTree(*node.pright, x);
}
return node;
}
void SetLeft (tree *p,int x) // p
{
*p->ltree = NewNode(x);
}
void SetRight(tree *p,int x) // p
{
*p->rtree = NewNode(x);
}
int GetInfo (tree *p) // p
{
if (p!= NULL) return p->info;
else return(0);
}
tree GetLeftTree (tree *p) //
// p
{
if (p!= NULL) return *p->ltree;
//else return(NULL);
}
tree GetRightTree (tree *p) //
// p
{
if (p!= NULL) return *p->ltree;
// else return (tree)NULL;
}
void DelLeaf (tree *p) //
{
if (p!= NULL) free(p);
}
. . . , . : ; ; ( ) .
:
, :
1. .
2. .
3. .
, , . 48, : /+*AB*CD*BC. .
:
, :
1. .
2. .
3. .
: A*B+C*D/B*C
:
, :
1. .
2. .
3. .
: AB*CD*+BC*/. .
, , , , , .. , , . . , , .
void PrefixObhod (tree *p)
{
if (p!=NULL) // , :
{
printf ("%d", p->info); // , .
|
|
PrefixObhod (p->ltree); //
PrefixObhod (p->rtree); //
}
}
void InfixObhod (tree *p)
{
if (p!= NULL) // , :
{
InfixObhod (p->ltree); //
printf ("%d", p->info); // , .
InfixObhod (p->rtree); //
}
}
void DelSubTree (tree *p) // p
{
if (p!= NULL) // , :
{
DelSubTree (p->ltree); //
DelSubTree (p->rtree); //
free(p); // ,
}
}
void DelLeftTree (tree *p) // p
{
if (p!= NULL)
{
DelSubTree (p->ltree);
p->ltree = NULL;
}
}
void DelRightTree (tree *p) // p
{
if (p!= NULL)
{
DelSubTree (p->rtree);
p->ltree = NULL;
}
}
( ) , . , . . ( ). . , . , .. , . , .
, , , .
bool TreeEqual(tree *p1, tree *p2)
{
if (p1 == p2) return true;
else
if ((p2!= NULL) && (p1!= NULL))
return ((p1->info = p2->info) && TreeEqual(p1->ltree, p2->ltree) &&
TreeEqual(p1->rtree, p2->rtree));
else return false;
}