This project was developed for 42 school. For comprehensive information regarding the requirements, please consult the PDF file in the subject folder of the repository. Furthermore, I have provided my notes and a concise summary below.
+ libft
+ data structure, linked lists
+ recap what was studied during PiscineMindmap BITS(shinckel, 2023)
Mindmap LINKED LISTS(shinckel, 2023)
Building lists according to Stanford CS Education Library, page 12
void push(t_list **head, int data)takes a list and a data value;node = (t_list *)malloc(sizeof(t_list));node->data = data;creates a new link with the given data and pushes it onto the front of the listnode->next = *head;;head = node;the list is not passed in by its head pointer...*head = node;instead the list is passed in as a "reference" pointer to the head pointer -- this allows us to modify the caller's memory.
Adding nodes to the tail through Local Reference according to Stanford CS Education Library, page 20
#include "list.h"
#include <stdlib.h>
#include <stdio.h>
/*
* what is the size of the list?
* iterate over the list with a local pointer(tmp)
* test the case in which head == NULL
* return the list by passing the head pointer
*/
int size_list(t_list *head) {
t_list *tmp;
int count;
count = 0;
tmp = head;
while (tmp != NULL)
{
count++;
tmp = tmp->next;
}
return (count);
}
/*
* I need it to be able to change some of the caller's memory — namely the head
* variable in heap. NOT AS A LOCAL VALUE, BUT UPDATE MEMORY
* solution - pointer to a struct node(**)... that is why the double pointer
* void push(&t_list **head, int data) - this would pass a copy of the
* head pointer instead, changing nothing in memory
*/
void push(t_list **head, int data) {
t_list *node;
node = (t_list *)malloc(sizeof(t_list));
node->data = data;
node->next = *head;
*head = node;
}
void print_list(t_list *head) {
t_list *current = head;
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
/* it is a reference pointer too */
void changetoNULL(t_list **head) {
*head = NULL;
}
t_list *add_at_head(void) {
t_list *head = NULL;
int i = 1;
while (i < 6)
{
push(&head, i);
i++;
}
return (head);
}
/*
* This is just a special case of the general rule
* to insert or delete a node inside a list, you need a pointer to the node
* just before that position, so you can change its .next field!
* HEAD POINTER adds the first, then TAIL POINTER adds the rest
*/
t_list *add_at_tail() {
t_list *head = NULL;
t_list *tail;
int i;
// deal with head, then set the tail pointer
push(&head, 1);
tail = head;
// do all other nodes using tail
i = 2;
while (i < 17)
{
push(&tail->next, i);
tail = tail->next;
i++;
}
return (head);
}
/*
* Option 02 is to add nodes to tail through (temporary)dummy nodes
* the tail pointer plays the same role as in the previous example...
* ...the difference is that it now also handles the first node
* Dummy Node -> Node1 -> Node2 -> Node3 -> NULL
*/
t_list *dummy_node() {
t_list dummy;
t_list *tail = &dummy;
int i;
dummy.next = NULL;
i = 20;
while (i < 30)
{
push(&tail->next, i);
i++;
tail = tail->next;
}
return (dummy.next);
}
/*
* Option 03 adds a pointer to the last next pointer instead of last node
*/
t_list *reference_node() {
t_list *head = NULL;
t_list **lastREF = &head;
int i = 0;
while(i < 10)
{
// add node at the last pointer in the list
push(lastREF, i);
// advance to point to the new last pointer
lastREF = &((*lastREF)->next);
i++;
}
return (head);
}
int main(void) {
t_list *head = NULL;
t_list *head2;
changetoNULL(&head2);
push(&head2, 17);
push(&head, 3);
push(&head, 2);
push(&head, 1);
push(&head, 13);
print_list(head);
print_list(head2);
printf("\nadd at head\n");
print_list(add_at_head());
printf("\nadd at tail - method1\n");
print_list(add_at_tail());
printf("\nadd at tail - method2\n");
print_list(dummy_node());
printf("\nadd at tail - method 03\n");
print_list(reference_node());
printf("\nlist size\n");
printf("%i\n", size_list(head));
return (0);
}ft_isalpha- checks for an alphabetic character.ft_isdigit- checks for a digit (0 through 9).ft_isalnum- checks for an alphanumeric character.ft_isascii- checks whether c fits into the ASCII character set.ft_isprint- checks for any printable character.ft_toupper- convert char to uppercase.ft_tolower- convert char to lowercase.
ft_memset- fill memory with a constant byte.ft_strlen- calculate the length of a string.ft_bzero- zero a byte string.ft_memcpy- copy memory area.ft_memmove- copy memory area.ft_strlcpy- copy string to an specific size.ft_strlcat- concatenate string to an specific size.ft_strchr- locate character in string.ft_strrchr- locate character in string.ft_strncmp- compare two strings.ft_memchr- scan memory for a character.ft_memcmp- compare memory areas.ft_strnstr- locate a substring in a string.ft_strdup- creates a dupplicate for the string passed as parameter.
ft_atoi- convert a string to an integer.ft_calloc- allocates memory and sets its bytes' values to 0.
ft_substr- returns a substring from a string.ft_strjoin- concatenates two strings.ft_strtrim- trims the beginning and end of string with specific set of chars.ft_split- splits a string using a char as parameter.ft_itoa- converts a number into a string.ft_strmapi- applies a function to each character of a string.ft_striteri- applies a function to each character of a string.ft_putchar_fd- output a char to a file descriptor.ft_putstr_fd- output a string to a file descriptor.ft_putendl_fd- output a string to a file descriptor, followed by a new line.ft_putnbr_fd- output a number to a file descriptor.
ft_lstnew- creates a new list element.ft_lstadd_front- adds an element(e.i.node) at the beginning of a list.ft_lstsize- counts the number of elements in a list.ft_lstlast- returns the address of the last node of the list.ft_lstadd_back- adds an element at the end of a list.ft_lstclear- deletes and free list, same as ft_lstdelone but here is **lst.ft_lstiter- applies a function to each element of a list.ft_lstmap- same as lstiter, but creates and return a new list.- ft_lstdelone.c - frees the memory of node's content (through function 'del').
| Task | Prototype | Description |
|---|---|---|
bitwise operators |
& ^ ~ << >> |
also known as bit operators as they work at the bit-level. IntroComputing about bits/ bytes |
print_bits |
void print_bits(unsigned char octet) |
the bitwise operations treat the octet as a bit pattern and work on the binary representation of the value, regardless of its sign. Therefore, even if octet is an unsigned char, the function will perform with negative numbers, but relying on implicit conversion in C |
| Linked lists | linked lists have been the domain where beginning programmers get the practice to really understand pointers. Store collections of data (elements), the same structure works to store elements of any type. Linked Lists Problems, from Stanford CS Education Library | |
| Binary Trees | struct node { int data; struct node* left; struct node* right; } |
recursive pointer algorithms |
Stack memory |
x | pointers are automatically allocated when the function starts and deallocated when it exits. The heap allocated links will remain even though stack allocated pointers which were pointing to them have been deleted |
Heap memory |
x | it is not automatically deallocated when the creating function exists (e.g. malloc() returns NULL if it fails the request), source code needs to explicitly check for allocation failures and explicitally deallocate it in the end using free() |
| Pointers and memory | ||
Makefile |
MIT example |