При подготовке к сертификации я решил заготовить «бомбы» какие-то стандартные не сложные вещи, которые скорей всего пригодятся мне во время решения теста и на которые не хотелось бы тратить время. И первое с чего я бы хотел начать это односвязный список. Односвязный список будет очень полезен для реализации обхода дерева как в глубину, так и в ширину, точней он необходима для итеративной реализации, потому что на нем можно реализовать как стек, так и очередь.
Немного информации из википедии:
Свя́зный спи́сок — базовая динамическая структура данных в информатике, состоящая из узлов, каждый из которых содержит как собственно данные, так и одну или две ссылки («связки») на следующий и/или предыдущий узел списка.[1]Принципиальным преимуществом перед массивом является структурная гибкость: порядок элементов связного списка может не совпадать с порядком расположения элементов данных в памяти компьютера[2], а порядок обхода списка всегда явно задаётся его внутренними связями.
/* Определяем элемент списка */ typedef struct list_node { struct list_node *next; void *data; } list_node_t; /* Определяем сам список */ typedef struct list { /* * Размер списка хранить не обязательно, * он нужен для упрощения работы */ int size; /* начало списка */ list_node_t *head; /* конец списка */ list_node_t *tail; } list_t; /* Инициализация массива */ list_t * create_list(void) { list_t *lt = malloc(sizeof(list_t)); lt->size = 0; lt->head = NULL; lt->tail = lt->head; return lt; } /* Добавляем элемент в начало списка */ void list_push(list_t *lt, void * data) { list_node_t * node = malloc(sizeof(list_node_t)); node->data = data; node->next = lt->head; lt->head = node; lt->size += 1; } /* Извлекаем элемент из начала списка */ void * list_pop(list_t *lt) { if(lt->size == 0){ /* Список пуст */ return NULL; } list_node_t *node = lt->head; void * ret_val = node->data; lt->size -= 1; lt->head = node->next; free(node); if(lt->size == 0){ /* Это был последний элемент */ lt->head = NULL; lt->tail = NULL; } return ret_val; } /* Добавляем элемент в конец списка */ void list_push_back(list_t *lt, void * data) { list_node_t * node = malloc(sizeof(list_node_t)); node->data = data; if(lt->tail != NULL) lt->tail->next = node; else { lt->head = node; } lt->tail = node; lt->size += 1; }
Теперь можно использовать этот список и как очередь и как стек.
Пример использования как стек:
list_t *st = create_list(); int data = 0, *ptr; /* Добавляем в начало списка */ list_push(st, &data); /* Извлекаем из начала списка*/ ptr = (int *)list_pop(st);
А вот пример использования как очереди:
list_t *queue = create_list(); int data = 0, *ptr; /* Добавляем в конец списка */ list_push_back(queue, &data); /* Извлекаем из начала списка*/ ptr = (int *)list_pop(queue);