Advanced Uses of Pointers - Brooklyn College



Advanced Uses of Pointers

Dynamic storage Allocation

C’s data structures are normally fixed in size. An array for example has a fixed number of elements, and each element has a fixed size.

The problem is it forces us to choose their sizes when writing a program and we can change the sizes without modifying the program and compiling it again. (example assignment one)

Dynamic storage allocation: the ability to allocate storage during program execution. We can design data structures that grow and shrink as needed. Used most often for strings, arrays, and structures. Dynamically allocated structures can link together to form lists, trees, and other data structures.

Memory Allocation Functions

To allocate storage dynamically, we’ll need to call one of the three memory allocation functions declared in the header:

• malloc –Allocates a block of memory, but doesn’t initialize it.

• Calloc – Allocates a block of memory and clears it.

• realloc – Resizes a previously allocated block of memory.

Malloc is the most used. More efficient than calloc, since it doesn’t have to clear the memory block that it allocates.

Function returns a value of type void * since it doesn’t know what type we’re planning to store in the block. A void * value is a generic pointer – just a memory address.

Null Pointers:

When we call a memory allocation function, there’s a possibility that it won’t be able to locate a block of memory large enough to satisfy our request. If that should happen the function will return a null pointer. A null pointer is a pointer to nothing. After we store the return value in a pointer variable p, we must test p to see if it’s a null pointer.

p = malloc(10000);

If(p==NULL){

/* allocation failed; take appropriate action */

}

or

if((p=malloc(10000))==NULL){

/*allocation failed; take appropriate action */

}

NULL is a macro defined and many other header files.

In C, pointers test true or false in the same way as numbers. All non-null pointers test true, only null pointers are false.

Instead of

If(p==NULL)

Can write

If(!p)

And instead of

If(p !=NULL)

Can write:

If(p)

Dynamically Allocated Strings:

Strings are stored in fixed-size arrays, but it can be hard to anticipate how long these arrays need to be.

Using malloc to allocate memory for a string:

void *malloc(size_t size);

Malloc allocates a block of size bytes and returns a pointer to it. Size has type size_t an unsigned integer type defined in the C library. Basically think of it (unless allocating a very large block of memory) as an ordinary integer.

To allocate space for a string of n characters (since a char value requires exactly one byte of storage), we’d write:

p = malloc(n+1);

Where p is a char * variable. The generic pointer that malloc returns will be converted to char * when the assignment is performed; no cast is necessary.

Some programmers prefer to cast malloc’s return value:

p = (char *) malloc(n+1);

/* remember to allocate for the null character */

memory allocated using malloc isn’t cleared or initialized in any way so p points to an uninitialized array of n+1 characters

p

| |

↓

| | | | |… | |

0 1 2 3 n

Calling strcpy(p, “ab”); is one way to initialize it.

The first 3 characters in the array will now be a, b, and \0:

p

| |

↓

|a |b |\0 | |… | |

0 1 2 3 n

Dynamic storage allocation makes it possible to write functions that return a pointer to a “new” string – a string that didn’t exist before the function was called.

Think of the strcat function. what if you want a function that concatenated without modifying one of the strings. Now we can write our own. Also strcat had that issue of overriding memory if the second was bigger than the first.

Our function will measure the lengths of the two strings to be concatenated then call malloc to allocate just the right amount of space for the result. Then it will copy the first sting into the new spaces and call strcat to concatenate the second.

char *concat(const char *s1, const char *s2)

{

char *result;

result = malloc(strlen(s1) + strlen(s2) + 1);

if(result == NULL){

printf(“Error: malloc failed in concat\n”);

exit(EXIT FAILURE);

}

strcpy(result, s1);

strcat(result, s2);

return result;

}

After the call, p will point to the string “abcdef”, which is stored in a dynamically allocated array. The array is seven characters long, including the null character at the end.

(functions that dynamically allocate storage (like concat) – need to be careful –when the string that concat returns is no longer needed, we’ll need to call free (talk about soon) to release the space that it occupies. If we don’t the program may run out of memory prematurely.)

Dynamically allocated arrays have the same advantage of dynamically allocated strings (since arrays are strings). When writing a program is difficult to estimate the size for an array, it would be more convenient to wait until the program is run to decide how large the array should be. C solves this program by allowing a program to allocate space for an array during execution, then access the array through a pointer to its first element.

For an array as opposed to string, the arbitrary array won’t necessarily be one byte long. As a result, we’ll need to use the sizeof operator to calculate the amount of space required for each element.

Example: program that needs an array of n integers, where n is to be computed during the execution of the program.

Int *a;

When the value of n is known, we’ll call malloc.

a= malloc(n * sizeof(int));

if did malloc(n *2); thinking int is 2 bytes, but on many computers it is larger than 2 bytes, it won’t allocate a large enough block of memory.

Now we can use a as an array and ignore the fact that it’s a pointer. (because of the relationship between arrays and pointers in c).

Ex: we could initialize a

For(i=0;i Operator

Accessing a member of a structure using a pointer is so common that C provides a special operator just for this purpose. This operator, known as right arrow selection, is a minus sign followed by >. Using he the -> operator we can write

New_node->value = 10;

Instead of

(*new_node).value = 10;

The -> operator is a combination of the * and . operators; it performs indirection on newnode to locate the structure that it points to, then selects the value member for the structure.

Scanf(“%d”, &new_node->value);

This is fine too.

Inserting a Node at the beginning of a Linked List:

Advantage to linked list: nodes can be added at any point in the list: at the beginning, at the end, or anywhere in the middle.

Beginning is the easiest place to insert a node.

Modify the new node’s next member to point to the node that was previously at the beginning ot he list:

new_node->next = first;

We’ll make first point to the new node.

first = new_node;

This will work if the list is empty: race the process of inserting two nodes into an empty list. First will contain the number 10 followed by a node containing 20. null pointers are shown as diagonal lines.

See picture.

Inserting a node into a linked list is common operation.

Function to do it:

First parameter: list (a pointer to the first node in the old list) and n (the integer to be stored in the new node).

Struct node *add_to_list(struct node *list, int n)

{

struct node *new_node;

new_node = malloc(sizeof(struct node));

if(new_node==NULL){

printf(“Error: malloc failed in add_to_list\n”);

exit(EXIT_FAILURE);

}

new_node->value=n;

new_node->next = list;

return new_node;

}

returns a pointer to the newly created node (now at the beginning of the list). It doesn’t modify the list pointer.

When we call add_to_list we’ll need to store its return value into first:

First = add_to_list(first, 10);

First = add_to_list(first, 20);

The statements add nodes containing 10 and 20 to the list pointed to by first.

Example: uses add_to_list to create a linked list containing numbers entered by the user:

Struct node *read_numbers(void)

{

struct node * first = NULL;

int n;

printf(“Enter a series of integers (0 to terminate): “);

for(;;){

scanf(“%d”, &n);

if(n==0)

return first;

first = add_to_list(first, n);

}

}

The numbers will be in reverse order within the list, since first always points to the node containing the last number entered.

Searching a linked list:

Once we’ve created a linked list, we may need to search it for a particular piece of data.

For(p = first; p != NULL; p = p->next)

…

p = p->next advances the p pointer from one node to the next.

Search_list function searches for an integer n. If it finds n, it will return a pointer to the node containing n; otherwise it will return a null pointer.

Struct node * search_list(struct node *list, int n)

{

struct node * p;

for(p = list; p!=NULL; p=p->next)

if(p->value ==n)

return p;

return NULL;

}

Deleting a node from a linked list

Advantage of using a linked list is that we can easily delete nodes that we no longer need. Deleting a node, like creating a node involves 3 steps:

1. locating the node to be deleted

2. altering the previous node so that it “bypasses” the deleted node, and

3. calling free to reclaim the space occupied by the deleted node.

Cur – pointer to current node

Prev – pointer to previous node

for(cur=list, prev=NULL; cur!=NULL && cur->value!=n; prev=cur, cur=cur->next)

;

power of c – empty body. And can use commas. Performs all operations for searching n, and when the oop terminates cur points to the node to be deleted, while prev points to the previous node (if there is one).

To understand look at sheet – picture: this locates the node to be deleted

Step 2 – code:

Prev->next=cur->next;

Makes the pointer in the previous node point to the node after the current node:

Picture sheet.

Step 3 – releasing the memory occupied by the current node:

free(cur);

function uses this strategy – deletes first node containing n. If no node contains n, the function does nothing. Function returns a pointer to the list.

Struct node *delete_from_list(struct node *list, in n)

{

struct node *cur, *prev;

for (cur = list, prev = NULL;

cur!=NULL && cur->value!=n;

prev = cur, cur = cur->next)

;

if(cur == NULL)

return list; /* n was not found */

if(prev == NULL)

list = list->next; /* n is in the first node */

else

prev->next=cur->next; /* n is in some other node */

free(cur);

return list;

}

Deleting the first node is a special case. The prev==NULL test checks for this case, which requires a different bypass step.

Pointers to Pointers

When passing a parameter to a function and you want this parameter to come back with a changed value, you must pass a pointer to a pointer. What if the value being passed to the function is a pointer and you wish it to come back with a changed value? You have to give the address of the pointer, which is just another way of saying a pointer to the pointer.

An array whose elements is type char * is a pointer to a pointer. To point to one of the array elements it’s char **. Also with linked data structures have pointers to pointers. Example: add_to_list function – we pass the first node in the list and it returns a pointer to the new list.

Struct node *add_to_list(struct node *list, int n)

{

struct node *new_node;

new_node = malloc(sizeof(struct node));

if(new_node==NULL){

printf(“Error: malloc failed in add_to_list\n”);

exit(EXIT_FAILURE);

}

new_node->value=n;

new_node->next = list;

return new_node;

}

If we want to modify the function so that it assigns new_node to list instead of returning new_node. Instead of return new_node, if we want to modify the function so it assigns new_node to list (modify the parameter)

list=new_node;

can’t do that because

add_to_list(first, 10);

first is copied into list (Pointers, like all other arguments are passed by value).

The last line makes list point to new_node, but that doesn’t affect first.

Correct version:

void add_to_list(struct node **list, int n)

{

struct node * new_node;

new_node = malloc(sizeof(struct node));

if(new_node==NULL){

printf(“Error: malloc failed in add_to_list\n”);

exit(EXIT_FAILURE);

}

new_node->value = n;

new_node->next= *list;

*list = new_node;

}

Another example:

#include

#include

int main()

{

char *s1, *s2;

if((s1=(char *) malloc(80)) == NULL ||

(s2 = (char *) malloc(80))==NULL)

{

printf(“Fatal memory error!\n”);

exit(1);

}

strcpy(s1, “Hello”);

strcpy(s2, “Goodbye”);

strswap(&s1, &s2);

printf(“s1 is now %s. s2 is now %s.\n”, s1, s2);

return 0;

}

void strswap(char **s1, char **s2)

{

char *temp;

temp = *s1;

*s1 = *s2;

*s2 = temp;

}

Function swaps two strings. In order to swap, we do so by changing the address contained in s1 so that it contains the address of the G in Goodbye and by changing the address contained in s2 so that it so that it contains the address of “H” in Hello.

Exit and malloc are in stdlib.

In strswap – before swapped what is the value of **s1 and **s2.

**s1 is the H in Hello and **s2 is the G in Goodbye.

Pointers to Functions

Can have pointers to functions. Functions occupy memory locations, so every function has an address, just like each variable has an address.

Functions Pointers as arguments

Can pass a function pointer as an argument.

Example:

double integrate(double (*f) (double), double a, double b);

The parentheses around *f indicate that f is a pointer to a function, not a function that returns a pointer.

Can also say:

double integrate(double f(double), double a, double b);

As though it were a function.

#include

main()

{

float reciprocal (int), square(int), funsum(int, float (*f) (int));

printf(“Sum of 5 reciprocals: %f\n”, funsum(5, reciprocal));

printf(“Sum of 3 squares: %f\n”, funsum(3, square));

}

float funsum(int n, float (*f)(int))

{

float sum = 0.0;

int I;

for(i=1;i ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download