Author : Mkoubaa
Page : << Previous 8 Next >>
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 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.
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.
Exercises
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.
Part 12: 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 requires several weeks or even months of study, so do not get discouraged if you do not understand it right away.
Let's start with the treatment of arrays in Pascal and other languages. C is nothing like Pascal in this regard, so it will provide a good contrast. Following is an example of arrays in Pascal:
program samp;
const
max=9;
var
a,b:array[0..max] of integer;
i:integer;
begin
for i:=0 to max do
a[i]:=i;
b:=a;
end.
The elements of the array a are initialized, and then all elements in a are copied into b, so that a and b are identical. Compare the C version:
#define MAX 10
void main()
{
int a[MAX];
int b[MAX];
int i;
for(i=0; i<MAX; i++)
a[i]=i;
b=a;
}
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:
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 but permanent pointers to arrays. Thus, they point to blocks of memory that hold the arrays. They hold the addresses of the actual arrays, but 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 b[MAX];
int i;
int *p,*q;
for(i=0; i<MAX; i++);
a[i]=i;
p=a;
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.
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++);</span
Page : << Previous 8 Next >>