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

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

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

Что надо:

+-------------+    +-------------+
| 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 - параметр - значение, которое надо удалить из списка.

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

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