Ce cours initie aux bases de la programmation en utilisant le langage Java : variables, boucles, fonctions, ... Il ne présuppose pas de connaissance préalable. Les aspects plus avancés (programmation orientée objet) sont donnés dans un cours suivant, «Introduction à la programmation orientée objet (en Java)». Il s'appuie sur de nombreux éléments pédagogiques : vidéos sous-titrées, quizz dans et hors vidéos, exercices, devoirs notés automatiquement, notes de cours.
Tableaux dynamiques
Loading...
來自 École Polytechnique Fédérale de Lausanne 的課程
Initiation à la programmation (en Java)
199 個評分
從本節課中
Tableaux dynamiques et chaînes de caractères
Nous continuons notre présentation des tableaux puis passons à un autre nouveau type : les chaînes de caractères (i.e. suites de lettres).
與講師見面
Jean-Cédric ChappelierDr.
School of Computer and Communication Sciences
Jamila SamDr
School of Computer and Communication Sciences
In a previous episode we studied
fixed-size arrays in Java.
We saw that for this type of arrays,
once the size is set when we initialize the array,
it isn't possible to modify it anymore when the program executes.
Today we'll study dynamic arrays,
which will free us from this constraint.
Dynamic arrays have the particularity to be able to increase
or decrease their size while the program executes.
Their use requires a number of concepts
related to object-oriented programing.
However, as with character strings,
it isn't necessary to have any preliminary knowledge
of these concepts to be able to use
their functionalities.
We decided to present them very early in the context of this course,
because dynamic arrays can be used in very natural manners
to resolve many problems
that aren't necessarily related to object-oriented programming.
As with fixed-size arrays,
dynamic arrays are a collection of homogeneous data.
To use them,
we use a particular predefined type in Java
called ArrayList. This type isn't defined by default.
To use it in a program, you must include, at the beginning of the file,
an import directive that will make the ArrayList type accessible.
In Java, we can declare a variable of ArrayList type
by using the following syntax:
we put the variable name, and as type,
we put the reserved name "ArrayList",
followed by two characters "less than" and "greater than".
Between these two characters, we put the type of data
we want to put in the array.
Note that the type must imperatively be an advanced type.
Here's a concrete example:
here we declare a variable "tableau" [TN: means "array"],
the type of this variable is a dynamic array of strings.
Note that the so-declared variable isn't initialized:
we didn't assign any initial value to it.
How can we initialize an ArrayList?
A usual way of initializing an ArrayList
is to initialize it with an empty array,
an array without any elements.
This is done like this:
to the variable associated with the array,
we'll assign an empty array created in the following manner.
It has to be used exactly like this.
The reserved word new, the reserved word ArrayList,
here we'll put the exact same type
as the one we used for the array declaration,
followed by two parenthesis, not to forget.
Here we resort to a way related to object-oriented programming,
but it isn't necessary to fully understand
the ins and outs of it to use it.
What you must remember here is that with this instruction line,
you constructed a dynamic array
without any elements.
Here you have a concrete example of declaration-initialization
of an ArrayList of Strings.
The "tableau" variable contains a reference to a dynamic array
of Strings without any element yet.
As this so-declared array doesn't contain any elements,
we'll naturally ask ourselves the following question:
how do we put the values in this array?
As for the strings, there exists a number
of specific methods related to the ArrayList type.
To be able to use these functions,
you must use a particular syntax; the array's name, followed by a dot,
followed by the name of the function
and then we must indicate, in parenthesis, the data
that the function needs to be able to be executed.
Here you have a concrete example.
I declare an ArrayList of strings,
named "prenoms" [TN: means "first name"] and I initialize this array
with an empty array.
Then I use a particular function
defined for ArrayList, called "size".
This function simply returns the current size
of the ArrayList.
I used the syntax I just mentioned,
that is the array's name, followed by a dot,
followed by the function's name.
"size" doesn't need any external information
to return us the array's size,
so I must put an empty pair of parenthesis.
Of course, this instruction line's execution will print 0,
as I've initialized the array with an empty array.
Now here's a non-exhaustive list
of a few typical functions associated with arrays.
We just saw the "size" function [a.k.a. "size" method]
that allows us to get the array's size
and that returns it as an integer.
There exists other functions/methods such as "get" and "set"
that I'll use according to the same principle,
that is the array's name, a dot, followed by the function's name.
Here I notice that unlike the "size" method,
I need to give data to the "get" or "set" methods
in order for them to work.
The "get" and "set" methods are the equivalent
of the indexation mechanism for static arrays.
For a simple static array, if I want to access
the element of index 'i', I use indexation.
This mechanism doesn't exist for dynamic arrays.
Instead, you must use methods such as "get" and "set".
For a dynamic array,
if I want to access the element of index 'i',
I'll use this notation
rather than this one.
The same applies if I want to modify a static array.
I'll use this notation,
so if I want to modify the i-th cell of a static array
I'll use this notation.
This doesn't exist for dynamic arrays,
instead we'll have to use this type of notation;
the array's name, a dot, "set", and in parenthesis the index of the cell
that I want to modify and the corresponding value.
So this notation doesn't exist either for dynamic arrays.
The restrictions on the index's bounds
stay however the same as for a fixed-size array,
the index varies between 0 and the array's size - 1.
array's size - 1 is written like this for
a dynamic array, for example.
So, as with fixed-size arrays,
any access attempt with an index out of the bounds
will translate into an error at the program's execution.
It's possible to test if a dynamic array is empty
by using the "isEmpty" function.
This is a function that doesn't need any data
to work. It will return
a value of boolean type, true or false,
depending if the array contains values or not.
The returned value will be true if the array doesn't contain any values
and false otherwise.
The "clear" method empties an ArrayList,
which means that it deletes all its elements,
and transforms it into an empty array.
If we imagine for example that at a given moment
in a program, I have an ArrayList
that is in this state of filling
-- let's imagine that it's an ArrayList of integers named "tab" --
if I call the "isEmpty" function,
it's obvious that the result will be the false boolean,
as the array isn't empty.
I can now apply the "clear" function, for example,
that will delete all the elements
and transform it into an empty array. There is no more element in it.
So if I call again the "isEmpty" function,
this time the result will be true, as the array is now empty.
The "remove" method allows us to delete
the element of index 'i' in an ArrayList.
So if we imagine for example that at a given moment,
we have an ArrayList of integers with three cells,
that has this particular form,
the indexes vary between 0 and size - 1, which gives us this.
Let's assume that the array is named "tab".
Now, if I call the "size" function on this array,
it will return 3 because my array contains three cells.
Now if I call the "remove" method
and pass it the index 1,
this element will be removed,
so all the elements
that follow this element will be shifted to the left
and I'll finally obtain an array with two cells.
And if I apply my "tab.size()" function again,
it will obviously return 2.
Here we see that for an ArrayList,
the size can indeed vary during the execution
with the calls to methods of this nature.
The index of the element that we want to remove
obivously has to exist in the array
when we call the "remove" function.
Let's suppose for example that instead of doing "tab.remove(1)*,
I try doing "tab.remove(4)".
This will result in an error during the program's execution.
If it's possible to remove elements from an ArrayList,
it is also possible to add values in such an array.
To achieve this we'll use the "add" method,
and we'll have to give the value that we want to add to the array.
The value will systematically be added at the end of the array.
Let's take a concrete example of an array of integers.
Here, "tab.size()" returns 3.
I add the value 8 to my array by using the "add" method.
The result will be an array with an additional cell.
This cell is at the end so I'll have this in "tab",
and of course "tab.size()" will now return 4;
we can see that the array increased by one cell.
Now here's an example with a few basic manipulations
that we can usually do on an ArrayList.
So we saw that to be able to use the ArrayList type,
it was necessary to begin the file
with an import directive
that will make the ArrayList type
available in the program.
I can now use the ArrayList type
to declare a variable
and here I'm declaring a variable
of type ArrayList of Strings.
We also saw
that in order to initialize the array to an empty array,
we have to use this sort of notation.
So at the end of the execution of this instruction line,
I get as a list the reference to an empty ArrayList.
I then execute the following instruction line.
I call the "add" method that allows me to add a particular element,
here the string "un" [TN: means "one"] at the end of the ArrayList.
As the array is empty, it doesn't make a big difference;
ultimately I'll have a dynamic array that will look like this.
I execute the following instruction line that adds a string,
the string "deux" [TN: means "two"] at the end of the array.
So here I get the following content in the array.
If I want to print the content of my ArrayList at this stage,
I use a for-loop. We saw that we could use
for example a for-loop iterating over a set of values.
Here my for-loop will alternately take each element of the list
and print it by separating them with a space.
So here, after the execution of this instruction line, will be printed
the string "un" separated by a whitespace from the string "two",
that will get printed like this on the screen.
If I want to access the i-th cell of an ArrayList,
either to look at its content, or to modify it,
I'll have to use the "get" and "set" methods.
So if I execute this instruction line,
knowing that the array filling at this stage is like this,
I'll use the "get" method
that will access the element of index 1 in the array.
This element of index 1 is the string "deux"
and at that moment I'll print the sequence "deux".
When I execute the following instruction line,
I'll modify the element at the index 0
in order that its new value is the string "premier" [TN: means "first"].
So my array will now look like this,
after the execution of this instruction line.
The element of index 0 that was "un" has been changed into "premier".
In every example of ArrayList showed until now,
the content was of type "String".
Of course, it's a deliberate choice
that responds to the constraint that the content of an ArrayList in Java
must systematically be of an advanced type.
It can however turn out that we need
to work with dynamic arrays of integers.
How would we then proceed?
It's enough to know at this stage
that Java offers for each basic type,
a corresponding advanced type. For example, for the 'int' type,
you have the Integer type, with an uppercase 'I',
that is equivalent to "int" but is of advanced type.
The same applies for the "double" type.
There is an equivalent, "Double with an uppercase 'D';
and this is valid for each basic type.
These advanced types of a patricular kind
are particularly useful in some contexts,
typically for ArrayList.
Why?
Because we saw that in an ArrayList,
it's only possible to store values of advanced type.
Thereby, in a Java program, I can never declare
an ArrayList of "double" with a lowercase 'd', nor an ArrayList of "int".
I can however declare an ArrayList of "Integer".
Once the array's declaration is done
and respects the constraint that the content is of an advanced type,
I can put
values of elementary type in my array,
for a very simple reason.
That reason is that the conversion of basic types into advanced types
can be done automatically.
That was't the case in the first versions of Java,
but that's how it's done now.
And I can therefore work with dynamic
arrays of "Integers" or of "Doubles"
while being nearly free from the constraint
of using advanced types.
Now let's see that with a concrete example.
Here we want to write a small program
that fills an ArrayList of integers
with stricly positive numbers.
We suppose that the values will be requested from the user
and we also want to adhere to a number of conventions.
If the user enters the value 0, that will be the convention
that we want to restart filling the array from the beginning.
If the user enters a negative number,
that will be the convention that we want to remove
the last element introduced in the array.
The program's execution could look like this.
We ask the user
to enter three strictly positive values,
and we'll ask him each of these values alternately.
Here we ask him to enter the value of index 0
and we suppose that he entered 5.
This value being strictly positive,
we'll store it in the array.
We then ask him the second value, the one of index 1.
This value is strictly positive,
we put it in the array, once again.
We then ask him to enter the last value,
the value of index 2. But it turns out that the user enters a 0,
which corresponds to the convention to restart from the beginning.
Which means that at this point,
we want the array to be empty again.
So as the array is emptied again, the next value
that we'll ask from the user will be the value of index 0 again.
Here the user enters a 7, we'll therefore have this array.
He then enters a 2, we get this array.
He then enters, for the last value again,
a negative value, which corresponds for us
to the second convention, the one that says to remove the last element.
The last entered element is the 2,
so we want the array to now look like this,
and that's why, at the next step,
we'll ask the user to enter the second value again,
as the array now contains only one value.
At that moment the user enters a 4,
that we'll store in the array,
he then enters a 12 as last value,
and we'll end up with this array.
As we indeed have the three desired values,
we constructed our array as we intended to,
and we'll finally end up with an array that contains 7, 4 and 12,
which are all strictly positive values.
Here we see that during the entire program's execution,
our array's size increases and decreases following our needs.
So that's typically a case
where the use of an ArrayList is particularly adapted.
Now let's see how all this looks like
in the form of a Java program.
The computations showed in the previous example
can be implemented with
a small Java program that looks like this.
We begin by declaring an ArrayList of integers.
As we can't create an ArrayList of "int" type,
of any elementary type, we use the "Integer" type.
Our ArrayList is named "vect"
and is initialized as an empty ArrayList.
So ultimately the "vect" variable will contain
the reference to an empty ArrayList of integers.
We then ask the user
how many values he wants to enter in the array.
We input the size that the user wants for the array
with a keyboard interaction.
We then ask the user
to input the different values to fill the array.
To achieve that, we use a loop,
as he is potentially going to enter many values.
The loop is such that
while the actual array size hasn't reached the desired size,
we continue to loop.
During each loop iteration,
we ask the user to input one of the values in the array.
But what value precisely?
Here we want to indicate to the user
the index of the value to input.
Let's suppose that the array's filling state is the following:
so at this moment
vect.size() has the value 2
and the last element
has index 1,
which is vect.size() - 1.
That means that the next value of the array that we want to input
does indeed have "vect.size()" as index,
and that's what we can see here.
We'll ask the user to input the value
that's at the position vect.size(), that will occupy the position vect.size().
The value to put in the array is again input
with a keyboard interaction.
And that's when we begin testing the different cases
to adhere to the different conventions presented
in the previous example.
One of the conventions that we wanted to implement
is that if the value introduced by the user is negative,
that would mean that we want to remove
the last element introduced in the array.
So concretely, we'll use the "remove" method
to do this suppression.
And at that moment we'll remove the last element of the array,
the element of index vect.size() - 1,
as we saw here.
However, we have to take a precaution.
We can process with this suppression
only if the ArrayList isn't empty.
Therefore, we must combine this first test
with a second test
that will test if the ArrayList,
is empty or not. So we'll proceed with the suppression
only if the value is negative and if the array isn't empty.
Whether it is empty or not is tested with the isEmpty function.
The fact it isn't empty is expressed with this negation.
If the condition expressed here isn't verified,
we must then proceed with other tests.
We saw that we wanted to have the convention
that if the user enters the value '0',
that means that we want to empty the array.
We therefore proceed with an alternative test here.
To completely empty an ArrayList,
you use the "clear" function.
So here, simply,
if the value entered by the user is null,
then we completely empty the array.
Otherwise, if we reach this stage of the execution,
that means that either the entered value
is strictly positive, or the vector is null.
It therefore isn't strictly guaranteed
that the entered value is positive.
You must therefore test it again; that's what we do here.
If this is the case, if the condition is verified,
we can then add the value to our ArrayList
and that is done with the "add" function.
So, we are going to iterate over these computations
while the ArrayList
hasn't reached the size wanted by the user.
Note an important thing.
We constructed our array, we declared it
by using the advanced type 'Integer'.
This means that in our array,
we don't directly have integer values
like this,
or like I have shown very schematically
in the example.
But to be exact, we have references to integers
in the array.
So here the situation would be as follows:
at the position '0' we would have a reference
to a memory address that contains '12', and not directly the value '12'.
In this case, how did we enter
a value of 'int' type in the array
like we have done here?
Indeed, as our array has been declared
as containing 'Integer',
we expect to be able to add to this array
only values of the same type,
and therefore not directly an integer, but a reference to an integer,
which we don't know how to construct or initialize for the moment.
However, we were able to directly enter an 'int'.
This is allowed thanks to the automatic conversion
that is done between the basic types
and the corresponding advanced types.
So in reality, when we execute this instruction line,
what we put in the array isn't directly the value "val"
entered by the user, which is of 'int' type,
but we put in the array
an "Integer", which is a reference to the value "val".
All this is done in a completely automatic and transparent way.
We didn't have to worry about conversions.
So thanks to this automatic conversion,
it becomes completely natural to also work
with ArrayLists of integers, of doubles, or of a basic type.
The only precaution that we must take
is to declare the array
with the corresponding advanced type.
This automatic conversion between a basic type
and a corresponding advanced type
is what we call "autoboxing", in technical terms.
We saw that an ArrayList can only contain
elements of advanced types.
To conclude, let's examine the incidence that this has on the comparison
of the elements of such an array.
At the first instruction line,
I'll have the automatic conversion of a value of basic type
to a value of 'Integer' type.
But I am in reality adding to my ArrayList isn't
directly the value 2000,
but a reference to this value.
So I end up with a memory situation
that is the following.
Here the value 2000 was not directly stored in our ArrayList,
but its address.
So when I execute the second instruction line,
it's exactly the same situation
that happens,
except that at that moment I have 2 references.
It turns out that these references have a similar content,
but they were created by two distinct "add".
And at that moment, they are two different, distinct, memory addresses.
So here, if I want to compare the content of the first entry of the array
with the second, with something like this,
the result of this instruction line's execution
will in reality be false.
Why? Because I indeed have
2 distinct memory addresses,
and it isn't the same memory location,
and the comparison will return false.
If we are more interested in comparing the contents,
then, as we did with the Strings, we mustn't resort to
an equality test with '==',
but rather to an equality test with 'equals'.
So we access the first element of the array, which is an 'Integer',
and we apply the 'equals' method on this element to compare
it with the second element of the array.
And here, the result of this instruction line's execution
will indeed be 'true' because the values are identical.
The values to which the references point are identical.
