In computer science, a data structure is a way of storing data in a computer so that it can be used efficiently. Often a carefully chosen data structure will allow the most efficient algorithm to be used. A well-designed data structure allows a variety of critical operations to be performed, using as few resources, both execution time and memory space, as possible. Data structures are implemented using the data types, references and operations on them provided by a programming language.
Chapter 1: Memory, Abstract Data Types, and Addresses
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
- are also called random access memory (is where instructions and data are stored)
- is volatile; that is, instructions and data contained in main memory are lost once the computer is powered down.
Cache memory
-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.
Persistent storage
- 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.
Data and Memory
Data used by your program is stored in memory and manipulated by various data structure techniques, depending on the nature of your program.
Reserving memory
Before any data can be stored in memory, you must tell the computer how much space to reserve for data by using an abstract data type.
Abstract data type
- is a keyword of a programming language that specifies the amount of memory needed to store data and the kind of data that will be stored in that memory location.
Memory Address
Imagine main memory as a series of seemingly endless boxes organized into groups of eight. Each box holds a zero or one. Each group of eight boxes (1 byte) is assigned a unique number called a memory address,
Chapter 2: The Point about Variables and Pointers
A pointer is a variable that is used to point to a memory address whose content you want to use in your program.
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
Primitive Data Type
- Primitive data type is defined by the programming language.
- Some programmers call these built-in data types.
User-defined data type
- group of primitive data types defined by the programmer
- User-defined data type varies depending on the programming language used to write the program.
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 body - open 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.
#include
using namespace std; ////use to look in the std library to find the object
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.
Pointers
- 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. 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;
No comments:
Post a Comment