Ch03-表栈队列

1、表栈队列高文宇1 抽象数据类型抽象数据类型 定义1（ADT）： Data Type = Objects Operations 示例1： int = 0, 1, 2, , INT_MAX, INT_MIN , , , , , 在面向对象程序设计中，类（对象）就可以视为ADT。2 表表ADT Objects: ( item0, item1, , itemN 1 ) Operations: Finding the length, N, of a list. Printing all the items in a list. Making an empty list. Finding the k-th

2、 item from a list, 0 k N. Inserting a new item after the k-th item of a list, 0 k data = ZHAO ;N2-data = QIAN ;N1-next = N2 ;N2-next = NULL ;ptr = N1 ;ZHAOQIANptrNULL链表的插入a1ptrNULLaiai+1an.nodebtemp temp-next = node-next node-next = tempQuestion: What will happen if the order of the two steps is rev

3、ersed?Question: How can we insert a new first item? takes O(1) time.链表的删除a1ptrNULLaiai+1an.bprenode pre-next = node-next free ( node )bnodeQuestion: How can wedelete the first node from a list?Answer: We can add a dummy head node to a list. takes O(1) time.双向循环链表typedef struct node *node_ptr ;typede

4、f struct node node_ptr llink; element item; node_ptr rlink; ;item llinkrlinkptr = ptr-llink-rlink = ptr-rlink-llinkA doubly linked circular list with head node:item1 item2 item3 HAn empty list : H表的应用多项式ADT Objects : P ( x ) = a1 x e1 + + an x en ; a set of ordered pairs of where ai is the coefficie

5、nt and ei is the exponent. ei are nonnegative integers. Operations: Finding degree, max ei , of a polynomial. Addition of two polynomials. Subtraction between two polynomials. Multiplication of two polynomials. Differentiation of a polynomial.多项式的数组实现typedef struct int CoeffArray MaxDegree + 1 ;int

6、HighPower; *Polynomial ; I like it! Its easy to implement most of the operations, such as Add and Multiplication. Really? What is the time complexity for finding the product of two polynomialsof degree N1 and N2?O( N1*N2 )Whats wrong with that?Try to apply MultPolynomial (p.53)On P1(x) = 10 x1000+5x

7、14+1 andP2(x) = 3x1990 2x1492+11x+5- now do you see my point?多项式的链式实现Given:0101)(eemxaxaxAm . 1, 1, 0for 0 and 0 where021 miaeeeimmWe represent each term as a node ExponentCoefficientNext Declaration:typedef struct poly_node *poly_ptr;struct poly_node int Coefficient ; /* assume coefficients are int

8、egers */ int Exponent; poly_ptr Next ; ;typedef poly_ptr a ; /* nodes sorted by exponent */am 1em 1 a0e0NULLa表的应用多重表Example Suppose that we have 40,000 students and 2,500 courses. Print the students name list for each courses, and print the registered classes list for each student.【Representation 1】

9、int Array400002500; otherwise0 coursefor registered is student if1Arrayjiji表的应用多重表S1S2S3S4S5C1C2C3C43 栈栈ADT 栈（Stack）：后进先出（LIFO）。 Objects: A finite ordered list with zero or more elements. Operations: Int IsEmpty( Stack S ); Stack CreateStack( ); DisposeStack( Stack S ); MakeEmpty( Stack S ); Push( E

10、lementType X, Stack S ); ElementType Top( Stack S ); Pop( Stack S ); 栈的链表实现 Linked List Implementation (with a header node)NULLElement Element Element Push: TmpCell-Next = S-Next S-Next = TmpCell Top: FirstCell = S-Next S-Next = S-Next-Next free ( FirstCell )return S-Next-Element S ElementTmpCell S

11、Pop:ElementFirstCell S But, the calls to malloc and free are expensive. Easy! Simply keep another stack asa recycle bin.栈的数组实现struct StackRecord int Capacity ; /* size of stack */int TopOfStack; /* the top pointer */* + for push, - for pop, -1 for empty stack */ElementType *Array; /* array for stack

12、 elements */ ; Note: The stack model must be well encapsulated. That is, no part of your code, except for the stack routines, can attempt to access the Array or TopOfStack variable. Error check must be done before Push or Pop (Top).Read Figures 3.38-3.52 for detailed implementations of stack operati

13、ons.栈的应用平衡符号Check if parenthesis ( ), brackets , and braces are balanced.Algorithm Make an empty stack S; while (read in a character c) if (c is an opening symbol) Push(c, S); else if (c is a closing symbol) if (S is empty) ERROR; exit; else /* stack is okay */ if (Top(S) doesnt match c) ERROR, exit

14、; else Pop(S); /* end else-stack is okay */ /* end else-if-closing symbol */ /* end while-loop */ if (S is not empty) ERROR;T( N ) = O ( N ) where N is the length of the expression.This is an on-line algorithm.栈的应用后缀表达式 后缀表达式的计算 中缀表达式转换成后缀表达式后缀表达式的计算ExampleAn infix expression: a b c d e A prefix exp

15、ression: a b c d e A postfix expression: a b c d e operandoperatoroperator with the highest precedenceExample 6 2 3 4 2 = ? 8topGet token: 6 ( operand )top6Get token: 2 ( operand )top2Get token: ( operator )2 6= 3toptop3topGet token: 3 ( operand )3topGet token: ( operator )3toptop3 = 00topGet token:

16、 4 ( operand )top4Get token: 2 ( operand )top2Get token: ( operator )top2top4 = 88topGet token: ( operator )top8top0 = 88top Pop: 8topReverse Polish notationT( N ) = O ( N ). No need to know precedence rules.中缀转后缀Example a b c d = ? a b c d Note: The order of operands is the same in infix and postfi

17、x. Operators with higher precedence appear before those with lower precedence.Output:topGet token: a (operand)a Get token: (plus) topGet token: b (operand)b Get token: (times) ?top Get token: c (operand)c Get token: (minus) ?top ?top top Get token: d (operand)dtop Isnt that simple? Wait till you see

18、 the nextexample.中缀转后缀( ?Example a ( b c ) d = ? a b c d topOutput: Get token: a (operand)a Get token: (times) top Get token: ( (lparen) ( ?top( Get token: b (operand)b Get token: (plus)NO?!top+ Get token: c (operand)c Get token: ) (rparen)top top Get token: (divide) ?top top Get token: d (operand)d

19、top T( N ) = O ( N ) 中缀转后缀Solutions: Never pop a ( from the stack except when processing a ) . Observe that when ( is not in the stack, its precedence is the highest; but when it is in the stack, its precedence is the lowest. Define in-stack precedence and incoming precedence for symbols, and each t

20、ime use the corresponding precedence for comparison. Note: a b c will be converted to a b c . However, 223 ( ) must be converted to 2 2 3 , not 2 2 3 since exponentiation associates right to left.322栈的应用函数调用Return AddressStack Frames pLocal VariablesReturn Addresss ps pOld Frame Pointers pf pf ps pf

21、 pvoid PrintList ( List L ) if ( L != NULL ) PrintElement ( L-Element ); PrintList( L-next ); /* a bad use of recursion */ What will happen if L contains 1 millionelements?tail recursionvoid PrintList ( List L )top: if ( L != NULL ) PrintElement ( L-Element ); L = L-next; goto top; /* do NOT do this

22、 */ /* compiler removes recursion */Recursion can always be completely removed.Non recursive programs are generally faster than equivalent recursive programs.However, recursive programs are in general much simpler and easier to understand.4 队列队列ADT 队列（Queue）：先进先出（FIFO）。 Objects: A finite ordered list with zero or more elements. Operations: int IsEmpty( Queue Q ); Queue CreateQueue( ); DisposeQueue( Queue Q ); MakeEmpty( Queue Q ); Enqueue(