3.数据结构课件cs01版

1、4 Polynomials1. Representing Polynomials as Singly Linked ListsGiven:We represent each term as a node exponcoefnext Declaration:typedef struct poly_node *poly_ptr;typedef struct poly_node int coef ; /* assume coefficients are integers */ int expon ; poly_ptr next ; ;poly_ptr a ;am1em1a0e0NULLa A sin

2、gly linked list in which the last node has a null link is called a chain.4 Polynomials2. Adding PolynomialsExample Add a ( x ) = 5x4 + 2x2 4x + 1 and b ( x ) = 6x3 + 3x2 + 4x54224110Na633241Nbfrontrear save the node in temptemp rear-next = temp rear = temprearrearab52rear63abab10Nrearatempfront54att

3、ach ( coef, expon, &rear )Programs padd and attach can be found on p.154 155.Tpadd = O ( m + n ) where m and n are the lengths of a and b, respectively.Question: Why did we need the empty node at front?4 Polynomials3. Erasing Polynomialsvoid erase ( poly_ptr *ptr ) /* erase the polynomial pointed to

4、 by ptr */ poly_ptr temp ; while ( *ptr ) temp = *ptr ; *ptr = ( *ptr )-next ; free ( temp ) ; /* end while-loop */Terase = O( n )where n is thelength of thelist. Isnt it simple andefficient?I can do it inO(1) time.What?!Impossible!You wantta bet?4 Polynomials4. Representing Polynomials as Circularl

5、y Linked ListsNULL.availam1em1a0e0NULLpam2em2Erase p : temp = p-nexttemp p-next = avail avail = tempavail p = NULLNULLTp = O ( ? )1The program cerase can be found on p.159 The trick is to maintain a recycle bin as a chain. So when we need a new node, we check this chain first. Only when this chain i

6、s empty do we need to use malloc.4 PolynomialsNULL.availGet a node from avail :nodeThe program get_node can be found on p.158Return a node to avail :NULL.availptrThe program ret_node can be found on p.15800zero_poly?Then how can we recognize the end of a polynomial in functions like Padd ?One more q

7、uestion:How shall we represent the zero polynomialas a circular list?HW:p.162 #1, 4Read the relevant material in the textbook and try to answer the question.Do you have a better idea?5 Additional List Operations1. Operations for Chains ( besides get_node & ret_node ) Inverting a chainlist_ptr invert

8、 ( list_ptr lead ) /* invert the list pointed to by lead */ list_ptr middle, trail ; middle = NULL ; /* middle is head of the inverted chain */ while ( lead ) trail = middle ; middle = lead ; lead = lead-next ; middle-next = trail ; /* end while-loop */ return middle ;123leadNULLmiddleNULLtrail23lea

9、dNULL1middleNULLtrail23leadNULL1middleNULLtrailTinvert = O( length of lead )5 Additional List Operations Concatenating two chainslist_ptr concatenate ( list_ptr ptr1, list_ptr ptr2 ) /* produce a new list that contains the list prt1 followed by the list ptr2. The non-empty list pointed to by ptr1 is

10、 changed permanently */ list_ptr temp ; if ( IS_EMPTY(ptr1) ) return ptr2; else if ( ! IS_EMPTY(ptr2) ) for ( temp = ptr1; temp-next; temp = temp-next ) ; /* find the last node of ptr1 */ temp-next = ptr2 ; /* attach ptr2 */ /* end else-if */ return ptr1 ; /* end else */Tconcatenate = O( length of p

11、tr1 )5 Additional List Operations2. Operations for Circularly Linked Lists Inserting a node.ptr12nAt front :node node-next = ptr-next ptr-next = nodeAt end : ptr = nodeThe program insert_front can be found on p.165 Finding the length of the listThe program length can be found on p.166Sure! Itll take

12、 time O( n ) to find the last node and then change its link. I bet you have a better idea?HW:p.166 #46 Equivalence Relations【Definition】A relation, , over a set, S, is said to be an equivalence relation over S iff it is symmetric, reflexive, and transitive over S.Example “=” is an equivalence relati

13、on since (1) x = x ( reflexive ) (2) x = y implies y = x ( symmetric ) (3) x = y and y = z implies x = z ( transitive )【Definition】Two members x and y of a set S are said to be in the same equivalence class iff x y.Goal: Divide a set S into equivalence classes6 Equivalence RelationsExample Given S =

14、 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 and 9 relations: 04, 31, 610, 89, 74, 68, 35, 211, 110. The answer should be 0, 2, 4, 7, 11 , 1, 3, 5 , 6, 8, 9, 10 Sketch of the idea: S = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 0,44,11,112,277 1,33,55 6,1010,8,899Note: We will need an array out12 to record the e

15、lements which have been printed. Representation of the pairsGiven S = s1, s2, , sn and m equivalence relations.(a) s i j = 1 if i j. s n n 6 Equivalence Relations(b) The ith row contains the elements which are directly paired to i s n m ExampleEasy random access, but still wastes too much of space,

16、and it is difficult to insert a new pair.(c) A combination of array and linked listseq 0 114Nseq 1 3Nseq 2 11Nseq 3 51Nseq 4 70Nseq 5 3Nseq 6 810Nseq 7 4Nseq 8 69Nseq 9 8Nseq10 6Nseq 11 02N6 Equivalence Relations#include #include #define MAX_SIZE 24#define IS_FULL ( ptr ) ( !(ptr) )#define FALSE 0#d

17、efine TRUE 1typedef struct node *node_ptr ;typedef struct node int data ; node_ptr next ; ;void main ( void ) /* find equivalence classes */ short int out MAX_SIZE ; node_ptr seq MAX_SIZE ; node_ptr x, y, top ; int i, j, n ;printf ( “Enter the size (= %d) ”, MAX_SIZE ) ;scanf ( “%d”, &n ) ;for ( i =

18、 0; i = 0 ) /* while there are more pairs */ x = (node_ptr) malloc ( sizeof(node) ); if (IS_FULL(x) fprintf (sdterr, “The memory is full n”) ; exit( 1 ); x-data = j; x-next = seqi; seqi = x; /* put j on seq i list */ x = (node_ptr) malloc ( sizeof(node) ); if (IS_FULL(x) fprintf (sdterr, “The memory

19、 is full n”) ; exit( 1 ); x-data = i; x-next = seqj; seqj = x; /* put i on seq j list */ printf ( “Enter a pair of numbers (1 1 to quit): ” ) ; scanf ( “%d%d”, &i, &j ) ; /* end while-loop */6 Equivalence Relations6 Equivalence Relations/* Phase 2: Output the equivalence classes */for ( i = 0; i dat

20、a ; /* denote it by j */ if ( out j ) /* if j has not been printed */ printf ( “ %5d”, j ); out j = FALSE; /* output j */ y = x-next; x-next = top; top = x; x = y; /* push j into stack, and x points to the next node */ /* end if */ else x = x-next; /* if j is out, x points to the next node */ /* end

21、 while(x)-loop */ if ( !top ) break; /* if stack is empty, finish this class */ x = seqtop-data; top = top-next; /* unstack */ /* end for-loop */ /* end if */ 6 Equivalence RelationsAnalysis of the equivalence program Initialization of seq and out O( n ) Phase 1: input the pairs O( m ) Phase 2: for-

22、loop O( n ) processing nodes O( m ) Tp = O( m + n ) which is optimal.S = O( ? )m + n What do you think ? Oh dont tell me you have a better idea. What can I say . I do have a better idea on saving some space, but wont tell you until we get to Chapter 5.7 Sparse MatricesExampleis represented by linked

23、 lists as the following:44021121433151012aH0H1H2H3H0H1H2H3#define MAX_SIZE 50 /* size of the largest matrix = max row, col */typedef enum head, entry tagfield;typedef struct matrix_node *matrix_ptr;typedef struct entry_node int row; int col; int value; typedef struct matrix_node matrix_ptr down; mat

24、rix_ptr right; tagfield tag; union matrix_ptr next; entry_node entry; u; ;matrix_ptr hdnode MAX_SIZE ;7 Sparse MatricesRepresentationrow colvalueentry_node : union u:entry_nodenext matrix_node:downrighttagudownrightheadnext downrightentryvaluerc7 Sparse Matrices44021121433151012aH0H1H2H3H0H1H2H3rdrd

25、rndrndrndrndrndrndrndrnrrrrddddHW:Read programs mread, mwrite,and merase on p.174 178.Do p.177 #1 (madd)8 Doubly Linked Lists Dont we have enough headache already?Why do we need the doubly linked lists? Suppose you have a list 1-2-3-m.Now how would youget the m-th node? Ill go from the 1st nodeto th

26、e m-th node. Then you are asked to find its previous node m 1? Uhhh . Then Ill have to go from the 1st node again.But hey, why do I wantta find the previous node? Why do you ask me? :-)Maybe you wantta deletethe m-th node?typedef struct node *node_ptr ;typedef struct node node_ptr llink; element ite

27、m; node_ptr rlink; ;itemllinkrlinkptr = ptr-llink-rlink = ptr-rlink-llinkA doubly linked circular list with head node:item1item2item3HAn empty list :H8 Doubly Linked Lists Insertionnodenewnode newnode-llink = node newnode-rlink = node-rlink node-rlink-llink = newnode node-rlink = newnode Deletiondeleted