字幕列表 影片播放 列印英文字幕 >> [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.