chapter 3 Lists 8 1 AbStract Data Type(adt) (Definition Data Type = Objects ]U[ Operations Example〗int={0,±1,±2,…, NT 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
CHAPTER 3 Lists §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
s2 The List ADt ADT. Objects:(item, item,., itemN-1) Operations: 9 Finding the length, N, of a list. Cg Printing all the items in a list 9 Making an empty list C Finding the k-th item from a list,0<k<N. Inserting a new item after the k-th item of a list, 0sk<N. C Deleting an item from a list C Finding next of the current item from a list e Finding previous of the current item from a list
§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:
1. Simple Array implementation of lists(seqlist) array i=item Address Content array+i item; Sequential mapping -array+i+1 item;1 Maxsize has to be estimated 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
1. Simple Array implementation of Lists (seqlist) 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
Seqlist's(顺序表 definition #define listsize 100 /max length typedef int ListData; typedef struct i ListData x data: //base address int length: //current items lengt th 3 Seqlist
SeqList ’s(顺序表)definition #define ListSize 100 //max length typedef int ListData; typedef struct { ListData * data; //base address int length; //current items’ length } SeqList ;
Basic operation of seqlist Initialize void InitList( Seq list &l)i L data=( ListData *) malloc Listsize s sizeof List Data ))i if (Ldata== NULL)( printf(“存储分配失败!n”); exit (1); length =0
Basic operation of SeqList ◼ Initialize void InitList ( SeqList & L ) { L.data = ( ListData * ) malloc ( ListSize * sizeof ( ListData ) ); if ( L.data == NULL ) { printf ( “存储分配失败!\n” ); exit (1); } L.length = 0; }