Placeholder Image

字幕列表 影片播放

  • >> [MUSIC PLAYING]

  • DOUG LLOYD: All right.

  • Working with single variables is pretty fun.

  • But what if we want to work with a lot of variables,

  • but we don't want to have a bunch of different names flying around our code?

  • In this case, arrays are going to come in really handy.

  • Arrays are a really fundamental data structure for any programming language

  • that you will use.

  • And they're really, really useful, particularly, as we'll see, in CS 50.

  • >> We use arrays to hold values of the same data type

  • at contiguous memory locations.

  • That is to say, it's a way that we can group

  • a bunch of integers together in memory or a bunch of characters

  • or floats in memory really close together and work

  • with them without having to give each one its own unique name, which can

  • get cumbersome after a little while.

  • >> Now, one way to analogize arrays is to think about your local post

  • office for a second.

  • So step away from programming and just close your eyes

  • and visualize in your mind your local post office.

  • Usually, in most post offices, there's a large bank

  • a post office boxes on the wall.

  • >> An array is a giant block of contiguous memory,

  • the same way that a mail bank in your post office

  • is a large space on the wall of the post office.

  • Arrays have been partitioned into small, identically sized blocks of space,

  • each of which is called an element, in the same way that the wall of the post

  • office has been partitioned into small, identically sized blocks of space,

  • which we call a PO box.

  • Each element of the array can store a certain amount of data,

  • just as each post office box is able to hold a certain amount of mail.

  • >> What can be stored in each element of the array is variables of the same data

  • type, such as int or char, just like in your post office box,

  • you can only fit things of a similar type,

  • such as letters or small packages.

  • Lastly, we can access each element of the array directly by index number,

  • just as we can access our post office box by knowing its mailbox number.

  • Hopefully, that analogy helps you get your head

  • around the idea of arrays by analogizing to something else

  • that you are probably already familiar with.

  • >> In C, the elements of an array are indexed starting from 0, not from 1.

  • And this is really important.

  • And in fact, this is why we, in CS 50, and why computer scientists frequently

  • will count from 0, is because of C's array

  • indexing, which always starts at 0.

  • So if an array consists of n elements, the first element of that array

  • is located at index 0, and the last element of the array

  • is located at index n minus 1.

  • Again, if there's n elements in our array, the last index is n minus 1.

  • >> So if our array has 50 elements, the first element is located at index 0,

  • and the last element is located at index 49.

  • Unfortunately, or fortunately, depending on your perspective,

  • C is very lenient here.

  • It will not prevent you from going out of bounds of your array.

  • You could access the minus 3 element of your array

  • or the 59th element of your array, if your array only has 50 elements.

  • It won't stop your program from compiling, but at run time,

  • you might encounter a dreaded segmentation fault

  • if you start to access memory that is outside the bounds of what

  • you asked your program to give you.

  • So do be careful.

  • >> What does an array declaration look like?

  • How do we code an array into existence like we code any other variable?

  • There are three parts to an array declaration-- a type, a name,

  • and a size.

  • This is very similar to a variable declaration, which

  • is just a type and a name, the size element being

  • the special case for an array, because we are getting a bunch of them

  • at the same time.

  • >> So the type is what kind of variable you want each element of the array to be.

  • Do want it to an array of integers?

  • Then, your data type should be int.

  • Do you want it to be an array of doubles or floats?

  • Data type should be double or float.

  • The name is what you want to call your array.

  • What do you want to name this giant bank of integers or floats or chars

  • or doubles, or whatever have you?

  • What do you want to call it?

  • Pretty self explanatory.

  • >> Lastly, size, which goes inside of square brackets,

  • is how many elements you would like your array to contain.

  • How many integers do you want?

  • How many floats do you want?

  • >> So for example, int student grades 40.

  • This declares an array called Student grades, which consists of 40 integers.

  • Pretty self explanatory, I hope.

  • Here's another example.

  • Double menu prices 8.

  • This creates an array called Menu prices, which consists

  • of room in memory for eight doubles.

  • >> If you think of every element of an array of type data-type,

  • so for example, a single element of an array of type int, the same way you

  • would think of any other variable of type int,

  • all the familiar operations that we discussed previously in the Operations

  • video will make sense.

  • So here, we could declare an array of Booleans called Truthtable,

  • which consists of room for 10 Booleans.

  • >> And then, just like we could just assign a value to any other variable of type

  • Boolean, we could say something like Truthtable square bracket

  • 2, which is how we indicate, which element of the truth table?

  • The third element of the truth table, because remember,

  • we're counting from 0.

  • So that's how we indicate the third element of the truth table.

  • Truthtable 2 equals false, just like we could declare--

  • or we could assign, rather, any Boolean type variable to be false.

  • >> We can also use it in conditions.

  • if(truthtable 7 == true), which is to say,

  • if the eighth element of Truthtable is true,

  • maybe we want to print a message to the user, printf("TRUE!n");.

  • That causes us to say Truthtable 10 equals true, right?

  • Well, I can, but it's pretty dangerous, because remember,

  • we have an array of 10 Booleans.

  • So the highest index that the compiler has given us is 9.

  • >> This program will compile, but if something else in memory

  • exists where we would expect Truthtable 10 to go,

  • we could suffer a segmentation fault. We might get away with it, but in general,

  • pretty dangerous.

  • So what I'm doing here is legal C, but not necessarily the best move.

  • Now, when you declare and initialize an array simultaneously,

  • there's actually a pretty special syntax that you

  • can use to fill up the array with its starting values.

  • It can get cumbersome to declare an array of size 100,

  • and then have to say, element 0 equals this; element 1 equals this;

  • element 2 equals that.

  • What's the point, right?

  • >> If it's a small array, you could do something like this.

  • Bool truthtable 3 equals open curly brace and then comma

  • separate the list of elements that you want to put in the array.

  • Then close curly brace semicolon.

  • This creates an array of size three called Truthtable,

  • with elements false, true, and true.

  • And in fact, the instantiation syntax I have here is

  • exactly the same as doing the individual element syntax below.

  • These two ways of coding would produce the exact same array.

  • >> Similarly, we could iterate over all of the elements

  • of an array using a loop, which, in fact, is a very strongly recommended

  • at-home exercise.

  • How do you create an array of 100 integers, where

  • every element of the array is its index?

  • So for example, we have a array of 100 integers, and in the first element,

  • we want to put 0.

  • In the second element, we want to put 1.

  • In the third element, we want to put 2; and so on and so on.

  • That's a really good at-home exercise to do that.

  • >> Here, it doesn't look like too much has changed.

  • But notice that in between the square brackets, this time,

  • I've actually omitted the number.

  • If you're using this very special instantiation

  • syntax to create an array, you actually don't

  • need to indicate the size of the array beforehand.

  • The compiler is smart enough to know that you actually

  • want an array of size 3, because you put three elements

  • to the right of the equal sign.

  • If you had put four, it would have given you a truth table of size four;

  • and so on and so on.

  • >> Arrays are not restricted to a single dimension, which is pretty cool.

  • You can actually have as many side specifiers as you wish.

  • So for example, if you want to create a board for the game Battleship, which,

  • if you ever played, is a game that is played with pegs on the 10 by 10 grid,

  • you could create an array like this.

  • You could say Bool battleship square bracket 10

  • closed square bracket square bracket 10 closed square bracket.

  • >> And then, you can choose to interpret this in your mind as a 10

  • by 10 grid of cells.

  • Now, in fact, in memory, it really does just

  • remain a 100 element, single dimensional array.

  • And this, in fact, goes for if you have three dimensions or four or five.

  • It really just does multiply all of the indices--

  • or all of the size specifiers-- together,

  • and you just get a one-dimensional array of that size.

  • >> But in terms of organization and visualization and human perception,

  • it can be a lot easier to work with a grid

  • if you're working on a game like Tic-tac-toe or Battleship,

  • or something like that.

  • It's a great abstraction, instead of having

  • to think about a Tic-tac-toe board as a line of nine

  • squares or a Battleship board as a line of 100 squares.

  • A 10 by 10 grid or a three by three grid is probably

  • a lot more easy to perceive.

  • >> Now, something really important about arrays.

  • We can treat each individual element of the array as a variable.

  • We saw that earlier when we were assigning

  • the value True to certain Booleans or testing them in conditionals.

  • But we can't treat entire arrays themselves as variables.

  • We cannot, for example, assign one array to another array using the assignment

  • operator.

  • It's not legal C.

  • >> If we want to, for example-- what we would be doing in that example

  • would be to copy one array into another.

  • If we want to do that, we actually need to use a loop to copy over

  • each individual element one at a time.

  • I know it's a little time consuming.

  • >> So for example, if we had these couple of lines of code, would this work?

  • Well, no, it wouldn't, right?

  • Because we're trying to assign food to bar.

  • That's not going to work, because it's an array,

  • and we just described that that's not legal C.

  • >> Instead, if we want to copy the contents of food

  • into bar, which is what we're trying to do here,

  • we would need a syntax like this.

  • We have a for loop that goes from J is equal to 0 up to 5,

  • and we increment J on every iteration of the loop and assign elements like that.

  • This would result in bar also being one, two, three, four, five,

  • but we have to do it this very slow element-by-element way,

  • instead of by just copying the entire array.

  • In other programming languages, more modern ones,

  • you can, in fact, do just that simple equals syntax.

  • But C, unfortunately, we're not allowed to do that.

  • >> Now, there's one other thing I want to mention

  • about arrays that can be a little bit tricky the first time you

  • work with them.

  • We discussed in a video about variable scope,

  • that most variables in C, when you call them in functions, are passed by value.

  • Do you remember what it means to pass something by value?

  • It means we're making a copy of the variable that's being passed in.

  • The callee function, the function that's receiving the variable,

  • doesn't get the variable itself.

  • It gets its own local copy of it to work with.

  • >> Arrays, of course, do not follow this rule.

  • Rather, what we call this is passing by reference.

  • The callee actually does receive the array.

  • It does not receive its own local copy of it.

  • And if you think about it, this makes sense.

  • If arrays are really large, it takes so much time and effort

  • to make a copy of an array of 100 or 1,000 or 10,000 elements,

  • that it's not worth it for a function to receive a copy of it,

  • do some work with it, and then just be done with the copy;

  • it doesn't need to have it hanging around anymore.

  • >> Because arrays are some bulky and cumbersome,

  • we just pass them by reference.

  • We just trust that function to, don't break anything.

  • So it does actually get the array.

  • It doesn't get its own local copy of it.

  • >> So what does this mean, then, when the callee

  • manipulates elements of the array?

  • What happens?

  • For now, we'll gloss over why exactly this

  • happens, why arrays are passed by reference

  • and everything else is passed by value.

  • But I promise you, we will return and give you the answer

  • to this in a later video.

  • >> Here's one more exercise for you before we wrap up things on arrays.

  • The bunch of code here, that's not particularly good style,

  • just I'll make that caveat.

  • There's no comments in here, which is pretty bad form.