算法和数据结构02.ppt

文档介绍：算法和数据结构02
Introduction
数据可以用不同的形式进行描述或存储。
The common data representation methods are:
Formula-based representat3
9

Length of Array element[ ]
Don’t know how many elements will be in list.
Must pick an initial length and dynamically increase as needed.
2019-03
15

Increasing Array Length
Length of array element[ ] is 6.
a
b
c
d
e
f
newArray = new Object[15];
First create a new and larger array
2019-03
16

Increasing Array Length
Now copy elements from old array to new one.
a
b
c
d
e
f
a
b
c
d
e
f
2019-03
17

Increasing Array Length
Finally, rename new array.
element = newArray;
= 15
a
b
c
d
e
f
element[0]
2019-03
18

Altogether Now
// create a new array of proper length and data type
Object[ ] newArray = new Object [newLength];
// copy all elements from old array into new one (element, 0, newArray, 0, );
// rename array
element = newArray;
2019-03
19

How Big Should The New Array Be?
At least 1 more than current array length.
Cost of increasing array length is
Θ(new length)
Cost of n add operations done on an initially empty linear list increases by Θ(n2)
2019-03
20

Space Complexity
newArray = new char[7];
space needed = 2 * newLength – 1
= 2 * maxListSize – 1
element[6]
a
b
c
d
e
f
2019-03
21

Array Doubling
Double the array length.
a
b
c
d
e
f
newArray = new char[12];
a
b
c
d
e
f
Time for n adds goes up by Θ(n).
Space needed = *newLength.
Space needed <= 3*maxListSize – 3
2019-03
22

How Big Should The New Array Be?
Resizing by any constant factor
new length = c * old length
increases the cost of n adds by Θ(n).
Resizing by an additive constant increases the cost of n add operations by Θ(n2).
2019-03
23

How Big Should The New Array Be?
Resizing by an additive constant c requires
at most
(maxListSize – 1)