thêm phần tiếng Anh ai mun thi copy ve nha tham khao nha !!!
2 posters
Trang 1 trong tổng số 1 trang
thêm phần tiếng Anh ai mun thi copy ve nha tham khao nha !!!
by waitingforever188 7/4/2010, 19:07
Pointers
Pointers are used everywhere in C, so if you want to use the C language fully you
have to have a very good understanding of pointers. They have to become
comfortable for you. The goal of this section and the next several that follow is to
help you build a complete understanding of pointers and how C uses them. For
most people it takes a little time and some practice to become fully comfortable
with pointers, but once you master them you are a full-fledged C programmer.
C uses pointers in three different ways:
• C uses pointers to create dynamic data structures -- data structures built
up from blocks of memory allocated from the heap at run-time.
• C uses pointers to handle variable parameters passed to functions.
• Pointers in C provide an alternative way to access information stored in
arrays. Pointer techniques are especially valuable when you work with
strings. There is an intimate link between arrays and pointers in C.
In some cases, C programmers also use pointers because they make the code
slightly more efficient. What you will find is that, once you are completely
comfortable with pointers, you tend to use them all the time.
We will start this discussion with a basic introduction to pointers and the concepts
surrounding pointers, and then move on to the three techniques described above.
Especially on this article, you will want to read things twice. The first time through
you can learn all the concepts. The second time through you can work on binding
the concepts together into an integrated whole in your mind. After you make your
way through the material the second time, it will make a lot of sense.
Why Use Pointers?
Imagine that you would like to create a text editor -- a program that lets you edit
normal ASCII text files, like "vi" on UNIX or "Notepad" on Windows. A text editor is
a fairly common thing for someone to create because, if you think about it, a text
editor is probably a programmer's most commonly used piece of software. The
text editor is a programmer's intimate link to the computer -- it is where you enter
all of your thoughts and then manipulate them. Obviously, with anything you use
that often and work with that closely, you want it to be just right. Therefore many
programmers create their own editors and customize them to suit their individual
working styles and preferences.
So one day you sit down to begin working on your editor. After thinking about the
features you want, you begin to think about the "data structure" for your editor.
That is, you begin thinking about how you will store the document you are editing
in memory so that you can manipulate it in your program. What you need is a way
to store the information you are entering in a form that can be manipulated quickly
and easily. You believe that one way to do that is to organize the data on the
basis of lines of characters. Given what we have discussed so far, the only thing
you have at your disposal at this point is an array. You think, "Well, a typical line
is 80 characters long, and a typical file is no more than 1,000 lines long." You
therefore declare a two-dimensional array, like this:
char doc[1000][80];
This declaration requests an array of 1,000 80-character lines. This array has a
total size of 80,000 characters.
As you think about your editor and its data structure some more, however, you
might realize three things:
• Some documents are long lists. Every line is short, but there are thousands
of lines.
• Some special-purpose text files have very long lines. For example, a
certain data file might have lines containing 542 characters, with each
character representing the amino acid pairs in segments of DNA.
• In most modern editors, you can open multiple files at one time.
Let's say you set a maximum of 10 open files at once, a maximum line length of
1,000 characters and a maximum file size of 50,000 lines. Your declaration now
looks like this:
char doc[50000][1000][10];
That doesn't seem like an unreasonable thing, until you pull out your calculator,
multiply 50,000 by 1,000 by 10 and realize the array contains 500 million
characters! Most computers today are going to have a problem with an array that
size. They simply do not have the RAM, or even the virtual memory space, to
support an array that large. If users were to try to run three or four copies of this
program simultaneously on even the largest multi-user system, it would put a
severe strain on the facilities.
Even if the computer would accept a request for such a large array, you can see
that it is an extravagant waste of space. It seems strange to declare a 500 million
character array when, in the vast majority of cases, you will run this editor to look
at 100 line files that consume at most 4,000 or 5,000 bytes. The problem with an
array is the fact that you have to declare it to have its maximum size in every
dimension from the beginning. Those maximum sizes often multiply together to
form very large numbers. Also, if you happen to need to be able to edit an odd file
with a 2,000 character line in it, you are out of luck. There is really no way for you
to predict and handle the maximum line length of a text file, because, technically,
that number is infinite.
Pointers are designed to solve this problem. With pointers, you can create
dynamic data structures. Instead of declaring your worst-case memory
consumption up-front in an array, you instead allocate memory from the heap
while the program is running. That way you can use the exact amount of memory
a document needs, with no waste. In addition, when you close a document you
can return the memory to the heap so that other parts of the program can use it.
With pointers, memory can be recycled while the program is running.
By the way, if you read the previous discussion and one of the big questions you
have is, "What IS a byte, really?," then the article How Bits and Bytes Work will
help you understand the concepts, as well as things like "mega," "giga" and "tera."
Go take a look and then come back.
Pointer Basics
To understand pointers, it helps to compare them to normal variables.
A "normal variable" is a location in memory that can hold a value. For example,
when you declare a variable i as an integer, four bytes of memory are set aside
for it. In your program, you refer to that location in memory by the name i. At the
machine level that location has a memory address. The four bytes at that address
are known to you, the programmer, as i, and the four bytes can hold one integer
value.
A pointer is different. A pointer is a variable that points to another variable. This
means that a pointer holds the memory address of another variable. Put another
way, the pointer does not hold a value in the traditional sense; instead, it holds
the address of another variable. A pointer "points to" that other variable by holding
a copy of its address.
Because a pointer holds an address rather than a value, it has two parts. The
pointer itself holds the address. That address points to a value. There is the
pointer and the value pointed to. This fact can be a little confusing until you get
comfortable with it, but once you get comfortable it becomes extremely powerful.
The following example code shows a typical pointer:
#include <stdio.h>
int main()
{
int i,j;
int *p; /* a pointer to an integer */
p = &i;
*p=5;
j=i;
printf("%d %d %d\n", i, j, *p);
return 0;
}
The first declaration in this program declares two normal integer variables named
i and j. The line int *p declares a pointer named p. This line asks the compiler to
declare a variable p that is a pointer to an integer. The * indicates that a pointer
is being declared rather than a normal variable. You can create a pointer to
anything: a float, a structure, a char, and so on. Just use a * to indicate that you
want a pointer rather than a normal variable.
The line p = &i; will definitely be new to you. In C, & is called the address
operator. The expression &i means, "The memory address of the variable i."
Thus, the expression p = &i; means, "Assign to p the address of i." Once you
execute this statement, p "points to" i. Before you do so, p contains a random,
unknown address, and its use will likely cause a segmentation fault or similar
program crash.
One good way to visualize what is happening is to draw a picture. After i, j and p
are declared, the world looks like this:
In this drawing the three variables i, j and p have been declared, but none of the
three has been initialized. The two integer variables are therefore drawn as boxes
containing question marks -- they could contain any value at this point in the
program's execution. The pointer is drawn as a circle to distinguish it from a
normal variable that holds a value, and the random arrows indicate that it can be
pointing anywhere at this moment.
After the line p = &I;, p is initialized and it points to i, like this:
Once p points to i, the memory location i has two names. It is still known as i, but
now it is known as *p as well. This is how C talks about the two parts of a pointer
variable: p is the location holding the address, while *p is the location pointed to
by that address. Therefore *p=5 means that the location pointed to by p should be
set to 5, like this:
Because the location *p is also i, i also takes on the value 5. Consequently, j=i;
sets j to 5, and the printf statement produces 5 5 5.
The main feature of a pointer is its two-part nature. The pointer itself holds an
address. The pointer also points to a value of a specific type - the value at the
address the point holds. The pointer itself, in this case, is p. The value pointed to
is *p.
Understanding Memory Addresses
The previous discussion becomes a little clearer if you understand how memory
addresses work in a computer's hardware. If you have not read it already, now
would be a good time to read How Bits and Bytes Work to fully understand bits,
bytes and words.
All computers have memory, also known as RAM (random access memory). For
example, your computer might have 16 or 32 or 64 megabytes of RAM installed
right now. RAM holds the programs that your computer is currently running along
with the data they are currently manipulating (their variables and data structures).
Memory can be thought of simply as an array of bytes. In this array, every
memory location has its own address -- the address of the first byte is 0, followed
by 1, 2, 3, and so on. Memory addresses act just like the indexes of a normal
array. The computer can access any address in memory at any time (hence the
name "random access memory"). It can also group bytes together as it needs to
to form larger variables, arrays, and structures. For example, a floating point
variable consumes 4 contiguous bytes in memory. You might make the following
global declaration in a program:
float f;
This statement says, "Declare a location named f that can hold one floating point
value." When the program runs, the computer reserves space for the variable f
somewhere in memory. That location has a fixed address in the memory space,
like this:
The variable f consumes four bytes of RAM in memory.
That location has a specific address, in this case 248,440.
While you think of the variable f, the computer thinks of a specific address in
memory (for example, 248,440). Therefore, when you create a statement like this:
f = 3.14;
The compiler might translate that into, "Load the value 3.14 into memory location
248,440." The computer is always thinking of memory in terms of addresses and
values at those addresses.
There are, by the way, several interesting side effects to the way your computer
treats memory. For example, say that you include the following code in one of
your programs:
int i, s[4], t[4], u=0;
for (i=0; i<=4; i++)
{
s[i] = i;
t[i] =i;
}
Printf("s:t\n");
for (i=0; i<=4; i++)
printf("%d:%d\n", s[i], t[i]);
printf("u = %d\n", u);
The output that you see from the program will probably look like this:
s:t
1:5
2:2
3:3
4:4
5:5
u = 5
Why are t[0] and u incorrect? If you look carefully at the code, you can see that
the for loops are writing one element past the end of each array. In memory, the
arrays are placed adjacent to one another, as shown here:
Therefore, when you try to write to s[4], which does not exist, the system writes
into t[0] instead because t[0] is where s[4] ought to be. When you write into t[4],
you are really writing into u. As far as the computer is concerned, s[4] is simply an
address, and it can write into it. As you can see however, even though the
computer executes the program, it is not correct or valid. The program corrupts
the array t in the process of running. If you execute the following statement, more
severe consequences result:
s[1000000] = 5;
The location s[1000000] is more than likely outside of your program's memory
space. In other words, you are writing into memory that your program does not
own. On a system with protected memory spaces (UNIX, Windows 98/NT), this
sort of statement will cause the system to terminate execution of the program. On
other systems (Windows 3.1, the Mac), however, the system is not aware of what
you are doing. You end up damaging the code or variables in another application.
The effect of the violation can range from nothing at all to a complete system
crash. In memory, i, s, t and u are all placed next to one another at specific
addresses. Therefore, if you write past the boundaries of a variable, the computer
will do what you say but it will end up corrupting another memory location.
Because C and C++ do not perform any sort of range checking when you access
an element of an array, it is essential that you, as a programmer, pay careful
attention to array ranges yourself and keep within the array's appropriate
boundaries. Unintentionally reading or writing outside of array boundaries always
leads to faulty program behavior.
As another example, try the following:
#include <stdio.h>
int main()
{
int i,j;
int *p; /* a pointer to an integer */
printf("%d %d\n", p, &i);
p = &i;
printf("%d %d\n", p, &i);
return 0;
}
This code tells the compiler to print out the address held in p, along with the
address of i. The variable p starts off with some crazy value or with 0. The
address of i is generally a large value. For example, when I ran this code, I
received the following output:
0 2147478276
2147478276 2147478276
which means that the address of i is 2147478276. Once the statement p = &i;
has been executed, p contains the address of i. Try this as well:
#include <stdio.h>
void main()
{
int *p; /* a pointer to an integer */
printf("%d\n",*p);
}
This code tells the compiler to print the value that p points to. However, p has not
been initialized yet; it contains the address 0 or some random address. In most
cases, a segmentation fault (or some other run-time error) results, which means
that you have used a pointer that points to an invalid area of memory. Almost
always, an uninitialized pointer or a bad pointer address is the cause of
segmentation faults.
Having said all of this, we can now look at pointers in a whole new light. Take this
program, for example:
#include <stdio.h>
int main()
{
int i;
int *p; /* a pointer to an integer */
p = &i;
*p=5;
printf("%d %d\n", i, *p);
return 0;
}
Here is what's happening:
The variable i consumes 4 bytes of memory. The pointer p also consumes 4
bytes (on most machines in use today, a pointer consumes 4 bytes of memory.
Memory addresses are 32-bits long on most CPUs today, although there is a
increasing trend toward 64-bit addressing). The location of i has a specific
address, in this case 248,440. The pointer p holds that address once you say p =
&i;. The variables *p and i are therefore equivalent.
The pointer p literally holds the address of i. When you say something like this in
a program:
printf("%d", p);
what comes out is the actual address of the variable i.
Here is a cool aspect of C: Any number of pointers can point to the same
address. For example, you could declare p, q, and r as integer pointers and set
all of them to point to i, as shown here:
int i;
int *p, *q, *r;
p = &i;
q = &i;
r = p;
Note that in this code, r points to the same thing that p points to, which is i. You
can assign pointers to one another, and the address is copied from the right-hand
side to the left-hand side during the assignment. After executing the above code,
this is how things would look:
The variable i now has four names: i, *p, *q and *r. There is no limit on the
number of pointers that can hold (and therefore point to) the same address.
C Errors to Avoid
Bug #1 - Uninitialized pointers
One of the easiest ways to create a pointer bug is to try to
reference the value of a pointer even though the pointer is
uninitialized and does not yet point to a valid address. For
example:
int *p;
*p = 12;
The pointer p is uninitialized and points to a random location in
memory when you declare it. It could be pointing into the system
stack, or the global variables, or into the program's code space, or
into the operating system. When you say *p=12;, the program will
simply try to write a 12 to whatever random location p points to.
The program may explode immediately, or may wait half an hour
and then explode, or it may subtly corrupt data in another part of
your program and you may never realize it. This can make this
error very hard to track down. Make sure you initialize all pointers
to a valid address before dereferencing them.
Bug #2 - Invalid Pointer References
An invalid pointer reference occurs when a pointer's value is
referenced even though the pointer doesn't point to a valid block.
One way to create this error is to say p=q;, when q is uninitialized.
The pointer p will then become uninitialized as well, and any
reference to *p is an invalid pointer reference.
The only way to avoid this bug is to draw pictures of each step of
the program and make sure that all pointers point somewhere.
Invalid pointer references cause a program to crash inexplicably
for the same reasons given in Bug #1.
Bug #3 - Zero Pointer Reference
A zero pointer reference occurs whenever a pointer pointing to
zero is used in a statement that attempts to reference a block. For
example, if p is a pointer to an integer, the following code is
invalid:
p = 0;
*p = 12;
There is no block pointed to by p. Therefore, trying to read or write
anything from or to that block is an invalid zero pointer reference.
There are good, valid reasons to point a pointer to zero, as we will
see in later articles. Dereferencing such a pointer, however, is
invalid.
All of these bugs are fatal to a program that contains them. You
must watch your code so that these bugs do not occur. The best
way to do that is to draw pictures of the code's execution step by
step.
Using Pointers for Function Parameters
Most C programmers first use pointers to implement something called variable
parameters in functions. You have actually been using variable parameters in the
scanf function -- that's why you've had to use the & (the address operator) on
variables used with scanf. Now that you understand pointers you can see what
has really been going on.
To understand how variable parameters work, lets see how we might go about
implementing a swap function in C. To implement a swap function, what you
would like to do is pass in two variables and have the function swap their values.
Here's one attempt at an implementation -- enter and execute the following code
and see what happens:
#include <stdio.h>
void swap(int i, int j)
{
int t;
t=i;
i=j;
j=t;
}
void main()
{
int a,b;
a=5;
b=10;
printf("%d %d\n", a, b);
swap(a,b);
printf("%d %d\n", a, b);
}
When you execute this program, you will find that no swapping takes place. The
values of a and b are passed to swap, and the swap function does swap them,
but when the function returns nothing happens.
To make this function work correctly you can use pointers, as shown below:
#include <stdio.h>
void swap(int *i, int *j)
{
int t;
t = *i;
*i = *j;
*j = t;
}
void main()
{
int a,b;
a=5;
b=10;
printf("%d %d\n",a,b);
swap(&a,&b);
printf("%d %d\n",a,b);
}
To get an idea of what this code does, print it out, draw the two integers a and b,
and enter 5 and 10 in them. Now draw the two pointers i and j, along with the
integer t. When swap is called, it is passed the addresses of a and b. Thus, i
points to a (draw an arrow from i to a) and j points to b (draw another arrow from
b to j). Once the pointers are initialized by the function call, *i is another name for
a, and *j is another name for b. Now run the code in swap. When the code uses
*i and *j, it really means a and b. When the function completes, a and b have
been swapped.
Suppose you accidentally forget the & when the swap function is called, and that
the swap line accidentally looks like this: swap(a, b);. This causes a
segmentation fault. When you leave out the &, the value of a is passed instead of
its address. Therefore, i points to an invalid location in memory and the system
crashes when *i is used.
This is also why scanf crashes if you forget the & on variables passed to it. The
scanf function is using pointers to put the value it reads back into the variable you
have passed. Without the &, scanf is passed a bad address and crashes.
Variable parameters are one of the most common uses of pointers in C. Now you
understand what's happening!
Dynamic Data Structures
Dynamic data structures are data structures that grow and shrink as you need
them to by allocating and deallocating memory from a place called the heap.
They are extremely important in C because they allow the programmer to exactly
control memory consumption.
Dynamic data structures allocate blocks of memory from the heap as required,
and link those blocks together into some kind of data structure using pointers.
When the data structure no longer needs a block of memory, it will return the
block to the heap for reuse. This recycling makes very efficient use of memory.
To understand dynamic data structures completely, we need to start with the
heap.
How the Heap Works
A typical personal computer or workstation today has somewhere between 16
and 64 megabytes of RAM installed. Using a technique called virtual memory,
the system can swap pieces of memory on and off the machine's hard disk to
create an illusion for the CPU that it has much more memory, for example 200 to
500 megabytes. While this illusion is complete as far as the CPU is concerned, it
can sometimes slow things down tremendously from the user's perspective.
Despite this drawback, virtual memory is an extremely useful technique for
"increasing" the amount of RAM in a machine in an inexpensive way. Let's
assume for the sake of this discussion that a typical computer has a total memory
space of, for example, 50 megabytes (regardless of whether that memory is
implemented in real RAM or in virtual memory).
The operating system on the machine is in charge of the 50-megabyte memory
space. The operating system uses the space in several different ways, as shown
here:
The operating system and several applications, along with
their global variables and stack spaces, all consume portions
of memory. When a program completes execution, it releases
its memory for reuse by other programs. Note that part of the
memory space remains unused at any given time.
This is, of course, an idealization, but the basic principles are correct. As you can
see, memory holds the executable code for the different applications currently
running on the machine, along with the executable code for the operating system
itself. Each application has certain global variables associated with it. These
variables also consume memory. Finally, each application uses an area of
memory called the stack, which holds all local variables and parameters used by
any function. The stack also remembers the order in which functions are called so
that function returns occur correctly. Each time a function is called, its local
variables and parameters are "pushed onto" the stack. When the function returns,
these locals and parameters are "popped." Because of this, the size of a
program's stack fluctuates constantly as the program is running, but it has some
maximum size.
As a program finishes execution, the operating system unloads it, its globals and
its stack space from memory. A new program can make use of that space at a
later time. In this way, the memory in a computer system is constantly "recycled"
and reused by programs as they execute and complete.
In general, perhaps 50 percent of the computer's total memory space might be
unused at any given moment. The operating system owns and manages the
unused memory, and it is collectively known as the heap. The heap is extremely
important because it is available for use by applications during execution using
the C functions malloc (memory allocate) and free. The heap allows programs to
allocate memory exactly when they need it during the execution of a program,
rather than pre-allocating it with a specifically-sized array declaration.
How malloc and free Work
Let's say that you would like to allocate a certain amount of memory during the
execution of your application. You can call the malloc function at any time, and it
will request a block of memory from the heap. The operating system will reserve a
block of memory for your program, and you can use it in any way you like. When
you are done with the block, you return it to the operating system for recycling by
calling the free function. Then other applications can reserve it later for their own
use.
For example, the following code demonstrates the simplest possible use of the
heap:
int main()
{
int *p;
p = (int *)malloc(sizeof(int));
if (p == 0)
{
printf("ERROR: Out of memory\n");
return 1;
}
*p = 5;
printf("&d\n", *p);
free(p);
return 0;
}
The first line in this program calls the malloc function. This function does three
things:
1. The malloc statement first looks at the amount of memory available on the
heap and asks, "Is there enough memory available to allocate a block of
memory of the size requested?" The amount of memory needed for the
block is known from the parameter passed into malloc -- in this case,
sizeof(int) is 4 bytes. If there is not enough memory available, the malloc
function returns the address zero to indicate the error (another name for
zero is NULL and you will see it used throughout C code). Otherwise
malloc proceeds.
2. If memory is available on the heap, the system "allocates" or "reserves" a
block from the heap of the size specified. The system reserves the block of
memory so that it isn't accidentally used by more than one malloc
statement.
3. The system then places into the pointer variable (p, in this case) the
address of the reserved block. The pointer variable itself contains an
address. The allocated block is able to hold a value of the type specified,
and the pointer points to it.
The following diagram shows the state of memory after calling malloc:
The block on the right is the block of memory malloc allocated.
The program next checks the pointer p to make sure that the allocation request
succeeded with the line if (p == 0) (which could have also been written as if (p ==
NULL) or even if (!p). If the allocation fails (if p is zero), the program terminates. If
the allocation is successful, the program then initializes the block to the value 5,
prints out the value, and calls the free function to return the memory to the heap
before the program terminates.
There is really no difference between this code and previous code that sets p
equal to the address of an existing integer i. The only distinction is that, in the
case of the variable i, the memory existed as part of the program's pre-allocated
memory space and had the two names: i and *p. In the case of memory allocated
from the heap, the block has the single name *p and is allocated during the
program's execution. Two common questions:
• Is it really important to check that the pointer is zero after each
allocation? Yes. Since the heap varies in size constantly depending on
which programs are running, how much memory they have allocated, etc.,
there is never any guarantee that a call to malloc will succeed. You should
check the pointer after any call to malloc to make sure the pointer is valid.
• What happens if I forget to delete a block of memory before the
program terminates? When a program terminates, the operating system
"cleans up after it," releasing its executable code space, stack, global
memory space and any heap allocations for recycling. Therefore, there are
no long-term consequences to leaving allocations pending at program
termination. However, it is considered bad form, and "memory leaks" during
the execution of a program are harmful, as discussed below.
The following two programs show two different valid uses of pointers, and try to
distinguish between the use of a pointer and of the pointer's value:
void main()
{
int *p, *q;
p = (int *)malloc(sizeof(int));
q = p;
*p = 10;
printf("%d\n", *q);
*q = 20;
printf("%d\n", *q);
}
The final output of this code would be 10 from line 4 and 20 from line 6. Here's a
diagram:
The following code is slightly different:
void main()
{
int *p, *q;
p = (int *)malloc(sizeof(int));
q = (int *)malloc(sizeof(int));
*p = 10;
*q = 20;
*p = *q;
printf("%d\n", *p);
}
The final output from this code would be 20 from line 6. Here's a diagram:
Notice that the compiler will allow *p = *q, because *p and *q are both integers.
This statement says, "Move the integer value pointed to by q into the integer
value pointed to by p." The statement moves the values. The compiler will also
allow p = q, because p and q are both pointers, and both point to the same type
(if s is a pointer to a character, p = s is not allowed because they point to different
types). The statement p = q says, "Point p to the same block q points to." In other
words, the address pointed to by q is moved into p, so they both point to the same
block. This statement moves the addresses.
From all of these examples, you can see that there are four different ways to
initialize a pointer. When a pointer is declared, as in int *p, it starts out in the
program in an uninitialized state. It may point anywhere, and therefore to
dereference it is an error. Initialization of a pointer variable involves pointing it to a
known location in memory.
1. One way, as seen already, is to use the malloc statement. This statement
allocates a block of memory from the heap and then points the pointer at
the block. This initializes the pointer, because it now points to a known
location. The pointer is initialized because it has been filled with a valid
address -- the address of the new block.
2. The second way, as seen just a moment ago, is to use a statement such as
p = q so that p points to the same place as q. If q is pointing at a valid
block, then p is initialized. The pointer p is loaded with the valid address
that q contains. However, if q is uninitialized or invalid, p will pick up the
same useless address.
3. The third way is to point the pointer to a known address, such as a global
variable's address. For example, if i is an integer and p is a pointer to an
integer, then the statement p=&i initializes p by pointing it to i.
4. The fourth way to initialize the pointer is to use the value zero. Zero is a
special values used with pointers, as shown here:
5. p = 0;
or:
p = NULL;
What this does physically is to place a zero into p. The pointer p's address
is zero. This is normally diagrammed as:
Any pointer can be set to point to zero. When p points to zero, however, it does
not point to a block. The pointer simply contains the address zero, and this value
is useful as a tag. You can use it in statements such as:
if (p == 0)
{
...
}
or:
while (p != 0)
{
...
}
The system also recognizes the zero value, and will generate error messages if
you happen to dereference a zero pointer. For example, in the following code:
p = 0;
*p = 5;
The program will normally crash. The pointer p does not point to a block, it points
to zero, so a value cannot be assigned to *p. The zero pointer will be used as a
flag when we get to linked lists.
The malloc command is used to allocate a block of memory. It is also possible to
deallocate a block of memory when it is no longer needed. When a block is
deallocated, it can be reused by a subsequent malloc command, which allows the
system to recycle memory. The command used to deallocate memory is called
free, and it accepts a pointer as its parameter. The free command does two
things:
1. The block of memory pointed to by the pointer is unreserved and given
back to the free memory on the heap. It can then be reused by later new
statements.
2. The pointer is left in an uninitialized state, and must be reinitialized before it
can be used again.
The free statement simply returns a pointer to its original uninitialized state and
makes the block available again on the heap.
The following example shows how to use the heap. It allocates an integer block,
fills it, writes it, and disposes of it:
#include <stdio.h>
int main()
{
int *p;
p = (int *)malloc (sizeof(int));
*p=10;
printf("%d\n",*p);
free(p);
return 0;
}
This code is really useful only for demonstrating the process of allocating,
deallocating, and using a block in C. The malloc line allocates a block of memory
of the size specified -- in this case, sizeof(int) bytes (4 bytes). The sizeof
command in C returns the size, in bytes, of any type. The code could just as
easily have said malloc(4), since sizeof(int) equals 4 bytes on most machines.
Using sizeof, however, makes the code much more portable and readable.
The malloc function returns a pointer to the allocated block. This pointer is
generic. Using the pointer without typecasting generally produces a type warning
from the compiler. The (int *) typecast converts the generic pointer returned by
malloc into a "pointer to an integer," which is what p expects. The free statement
in C returns a block to the heap for reuse.
The second example illustrates the same functions as the previous example, but
it uses a structure instead of an integer. In C, the code looks like this:
#include <stdio.h>
struct rec
{
int i;
float f;
char c;
};
int main()
{
struct rec *p;
p=(struct rec *) malloc (sizeof(struct rec));
(*p).i=10;
(*p).f=3.14;
(*p).c='a';
printf("%d %f %c\n",(*p).i,(*p).f,(*p).c);
free(p);
return 0;
}
Note the following line:
(*p).i=10;
Many wonder why the following doesn't work:
*p.i=10;
The answer has to do with the precedence of operators in C. The result of the
calculation 5+3*4 is 17, not 32, because the * operator has higher precedence
than + in most computer languages. In C, the . operator has higher precedence
than *, so parentheses force the proper precedence.
Most people tire of typing (*p).i all the time, so C provides a shorthand notation.
The following two statements are exactly equivalent, but the second is easier to
type:
(*p).i=10;
p->i=10;
You will see the second more often than the first when reading other people's
code.
Advanced Pointers
You will normally use pointers in somewhat more complicated ways than those
shown in some of the previous examples. For example, it is much easier to create
a normal integer and work with it than it is to create and use a pointer to an
integer. In this section, some of the more common and advanced ways of working
with pointers will be explored.
Pointer Types
It is possible, legal, and beneficial to create pointer types in C, as shown below:
typedef int *IntPointer;
...
IntPointer p;
This is the same as saying:
int *p;
This technique will be used in many of the examples below. The technique often
makes a data declaration easier to read and understand, and also makes it easier
to include pointers inside of structures or pass pointer parameters in functions.
Pointers to Structures
It is possible to create a pointer to almost any type in C, including user-defined
types. It is extremely common to create pointers to structures. An example is
shown below:
typedef struct
{
char name[21];
char city[21];
char state[3];
} Rec;
typedef Rec *RecPointer;
RecPointer r;
r = (RecPointer)malloc(sizeof(Rec));
The pointer r is a pointer to a structure. Please note the fact that r is a pointer,
and therefore takes four bytes of memory just like any other pointer. However, the
malloc statement allocates 45 bytes of memory from the heap. *r is a structure
just like any other structure of type Rec. The following code shows typical uses of
the pointer variable:
strcpy((*r).name, "Leigh");
strcpy((*r).city, "Raleigh");
strcpy((*r).state, "NC");
printf("%s\n", (*r).city);
free(r);
You deal with *r just like a normal structure variable, but you have to be careful
with the precedence of operators in C. If you were to leave off the parenthesis
around *r the code would not compile because the "." operator has a higher
precedence than the "*" operator. Because it gets tedious to type so many
parentheses when working with pointers to structures, C includes a shorthand
notation that does exactly the same thing:
strcpy(r->name, "Leigh");
The r-> notation is exactly equivalent to (*r)., but takes two fewer characters.
Pointers to Arrays
It is also possible to create pointers to arrays, as shown below:
int *p;
int i;
p = (int *)malloc(sizeof(int[10]));
for (i=0; i<10; i++)
p[i] = 0;
free(p);
or:
int *p;
int i;
p = (int *)malloc(sizeof(int[10]));
for (i=0; i<10; i++)
*(p+i) = 0;
free(p);
Note that when you create a pointer to an integer array, you simply create a
normal pointer to int. The call to malloc allocates an array of whatever size you
desire, and the pointer points to that array's first element. You can either index
through the array pointed to by p using normal array indexing, or you can do it
using pointer arithmetic. C sees both forms as equivalent.
This particular technique is extremely useful when working with strings. It lets you
allocate enough storage to exactly hold a string of a particular size.
Arrays of Pointers
Sometimes a great deal of space can be saved, or certain memory-intensive
problems can be solved, by declaring an array of pointers. In the example code
below, an array of 10 pointers to structures is declared, instead of declaring an
array of structures. If an array of the structures had been created instead, 243 *
10 = 2,430 bytes would have been required for the array. Using the array of
pointers allows the array to take up minimal space until the actual records are
allocated with malloc statements. The code below simply allocates one record,
places a value in it, and disposes of the record to demonstrate the process:
typedef struct
{
char s1[81];
char s2[81];
char s3[81];
} Rec;
Rec *a[10];
a[0] = (Rec *)malloc(sizeof(Rec));
strcpy(a[0]->s1, "hello");
free(a[0]);
Structures Containing Pointers
Structures can contain pointers, as shown below:
typedef struct
{
char name[21];
char city[21];
char phone[21];
char *comment;
} Addr;
Addr s;
char comm[100];
gets(s.name, 20);
gets(s.city, 20);
gets(s.phone, 20);
gets(comm, 100);
s.comment =
(char *)malloc(sizeof(char[strlen(comm)+1]));
strcpy(s.comment, comm);
This technique is useful when only some records actually contained a comment in
the comment field. If there is no comment for the record, then the comment field
would consist only of a pointer (4 bytes). Those records having a comment then
allocate exactly enough space to hold the comment string, based on the length of
the string typed by the user.
Pointers to Pointers
It is possible and often useful to create pointers to pointers. This technique is
sometimes called a handle, and is useful in certain situations where the operating
system wants to be able to move blocks of memory on the heap around at its
discretion. The following example demonstrates a pointer to a pointer:
int **p;
int *q;
p = (int **)malloc(sizeof(int *));
*p = (int *)malloc(sizeof(int));
**p = 12;
q = *p;
printf("%d\n", *q);
free(q);
free(p);
Windows and the Mac OS use this structure to allow memory compaction on the
heap. The program manages the pointer p, while the operating system manages
the pointer *p. Because the OS manages *p, the block pointed to by *p (**p) can
be moved, and *p can be changed to reflect the move without affecting the
program using p. Pointers to pointers are also frequently used in C to handle
pointer parameters in functions.
Pointers to Structures Containing Pointers
It is also possible to create pointers to structures that contain pointers. The
following example uses the Addr record from the previous section:
typedef struct
{
char name[21];
char city[21];
char phone[21];
char *comment;
} Addr;
Addr *s;
char comm[100];
s = (Addr *)malloc(sizeof(Addr));
gets(s->name, 20);
gets(s->city, 20);
gets( s->phone, 20);
gets(comm, 100);
s->comment =
(char *)malloc(sizeof(char[strlen(comm)+1]));
strcpy(s->comment, comm);
The pointer s points to a structure that contains a pointer that points to a string:
In this example, it is very easy to create lost blocks if you aren't careful. For
example, here is a different version of the AP example.
s = (Addr *)malloc(sizeof(Addr));
gets(comm, 100);
s->comment =
(char *)malloc(sizeof(char[strlen(comm)+1]));
strcpy(s->comment, comm);
free(s);
This code creates a lost block because the structure containing the pointer
pointing to the string is disposed of before the string block is disposed of, as
shown below:
Linking
Finally, it is possible to create structures that are able to point to identical
structures, and this capability can be used to link together a whole string of
identical records in a structure called a linked list.
typedef struct
{
char name[21];
char city[21];
char state[21];
Addr *next;
} Addr;
Addr *first;
The compiler will let you do this, and it can be used with a little experience to
create structures like the one shown below:
A Linked Stack Example
A good example of dynamic data structures is a simple stack library, one that
uses a dynamic list and includes functions to init, clear, push, and pop. The
library's header file looks like this:
/* Stack Library - This library offers the
minimal stack operations for a
stack of integers (easily changeable) */
typedef int stack_data;
extern void stack_init();
/* Initializes this library.
Call first before calling anything. */
extern void stack_clear();
/* Clears the stack of all entries. */
extern int stack_empty();
/* Returns 1 if the stack is empty, 0 otherwise. */
extern void stack_push(stack_data d);
/* Pushes the value d onto the stack. */
extern stack_data stack_pop();
/* Returns the top element of the stack,
and removes that element.
Returns garbage if the stack is empty. */
The library's code file follows:
#include "stack.h"
#include <stdio.h>
/* Stack Library - This library offers the
minimal stack operations for a stack of integers */
struct stack_rec
{
stack_data data;
struct stack_rec *next;
};
struct stack_rec *top=NULL;
void stack_init()
/* Initializes this library.
Call before calling anything else. */
{
top=NULL;
}
void stack_clear()
/* Clears the stack of all entries. */
{
stack_data x;
while (!stack_empty())
x=stack_pop();
}
int stack_empty()
/* Returns 1 if the stack is empty, 0 otherwise. */
{
if (top==NULL)
return(1);
else
return(0);
}
void stack_push(stack_data d)
/* Pushes the value d onto the stack. */
{
struct stack_rec *temp;
temp=
(struct stack_rec *)malloc(sizeof(struct stack_rec));
temp->data=d;
temp->next=top;
top=temp;
}
stack_data stack_pop()
/* Returns the top element of the stack,
and removes that element.
Returns garbage if the stack is empty. */
{
struct stack_rec *temp;
stack_data d=0;
if (top!=NULL)
{
d=top->data;
temp=top;
top=top->next;
free(temp);
}
return(d);
}
Note how this library practices information hiding: Someone who can see only the
header file cannot tell if the stack is implemented with arrays, pointers, files, or in
some other way. Note also that C uses NULL. NULL is defined in stdio.h, so you
will almost always have to include stdio.h when you use pointers. NULL is the
same as zero.
Try This!
• Add a dup, a count, and an add function to the stack
library to duplicate the top element of the stack, return a
count of the number of elements in the stack, and add the
top two elements in the stack.
• Build a driver program and a makefile, and compile the
stack library with the driver to make sure it works.
C Errors to Avoid
• Forgetting to include parentheses when you reference a
record, as in (*p).i above
• Failing to dispose of any block you allocate - For example,
you should not say top=NULL in the stack function,
because that action orphans blocks that need to be
disposed.
• Forgetting to include stdio.h with any pointer operations
so that you have access to NULL.
Using Pointers with Arrays
Arrays and pointers are intimately linked in C. To use arrays effectively, you have
to know how to use pointers with them. Fully understanding the relationship
between the two probably requires several days of study and experimentation, but
it is well worth the effort.
Let's start with a simple example of arrays in C:
#define MAX 10
int main()
{
int a[MAX];
int b[MAX];
int i;
for(i=0; i<MAX; i++)
a[i]=i;
b=a;
return 0;
}
Enter this code and try to compile it. You will find that C will not compile it. If you
want to copy a into b, you have to enter something like the following instead:
for (i=0; i<MAX; i++)
a[i]=b[i];
Or, to put it more succinctly:
for (i=0; i<MAX; a[i]=b[i], i++);
Better yet, use the memcpy utility in string.h.
Arrays in C are unusual in that variables a and b are not, technically, arrays
themselves. Instead they are permanent pointers to arrays. a and b permanently
point to the first elements of their respective arrays -- they hold the addresses of
a[0] and b[0] respectively. Since they are permanent pointers you cannot
change their addresses. The statement a=b; therefore does not work.
Because a and b are pointers, you can do several interesting things with pointers
and arrays. For example, the following code works:
#define MAX 10
void main()
{
int a[MAX];
int i;
int *p;
p=a;
for(i=0; i<MAX; i++)
a[i]=i;
printf("%d\n",*p);
}
The statement p=a; works because a is a pointer. Technically, a points to the
address of the 0th element of the actual array. This element is an integer, so a is
a pointer to a single integer. Therefore, declaring p as a pointer to an integer and
setting it equal to a works. Another way to say exactly the same thing would be to
replace p=a; with p=&a[0];. Since a contains the address of a[0], a and &a[0]
mean the same thing.
The following figure shows the state of the variables right before the for loop
starts executing:
Now that p is pointing at the 0th element of a, you can do some rather strange
things with it. The a variable is a permanent pointer and can not be changed, but
p is not subject to such restrictions. C actually encourages you to move it around
using pointer arithmetic . For example, if you say p++;, the compiler knows that p
points to an integer, so this statement increments p the appropriate number of
bytes to move it to the next element of the array. If p were pointing to an array of
100-byte-long structures, p++; would move p over by 100 bytes. C takes care of
the details of element size.
You can copy the array a into b using pointers as well. The following code can
replace (for i=0; i<MAX; a[i]=b[i], i++); :
p=a;
q=b;
for (i=0; i<MAX; i++)
{
*q = *p;
q++;
p++;
}
You can abbreviate this code as follows:
p=a;
q=b;
for (i=0; i<MAX; i++)
*q++ = *p++;
And you can further abbreviate it to:
for (p=a,q=b,i=0; i<MAX; *q++ = *p++, i++);
What if you go beyond the end of the array a or b with the pointers p or q? C
does not care -- it blithely goes along incrementing p and q, copying away over
other variables with abandon. You need to be careful when indexing into arrays in
C, because C assumes that you know what you are doing.
You can pass an array such as a or b to a function in two different ways. Imagine
a function dump that accepts an array of integers as a parameter and prints the
contents of the array to stdout. There are two ways to code dump:
void dump(int a[],int nia)
{
int i;
for (i=0; i<nia; i++)
printf("%d\n",a[i]);
}
or:
void dump(int *p,int nia)
{
int i;
for (i=0; i<nia; i++)
printf("%d\n",*p++);
}
The nia (number_in_array) variable is required so that the size of the array is
known. Note that only a pointer to the array, rather than the contents of the array,
is passed to the function. Also note that C functions can accept variable-size
arrays as parameters.
Pointers are used everywhere in C, so if you want to use the C language fully you
have to have a very good understanding of pointers. They have to become
comfortable for you. The goal of this section and the next several that follow is to
help you build a complete understanding of pointers and how C uses them. For
most people it takes a little time and some practice to become fully comfortable
with pointers, but once you master them you are a full-fledged C programmer.
C uses pointers in three different ways:
• C uses pointers to create dynamic data structures -- data structures built
up from blocks of memory allocated from the heap at run-time.
• C uses pointers to handle variable parameters passed to functions.
• Pointers in C provide an alternative way to access information stored in
arrays. Pointer techniques are especially valuable when you work with
strings. There is an intimate link between arrays and pointers in C.
In some cases, C programmers also use pointers because they make the code
slightly more efficient. What you will find is that, once you are completely
comfortable with pointers, you tend to use them all the time.
We will start this discussion with a basic introduction to pointers and the concepts
surrounding pointers, and then move on to the three techniques described above.
Especially on this article, you will want to read things twice. The first time through
you can learn all the concepts. The second time through you can work on binding
the concepts together into an integrated whole in your mind. After you make your
way through the material the second time, it will make a lot of sense.
Why Use Pointers?
Imagine that you would like to create a text editor -- a program that lets you edit
normal ASCII text files, like "vi" on UNIX or "Notepad" on Windows. A text editor is
a fairly common thing for someone to create because, if you think about it, a text
editor is probably a programmer's most commonly used piece of software. The
text editor is a programmer's intimate link to the computer -- it is where you enter
all of your thoughts and then manipulate them. Obviously, with anything you use
that often and work with that closely, you want it to be just right. Therefore many
programmers create their own editors and customize them to suit their individual
working styles and preferences.
So one day you sit down to begin working on your editor. After thinking about the
features you want, you begin to think about the "data structure" for your editor.
That is, you begin thinking about how you will store the document you are editing
in memory so that you can manipulate it in your program. What you need is a way
to store the information you are entering in a form that can be manipulated quickly
and easily. You believe that one way to do that is to organize the data on the
basis of lines of characters. Given what we have discussed so far, the only thing
you have at your disposal at this point is an array. You think, "Well, a typical line
is 80 characters long, and a typical file is no more than 1,000 lines long." You
therefore declare a two-dimensional array, like this:
char doc[1000][80];
This declaration requests an array of 1,000 80-character lines. This array has a
total size of 80,000 characters.
As you think about your editor and its data structure some more, however, you
might realize three things:
• Some documents are long lists. Every line is short, but there are thousands
of lines.
• Some special-purpose text files have very long lines. For example, a
certain data file might have lines containing 542 characters, with each
character representing the amino acid pairs in segments of DNA.
• In most modern editors, you can open multiple files at one time.
Let's say you set a maximum of 10 open files at once, a maximum line length of
1,000 characters and a maximum file size of 50,000 lines. Your declaration now
looks like this:
char doc[50000][1000][10];
That doesn't seem like an unreasonable thing, until you pull out your calculator,
multiply 50,000 by 1,000 by 10 and realize the array contains 500 million
characters! Most computers today are going to have a problem with an array that
size. They simply do not have the RAM, or even the virtual memory space, to
support an array that large. If users were to try to run three or four copies of this
program simultaneously on even the largest multi-user system, it would put a
severe strain on the facilities.
Even if the computer would accept a request for such a large array, you can see
that it is an extravagant waste of space. It seems strange to declare a 500 million
character array when, in the vast majority of cases, you will run this editor to look
at 100 line files that consume at most 4,000 or 5,000 bytes. The problem with an
array is the fact that you have to declare it to have its maximum size in every
dimension from the beginning. Those maximum sizes often multiply together to
form very large numbers. Also, if you happen to need to be able to edit an odd file
with a 2,000 character line in it, you are out of luck. There is really no way for you
to predict and handle the maximum line length of a text file, because, technically,
that number is infinite.
Pointers are designed to solve this problem. With pointers, you can create
dynamic data structures. Instead of declaring your worst-case memory
consumption up-front in an array, you instead allocate memory from the heap
while the program is running. That way you can use the exact amount of memory
a document needs, with no waste. In addition, when you close a document you
can return the memory to the heap so that other parts of the program can use it.
With pointers, memory can be recycled while the program is running.
By the way, if you read the previous discussion and one of the big questions you
have is, "What IS a byte, really?," then the article How Bits and Bytes Work will
help you understand the concepts, as well as things like "mega," "giga" and "tera."
Go take a look and then come back.
Pointer Basics
To understand pointers, it helps to compare them to normal variables.
A "normal variable" is a location in memory that can hold a value. For example,
when you declare a variable i as an integer, four bytes of memory are set aside
for it. In your program, you refer to that location in memory by the name i. At the
machine level that location has a memory address. The four bytes at that address
are known to you, the programmer, as i, and the four bytes can hold one integer
value.
A pointer is different. A pointer is a variable that points to another variable. This
means that a pointer holds the memory address of another variable. Put another
way, the pointer does not hold a value in the traditional sense; instead, it holds
the address of another variable. A pointer "points to" that other variable by holding
a copy of its address.
Because a pointer holds an address rather than a value, it has two parts. The
pointer itself holds the address. That address points to a value. There is the
pointer and the value pointed to. This fact can be a little confusing until you get
comfortable with it, but once you get comfortable it becomes extremely powerful.
The following example code shows a typical pointer:
#include <stdio.h>
int main()
{
int i,j;
int *p; /* a pointer to an integer */
p = &i;
*p=5;
j=i;
printf("%d %d %d\n", i, j, *p);
return 0;
}
The first declaration in this program declares two normal integer variables named
i and j. The line int *p declares a pointer named p. This line asks the compiler to
declare a variable p that is a pointer to an integer. The * indicates that a pointer
is being declared rather than a normal variable. You can create a pointer to
anything: a float, a structure, a char, and so on. Just use a * to indicate that you
want a pointer rather than a normal variable.
The line p = &i; will definitely be new to you. In C, & is called the address
operator. The expression &i means, "The memory address of the variable i."
Thus, the expression p = &i; means, "Assign to p the address of i." Once you
execute this statement, p "points to" i. Before you do so, p contains a random,
unknown address, and its use will likely cause a segmentation fault or similar
program crash.
One good way to visualize what is happening is to draw a picture. After i, j and p
are declared, the world looks like this:
In this drawing the three variables i, j and p have been declared, but none of the
three has been initialized. The two integer variables are therefore drawn as boxes
containing question marks -- they could contain any value at this point in the
program's execution. The pointer is drawn as a circle to distinguish it from a
normal variable that holds a value, and the random arrows indicate that it can be
pointing anywhere at this moment.
After the line p = &I;, p is initialized and it points to i, like this:
Once p points to i, the memory location i has two names. It is still known as i, but
now it is known as *p as well. This is how C talks about the two parts of a pointer
variable: p is the location holding the address, while *p is the location pointed to
by that address. Therefore *p=5 means that the location pointed to by p should be
set to 5, like this:
Because the location *p is also i, i also takes on the value 5. Consequently, j=i;
sets j to 5, and the printf statement produces 5 5 5.
The main feature of a pointer is its two-part nature. The pointer itself holds an
address. The pointer also points to a value of a specific type - the value at the
address the point holds. The pointer itself, in this case, is p. The value pointed to
is *p.
Understanding Memory Addresses
The previous discussion becomes a little clearer if you understand how memory
addresses work in a computer's hardware. If you have not read it already, now
would be a good time to read How Bits and Bytes Work to fully understand bits,
bytes and words.
All computers have memory, also known as RAM (random access memory). For
example, your computer might have 16 or 32 or 64 megabytes of RAM installed
right now. RAM holds the programs that your computer is currently running along
with the data they are currently manipulating (their variables and data structures).
Memory can be thought of simply as an array of bytes. In this array, every
memory location has its own address -- the address of the first byte is 0, followed
by 1, 2, 3, and so on. Memory addresses act just like the indexes of a normal
array. The computer can access any address in memory at any time (hence the
name "random access memory"). It can also group bytes together as it needs to
to form larger variables, arrays, and structures. For example, a floating point
variable consumes 4 contiguous bytes in memory. You might make the following
global declaration in a program:
float f;
This statement says, "Declare a location named f that can hold one floating point
value." When the program runs, the computer reserves space for the variable f
somewhere in memory. That location has a fixed address in the memory space,
like this:
The variable f consumes four bytes of RAM in memory.
That location has a specific address, in this case 248,440.
While you think of the variable f, the computer thinks of a specific address in
memory (for example, 248,440). Therefore, when you create a statement like this:
f = 3.14;
The compiler might translate that into, "Load the value 3.14 into memory location
248,440." The computer is always thinking of memory in terms of addresses and
values at those addresses.
There are, by the way, several interesting side effects to the way your computer
treats memory. For example, say that you include the following code in one of
your programs:
int i, s[4], t[4], u=0;
for (i=0; i<=4; i++)
{
s[i] = i;
t[i] =i;
}
Printf("s:t\n");
for (i=0; i<=4; i++)
printf("%d:%d\n", s[i], t[i]);
printf("u = %d\n", u);
The output that you see from the program will probably look like this:
s:t
1:5
2:2
3:3
4:4
5:5
u = 5
Why are t[0] and u incorrect? If you look carefully at the code, you can see that
the for loops are writing one element past the end of each array. In memory, the
arrays are placed adjacent to one another, as shown here:
Therefore, when you try to write to s[4], which does not exist, the system writes
into t[0] instead because t[0] is where s[4] ought to be. When you write into t[4],
you are really writing into u. As far as the computer is concerned, s[4] is simply an
address, and it can write into it. As you can see however, even though the
computer executes the program, it is not correct or valid. The program corrupts
the array t in the process of running. If you execute the following statement, more
severe consequences result:
s[1000000] = 5;
The location s[1000000] is more than likely outside of your program's memory
space. In other words, you are writing into memory that your program does not
own. On a system with protected memory spaces (UNIX, Windows 98/NT), this
sort of statement will cause the system to terminate execution of the program. On
other systems (Windows 3.1, the Mac), however, the system is not aware of what
you are doing. You end up damaging the code or variables in another application.
The effect of the violation can range from nothing at all to a complete system
crash. In memory, i, s, t and u are all placed next to one another at specific
addresses. Therefore, if you write past the boundaries of a variable, the computer
will do what you say but it will end up corrupting another memory location.
Because C and C++ do not perform any sort of range checking when you access
an element of an array, it is essential that you, as a programmer, pay careful
attention to array ranges yourself and keep within the array's appropriate
boundaries. Unintentionally reading or writing outside of array boundaries always
leads to faulty program behavior.
As another example, try the following:
#include <stdio.h>
int main()
{
int i,j;
int *p; /* a pointer to an integer */
printf("%d %d\n", p, &i);
p = &i;
printf("%d %d\n", p, &i);
return 0;
}
This code tells the compiler to print out the address held in p, along with the
address of i. The variable p starts off with some crazy value or with 0. The
address of i is generally a large value. For example, when I ran this code, I
received the following output:
0 2147478276
2147478276 2147478276
which means that the address of i is 2147478276. Once the statement p = &i;
has been executed, p contains the address of i. Try this as well:
#include <stdio.h>
void main()
{
int *p; /* a pointer to an integer */
printf("%d\n",*p);
}
This code tells the compiler to print the value that p points to. However, p has not
been initialized yet; it contains the address 0 or some random address. In most
cases, a segmentation fault (or some other run-time error) results, which means
that you have used a pointer that points to an invalid area of memory. Almost
always, an uninitialized pointer or a bad pointer address is the cause of
segmentation faults.
Having said all of this, we can now look at pointers in a whole new light. Take this
program, for example:
#include <stdio.h>
int main()
{
int i;
int *p; /* a pointer to an integer */
p = &i;
*p=5;
printf("%d %d\n", i, *p);
return 0;
}
Here is what's happening:
The variable i consumes 4 bytes of memory. The pointer p also consumes 4
bytes (on most machines in use today, a pointer consumes 4 bytes of memory.
Memory addresses are 32-bits long on most CPUs today, although there is a
increasing trend toward 64-bit addressing). The location of i has a specific
address, in this case 248,440. The pointer p holds that address once you say p =
&i;. The variables *p and i are therefore equivalent.
The pointer p literally holds the address of i. When you say something like this in
a program:
printf("%d", p);
what comes out is the actual address of the variable i.
Here is a cool aspect of C: Any number of pointers can point to the same
address. For example, you could declare p, q, and r as integer pointers and set
all of them to point to i, as shown here:
int i;
int *p, *q, *r;
p = &i;
q = &i;
r = p;
Note that in this code, r points to the same thing that p points to, which is i. You
can assign pointers to one another, and the address is copied from the right-hand
side to the left-hand side during the assignment. After executing the above code,
this is how things would look:
The variable i now has four names: i, *p, *q and *r. There is no limit on the
number of pointers that can hold (and therefore point to) the same address.
C Errors to Avoid
Bug #1 - Uninitialized pointers
One of the easiest ways to create a pointer bug is to try to
reference the value of a pointer even though the pointer is
uninitialized and does not yet point to a valid address. For
example:
int *p;
*p = 12;
The pointer p is uninitialized and points to a random location in
memory when you declare it. It could be pointing into the system
stack, or the global variables, or into the program's code space, or
into the operating system. When you say *p=12;, the program will
simply try to write a 12 to whatever random location p points to.
The program may explode immediately, or may wait half an hour
and then explode, or it may subtly corrupt data in another part of
your program and you may never realize it. This can make this
error very hard to track down. Make sure you initialize all pointers
to a valid address before dereferencing them.
Bug #2 - Invalid Pointer References
An invalid pointer reference occurs when a pointer's value is
referenced even though the pointer doesn't point to a valid block.
One way to create this error is to say p=q;, when q is uninitialized.
The pointer p will then become uninitialized as well, and any
reference to *p is an invalid pointer reference.
The only way to avoid this bug is to draw pictures of each step of
the program and make sure that all pointers point somewhere.
Invalid pointer references cause a program to crash inexplicably
for the same reasons given in Bug #1.
Bug #3 - Zero Pointer Reference
A zero pointer reference occurs whenever a pointer pointing to
zero is used in a statement that attempts to reference a block. For
example, if p is a pointer to an integer, the following code is
invalid:
p = 0;
*p = 12;
There is no block pointed to by p. Therefore, trying to read or write
anything from or to that block is an invalid zero pointer reference.
There are good, valid reasons to point a pointer to zero, as we will
see in later articles. Dereferencing such a pointer, however, is
invalid.
All of these bugs are fatal to a program that contains them. You
must watch your code so that these bugs do not occur. The best
way to do that is to draw pictures of the code's execution step by
step.
Using Pointers for Function Parameters
Most C programmers first use pointers to implement something called variable
parameters in functions. You have actually been using variable parameters in the
scanf function -- that's why you've had to use the & (the address operator) on
variables used with scanf. Now that you understand pointers you can see what
has really been going on.
To understand how variable parameters work, lets see how we might go about
implementing a swap function in C. To implement a swap function, what you
would like to do is pass in two variables and have the function swap their values.
Here's one attempt at an implementation -- enter and execute the following code
and see what happens:
#include <stdio.h>
void swap(int i, int j)
{
int t;
t=i;
i=j;
j=t;
}
void main()
{
int a,b;
a=5;
b=10;
printf("%d %d\n", a, b);
swap(a,b);
printf("%d %d\n", a, b);
}
When you execute this program, you will find that no swapping takes place. The
values of a and b are passed to swap, and the swap function does swap them,
but when the function returns nothing happens.
To make this function work correctly you can use pointers, as shown below:
#include <stdio.h>
void swap(int *i, int *j)
{
int t;
t = *i;
*i = *j;
*j = t;
}
void main()
{
int a,b;
a=5;
b=10;
printf("%d %d\n",a,b);
swap(&a,&b);
printf("%d %d\n",a,b);
}
To get an idea of what this code does, print it out, draw the two integers a and b,
and enter 5 and 10 in them. Now draw the two pointers i and j, along with the
integer t. When swap is called, it is passed the addresses of a and b. Thus, i
points to a (draw an arrow from i to a) and j points to b (draw another arrow from
b to j). Once the pointers are initialized by the function call, *i is another name for
a, and *j is another name for b. Now run the code in swap. When the code uses
*i and *j, it really means a and b. When the function completes, a and b have
been swapped.
Suppose you accidentally forget the & when the swap function is called, and that
the swap line accidentally looks like this: swap(a, b);. This causes a
segmentation fault. When you leave out the &, the value of a is passed instead of
its address. Therefore, i points to an invalid location in memory and the system
crashes when *i is used.
This is also why scanf crashes if you forget the & on variables passed to it. The
scanf function is using pointers to put the value it reads back into the variable you
have passed. Without the &, scanf is passed a bad address and crashes.
Variable parameters are one of the most common uses of pointers in C. Now you
understand what's happening!
Dynamic Data Structures
Dynamic data structures are data structures that grow and shrink as you need
them to by allocating and deallocating memory from a place called the heap.
They are extremely important in C because they allow the programmer to exactly
control memory consumption.
Dynamic data structures allocate blocks of memory from the heap as required,
and link those blocks together into some kind of data structure using pointers.
When the data structure no longer needs a block of memory, it will return the
block to the heap for reuse. This recycling makes very efficient use of memory.
To understand dynamic data structures completely, we need to start with the
heap.
How the Heap Works
A typical personal computer or workstation today has somewhere between 16
and 64 megabytes of RAM installed. Using a technique called virtual memory,
the system can swap pieces of memory on and off the machine's hard disk to
create an illusion for the CPU that it has much more memory, for example 200 to
500 megabytes. While this illusion is complete as far as the CPU is concerned, it
can sometimes slow things down tremendously from the user's perspective.
Despite this drawback, virtual memory is an extremely useful technique for
"increasing" the amount of RAM in a machine in an inexpensive way. Let's
assume for the sake of this discussion that a typical computer has a total memory
space of, for example, 50 megabytes (regardless of whether that memory is
implemented in real RAM or in virtual memory).
The operating system on the machine is in charge of the 50-megabyte memory
space. The operating system uses the space in several different ways, as shown
here:
The operating system and several applications, along with
their global variables and stack spaces, all consume portions
of memory. When a program completes execution, it releases
its memory for reuse by other programs. Note that part of the
memory space remains unused at any given time.
This is, of course, an idealization, but the basic principles are correct. As you can
see, memory holds the executable code for the different applications currently
running on the machine, along with the executable code for the operating system
itself. Each application has certain global variables associated with it. These
variables also consume memory. Finally, each application uses an area of
memory called the stack, which holds all local variables and parameters used by
any function. The stack also remembers the order in which functions are called so
that function returns occur correctly. Each time a function is called, its local
variables and parameters are "pushed onto" the stack. When the function returns,
these locals and parameters are "popped." Because of this, the size of a
program's stack fluctuates constantly as the program is running, but it has some
maximum size.
As a program finishes execution, the operating system unloads it, its globals and
its stack space from memory. A new program can make use of that space at a
later time. In this way, the memory in a computer system is constantly "recycled"
and reused by programs as they execute and complete.
In general, perhaps 50 percent of the computer's total memory space might be
unused at any given moment. The operating system owns and manages the
unused memory, and it is collectively known as the heap. The heap is extremely
important because it is available for use by applications during execution using
the C functions malloc (memory allocate) and free. The heap allows programs to
allocate memory exactly when they need it during the execution of a program,
rather than pre-allocating it with a specifically-sized array declaration.
How malloc and free Work
Let's say that you would like to allocate a certain amount of memory during the
execution of your application. You can call the malloc function at any time, and it
will request a block of memory from the heap. The operating system will reserve a
block of memory for your program, and you can use it in any way you like. When
you are done with the block, you return it to the operating system for recycling by
calling the free function. Then other applications can reserve it later for their own
use.
For example, the following code demonstrates the simplest possible use of the
heap:
int main()
{
int *p;
p = (int *)malloc(sizeof(int));
if (p == 0)
{
printf("ERROR: Out of memory\n");
return 1;
}
*p = 5;
printf("&d\n", *p);
free(p);
return 0;
}
The first line in this program calls the malloc function. This function does three
things:
1. The malloc statement first looks at the amount of memory available on the
heap and asks, "Is there enough memory available to allocate a block of
memory of the size requested?" The amount of memory needed for the
block is known from the parameter passed into malloc -- in this case,
sizeof(int) is 4 bytes. If there is not enough memory available, the malloc
function returns the address zero to indicate the error (another name for
zero is NULL and you will see it used throughout C code). Otherwise
malloc proceeds.
2. If memory is available on the heap, the system "allocates" or "reserves" a
block from the heap of the size specified. The system reserves the block of
memory so that it isn't accidentally used by more than one malloc
statement.
3. The system then places into the pointer variable (p, in this case) the
address of the reserved block. The pointer variable itself contains an
address. The allocated block is able to hold a value of the type specified,
and the pointer points to it.
The following diagram shows the state of memory after calling malloc:
The block on the right is the block of memory malloc allocated.
The program next checks the pointer p to make sure that the allocation request
succeeded with the line if (p == 0) (which could have also been written as if (p ==
NULL) or even if (!p). If the allocation fails (if p is zero), the program terminates. If
the allocation is successful, the program then initializes the block to the value 5,
prints out the value, and calls the free function to return the memory to the heap
before the program terminates.
There is really no difference between this code and previous code that sets p
equal to the address of an existing integer i. The only distinction is that, in the
case of the variable i, the memory existed as part of the program's pre-allocated
memory space and had the two names: i and *p. In the case of memory allocated
from the heap, the block has the single name *p and is allocated during the
program's execution. Two common questions:
• Is it really important to check that the pointer is zero after each
allocation? Yes. Since the heap varies in size constantly depending on
which programs are running, how much memory they have allocated, etc.,
there is never any guarantee that a call to malloc will succeed. You should
check the pointer after any call to malloc to make sure the pointer is valid.
• What happens if I forget to delete a block of memory before the
program terminates? When a program terminates, the operating system
"cleans up after it," releasing its executable code space, stack, global
memory space and any heap allocations for recycling. Therefore, there are
no long-term consequences to leaving allocations pending at program
termination. However, it is considered bad form, and "memory leaks" during
the execution of a program are harmful, as discussed below.
The following two programs show two different valid uses of pointers, and try to
distinguish between the use of a pointer and of the pointer's value:
void main()
{
int *p, *q;
p = (int *)malloc(sizeof(int));
q = p;
*p = 10;
printf("%d\n", *q);
*q = 20;
printf("%d\n", *q);
}
The final output of this code would be 10 from line 4 and 20 from line 6. Here's a
diagram:
The following code is slightly different:
void main()
{
int *p, *q;
p = (int *)malloc(sizeof(int));
q = (int *)malloc(sizeof(int));
*p = 10;
*q = 20;
*p = *q;
printf("%d\n", *p);
}
The final output from this code would be 20 from line 6. Here's a diagram:
Notice that the compiler will allow *p = *q, because *p and *q are both integers.
This statement says, "Move the integer value pointed to by q into the integer
value pointed to by p." The statement moves the values. The compiler will also
allow p = q, because p and q are both pointers, and both point to the same type
(if s is a pointer to a character, p = s is not allowed because they point to different
types). The statement p = q says, "Point p to the same block q points to." In other
words, the address pointed to by q is moved into p, so they both point to the same
block. This statement moves the addresses.
From all of these examples, you can see that there are four different ways to
initialize a pointer. When a pointer is declared, as in int *p, it starts out in the
program in an uninitialized state. It may point anywhere, and therefore to
dereference it is an error. Initialization of a pointer variable involves pointing it to a
known location in memory.
1. One way, as seen already, is to use the malloc statement. This statement
allocates a block of memory from the heap and then points the pointer at
the block. This initializes the pointer, because it now points to a known
location. The pointer is initialized because it has been filled with a valid
address -- the address of the new block.
2. The second way, as seen just a moment ago, is to use a statement such as
p = q so that p points to the same place as q. If q is pointing at a valid
block, then p is initialized. The pointer p is loaded with the valid address
that q contains. However, if q is uninitialized or invalid, p will pick up the
same useless address.
3. The third way is to point the pointer to a known address, such as a global
variable's address. For example, if i is an integer and p is a pointer to an
integer, then the statement p=&i initializes p by pointing it to i.
4. The fourth way to initialize the pointer is to use the value zero. Zero is a
special values used with pointers, as shown here:
5. p = 0;
or:
p = NULL;
What this does physically is to place a zero into p. The pointer p's address
is zero. This is normally diagrammed as:
Any pointer can be set to point to zero. When p points to zero, however, it does
not point to a block. The pointer simply contains the address zero, and this value
is useful as a tag. You can use it in statements such as:
if (p == 0)
{
...
}
or:
while (p != 0)
{
...
}
The system also recognizes the zero value, and will generate error messages if
you happen to dereference a zero pointer. For example, in the following code:
p = 0;
*p = 5;
The program will normally crash. The pointer p does not point to a block, it points
to zero, so a value cannot be assigned to *p. The zero pointer will be used as a
flag when we get to linked lists.
The malloc command is used to allocate a block of memory. It is also possible to
deallocate a block of memory when it is no longer needed. When a block is
deallocated, it can be reused by a subsequent malloc command, which allows the
system to recycle memory. The command used to deallocate memory is called
free, and it accepts a pointer as its parameter. The free command does two
things:
1. The block of memory pointed to by the pointer is unreserved and given
back to the free memory on the heap. It can then be reused by later new
statements.
2. The pointer is left in an uninitialized state, and must be reinitialized before it
can be used again.
The free statement simply returns a pointer to its original uninitialized state and
makes the block available again on the heap.
The following example shows how to use the heap. It allocates an integer block,
fills it, writes it, and disposes of it:
#include <stdio.h>
int main()
{
int *p;
p = (int *)malloc (sizeof(int));
*p=10;
printf("%d\n",*p);
free(p);
return 0;
}
This code is really useful only for demonstrating the process of allocating,
deallocating, and using a block in C. The malloc line allocates a block of memory
of the size specified -- in this case, sizeof(int) bytes (4 bytes). The sizeof
command in C returns the size, in bytes, of any type. The code could just as
easily have said malloc(4), since sizeof(int) equals 4 bytes on most machines.
Using sizeof, however, makes the code much more portable and readable.
The malloc function returns a pointer to the allocated block. This pointer is
generic. Using the pointer without typecasting generally produces a type warning
from the compiler. The (int *) typecast converts the generic pointer returned by
malloc into a "pointer to an integer," which is what p expects. The free statement
in C returns a block to the heap for reuse.
The second example illustrates the same functions as the previous example, but
it uses a structure instead of an integer. In C, the code looks like this:
#include <stdio.h>
struct rec
{
int i;
float f;
char c;
};
int main()
{
struct rec *p;
p=(struct rec *) malloc (sizeof(struct rec));
(*p).i=10;
(*p).f=3.14;
(*p).c='a';
printf("%d %f %c\n",(*p).i,(*p).f,(*p).c);
free(p);
return 0;
}
Note the following line:
(*p).i=10;
Many wonder why the following doesn't work:
*p.i=10;
The answer has to do with the precedence of operators in C. The result of the
calculation 5+3*4 is 17, not 32, because the * operator has higher precedence
than + in most computer languages. In C, the . operator has higher precedence
than *, so parentheses force the proper precedence.
Most people tire of typing (*p).i all the time, so C provides a shorthand notation.
The following two statements are exactly equivalent, but the second is easier to
type:
(*p).i=10;
p->i=10;
You will see the second more often than the first when reading other people's
code.
Advanced Pointers
You will normally use pointers in somewhat more complicated ways than those
shown in some of the previous examples. For example, it is much easier to create
a normal integer and work with it than it is to create and use a pointer to an
integer. In this section, some of the more common and advanced ways of working
with pointers will be explored.
Pointer Types
It is possible, legal, and beneficial to create pointer types in C, as shown below:
typedef int *IntPointer;
...
IntPointer p;
This is the same as saying:
int *p;
This technique will be used in many of the examples below. The technique often
makes a data declaration easier to read and understand, and also makes it easier
to include pointers inside of structures or pass pointer parameters in functions.
Pointers to Structures
It is possible to create a pointer to almost any type in C, including user-defined
types. It is extremely common to create pointers to structures. An example is
shown below:
typedef struct
{
char name[21];
char city[21];
char state[3];
} Rec;
typedef Rec *RecPointer;
RecPointer r;
r = (RecPointer)malloc(sizeof(Rec));
The pointer r is a pointer to a structure. Please note the fact that r is a pointer,
and therefore takes four bytes of memory just like any other pointer. However, the
malloc statement allocates 45 bytes of memory from the heap. *r is a structure
just like any other structure of type Rec. The following code shows typical uses of
the pointer variable:
strcpy((*r).name, "Leigh");
strcpy((*r).city, "Raleigh");
strcpy((*r).state, "NC");
printf("%s\n", (*r).city);
free(r);
You deal with *r just like a normal structure variable, but you have to be careful
with the precedence of operators in C. If you were to leave off the parenthesis
around *r the code would not compile because the "." operator has a higher
precedence than the "*" operator. Because it gets tedious to type so many
parentheses when working with pointers to structures, C includes a shorthand
notation that does exactly the same thing:
strcpy(r->name, "Leigh");
The r-> notation is exactly equivalent to (*r)., but takes two fewer characters.
Pointers to Arrays
It is also possible to create pointers to arrays, as shown below:
int *p;
int i;
p = (int *)malloc(sizeof(int[10]));
for (i=0; i<10; i++)
p[i] = 0;
free(p);
or:
int *p;
int i;
p = (int *)malloc(sizeof(int[10]));
for (i=0; i<10; i++)
*(p+i) = 0;
free(p);
Note that when you create a pointer to an integer array, you simply create a
normal pointer to int. The call to malloc allocates an array of whatever size you
desire, and the pointer points to that array's first element. You can either index
through the array pointed to by p using normal array indexing, or you can do it
using pointer arithmetic. C sees both forms as equivalent.
This particular technique is extremely useful when working with strings. It lets you
allocate enough storage to exactly hold a string of a particular size.
Arrays of Pointers
Sometimes a great deal of space can be saved, or certain memory-intensive
problems can be solved, by declaring an array of pointers. In the example code
below, an array of 10 pointers to structures is declared, instead of declaring an
array of structures. If an array of the structures had been created instead, 243 *
10 = 2,430 bytes would have been required for the array. Using the array of
pointers allows the array to take up minimal space until the actual records are
allocated with malloc statements. The code below simply allocates one record,
places a value in it, and disposes of the record to demonstrate the process:
typedef struct
{
char s1[81];
char s2[81];
char s3[81];
} Rec;
Rec *a[10];
a[0] = (Rec *)malloc(sizeof(Rec));
strcpy(a[0]->s1, "hello");
free(a[0]);
Structures Containing Pointers
Structures can contain pointers, as shown below:
typedef struct
{
char name[21];
char city[21];
char phone[21];
char *comment;
} Addr;
Addr s;
char comm[100];
gets(s.name, 20);
gets(s.city, 20);
gets(s.phone, 20);
gets(comm, 100);
s.comment =
(char *)malloc(sizeof(char[strlen(comm)+1]));
strcpy(s.comment, comm);
This technique is useful when only some records actually contained a comment in
the comment field. If there is no comment for the record, then the comment field
would consist only of a pointer (4 bytes). Those records having a comment then
allocate exactly enough space to hold the comment string, based on the length of
the string typed by the user.
Pointers to Pointers
It is possible and often useful to create pointers to pointers. This technique is
sometimes called a handle, and is useful in certain situations where the operating
system wants to be able to move blocks of memory on the heap around at its
discretion. The following example demonstrates a pointer to a pointer:
int **p;
int *q;
p = (int **)malloc(sizeof(int *));
*p = (int *)malloc(sizeof(int));
**p = 12;
q = *p;
printf("%d\n", *q);
free(q);
free(p);
Windows and the Mac OS use this structure to allow memory compaction on the
heap. The program manages the pointer p, while the operating system manages
the pointer *p. Because the OS manages *p, the block pointed to by *p (**p) can
be moved, and *p can be changed to reflect the move without affecting the
program using p. Pointers to pointers are also frequently used in C to handle
pointer parameters in functions.
Pointers to Structures Containing Pointers
It is also possible to create pointers to structures that contain pointers. The
following example uses the Addr record from the previous section:
typedef struct
{
char name[21];
char city[21];
char phone[21];
char *comment;
} Addr;
Addr *s;
char comm[100];
s = (Addr *)malloc(sizeof(Addr));
gets(s->name, 20);
gets(s->city, 20);
gets( s->phone, 20);
gets(comm, 100);
s->comment =
(char *)malloc(sizeof(char[strlen(comm)+1]));
strcpy(s->comment, comm);
The pointer s points to a structure that contains a pointer that points to a string:
In this example, it is very easy to create lost blocks if you aren't careful. For
example, here is a different version of the AP example.
s = (Addr *)malloc(sizeof(Addr));
gets(comm, 100);
s->comment =
(char *)malloc(sizeof(char[strlen(comm)+1]));
strcpy(s->comment, comm);
free(s);
This code creates a lost block because the structure containing the pointer
pointing to the string is disposed of before the string block is disposed of, as
shown below:
Linking
Finally, it is possible to create structures that are able to point to identical
structures, and this capability can be used to link together a whole string of
identical records in a structure called a linked list.
typedef struct
{
char name[21];
char city[21];
char state[21];
Addr *next;
} Addr;
Addr *first;
The compiler will let you do this, and it can be used with a little experience to
create structures like the one shown below:
A Linked Stack Example
A good example of dynamic data structures is a simple stack library, one that
uses a dynamic list and includes functions to init, clear, push, and pop. The
library's header file looks like this:
/* Stack Library - This library offers the
minimal stack operations for a
stack of integers (easily changeable) */
typedef int stack_data;
extern void stack_init();
/* Initializes this library.
Call first before calling anything. */
extern void stack_clear();
/* Clears the stack of all entries. */
extern int stack_empty();
/* Returns 1 if the stack is empty, 0 otherwise. */
extern void stack_push(stack_data d);
/* Pushes the value d onto the stack. */
extern stack_data stack_pop();
/* Returns the top element of the stack,
and removes that element.
Returns garbage if the stack is empty. */
The library's code file follows:
#include "stack.h"
#include <stdio.h>
/* Stack Library - This library offers the
minimal stack operations for a stack of integers */
struct stack_rec
{
stack_data data;
struct stack_rec *next;
};
struct stack_rec *top=NULL;
void stack_init()
/* Initializes this library.
Call before calling anything else. */
{
top=NULL;
}
void stack_clear()
/* Clears the stack of all entries. */
{
stack_data x;
while (!stack_empty())
x=stack_pop();
}
int stack_empty()
/* Returns 1 if the stack is empty, 0 otherwise. */
{
if (top==NULL)
return(1);
else
return(0);
}
void stack_push(stack_data d)
/* Pushes the value d onto the stack. */
{
struct stack_rec *temp;
temp=
(struct stack_rec *)malloc(sizeof(struct stack_rec));
temp->data=d;
temp->next=top;
top=temp;
}
stack_data stack_pop()
/* Returns the top element of the stack,
and removes that element.
Returns garbage if the stack is empty. */
{
struct stack_rec *temp;
stack_data d=0;
if (top!=NULL)
{
d=top->data;
temp=top;
top=top->next;
free(temp);
}
return(d);
}
Note how this library practices information hiding: Someone who can see only the
header file cannot tell if the stack is implemented with arrays, pointers, files, or in
some other way. Note also that C uses NULL. NULL is defined in stdio.h, so you
will almost always have to include stdio.h when you use pointers. NULL is the
same as zero.
Try This!
• Add a dup, a count, and an add function to the stack
library to duplicate the top element of the stack, return a
count of the number of elements in the stack, and add the
top two elements in the stack.
• Build a driver program and a makefile, and compile the
stack library with the driver to make sure it works.
C Errors to Avoid
• Forgetting to include parentheses when you reference a
record, as in (*p).i above
• Failing to dispose of any block you allocate - For example,
you should not say top=NULL in the stack function,
because that action orphans blocks that need to be
disposed.
• Forgetting to include stdio.h with any pointer operations
so that you have access to NULL.
Using Pointers with Arrays
Arrays and pointers are intimately linked in C. To use arrays effectively, you have
to know how to use pointers with them. Fully understanding the relationship
between the two probably requires several days of study and experimentation, but
it is well worth the effort.
Let's start with a simple example of arrays in C:
#define MAX 10
int main()
{
int a[MAX];
int b[MAX];
int i;
for(i=0; i<MAX; i++)
a[i]=i;
b=a;
return 0;
}
Enter this code and try to compile it. You will find that C will not compile it. If you
want to copy a into b, you have to enter something like the following instead:
for (i=0; i<MAX; i++)
a[i]=b[i];
Or, to put it more succinctly:
for (i=0; i<MAX; a[i]=b[i], i++);
Better yet, use the memcpy utility in string.h.
Arrays in C are unusual in that variables a and b are not, technically, arrays
themselves. Instead they are permanent pointers to arrays. a and b permanently
point to the first elements of their respective arrays -- they hold the addresses of
a[0] and b[0] respectively. Since they are permanent pointers you cannot
change their addresses. The statement a=b; therefore does not work.
Because a and b are pointers, you can do several interesting things with pointers
and arrays. For example, the following code works:
#define MAX 10
void main()
{
int a[MAX];
int i;
int *p;
p=a;
for(i=0; i<MAX; i++)
a[i]=i;
printf("%d\n",*p);
}
The statement p=a; works because a is a pointer. Technically, a points to the
address of the 0th element of the actual array. This element is an integer, so a is
a pointer to a single integer. Therefore, declaring p as a pointer to an integer and
setting it equal to a works. Another way to say exactly the same thing would be to
replace p=a; with p=&a[0];. Since a contains the address of a[0], a and &a[0]
mean the same thing.
The following figure shows the state of the variables right before the for loop
starts executing:
Now that p is pointing at the 0th element of a, you can do some rather strange
things with it. The a variable is a permanent pointer and can not be changed, but
p is not subject to such restrictions. C actually encourages you to move it around
using pointer arithmetic . For example, if you say p++;, the compiler knows that p
points to an integer, so this statement increments p the appropriate number of
bytes to move it to the next element of the array. If p were pointing to an array of
100-byte-long structures, p++; would move p over by 100 bytes. C takes care of
the details of element size.
You can copy the array a into b using pointers as well. The following code can
replace (for i=0; i<MAX; a[i]=b[i], i++); :
p=a;
q=b;
for (i=0; i<MAX; i++)
{
*q = *p;
q++;
p++;
}
You can abbreviate this code as follows:
p=a;
q=b;
for (i=0; i<MAX; i++)
*q++ = *p++;
And you can further abbreviate it to:
for (p=a,q=b,i=0; i<MAX; *q++ = *p++, i++);
What if you go beyond the end of the array a or b with the pointers p or q? C
does not care -- it blithely goes along incrementing p and q, copying away over
other variables with abandon. You need to be careful when indexing into arrays in
C, because C assumes that you know what you are doing.
You can pass an array such as a or b to a function in two different ways. Imagine
a function dump that accepts an array of integers as a parameter and prints the
contents of the array to stdout. There are two ways to code dump:
void dump(int a[],int nia)
{
int i;
for (i=0; i<nia; i++)
printf("%d\n",a[i]);
}
or:
void dump(int *p,int nia)
{
int i;
for (i=0; i<nia; i++)
printf("%d\n",*p++);
}
The nia (number_in_array) variable is required so that the size of the array is
known. Note that only a pointer to the array, rather than the contents of the array,
is passed to the function. Also note that C functions can accept variable-size
arrays as parameters.
waitingforever188- Members
- Tổng số bài gửi : 32
Points : 87
Reputation : 1
Join date : 03/12/2009
Age : 32
Re: thêm phần tiếng Anh ai mun thi copy ve nha tham khao nha !!!
by mrhau 8/4/2010, 21:27
rảnh ha! tiếng anh ko ai mà rảnh ngồi đọc cho lòi mắt hả!
mrhau- Members
- Tổng số bài gửi : 15
Points : 25
Reputation : 0
Join date : 16/11/2009
Age : 32
Re: thêm phần tiếng Anh ai mun thi copy ve nha tham khao nha !!!
by waitingforever188 15/4/2010, 19:37
thi coi may doan code thui chu ai ma keu coi het dau ' 
waitingforever188- Members
- Tổng số bài gửi : 32
Points : 87
Reputation : 1
Join date : 03/12/2009
Age : 32
Sponsored content
Similar topics» PHẢN XẠ NGẪU NHIÊN LIÊN TỤC-p2 Học tiếng Nhật mới
» Học tiếng Nhật là niềm vui của bạn - Dạy tiếng Nhật là niềm tự hào của TOP GLOBIS.
» Học tiếng Nhật - Top Globis
» Học tiếng Nhật - Top Globis
» Học tiếng nhật miễn phí tại Top Globis
» Học tiếng Nhật là niềm vui của bạn - Dạy tiếng Nhật là niềm tự hào của TOP GLOBIS.
» Học tiếng Nhật - Top Globis
» Học tiếng Nhật - Top Globis
» Học tiếng nhật miễn phí tại Top Globis
Trang 1 trong tổng số 1 trang
Permissions in this forum:
Bạn không có quyền trả lời bài viết
