03장.스택.key

Size: px

Start display at page:

Download "03장.스택.key"

도환 후
6 years ago
Views:

1 DATA STRUCTURES USING C CHAPTER 1

2 ? (stack): (LIFO:Last-In First-Out) 2

3 : top : ( index -1 ),,, 3

4 : ( ) ( ) -> ->. ->.... 4

5 Stack ADT : (LIFO) : init():. is_empty(): TRUE FALSE. is_full(): TRUE FALSE. size():. push(x): x. pop():. peek():. 5

6 (push), (pop) is_empty(): is_full(): peek(s): ( ) pop. 6

7 Undo 7

8 (Undo) - LAB ^+Z Comm+Z 8

9 1 stack[ ] top: stack[0] stack[top]: top -1 9

10 Push C C top 1 B top 1 B 0 A 0 A push(x) if is_full(s) then error "overflow" else top top+1 data[top] x 10

11 Pop C top 2 1 B 1 B top 0 A 0 A pop() if is_empty() then error "underflow" else e data[top] top top-1 return e 11

12 data[] top! typedef int Element; Element data[max_stack_size]; int top; int is_empty() { if( top == -1 ) return 1; else return 0; } void init_stack() { top = -1; } int size() { return top+1; } int is_empty() { return (top == -1); } int is_full() { return (top == MAX_STACK_SIZE-1); } 12

13 void push ( Element e ) { if( is_full() ) error (" "); data[++top] = e; } Element pop ( ) { if( is_empty() ) error (" "); return data[top--]; } Element peek ( ) { if( is_empty() ) error (" "); return data[top]; } void print_stack(char msg[]) { int i; printf("%s[%2d]= ", msg, size()) ; for (i=0 ; i<size() ; i++ ) printf("%2d ", data[i]); printf("\n"); } 13

$void main() { int i; init_stack(); for( i=1 ; i<10 ; i++ ) push( i ); print_stack(" push 9 "); printf("\tpop()$

14 void main() { int i; init_stack(); for( i=1 ; i<10 ; i++ ) push( i ); print_stack(" push 9 "); printf("\tpop() --> %d\n", pop()); printf("\tpop() --> %d\n", pop()); printf("\tpop() --> %d\n", pop()); print_stack(" pop 3 "); } 14

15 Lab ex3.1 15

16 Element typedef struct Student_t { int id; char name[32]; char dept[32]; } Student; typedef Student Element; void print_stack(char msg[]) { int i; printf("%s[%2d]= ", msg, size()) ; for (i=0 ; i<size() ; i++ ) printf("\n\t%-15d %-10s %-20s", data[i].id, data[i].name, data[i].dept); printf("\n"); } 16

17 Student get_student(int id, char* name, char* dept) { Student s; s.id = id; strcpy(s.name, name); strcpy(s.dept, dept); return s; } void main() { init_stack( ); push( get_student( , " ", " ") ); push( get_student( , " ", " ") ); push( get_student( , " ", " ") ); push( get_student( , " ", " ") ); print_stack(" 4 "); pop( ); print_stack(" 1 "); } 17

18 Lab ex3.2 18

19 19

20 20

21 : : ( [, ] ), ( {, } ), ( (, ) )... (a(b) a(b)c) a{b(c[d]e}f) 21

23 23

24 , top., ( ), 1( ). 24

25 check_matching(expr) while ( expr ) ch expr switch(ch) case '(': case '[': case '{': ch break case ')': case ']': case ']': if ( ) then else open_ch break if( ) then if (ch open_ch ) then 25

26 void main() { char expr[4][80] = { "{A[(i+1)]=0;}", "if((i==0) && (j==0)", "A[(i+1])=0;", "A[i] =f)(;" }; int err, i; for( i=0 ; i<4 ; i++ ) { err = check_matching(expr[i]); if( err == 0 ) printf(" : %s\n", expr[i]); else printf(" : %s ( %d )\n", expr[i], err); } } 26

27 Lab - ex3.3 27

28 28

29 : (prefix), (infix), (postfix) 2+3*4 +2*34 234*+ a*b+5 +5*ab ab*5+ (1+2) > -> 2+3*4 -> 234*+ -> 14 29

30 Calc_postfix (expr) ; for in expr do if ( ) s.push(item); if ( op ) then second pop(); first pop(); result pop(); temp first op second; // op +-*/ push(temp); 30

31 31

32 double calc_postfix( char expr[] ) {... init_stack( ); while( expr[i]!= '\0' ) { c = expr[i++]; if (c>='0' && c<='9') { val = c - '0'; push( val ); } else if( c=='+' c=='-' c=='*' c=='/' ){... switch( c ) { case '+': push( val1 + val2); break;... } void main() { char expr[2][80] = { "8 2 / * +", "1 2 / 4 * 1 4 / *" }; printf(" : %s = %lf\n", expr[0], calc_postfix(expr[0])); printf(" : %s = %lf\n", expr[1], calc_postfix(expr[1])); } 32

33 : ( ) 2+3*4 -> 234*+ 33

34 ! 34

35 35

36 Infix_to_postfix(expr). while (expr ) term ; switch (term) case : term ; break; case : push(term); break; case : e pop(); while( e ) do e ; e pop(); break; case : while ( peek() term ) do e pop(); e ; push(term); break; while( not is_empty() ) do e pop(); e ; 36

37 static int precedence( char op ) { switch (op) { case '(' : case ')' : return 0; case '+' : case '-' : return 1; case '*' : case '/' : return 2; } return -1; } void infix_to_postfix( char expr[] ) {...} void main() { char expr[2][80] = { "8/2-3+(3*2)", "1/2* 4 * (1/4)" }; printf(" : %s ==> :", expr[0]); infix_to_postfix(expr[0]); printf(" : %s ==> :", expr[1]); infix_to_postfix(expr[1]); } 37

38 38

03장.스택

03장.스택 ---------------- DT STRUCTURES USING C ---------------- CHPTER 스택 1/30 스택이란? 스택 (stack): 쌓아놓은더미 후입선출 (LIFO:Last-In First-Out) 가장최근에들어온데이터가가장먼저나감 2/30 스택의구조 스택상단 : top 스택하단 : 불필요 요소, 항목 공백상태, 포화상태 삽입, 삭제연산