Skip to main content

Advanced Uses of Pointers

Exercises​

Question 17.1​

Having to check the return value of malloc (or any other memory allocation function) each time we call it can be an annoyance. Write a function named my_malloc that serves as a "wrapper" for malloc. When we call my_malloc and ask it to allocate n bytes, it in turn calls malloc, tests to make sure that malloc doesn't return a null pointer, and then returns the pointer from malloc. Have my_malloc print an error message and terminate the program if malloc returns a null pointer.

#include <stdio.h>
#include <stdlib.h>


#define MALLOC_ERR(size_t_bytes)          \
printf("[ERROR] Failed to allocate %zu bytes of memory on\nfile: %s\nline: %d\n", size_t_bytes, __FILE__, __LINE__)

/*
* my_malloc: Returns a pointer/address that can store bytes byte of data
Login to view full code

Question 17.2​

Write a function named duplicate that uses dynamic storage allocation to create a copy of a string. For example, the call

p = duplicate(str);

would allocate space for a string of the same length as str, copy the contents of str into the new string and return a pointer to it. Have duplicate return a null pointer if the memory allocation fails.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define STR_SIZE 100

/*
* duplicate: Returns a memory address that allocates the number of bytes
Login to view full code

Question 17.3​

Write the following function:

int *create_array(int n, int initial_value);

The function should return a pointer to a dynamically allocated int array with n members, each of which is initialized to initial_value. The return value should be NULL if the array can't be allocated.

#include <stdio.h>
#include <stdlib.h>

/*
* create_array:  Creates an array of n elements, each element is initialized 
*                with the value initial_value. If the cannot be created, returns 
*                NULL.
*/
int *create_array (int n, int initial_value);
Login to view full code

Question 17.4​

Suppose that the following declarations are in effect:

struct point { int x, y; };
struct rectangle { struct point upper_left, lower_right; };
struct rectangle *p;

Assume that we want p to point to a rectangle structure whose upper left corner is at (10, 25) and whose lower right corner is at (20. 15). Write a series of statements that allocate such a structure and initialize it as indicated.

#include <stdio.h>
#include <stdlib.h>

struct point { int x, y; };
struct rectangle { struct point upper_left, lower_right; };

/*
* initialize_rectangle:  Returns a pointer to a rectangle structure which has the 
*                        member upper_left and lower_right initialized as provided
Login to view full code

Question 17.5​

Suppose that f and p are declared as follows:

struct {
   union {
      char a, b;
      int c;
   } d;
   int e[5];
} f, *p = &f;

Which of the following statements are legal?

  1. p->b = ' '
  2. p->e[3] = 10;
  3. (*p).d.a = '*';
  4. p->d->c = 20;

Based on the provided structre, I'd say that:

  1. is not legal as it is accessing member b of union d without specifying. The correct and legal way would probably be p->d.b = ' ';
  2. is probably legal as it would go as: p->*(e+3) = 10; which is similar to accesing a integer value.
  3. is legal as (*p) will "indirect" the pointer p, making it act like a normal structure variable. We can then use the dot (.) operator to access the members without any issue.
  4. is probably not legal as the arrow operator (->) is used to access member of a pointer variable. While p is a pointer variable, d - which is a union - is not a pointer to the union. Since d is not a pointer, we cannot use the arrow operator to access the member c of the union. The correct way would be: p->d.c = 20;

After checking the ouput, it was as expected. But for (b), p->*(e+3) is not correct way to visualize the array operation. It will be roguhly equivalent to: *((p->e) + 3)

Question 17.6​

Modify the delete_from_list function so that it uses only one pointer variable instead of two (cur and prev).

Some constraints need to be defined before we solve the problem:

  1. The return type of the function delete_from_list (sll_delete_node in the program) must be void because the program utilizes the parameter list for traversing through the linked list.

  2. The linked list fails to delete the first node, of the list. This means, the latest node added using the n command cannot be removed. The reason for this is, when we send the root pointer to the function sll_delete_node, we are passing a value - an address of the root node in the linked list - which cannot change the root node's address through the function call. Say that the root node's address is 0x1234, then when we pass it as an argument to the function, we are essentially initializing the list pointer with the address 0x1234. Now say that the first node needs to be deleted, that means that list = list->next. But this will only change the pointer variable list and not the root pointer variable. This can be solved if the function takes in pointer to a pointer to the type singly_linked_list_node, i.e. the function parameter should be struct singly_linked_list_node **list. By doing so, the address of the root pointer variable can be modified, but the issue is that the other nodes cannot be deleted with just one pointer variable as asked by the question.

Question 17.7​

The following loop is supposed to delete all nodes from a linked list and release the memory that they occupy. Unfortunately, the loop is incorrect. Explain what's wrong with it and show how to fix the bug.

for (p = first; p != NULL; p = p->next)
   free(p);

Looking at the code, one of the flaw at the first observation is that, once free is called inside the for loop block, the memory allocated by the pointer p (which is assumed to be a pointer to a structure of members int num and struct linked_list *next) will be released by the program. After the for block is executed, the third expression described in the for statement, i.e. p = p->next is executed. This is illegal as it is trying to access a memory block that is released by the program which will probably send a SIGSEGV (segfault). Since p is being assigned the address pointed to by first, one potential solution can be:

for (; first != NULL;) {
   p = first;
   first = first->next;
   free(p);
}

This program will run as follows:

  1. p will be assigned the address of pointed to by first.
  2. first will be assigned the address pointed to by the member next of the structure variable.
  3. p will be freed, without any issue of the program accessing the "illegal" address in the heap.

Question 17.8​

Section 15.2 describes a file, stack.c, that provides functions for storing integers in a stack. In that section, the stack was implemented as an array. Modify stack.c so that a stack is now stored as a linked list. Replace the contents and top variables by a single variable that points to the first node in the list (the "top" of the stack). Write the functions in stack.c so that they use this pointer. Remove the is_full function, instead having push return either true (if memory was available to create a node) or false (if not).

#include <stdio.h>
#include <stdlib.h>

struct stack_sll {
   int content;
   struct stack_sll *next;
};

struct stack_sll *push_stack_sll (struct stack_sll *s_list, int content);
Login to view full code

Question 17.9​

True or false: If x is a structure and a is a member of that structure, then (&x) -> a is the same as x.a. Justify your answer.

True. Given that x is a structure variable with a as its member, we can access structure in both ways as described in the question. As &x gives the address of the structure variable, we can use the arrow operator (->) to access the members of a pointer to a structure. We use the dot (.) operator to access the members of a structure variable.

Question 17.10​

Modify the print_part function of Section 1672 so that its parameter is a pointer to a part structure. Use the -> operator in your answer.

The function definition in #26 of Chapter 16 notes is:

void print_part (struct part p) {
   printf("Part number: %d\n", p.number);
   printf("Part name: %s\n", p.name);
   printf("Quantity on hand: %d\n", p.on_hand);
}

To modify the function parameter such that it takes a pointer to the structure part and print its details, we can do so as:

void print_part (struct part *p) {
   printf("Part number: %d\n", p->number);
   printf("Part name: %s\n", p->name);
   printf("Quantity on hand: %d\n", p->on_hand);
}

To call the function given that a variable of type struct part is defined, we can do so as:

...
struct part p1;
...
print_part(&p1);

Question 17.11​

Write the following function:

int count_occurrences(struct node *list, int n);

The list parameter points to a linked list; the function should return the number of times that n appears in this list. Assume that the node structure is the one defined in Section 17.5.

#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>

size_t num_nodes = 0;

typedef unsigned long size_t;

struct singly_linked_list_node {
Login to view full code

Question 17.12​

Write the following function:

struct node *find_last(struct node *list, int n);

The list parameter points to a linked list. The function should return a pointer to the last node that contains n: it should return NULL if n doesn't appear in the list. Assume that the node structure is the one defined in Section 17.5.

#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>

size_t num_nodes = 0;

typedef unsigned long size_t;

struct singly_linked_list_node {
Login to view full code

Question 17.13​

The following function is supposed to insert a new node into its proper place in an ordered list, returning a pointer to the first node in the modified list. Unfortunately, the function doesn't work correctly in all cases. Explain what's wrong with it and show how to fix it. Assume that the node structure is the one defined in Section 17.5.

struct node *insert_into_ordered_list(struct node *list, struct node *new_node)
{
   struct node *cur = list, *prev = NULL;
   while (cur->value <= new_node->value) {
      prev = cur;
      cur = cur->next;
   }
   prev->next = new_node;
   new_node->next = cur;
   return list;
}

Consider a scenario where we call the function with root as the first argument and new_node as the second argument. Say that one function has the memory allocated for the new_node as follows:

void create_new_node (...) {
   struct node *new_node;
   new_node = malloc(sizeof(struct node));
   new_node->value = ...;
   struct node *temp;
   temp = insert_into_ordered_list(root, new_node);
}

When we call the function in this manner, the function parameter:

  1. list will hold the pointer to the struct node variable root, and,
  2. new_node will hold the pointer to the struct node variable new_node - defined in create_new_node.

One of the problem of the program is that say that we have a linked list of data: 5, 10. The new value we need to store is 15. What will happen is:

  1. (5 <= 15) is true, so prev will now point to address pointed to by cur, and cur will point to address pointed to by cur->next - which holds the value 10.
  2. (10 <= 15) is true, so prev will point to node which contains the value 10, and cur will point to the NULL pointer, assuming that the end of the linked list has the NULL node.
  3. (cur->value <= 15) is evaluated, the expression is not valid as it is trying to access the memory pointed by a NULL pointer, which is a ERR_BAD_ACCESS.

To fix this problem, we must have the condition for the while statement as follows:

while (cur != NULL && cur->value <= new_node->value);

Notice that the first expression (cur != NULL) preceeds the given expression (cur->value <= new_node->value). This is done to conform to the short circuiting functionality provided by C. If the first expression is false, lazy evaluation takes places as 0 && anything will result in 0.

This will fix the issue of adding nodes in the list. BUT, this does not solve the problem of adding the node whose value is smaller as compared to other node's value. In such case, the new_node should be added first, which is not the behavior of this program.

To solve this, the following modification needs to be done:

if (prev == NULL) {
   new_node->next = cur;
   return new_node;
} else {
   prev->next      = new_node;
   new_node->next  = cur;
   return list;
}

If the new_node contains the value which is lower as compared to other node's value, then the while loop will not run, making prev still point to NULL as it was initialized. Then, the new_node can be modified to act as the first node in the linked list. If not, and the new_node is the one which is to be added between the list or at the end, the else clause will run, and the desired effect is noticed.

Question 17.14​

Modify the delete_from_list function (Section 17.5) so that its first parameter has type struct node ** (a pointer to a pointer to the first node in a list) and its return type is void. delete_from_list must modify its first argument to point to the list after the desired node has been deleted.

NOTE: Take reference from the function definition sll_delete_node

One way to visualize this is, consider that the first node in the linked list, pointed to by root is:

  1. address of first node - of type struct singly_linked_list_node - has the address: 0x1234.
  2. root is, say, in address 0x5678, whose content is 0x1234.
  3. When sending the address of root, what we're essentially doing is, we're sending 0x5678 in the function.

When the first node is the one that needs to be deleted, prev will be NULL. Keep in mind the following assignments to the function parameters:

  1. list is a pointer to a pointer to a struct singly_linked_list_node variable, which will be the address of root in this case.
  2. num is a number that needs to be checked in the linked list to delete the respective node.

When the first node is to be deleted, *list = (*list)->next is done. What this does is, as list is 0x5678, dereferencing it will point to the address 0x1234, and (*list)->next is the one next to the first pointer. What is essentially happening here is, we're changing the address of the first node with the address of the node which is being pointed to by the member of the first node's next member.

Question 17.15​

Show the output of the following program and explain what it does.

#include <stdio.h>

int f1(int (*f)(int));
int f2(int i);

int main(void)
{
   printf("Answer: %d\n", f1(f2) );
   return 0;
}

int f1(int (*f)(int))
{
   int n = 0;

   while ((*f) (n)) n++;
   return n;
}

int f2(int i)
{
   return i * i + i - 12;
}
  1. When f1 is called from main function, with f2 as it's argument, which is valid as f1 is expecting a parameter of type "function pointer" which take one int as it's parameter.
  2. On the function f1, n is a local variable initialized as 0. In the while loop, function f2 is called with 0 as it's arugment, and in function f2, 0 * 0 + 0 - 12 = -12 is returned.
  3. As it is not 0 - the termination condition for a loop - n is incremented, and n is now 1. Again the function f2 is called. So f2 is now called as f2(1). In f2, 1 * 1 + 1 - 12 = -10 is returned. Again, loop is not terminated and n is computed again. In tabular representation:
nn × n + n − 12f₂(n)
0-12-12
1-10-10
2-6-6
300

Notice that when n is 3, and f2 is called with n as its argument, f2 will return 0, which is indeed a valid loop termination condition. So the loop will terminate, and f1 will return n - which is 3 - to the main function. Hence, the output will be: Answer: 3

NOTE: We can replace f1(f2) with f1(&f2), as f1 is expecting a pointer to a function which takes one int as a parameter and returns an int. Also, (*f)(n) in the while statement can be replaced with f(n), see #57 of Chapter's notes.

Question 17.16​

Write the following function. The call sum(g, i, j) should return g(i) + ... + g(j).

int sum(int (*f)(int), int start, int end);

#include <stdio.h>

int square (int num);

int sum (int (*f)(int), int start, int end);

void clear_input_stream (void);

int main (void) {
Login to view full code

Question 17.17​

Let a be an array of 100 integers. Write a call of qsort that sorts only the last 50 elements in a. (You don't need to write the comparison function).

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define ARR_SIZE 100

/*
* compare: compares the elements, returns 1 if element_1 is greater than element_2. -1 if 
*          element_1 is less than element_2, and 0 if element_1 is equal to element_2.
Login to view full code

Question 17.18​

Modify the compare_parts function so that parts are sorted with their numbers in descending order.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/* For demonstration purposes. Actual structure contains name, and on_hand members as well. */
struct part {
   int number;
};
Login to view full code

Question 17.19​

Write a function that, when given a string as its argument, searches the following array of structures for a matching command name, then calls the function associated with that name.

struct {
   char *cmd_name;
   void (*cmd_pointer)(void);
} file_cmd[]=
  {{"new",        new_cmd },
   {"open",       open_cmd },
   {"close",      close_cmd },
   {"close all",  close_all_cmd },
   {"save",       save_cmd },
   {"save as",    save_as_cmd },
   {"save all",   save_all_cmd },
   {"print",      print_cmd },
   {"exit",       exit_cmd },
  };
#include <stdio.h>

#define CMD_LEN 10

void new_cmd          (void);
void open_cmd         (void);
void close_cmd        (void);
void close_all_cmd    (void);
void save_cmd         (void);
Login to view full code

Programming Projects​

Project 17.1​

Modify the inventory.c program of Section 16.3 so that the inventory array is allocated dynamically and later reallocated when it fills up. Use malloc initially to allocate enough space for an array of 10 part structures. When the array has no more room for new parts, use realloc to double its size. Repeat the doubling step each time the array becomes full.

  • Makefile
  • main.c
  • utils.c
  • utils.h

Project 17.2​

Modify the inventory.c program of Section 16.3 so that the p(print) command calls qsort to sort the inventory array before it prints the parts.

  • Makefile
  • main.c
  • utils.c
  • utils.h

Project 17.3​

Modify the inventory2.c program of Section 17.5 by adding an e(erase) command that allows the user to remove a part from the database.

  • Makefile
  • main.c
  • readline.c
  • readline.h

Project 17.4​

Modify the justify program of Section 15.3 by rewriting the line.c file so that it stores the current line in a linked list. Each node in the list will store a single word. The line array will be replaced by a variable that points to the node containing the first word. This variable will store a null pointer whenever the line is empty.

  • Makefile
  • line.c
  • line.h
  • main.c
  • quote
  • temp
  • word.c
  • word.h

Project 17.5​

Write a program that sorts a series of words entered by the user:

Enter word: foo
Enter word: bar
Enter word: baz
Enter word: quux
Enter word:

In sorted order: bar baz foo quux

Assume that each word is no more than 20 characters long. Stop reading when the user enters an empty word (i.e., presses Enter without entering a word). Store each word in a dynamically allocated string, using an array of pointers to keep track of the strings, as in the remind2.c program (Section 17.2). After all words have been read, sort the array (using any sorting technique) and then use a loop to print the words in sorted order. Hint: Use the read_line function to read each word, as in remind2.c.

  • Makefile
  • main.c
  • utils.c
  • utils.h

Project 17.6​

Modify Programming Project 5 so that it uses qsort to sort the array of pointers.

  • Makefile
  • main.c
  • utils.c
  • utils.h

Project 17.7​

(C99) Modify the remind2.c program of Section 17.2 so that each element of the reminders array is a pointer to a vstring structure (see Section 17.9) rather than a pointer to an ordinary string.

  • Makefile
  • main.c

Contents

Edit this page