Dynamic data structures-those that grow and shrink as you need them to by allocating and deallocating memory from the heap-are extremely important in C. If you have never seen them before, pick up a book on data structures so that you can learn about them in depth.
Dynamic data structures allocate blocks of memory from the heap as required and link those blocks together into some kind of structure that uses pointers. When a structure no longer needs a block, it will return it to the heap for reuse.
The following two examples show the correspondence between Pascal code and C code using the heap. The first example allocates an integer block, fills it, writes it, and disposes of it. In Pascal, it looks like this:
program samp;
var
p:^integer;
begin
new(p);
p^:=10;
writeln(p^);
dispose(p);
end.
The same code in C looks like this:
#include
void main()
{
int *p;
p=(int *) malloc (sizeof(int));
*p=10;
printf("%d\n",*p);
free(p);
}
This code is really useful only for demonstrating the process of allocating, deallocating, and using a block in C. The malloc line does the same thing as the new statement does in Pascal. It allocates a block of memory of the size specified---in this case, sizeof(int) 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 four bytes on most UNIX 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 dispose statement in Pascal is replaced by free in C. It returns the specified block to the heap for reuse.
The second example illustrates the same functions as the previous example, but it uses a record instead of an integer. In Pascal, the code looks like this:
program samp;
type
rec=record
i:integer;
f:real;
c:char;
end;
var
p:^rec;
begin
new(p);
p^.i:=10;
p^.f:=3.14;
p^.c='a';
writeln(p^.i,p^.f,p^.c);
dispose(p);
end.
In C, the code looks like this:
#include
struct rec
{
int i;
float f;
char c;
};
void 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);
}
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. See tutorial 14 for more information on 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 referencing records pointed to by a pointer.
A more complex 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
/* 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 in place of the Pascal nil. NULL is defined in stdio.h, so you will almost always have to include stdio.h when you use pointers.
Dynamic data structures allocate blocks of memory from the heap as required and link those blocks together into some kind of structure that uses pointers. When a structure no longer needs a block, it will return it to the heap for reuse.
The following two examples show the correspondence between Pascal code and C code using the heap. The first example allocates an integer block, fills it, writes it, and disposes of it. In Pascal, it looks like this:
program samp;
var
p:^integer;
begin
new(p);
p^:=10;
writeln(p^);
dispose(p);
end.
The same code in C looks like this:
#include
void main()
{
int *p;
p=(int *) malloc (sizeof(int));
*p=10;
printf("%d\n",*p);
free(p);
}
This code is really useful only for demonstrating the process of allocating, deallocating, and using a block in C. The malloc line does the same thing as the new statement does in Pascal. It allocates a block of memory of the size specified---in this case, sizeof(int) 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 four bytes on most UNIX 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 dispose statement in Pascal is replaced by free in C. It returns the specified block to the heap for reuse.
The second example illustrates the same functions as the previous example, but it uses a record instead of an integer. In Pascal, the code looks like this:
program samp;
type
rec=record
i:integer;
f:real;
c:char;
end;
var
p:^rec;
begin
new(p);
p^.i:=10;
p^.f:=3.14;
p^.c='a';
writeln(p^.i,p^.f,p^.c);
dispose(p);
end.
In C, the code looks like this:
#include
struct rec
{
int i;
float f;
char c;
};
void 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);
}
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. See tutorial 14 for more information on 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 referencing records pointed to by a pointer.
A more complex 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
/* 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 in place of the Pascal nil. NULL is defined in stdio.h, so you will almost always have to include stdio.h when you use pointers.
No comments:
Post a Comment