I'm relatively new to programming as I've just started university. My assignment was to develop a program (by using a function and a linked list with pointers with integer elements) which does the following:
- The function visits every element from the beginning. If the current element plus one is <= to the following element (e.g. if the first one is i and the second one is j, j>=i+1), you have to complete the list by adding all the values between i and j-1.
- If the current element is followed by an element <=, it is to be removed by the list and added to an array declared in the formal parameters. You also have to put in the formal parameters a counter for the deleted elements.
I had already asked a question about this function since I couldn't get it to work, but using recursive functions I finally made it. I would now like to know how I might improve it! Sorry if I made any grammar mistakes, English is not my native language.
I left all the comments I made about how each function works.
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
// list declaration
struct list {
int value;
struct list * next_ptr; };
// pre_insert function.
void pre_insert(struct list ** ptrptr, int value) {
struct list * tmp_ptr;
tmp_ptr = *ptrptr;
*ptrptr = malloc(sizeof(struct list));
(*ptrptr)->value = value;
(*ptrptr)->next_ptr = tmp_ptr;
}
// if the following item is bigger than the current one, a call to this function inserts all the items missing between the two values.
// the cost of this function is T(N) = c * (N-1) (because of the while loop).
void succ_value_bigger(struct list * ptr) {
while (ptr->value + 1 < ptr->next_ptr->value)
pre_insert(&ptr->next_ptr, ptr->next_ptr->value-1);
}
// if succ_value_smaller is called by complete_list_to_array, this function deletes the item following the one pointed by ptr.
// the function has linear cost as there are no iterations.
int delete_element (struct list * succ_ptr, int * V, int k) {
V[k] = succ_ptr->value;
free(succ_ptr);
return k;
}
// if i value is bigger than the following one, complete_list_to_array calls this function.
// the function deletes the following element using a call to delete_element function, then increases both count and k.
// the first one counts the deleted elements, the second one is an index for the array V collecting all the deleted elements.
// the function has a recursive behaviour, calling main function complete_list_to_array for the following element to be confronted with i.
// the function has cost T(N) = c1*N + c2 (since the else guard only works for the last item).
int succ_value_smaller(struct list * ptr, int * V, int * count, int k) {
struct list *succ_ptr = ptr->next_ptr;
// the guard sees if the current item isn't the last one. if so, it sends the flow to else, below.
// if it is not the case, it deletes the following element and increases the indexes.
if (succ_ptr->next_ptr != NULL)
{
ptr->next_ptr = succ_ptr->next_ptr;
delete_element(succ_ptr, V, k);
k++;
(*count)++;
// after doing so, it calls recursively to complete_list_to_array,
// so that the current item is confronted with its new following element.
// the returned value is *count.
(*count) = complete_list_to_array(ptr, V, count, k);
}
else {
// if the flow is sent here, it means the list has arrived at its last item, after the current one.
// the succ_ptr->next_ptr pointer will so point to NULL, indicating the list has reached its end.
// as above, the following item is deleted and count increased. The k index, though, has no need to
// as it's the last time an element will be inserted in the array V.
ptr->next_ptr = NULL;
delete_element(succ_ptr, V, k);
(*count)++;
}
return (*count);
}
// complete_list_to_array is the main recursive function of the program. Getting its data directly from main(),
// it uses while both as a loop and as a guard, checking each time if the list has reached its end or its last element.
// the function has cost T(N) = c1 if N == 2 || c1*N + T(N-1) if N > 2
int complete_list_to_array(struct list * ptr, int * V, int * count, int k) {
struct list * succ_ptr;
while (ptr != NULL)
{
if(ptr->next_ptr != NULL)
{
succ_ptr = ptr->next_ptr;
// if the following element is bigger than the current element plus one, it sends
// the flow to function succ_value_bigger and slides ptr to its following pointer.
if(ptr->value + 1 <= succ_ptr->value) {
succ_value_bigger(ptr);
ptr = ptr->next_ptr;
}
// if the following element is smaller than the current, it increases the index *count as return value
//and sends the flow to succ_value_smaller, then slides ptr to the following pointer.
else if (succ_ptr->value <= ptr->value)
{
(*count) = succ_value_smaller(ptr, V, count, k);
if (ptr->next_ptr != NULL)
ptr = ptr->next_ptr;
else
ptr->next_ptr = NULL;
}
}
// if the list only has one item, the flow is sent here. The break instruction sends the flow to the following
// instruction, and is widely used to change the flow in switch iterations.
else break;
}
return (*count);
}
// the following function creates the list which will then be used in the function. It uses two pointers, one to the
// first item, which is the return value (so that the main() function can begin its work from the first item), and
// a general pointer which is slid each time a value is inserted, according to the number N of items in the list.
struct list * create_list(int N) {
struct list * first_ptr, * ptr;
int i;
// if the list contains 0 elements (N == 0) the first pointer will point to NULL, contained in the memory.h library.
if(N == 0) {
first_ptr = NULL;
}
else {
first_ptr = malloc(sizeof(struct list));
printf("Insert the first value:\n");
scanf("%d", &first_ptr->value);
ptr = first_ptr;
for(i = 2; i <= N; i++) {
ptr->next_ptr = malloc(sizeof(struct list));
ptr = ptr->next_ptr;
printf("Insert element number %d:\n", i);
scanf("%d", &ptr->value);
}
ptr->next_ptr = NULL;
}
return(first_ptr);
}
// this simple function prints all the items contained in the list. It uses a while loop until the list
// has reached its last element.
void visit(struct list * ptr) {
int i = 1;
while(ptr != NULL) {
printf("Item number %d in the list has value %d.\n", i, ptr->value);
ptr = ptr->next_ptr;
i++;
}
}
// main function
int main(void) {
// variables declaration and dynamic allocation of the array.
struct list * first_ptr;
int N, k = 0;
int i;
int * V, count = 0;
V = (int *)malloc(sizeof(int)*count);
// choice of the dimension of the list.
printf("Insert the number of elements in the list.\n");
scanf("%d", &N);
// call to create_list function.
first_ptr = create_list(N);
printf("\n----------------------------\n\n");
// call to visit function in order to print the items initally contained in the list.
printf("At the beginning, the list contained the following items:\n\n");
visit(first_ptr);
printf("\n----------------------------\n\n");
// call to complete_list_to_array function, using first_ptr so that it begins from the first item
// and count's address, as the list requires in its formal parameters a pointer to int.
count = complete_list_to_array(first_ptr, V, &count, k);
// results after the flow returns from the function to main(). It first tells the user which and how many items
// have been removed (if count == 0 it skips the first step), then prints the modified list.
printf("After the function call, the following items have been removed from the list and put into the array:\n\n");
if(count == 0) {
printf("No item has been removed from the list.\n");
}
else {
for(i = 0; i < count; i++) {
printf("The value of V[%d] is: %d.\n", i, V[i]); }
printf("\nThe total number of removed elements is %d.\n", count);
}
// using function free(void *), the memory section occupied by array V, which was first allocated with
// library <stdlib.h>'s function malloc. This way, the allocated section for V is freed from the memory.
free(V);
printf("\n----------------------------\n\n");
printf("After the function call, the list contains the following items:\n\n");
visit(first_ptr);
return 0;
}
