Программы
Упражнение: связный список

Упражнение: связный список

Теория без практики суха и даже вредна: немного разомнёмся на связном списке

Что надо:

+-------------+    +-------------+
| DATA | NEXT |--->| DATA | NEXT |
+-------------+    +-------------+

– получить структуру данных и функции работы с ней, позволяющие хранить данные в виде связного списка: каждое следующее звено данных можно получить по ссылке из предыдущего.

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

/**
 * Структура для описания элемента списка.
 * Объявим структуру,
 * полем которой является указатель на неё же.
 */
typedef struct node {
  struct node * next;  // Если NULL - значит конец списка
  char val;
} node_t;

/**
 * Функция вывода связного списка.
 * За представление списка отвечает его голова –
 * именно по ней мы можем получить все данные,
 * манипулировать ими.
 * Можно завести отдельную структуру именно под список,
 * но зачем?
 */
void print_list(node_t *head) {
  node_t * current = head;

  while (current != NULL) {
    printf("%c->", current->val);
    current = current->next;
  }

  printf("\n");
}

/**
 * Функция добавления элемена в список.
 */
void add(node_t * head, char val) {
  node_t * current = head;

  // Получаем последний элемент списка
  while (current->next != NULL) {
    current = current->next;
  }

  current->next = (node_t *)malloc(sizeof(node_t));
  current->next->val = val;
  current->next->next = NULL;
}

int main() {
  char c;
  // Из-за лени инициализируем "список" сразу,
  // а не получив первое значение.
  node_t head = { .next = NULL, .val = ' ' };

  while ((c = getc(stdin)) != EOF) {
    add(&head, c);
  }

  print_list(&head);
  return 0;
}

ДЗ

Добавить функции:

  • index (-1, если не найден, сдвиг от head - иначе)
  • remove_first / remove_last - параметр - значение, которое надо удалить из списка.

Альтернативное задание:

  • Реализовать декартово дерево: добавление элемента, поиск элемента, удаление элемента.
Также может быть вам интересно:

Динамическое выделение памяти

Итак, динамическое управление памятью – сбрасываем оковы прибитых при компиляции размеров структур!

Читать »

Два джунá писали АПИ

Небольшой рассказ о разработке API

Читать »
Фото Как сделать свою middleware в Django (с примерами)

Как сделать свою middleware в Django (с примерами)

Middleware или "промежуточное программное обеспечение" - элегантный способ установить общие правила обработки запросов и ответов приложения. Давайте напишем парочку middleware, чтобы понять, как они работают.

Фото Как настроить отправку почты из Django

Как настроить отправку почты из Django

Письма об ошибках, отчёты на почту, восстановление паролей - всё это полезно при работе с сайтом. Django предоставляет удобный способ это сделать с минимумом настроек!

Фото Добавляем поддержку медиа-файлов в Django проект

Добавляем поддержку медиа-файлов в Django проект

Современные сайты редко ограничиваются только текстом и вёрсткой. Часто в заметках красуются фотографии, а рядом с описанием товаров - их изображения.

Фото Настройка журналирования (логирования) в Python с примерами

Настройка журналирования (логирования) в Python с примерами

Во время работы программы часто нужно сохранять некоторые важные записи о процессе выполнения команды. В Python есть довольно мощный модуль для работы с логами - давайте разберёмся с тем, как его использовать.

Фото Нет слов, одни... однострочники

Нет слов, одни... однострочники

На днях вышел пост со списком полезных однострочников для JavaScript программистов. Памятуя Perl-овую молодость, заглянул туда.

Фото Добавляем переменные в контекст Django шаблонов (свой контекст-процессор)

Добавляем переменные в контекст Django шаблонов (свой контекст-процессор)

В Django вы можете передавать данные в шаблоны посредством контекстов. Контекст передаётся из контроллера (view в терминах Django), однако, если одни и те же данные нужны в разных местах, лучше сделать свой контекст-процессор.

Фото Пример своей консольной команды в Django проекте

Пример своей консольной команды в Django проекте

Если вы работали с Django проектом, то, скорее всего, запускали команды из консоли (manage.py). В Django есть простой способ писать свои команды для управления проектом.

Фото Разграничение прав доступа на Django сайте

Разграничение прав доступа на Django сайте

Почти на любом веб-сайте необходимо разделять пользователей на группы и предоставлять им разные возможности. В Django есть довольно серьёзная система прав доступа для пользователей - давайте её рассмотрим!