第四讲(表).pptVIP

* CHAPTER 3 Lists, Stacks, and Queues §1 Abstract Data Type (ADT) 【Definition】Data Type = { Objects } ? { Operations } 〖Example〗 int = { 0, ?1, ?2, ? ? ?, INT_MAX, INT_MIN } ? { ?, ?, ?, ?, ?, ? ? ? } 【Definition】An Abstract Data Type (ADT) is a data type that is organized in such a way that the specification on the objects and specification of the operations on the objects are separated from the representation of the objects and the implementation on the operations. §2 The List 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 item from a list, 0 ? k N. ? Inserting a new item after the k-th item of a list, 0 ? k N. ? Deleting an item from a list. ? Finding next of the current item from a list. ? Finding previous of the current item from a list. ? ADT: Why after? 2/18 1. Simple Array implementation of Lists §2 The List ADT array[ i ] = itemi ? MaxSize has to be estimated. Address Content array+i itemi array+i+1 itemi+1 …… …… …… …… Sequential mapping ? Find_Kth takes O(1) time. ? Insertion and Deletion not only take O(N) time, but also involve a lot of data movements which takes time. 3/18 1020 1008 A1 1002 Memory representation A2 1036 A3 1008 A4 1020 A5 1030 1036 1030 §2 The List ADT §2 The List ADT 2. Linked Lists Address Data Pointer 0010 0011 0110 1011 SUN QIAN ZHAO LI 1011 0010 0011 NULL Head pointer ptr = 0110 ZHAO QIAN SUN LI ptr NULL Initialization: struct node { char data [ 4 ] ; struct node *next ; } ; struct node *ptr ; To link ‘ZHAO’ and ‘QIAN’: struct node *N1, *N2 ; N1 = (struct node*)malloc(sizeof(struct node)); N2 = (struct node*)malloc(sizeof(struct node)); N1-data = ‘ZHAO’ ; N2-data = ‘QIAN’ ; N1-next = N2 ; N2-next = NULL ; ptr = N1 ; ZHAO QIAN ptr NULL Locations of the nodes may change on different runs. §2 The List ADT a1 ptr NULL ai ai+1 an ...