算法和数据结构02.ppt

2004-03 L.Chen Chapter 3 DATA REPRESENTATION(1) 3.1 Introduction 数据可以用不同的形式进行描述或存储。 The common data representation methods are: Formula-based representation Linked representation Indirect addressing A simulated-pointer representation What is the data object ? Data, Data Element, Data Item Primitive 原语 / atomic 原子 （不可分割） Data Element – 由数据对象的实例复合而成。 set or collection of instances N = { 0, +1, -1, +2, -2, +3, -3, … } daysOfWeek = { S,M,T,W,Th,F,Sa } C = { ‘A’, ‘B’, …, ‘Z’ } instances may or may not be related myDataObject = { apple, chair, 2, 5.2, red, green, Jack} What is the data structure ? Data_structure = ( D , S ) Data object + relationships that exist among instances and elements that comprise an instance Among instances of integer 369 370 280 + 4 = 284 3.2 Linear Lists L = (e0, e1, e2, e3, …, en-1) relationships e0 is the zero’th (or front) element en-1 is the last element ei immediately precedes ei+1 n = 0 is finite; list size is n 当n=0时称为空表 3.3 Formula-based Representation3.3.1 Representation Location( i ) = i – 1 LOC( ei ) = LOC( e1 ) + ( i – 1) * i Linear List Array Representation use a one-dimensional array element[ ] Representation Used In Text put element i of list in element[i] use a variable size to record current number of elements Add / Remove An Element Data Type Of Array element[ ] Data type of list elements is unknown. Define element[ ] to be of data type Object. Cannot put elements of primitive data types (int, float, double, char, etc.) into our linear lists. Length of Array element[ ] Don’t know how many elements will be in list. Must pick an initial length and dynamically increase as needed. Increasing Array Length Length of array element[ ] is 6. Increasing Array Length Now copy elements from old array to new one. Increasing Array Length Finally, rename new array. element = newArray; Altogether Now // create a new array of proper length and data type Object[ ] newArray = new Object [newLength]; How