Простой, но мощный «Список» на C

«C» - замечательный язык программирования, который иногда вызывает затруднения при работе с памятью. Когда дело доходит до языка, встроенного в утилиту структуры данных (например, List, Queue, Stack и т. Д.), Кроме Array, ни один из них не доступен из коробки.

Но отсутствие этой структуры данных не означает, что вы не можете их использовать. Infect, они жизненно важны почти для каждого маленького или большого программного проекта. Итак, язык C заставляет вас создавать собственную реализацию этой структуры данных.

Моя цель в этом блоге - познакомить моих читателей с очень маленькой, но мощной реализацией структуры данных «Список» на языке C.

Итак, зачем мне «Список»?

Список - очень важная часть почти всего, что вы делаете с данными. Любая запись, которую вы хотите сохранить в памяти. Вам лучше организовать каждую запись в «Списке», если вы не хотите терять их адрес (если вы потеряете какой-либо адрес, это вызовет утечку памяти, это может привести к аварии вашего корабля).

Например, если вы хотите создать музыкальное приложение, которое просто показывает список песен и воспроизводит песню при выборе любой песни. Чтобы создать подобное приложение, вам понадобится «Список».

Другой пример. Вы хотите создать программу для отметки посещаемости учеников в классе. Вам нужно вести рекорд по каждому ученику. Вам нужен «Список» для записи каждого студента.

Как мне составить «список»?

Давайте напишем код и посмотрим, как он работает.

struct wv_list {
    struct wv_list *prev;
    struct wv_list *next;
};

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

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

Вставить - добавить новую запись в список.

Удалить - удалить запись из списка.

Итерация - прокрутите каждую запись в списке.

Отпусти, через них одного за другим,

Вставить

void wv_list_insert(struct wv_list *list, struct wv_list *elm)
{
    elm->prev = list;
    elm->next = list->next;
    list->next->prev = elm;
    list->next = elm;
}

Над фрагментом кода поместите новую запись под названием «вяз» сразу после заголовка в списке. Итак, после добавления еще одной записи в список выше изображение будет выглядеть примерно так

Удалить

void wv_list_remove(struct wv_list *elm)
{
    elm->next->prev = elm->prev;
    elm->prev->next = elm->next;
    elm->next = NULL;
    elm->prev = NULL;
}

Приведенный выше фрагмент кода удалит запись с именем «вяз» из «Списка». После удаления записи «ПЕСНЯ 1» из «Списка». Приведенное выше изображение изменится на что-то вроде этого

Итерировать

Итерация - одна из самых интересных частей этого блога. Многие языки, такие как Java, C # и т. Д., Имеют встроенную функцию для итерации каждой записи списка или коллекции, и в этих языках это называется циклом «foreach». Но наш любимый язык «C» ничего не знает о «foreach» и должен будет создать нашу собственную реализацию цикла «foreach».

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

Давайте понимать "контейнеры"

#define wv_container_of (ptr, sample, member)
(void *) ((char *) (ptr) - ((char *) & (sample) - ›member - (char *)
(sample )))

Чтобы понять приведенный выше фрагмент кода, предположим, что у вас есть структура, содержащая несколько членов. Если у вас есть указатель на один из этих членов, но у вас нет указателя на саму структуру (который является не чем иным, как начальным адресом структуры). Затем приведенный выше код даст вам указатель на саму структуру.

На рисунке выше адрес памяти «0x5f5f0020» указывает на переменную-член «Размер» структуры «Песня», а серый прямоугольник - это начальный адрес структуры (который нам неизвестен). Если вы хотите получить доступ к другим членам структуры, таким как Имя и Описание, вам понадобится указатель от начала структуры или указатель на саму структуру. «wv_container_of» Марко извлечет указатель на структуру, просто передав ему указатель на известный член структуры.

Его принимают 3 параметра,

ptr - действительный указатель на содержащийся член.

образец - указатель на структуру, тип которой содержит ptr (также может иметь значение null)

member - именованное расположение ptr в типе выборки.

Вернемся к итерации в «Списке»

#define wv_list_for_each(pos, head, member)
    for (pos = wv_container_of((head)->next, pos, member);\
         &pos->member != (head);\
         pos = wv_container_of(pos->member.next, pos, member))

Приведенный выше код создаст цикл for, который будет перебирать каждую запись в List. На каждой итерации «pos» будет содержать указатель на запись (или узел). «Head» - это указатель на сам список, а «member» - это имя структуры-члена типа «wv_list». Любая структура, которая хочет стать узлом в списке, должна содержать член типа wv_list.

Я закончил с объяснением структуры данных List, чтобы внести больше ясности в ваше понимание «List» на языке C, я написал небольшой пример приложения, которое может помочь вам получить более полное представление о его использовании.

Ссылка на Github - https://github.com/xsumirx/medium_tutorials/tree/master/List