Структуры данных
Память , абстрактные типы данных , адреса
Каково максимальное число попыток , которое нужно вам для того ,
чтобы найти определенное имя в списке из миллиона имен ?
Миллион ? Гораздо меньше.
Это можно сделать за 20 попыток ,
если ваш список имеет эффективный алгоритм поиска.
Поисковые списки - один из способов структурирования данных ,
который помогает вам манипулировать этими данными в памяти вашего компьютера
В этом разделе вы увидите , как устроена память компьютера ,
и почему в памяти хранятся только нули и единицы :-)
Обзор памяти
Computer memory is divided into three sections: main memory, cache memory in the central processing unit (CPU), and persistent storage. Main memory, also called random access memory (RAM), is where instructions (programs) and data are stored. Main memory is volatile; that is, instructions and data contained in main memory are lost once the computer is powered down.
Cache memory in the CPU is used to store frequently used instructions and data that either is, will be, or has been used by the CPU. A segment of the CPU’s cache memory is called a register. A register is a small amount of memory within the CPU that is used to temporarily store instructions and data.
A bus connects the CPU and main memory. A bus is a set of etched wires on the motherboard that is similar to a highway and transports instructions and data between the CPU, main memory, and other devices connected to a computer (see Figure 1-1).
Persistent storage is an external storage device such as a hard disk that stores instructions and data. Persistent storage is nonvolatile; that is, instructions and data remain stored even when the computer is powered down.
Persistent storage is commonly used by the operating system as virtual memory. Virtual memory is a technique an operating system uses to increase the main memory capacity beyond the random access memory (RAM) inside the computer. When main memory capacity is exceeded, the operating system temporarily copies the contents of a block of memory to persistent storage. If a program needs access to instructions or data contained in the block, the operating system switches the block stored in persistent storage with a block of main memory that isn’t being used.
CPU cache memory is the type of memory that has the fastest access speed. A close second is main memory. Persistent storage is a distant third because persistent storage devices usually involve a mechanical process that inhibits the quick transfer of instructions and data.
Throughout this book, we’ll focus on main memory because this is the type of memory used by data structures (although the data structures and techniques presented can also be applied to file systems on persistent storage).
Данные и память Data used by your program is stored in memory and manipulated by various data structure techniques, depending on the nature of your program. Let’s take a close look at main memory and how data is stored in memory before exploring how to manipulate data using data structures.
Memory is a bunch of electronic switches called transistors that can be placed in one of two states: on or off. The state of a switch is meaningless unless you assign a value to each state, which you do using the binary numbering system.
The binary numbering system consists of two digits called binary digits (bits): zero and one. A switch in the off state represents zero, and a switch in the on state represents one. This means that one transistor can represent one of two digits.
However, two digits don’t provide you with sufficient data to do anything but store the number zero or one in memory. You can store more data in memory by logically grouping together switches. For example, two switches enable you to store two binary digits, which gives you four combinations, as shown Table 1-1, and these combinations can store numbers 0 through 3. Digits are zero-based, meaning that the first digit in the binary numbering system is zero, not 1. Memory is organized into groups of eight bits called a byte, enabling 256 combinations of zeros and ones that can store numbers from 0 through 255.
Table 1-1: Combinations of Two Bits and Their Decimal Value Equivalents
Switch 1
|
Switch 2
|
Decimal Value
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
0
|
2
|
1
|
1
|
3
|
The Binary Numbering System
A numbering system is a way to count things and perform arithmetic. For example, humans use the decimal numbering system, and computers use the binary numbering system. Both these numbering systems do exactly the same thing: they enable us to count things and perform arithmetic. You can add, subtract, multiply, and divide using the binary numbering system and you’ll arrive at the same answer as if you used the decimal numbering system.
However, there is a noticeable difference between the decimal and binary numbering systems: the decimal numbering system consists of 10 digits (0 through 9) and the binary numbering system consists of 2 digits (0 and 1).
To jog your memory a bit, remember back in elementary school when the teacher showed you how to “carry over” a value from the right column to the left column when adding two numbers? If you had 9 in the right column and added 1, you changed the 9 to a 0 and placed a 1 to the left of the 0 to give you 10:
The same “carry over” technique is used when adding numbers in the binary numbering system except you carry over when the value in the right column is 1 instead of 9. If you have 1 in the right column and add 1, you change the 1 to a 0 and place a 1 to the left of the 0 to give you 10:
Now the confusion begins. Both the decimal number and the binary number seem to have the same value, which is ten. Don’t believe everything you see. The decimal number does represent the number 10. However, the binary number 10 isn’t the value 10 but the value 2.
The digits in the binary numbering system represent the state of a switch. A computer performs arithmetic by using the binary numbering system to change the state of sets of switches.
Chapter 2: The Point About Variables and Pointers
Some programmers cringe at the mere mention of the word “pointer” because it brings to mind complex, low-level programming techniques that are confounding. Hogwash. Pointers are child play, literally. Watch a 15-month-old carefully and you’ll notice that she points to things she wants, and that’s a pointer in a nutshell. A pointer is a variable that is used to point to a memory address whose content you want to use in your program. You’ll learn all about pointer variables in this chapter.
Declaring Variables and Objects
Memory is reserved by using a data type in a declaration statement. The form of a declaration statement varies depending on the programming language you use. Here is a declaration statement for C, C++, and Java:
int myVariable;
There are three parts to this declaration statement:
-
Data type Tells how much memory to reserve and the kind of data that will be stored in that memory location
-
Variable name A name used within the program to refer to the contents of that memory location
-
Semicolon Tells the computer this is an instruction (statement)
Primitive Data Types and User-Defined Data Types
In Chapter 1, you were introduced to the concept of abstract data types, which are used to reserve computer memory. Abstract data types are divided into two categories, primitive data types and user-defined data types. A primitive data type is defined by the programming language, such as the data types you learned about in the previous chapter. Some programmers call these built-in data types.
The other category of abstract data type, a user-defined data type, is a group of primitive data types defined by the programmer. For example, let’s say you want to store students’ grades in memory. You’ll need to store 4 data elements: the student’s ID, first name, last name, and grade. You could use primitive data types for each data element, but primitive data types are not grouped together; each exists as separate data elements.
A better approach is to group primitive data types into a user-defined data type to form a record. You probably heard the term “record” used when you learned about databases. Remember that a database consists of one or more tables. A table is similar to a spreadsheet consisting of columns and rows. A row is also known as a record. A user-defined data type defines columns (primitive data types) that comprise a row (a user-defined data type).
The form used to define a user-defined data type varies depending on the programming language used to write the program. Some programming languages, such as Java, do not support user-defined data types. Instead, attributes of a class are used to group together primitive data types; this is discussed later in this chapter.
In the C and C++ programming languages, you define a user-defined data type by defining a structure. Think of a structure as a stencil of the letter A. The stencil isn’t the letter A, but it defines what the letter A looks like. If you want a letter A, you place the stencil on a piece of paper and trace the letter A. If you want to make another letter A, you use the same stencil and repeat the process. You can make as many letter A’s as you wish by using the stencil.
The same is true about a structure. When you want the group of primitive data types represented by the structure, you create an instance of the structure. An instance is the same as the letter A appearing on the paper after you remove the stencil.
Each instance contains the same primitive data types that are defined in the structure, although each instance has its own copy of those primitive data types.
Defining a User-Defined Data Type
A structure definition consists of four elements:
-
struct Tells the computer that you are defining a structure
-
Structure name The name used to uniquely identify the structure and used to declare instances of a structure
-
Structure bodypen and close braces within which are primitive data types that are declared when an instance of the structure is declared
-
Semicolon Tells the computer this is an instruction (statement)
The body of a structure can contain any combination of primitive data types and previously defined user-defined data types depending on the nature of the data required by your program. Here is a structure that defines a student record consisting of a student number and grade. The name of this user-defined data type is StudentRecord:
struct StudentRecord
{
int studentNumber;
char grade;
};
Declaring a User-Defined Data Type
You declare an instance of a user-defined data type using basically the same technique that you used to declare a variable. However, you use the name of the structure in place of the name of the primitive data type in the declaration station.
Let’s say that you want to create an instance of the StudentRecord structure defined in the previous section. Here’s the declaration statement that you need to declare in your program:
#include <iostream>
using namespace std;
struct StudentRecord
{
int studentNumber;
char grade;
} ;
void main()
{
StudentRecord myStudent;
myStudent.studentNumber = 10;
myStudent.grade = 'A';
cout << "grades: " << myStudent.studentNumber << " "
<< myStudent.grade << endl;
}
The declaration statement tells the computer to reserve memory the size required to store the StudentRecord user-defined data type and to associate myStudent with that memory location. The size of a user-defined data type is equal to the sum of the sizes of the primitive data types declared in the body of the structure.
The size of the StudentRecord user-defined data type is the sum of the sizes of an integer and a char. As you recall from Chapter 1, the size of a primitive data type is measured in bits. The number of bits for the same primitive data type varies depending on the programming language. Therefore, programmers refer to the name of the primitive data type rather than the number of bits when reserving memory. The computer knows how many bits to reserve for each primitive data type.
User-Defined Data Types and Memory
Data elements within the body of a structure are placed sequentially in memory when an instance of the structure is declared within a program. Figure 2-1 illustrates memory reserved when the myStudent instance of StudentRecord is declared.
The instance name myStructure is an alias for the memory address that is reserved for the first primitive data type defined in the StudentRecord structure, which is memory address 1 in Figure 2-1. For the sake of simplicity, let’s say each block shown in Figure 2-1 represents 1 byte of memory and the size of an int is 2 bytes.
Each primitive data type of a structure has its own memory address. The first primitive data type in this example is studentNumber, and its name references memory location 1. The second primitive data type is grade, and its name references memory location 2.
What happened to memory location 1? This can be confusing. Remember that each byte of memory is assigned a unique memory address. Some primitive data types are larger than a byte and therefore must occupy more than one memory address, which is the case in this example with an int. The first primitive data type takes up the first 2 bytes of memory. Therefore, the second primitive data type defined in the structure is placed in the next available byte of memory, which is memory location 2.
Accessing Elements of a User-Defined Data Type
Elements of a data structure are accessed by using the name of the instance of the structure and the name of the element separated by a dot operator. Let’s say that you want to assign the grade A to the grade element of the myStudent instance of the StudentRecord structure. Here’s how you would write the assignment statement:
myStudent.grade = 'A';
You use elements of a structure the same way you use a variable within your program except you must reference both the name of the instance and the name of the element in order to access the element. The combination of instance name and element name is the alias for the memory location of the element.
User-Defined Data Type and Classes
Structures are used in procedure languages such as C. Object-oriented languages such as C++ and Java use both structures and classes to group together unlike primitive data types into a cohesive unit.
A class definition is a stencil similar in concept to a structure definition in that both use the definition to create instances. A structure definition creates an instance of a structure, while a class definition creates an instance of a class.
A class definition translates attributes and behaviors of a real life object into a simulation of that object within a program. Attributes are data elements similar to elements of a structure. Behaviors are instructions that perform specific tasks known as either methods or functions, depending on the programming language used to write the program. Java references these as methods and C++ references them as functions.
Defining a Class
A class definition resembles a definition of a structure, as you can see in the following example. A class definition consists of four elements:
-
class Tells the computer that you are defining a class
-
Class name The name used to uniquely identify the class and used to declare instances of a class
-
Class body Open and close braces within which are primitive data types that are declared when an instance of the class is declared and definitions
-
of methods and functions that are members of the class
-
Semicolon Tells the computer this is an instruction (statement)
The following class definition written in C++ defines the same student record that is defined in the structure defined in the previous section of this chapter. However, the class definition also defines a function that displays the student number and grade on the screen.
class StudentRecord {
int studentNumber;
char grade;
void displayGrade() {
cout<<"Student: " << studentNumber << " Grade: "
<< grade << endl;
}
};
Declaring an Instance of a Class and a Look at Memory
You declare an instance of a class much the same way you declare a structure. That is, you use the name of the class followed by the name of the instance of the class in a declaration statement. Here is how an instance of the StudentRecord class is declared:
StudentRecord myStudent;
Memory is reserved for attributes of a class definition sequentially when an instance is declared, much the same way as memory is reserved for elements of a structure. Figure 2-2 shows memory allocation for the myStudent instances of the StudentRecord class. Notice that this is basically the same way memory for a structure is allocated.
Methods and functions are stored separately in memory from attributes when an instance is declared because methods and functions are shared among all instances of the same class.
Accessing Members of a Class
Attributes, methods, and functions are referred to as members of a class. You access members of an instance of a class using the name of the instance, the dot operator and the name of the member, much the same ways as you access an element of a structure.
Here is how to access the grade attribute of the myStudent instance of the StudentRecord class and call the displayGrade() method:
myStudent.grade = 'A';
myStudent.displayGrade();
PointersWhenever you reference the name of a variable, the name of an element of a structure, or the name of an attribute of a class, you are telling the computer that you want to do something with the contents stored at the corresponding memory location.
In the first statement in the following example, the computer is told to store the letter A into the memory location represented by the variable grade. The last statement tells the computer to copy the contents of the memory location represented by the grade variable and store it in the memory location represented by the oldGrade variable.
char grade = 'A';
char oldGrade;
oldGrade = grade;
A pointer is a variable and can be used as an element of a structure and as an attribute of a class in some programming languages such as C++, but not Java. However, the contents of a pointer is a memory address of another location of memory, which is usually the memory address of another variable, element of a structure, or attribute of a class.
Declaring a Pointer
A pointer is declared similar to how you declare a variable but with a slight twist. The following example declares a pointer called ptGrade. There are four parts of this declaration:
-
Data type The data type of the memory address stored in the pointer
-
Asterisk (*) Tells the computer that you are declaring a pointer
-
Variable name The name that uniquely identifies the pointer and is used to reference the pointer within your program
-
Semicolon Tells the computer this is an instruction (statement)
char *ptGrade;
Data Type and Pointers
As you will recall, a data type tells the computer the amount of memory to reserve and the kind of data that will be stored at that memory location. However, the data type of a pointer tells the computer something different. It tells the computer the data type of the value at the memory location whose address is contained in the pointer.
Confused? Many programmers are confused about the meaning of the data type used to declare a pointer, so you’re in good company. The best way to clear any confusion is to get back to basics.
The asterisk (*) used when declaring a pointer tells the computer the amount of memory to reserve and the kind of data that will be stored at that location. That is, the memory size is sufficient to hold a memory address, and the kind of data stored there is a memory address.
You’re probably wondering why you use a data type when declaring a pointer. Before answering that question, let’s make sure you have a firm understanding of pointers. The following example declares four variables. The first statement declares an integer variable called studentNumber. The second statement declares a char variable called grade. The last two statements each declare a pointer. Figure 2-3 depicts memory reserved by these statements. Assume that a memory address is 4 bytes for this example.
int studentNumber;
char grade;
char *ptGrade;
int *ptStudentNumber;
The char data type in the ptGrade pointer declaration tells the computer that the address that will be stored in ptGrade is the address of a character. As you’ll see in the next section, the contents of the memory location associated with ptGrade will contain the address of the grade variable.
Likewise, the int data type of the ptStudentNumber pointer states that the contents of the memory location associated with ptStudentNumber will contain the address of an integer variable, which will be the address of the studentNumber variable.
Why does the computer need to know this? For now, let’s simply say that programmers instruct the computer to manipulate memory addresses using pointer arithmetic. In order for the computer to carry out those instructions, the computer must know the data type of the address contained in a pointer. You’ll learn pointer arithmetic later in this chapter.
Assigning an Address to a Pointer
An address of a variable is assigned to a pointer variable by using the address operator (&). Before you learn about dereferencing a variable, let’s review an assignment statement. The following assignment statement tells the computer to copy the value stored at the memory location that is associated with the grade variable and store the value into the memory location associated with the oldGrade variable:
oldGrade = grade;
An assignment statement implies that you want the contents of a variable and not the address of the variable. The address operator tells the computer to ignore the implied assignment and assign the memory address of the variable and not the content of the variable.
The next example tells the computer by using the address operator to copy the address of the variable to the pointer variable. That is, the memory address of the grade variable is copied to the ptGrade pointer variable, and the memory address of the studentNumber variable is assigned to the ptStudentNumber pointer:
ptGrade = &grade;
ptStudentNumber = &studentNumber;
Figure 2-4 depicts memory after the previous two statements execute. Notice that the grade variable is an alias for memory address 3 and the studentNumber variable is the alias for memory address 1. The content of ptGrade pointer is 3, which is the memory address of the grade variable. Likewise, the content of pointer ptStudentNumber is 1, which is the memory address of studentNumber.
Accessing Data Pointed to by a Pointer
A pointer variable references a memory location that contains a memory address. Sometimes a programmer wants to copy that memory address to another pointer variable. This is accomplished by using an assignment statement as shown here:
ptOldGrade = ptNewGrade;
You’ll notice that this assignment statement is identical to assignment statements used with any variable. Remember that the assignment statement tells the computer to copy the contents of a variable regardless if the content is a memory address or any other value.
Other times, programmers want to the use the content of the memory address stored in the pointer variable. This may be tricky to understand, so let’s look at an example to clear up any confusion. The following statements will be familiar to you because we’ve used them in examples throughout this chapter.
The first two statements declare variables, one of which is initialized with a value. The next two statements declare pointer variables. And the last statement assigns the address of the first variable to pointer variables. Figure 2-5 shows how memory looks after these statements execute.
char oldGrade;
char grade = 'A';
char *ptGrade;
char *ptOldGrade;
ptGrade = &grade;
Let’s say a programmer wants to use the value stored in the grade variable to display the grade on the screen. However, the programmer wants to use only the ptGrade pointer to do this. Here’s how it is done.
The programmer uses the pointer dereferencing operator (sometimes called the dereferencing operator), which is the asterisk (*), to dereference the point variable. Think of dereferencing as telling the computer you are referring to to go to the memory address contained in the pointer and then perform the operation. Without dereferencing, the computer is told to use the contents of the pointer when performing the operation.
Let’s say that you want to copy the content of ptGrade to ptOldGrade. Here’s how you would do it:
ptOldGrade = ptGrade;
Figure 2-6 shows you the effect this statement has on memory.
Now let’s suppose you want to copy the contents of grade to the oldGrade variable, but you only want to use the ptGrade pointer. You do this by dereferencing the ptGrade pointer variable using the asterisk (*) as the dereferencing pointer operator as shown here:
char oldGrade = *ptGrade;
The previous statement tells the computer to go to the memory address contained in the ptGrade pointer variable and then perform the assignment operation, which copies the value of memory address 2 to the memory address represented by the oldGrade variable, which is memory address 1. The result is shown in Figure 2-7.
You can dereference a pointer variable any time you want to use the contents of the memory address pointed to by the variable and use the dereference pointer variable in any statement that you would use a variable.
Pointer Arithmetic
Pointers are used to step through memory sequentially by using pointer arithmetic and the incremental (++) or decremental (- -) operator. The incremental operator increases the value of a variable by 1, and the decremental operator decreases the value of a variable by 1.
In the following example, the value of the studentNumber variable is incremented by 1, making the final value 1235.
int studentNumber = 1234;
studentNumber++;
Likewise, the next example decreases the value of the studentNumber variable by 1, resulting in the final value of 1233.
int studentNumber = 1234;
studentNumber--;
Pointer arithmetic uses the incremental and decremental operator in a similar but slightly different way. The following statements declare two variables used to store student numbers and two pointers each pointing to one of those variables. Figure 2-8 depicts memory allocation after these statements execute.
int studentNumber1 = 1234;
int studentNumber2 = 5678;
int *ptStudentNumber1;
int *ptStudentNumber2;
ptStudentNumber1 = &studentNumber1;
ptStudentNumber2 = &studentNumber2;
What would be the value stored in the pointer variable studentNumber1 if the studentNumber1 is incremented by 1 using the following statement?
ptStudentNumber1++;
This is tricky because the value of ptStudentNumber1 is 0. If you increment it by one, the new value is 1. However, memory address 2 is the second half of the memory location reserved for studentNumber1. This means that ptStudentNumber1 would point to the middle of the values of studentNumber1, which doesn’t make sense.
That’s not what happens. The computer uses pointer arithmetic. Values are incremented and decremented in pointer arithmetic using the size of a data type. That is, if the memory address contains an integer and the memory address is incremented, the computer adds the size of an integer to the current memory address.
Let’s return to Figure 2-8 and see how this works. ptStudentNumber1 contains the memory address 1. If you go to memory address 1, you’ll notice that the memory address stores an integer. In the example, the size of an integer is 2 bytes. When ptStudentNumber1 is incremented using pointer arithmetic, the computer adds 2 bytes to the address stored in ptStudentNumber1 making the new value 2, which is stored in ptStudentNumber1. Figure 2-9 shows the results of incrementing using pointer arithmetic.
Decrementing a value using pointer arithmetic is very similar to incrementing a value, except the size of a data type is subtracted from the value. Let’s return to Figure 2-8 for a moment. If the following statement executed, the value of ptStudentNumber2 would be 1 because the computer subtracts the size of an integer (2 bytes) from the current value of the ptStudentNumber2 (2).
ptStudentNumber2--;
Pointers to Pointers
Imagine having a list of a million students along with their final grades and student numbers and being asked to sort the list by last name, first name, and student number. Intuitively, you might think about making two copies of this list, each placed in one of the sort orders. However, this wastes memory. There is a better approach to sort the list: use pointers to pointers.
You learned that a pointer is a variable that contains the memory address of another variable. A pointer to a pointer is also a variable that contains the memory address, except a pointer to a pointer contains the memory address of another pointer variable.
Confused? You’re not alone. The concept of a pointer to a pointer isn’t intuitive to understand. However, we can clear up any confusion by declaring variables and storing values into memory.
Let’s begin by declaring four char variables and initializing them with letters of the alphabet. This is shown in the first statement of the following example. The second statement declares a pointer called ptInitial and a pointer to a pointer called ptPtInitial. A pointer is declared using a signal asterisk (*). A pointer to a pointer is declared using a double asterisk (**).
char inital1 = 'D', inital2 = 'A', inital3 = 'C', inital4 = 'B';
char *ptInitial, **ptPtInitial;
ptInitial = &inital1;
ptPtInitial = &ptInitial;
With variables declared, the next two statements assign values to the pointer and to the pointer to a pointer. In both cases, the ampersand (&) is used as the dereferencing operator.
The ptInitial pointer variable is assigned the address of variable inital1, which is memory address 1. The ptPtInitial pointer to a pointer variable is assigned the memory address of ptInitial. The address of ptInitial is memory address 5. Figure 2-10 shows the allocated memory after these statements execute.
Programmers use a pointer to a pointer to tell a computer to use the contents of the memory address contained in the pointer variable that the pointer to a pointer is pointing to. This is a mouthful, so we’ll restate this using an example:
You can use the content of the inital1 variable by referencing the ptPtInitial variable. Here’s how this is done:
cout << **ptPtInitial;
The cout statement is used in C++ to display something on the screen. In this example, you’re displaying the content of the initial1 variable, although it doesn’t seem to be doing so. This statement is telling the computer to go to the memory address stored in the ptPtInitial pointer to a pointer variable, which is memory address 5 (see Figure 2-11). The content of that memory address is another memory address, which is memory address 1. The computer is told to go to memory address 1 and display the content of that memory address, which is the letter D.
|
|