------------------------- ------------------------
| | | \ | | |
| DATA | NEXT |-------------| DATA | NEXT |
| | | / | | |
------------------------- ------------------------Одним из способов создания динамических структур данных в C является использование связанных списков. В этой статье я представляю основные методы добавления, удаления и поиска элемента.
Для этих примеров структура данных, которую мы используем, выглядит следующим образом:
typedef struct listas {
int info;
struct listas * next;
} list_t;
Добавить элемент в head:
list_t * listaddhead (list_t * t, int val)
{
list_t * new_item;
if((new_item = malloc(sizeof(list_t)))){
new_item->info = val;
new_item->next = t;
t = new_item;
} else
printf("out of memory");
return t;
}
Давайте посмотрим подробнее, метод добавления в начало получает указатель на первый элемент списка и значение для добавления в список.
Мы создадим экземпляр памяти с помощью MALLOC. Если памяти достаточно, мы присвоим значение, полученное на входе от метода, новому элементу, а в начало списка присвоим указатель на следующий элемент. Новый заголовок списка будет указателем на вновь созданный элемент.
Для большей наглядности сделаю несколько рисунков, имена переменных те же, что и в коде.
Это исходная ситуация:
------------- ------------------------ | | \ | | | \ | T(HEAD) |-------------| INFO | NEXT |------------- | | / | | | / ------------- ------------------------------------- ------------ | | \ | | |new_item|-------------| NULL | | | / | | ------------- ------------
Первое, что происходит, мы создаем экземпляр области памяти.
(new_item = malloc(sizeof(list_t))------------- ------------------------ | | \ | | | \ | T(HEAD) |-------------| INFO | NEXT |------- | | / | | | / ------------- ------------------------------------- ------------------------ | | \ | | | \ |new_item|-------------| INFO | NEXT |------- NULL | | / | | | / ------------- ------------------------
Теперь мы назначаем голову следующему новому элементу
new_item->next = t;------------- ------------------------ | | \ | | | \ | T(HEAD) |-------------| INFO | NEXT |------- | | | / | | | / ------------- | ------------------------ |---------------------------------- |------------- ------------------------ | | | \ | | | | |new_item|-------------| INFO | NEXT |--- | | / | | | ------------- ------------------------
Мы делаем так, чтобы заголовок указывал на новый элемент, и именно его возвращает метод.
t = new_item;------------- ------------------------ | | \ | | | \ | T(HEAD) |--- -------| INFO | NEXT |------- | | | | / | | | / ------------- | | ------------------------ | || ---------------------------------- | |------------- | ------------------------ | | | | \ | | | | |new_item|-------------| INFO | NEXT |--- | | / | | | ------------- ------------------------
Добавить элемент в хвост:
list_t * listaddtail (list_t * t, int val) /* add in queue */
{
list_t * new_item;
list_t * tmp1;
list_t * tmp2;
int i;
for(tmp2 = t, i = 0; tmp2; tmp1 = tmp2, tmp2 = tmp2->next)
i++;
if(i){
if((new_item = malloc(sizeof(list_t)))){
new_item->info = val;
new_item->next = NULL;
tmp1->next = new_item;
} else
printf("out of memory");
} else
t = listaddhead(t, val);
return t;
}
Как добавить элемент в конец списка? Сначала я прокручиваю список до последнего элемента, если список пуст, я вызываю метод добавления в начале, если он не пуст, я создаю экземпляр памяти для нового элемента. Я присваиваю значение, полученное в качестве входных данных от метода, для новый элемент, и я установил в NULL указатель на следующий объект.
В дополнение к последнему элементу в списке, мы собираемся сделать так, чтобы он указывал на вновь созданный элемент.
Это исходная ситуация:
-------------------- --------------------
\ | | | \ | | | \
-----| INFO | NEXT |------| INFO | NEXT |------ NULL
/ | | | / | | | /
-------------------- --------------------
Первое, что происходит, мы создаем экземпляр области памяти.
(new_item = malloc(sizeof(list_t)
TMP1 TMP2
-------------------- --------------------
\ | | | \ | | | \
-----| INFO | NEXT |------| INFO | NEXT |------ NULL
/ | | | / | | | /
-------------------- --------------------
------------ --------------------
| | \ | | | \
| new_item | ------| INFO | NEXT |------ NULL
| | / | | | /
------------ --------------------
Теперь давайте укажем последний элемент списка на новый элемент
tmp1->next = new_item;
TMP1
-------------------- --------------------
\ | | | \ | | |
-----| INFO | NEXT |------| INFO | NEXT |----
/ | | | / | | | |
-------------------- -------------------- |
-----------------------------------------
------------ | --------------------
| | | \ | | | \
| new_item | ------| INFO | NEXT |------ NULL
| | / | | | /
------------ --------------------
Удалить элемент
Чтобы удалить элемент, я прокручиваю список, пока не найду этот элемент, и при прокрутке списка я сохраняю указатель на текущий элемент и указатель на предыдущий элемент.
Как только я нахожу элемент, я обновляю указатель предыдущего элемента с указателем элемента, следующего за удаляемым. Затем мы освобождаем память элемента, который хотим удалить.
Сначала мы находим элемент для удаления
for(tmp1 = NULL, tmp2 = t; tmp2->next && tmp2->info != val; tmp1 = tmp2, tmp2 = tmp2->next);
TMP1 TMP2 (TO DELETE)
--------------- --------------- ---------------
\ | | | \ | | | \ | | | \
----| INFO | NEXT |----| INFO | NEXT |----| INFO | NEXT |----
/ | | | / | | | / | | | /
--------------- --------------- ---------------
Мы обновляем указатель
tmp1->next = tmp2->next;
free (tmp2);
TMP1 TMP2 (TO DELETE)
--------------- --------------- ---------------
\ | | | | | | \ | | | \
----| INFO | NEXT |-- | INFO | NEXT | ---| INFO | NEXT |----
/ | | | | | | | |/ | | | /
--------------- | --------------- | ---------------
--------------------
Освободить память
free (tmp2);
TMP1
--------------- ---------------
\ | | | \ | | | \
----| INFO | NEXT |-- ---| INFO | NEXT |----
/ | | | | |/ | | | /
--------------- | | ---------------
--------------------
Это основные методы управления списком в C.
Я помещаю здесь полный код, а также основной, чтобы попытаться выполнить код.
Compile: gcc -include list.c main.c Run: ./a.out
Если у вас возникли проблемы или вы решили их каким-либо другим способом, не стесняйтесь, пишите в комментариях!
Чтобы получить доступ к неограниченному количеству историй, вы также можете зарегистрироваться и стать участником Medium всего за 5 долларов США. Если вы зарегистрируетесь по моей ссылке, я получу небольшую комиссию.
