Реализация связных списков на языке C
Связанные списки — это способ хранения данных со структурами, так что программист может автоматически создавать новое место для хранения данных всякий раз, когда это необходимо. В частности, программист пишет определение структуры, которое содержит переменные, содержащие информацию о чем-то, и которое имеет указатель на структуру того же типа (это должен быть указатель — в противном случае каждый раз, когда элемент был создан, он будет создавать новый элемент бесконечно). Каждая из этих отдельных структур или классов в списке обычно называется узлом или элементом списка.
Один из способов визуализировать связанный список-это как если бы это был поезд. Программист всегда хранит первый узел списка в указателе, к которому он не потеряет доступ. Это будет паровоз поезда. Сам указатель является соединителем между вагонами поезда. Каждый раз, когда поезд добавляет вагон, он использует разъемы, чтобы добавить новый вагон. Это похоже на то, как программист использует malloc для создания указателя на новую структуру.
В памяти связанный список часто описывается так:
———- ———-
— Data — — Data —
———- ———-
— Pointer — — — — > — Pointer-
———- ———-
Представление не совсем точное во всех деталях, но для наших целей этого будет достаточно. Каждый из больших блоков-это структура, имеющая указатель на другой. Помните, что указатель хранит только место памяти чего-то — это не сама вещь — поэтому стрелка указывает на следующую структуру.
В конце списка нет ничего, на что указывал бы указатель, поэтому он ни на что не указывает. Это должен быть нулевой указатель или фиктивный узел, чтобы предотвратить случайное указание узла на случайное место в памяти (что очень плохо).
Связный список
Этот связанный список имеет четыре узла данных. Каждый узел имеет целое число и ссылку на следующий узел. Head всегда указывает на первый узел, а последний узел всегда указывает на NULL. Мы можем пройти список от головы до последнего узла, но не в обратном направлении. Вот почему он называется односвязным списком.
Структура данных для односвязного списка
Мы обсудим основной строительный блок связанного списка.
struct node{
intval;
struct node * next;
};structnode *head = NULL;
Вот еще один вариант того, как должна выглядеть структура узла:
#include <stdlib.h>
struct node {
int x;
struct node *next;
};intmain()
{
/* Это будет неизменный первый узел */
structnode *root;/* Теперь root указывает на структуру узла */
root = (struct node *) malloc( sizeof(struct node) );/* Корневая точка узла имеет свой следующий указатель, равный нулевому
набору указателей */
root->next = 0;
/* С помощью оператора -> вы можете изменить то, что узел,
указатель (в данном случае корень) указывает на. */
root->x = 5;
}
Это пока не очень полезно для того, чтобы что-то делать. Необходимо понять, как пройти через связанный список, прежде чем он действительно станет полезным. Это позволит нам сохранить некоторые данные в списке и позже найти их, не зная точно, где они находятся.
Вспомните поезд. Давайте представим себе кондуктора, который может войти в поезд только через первый вагон и может пройти через поезд вниз по линии до тех пор, пока соединитель соединяется с другим вагоном. Именно так программа будет пересекать связанный список.
Проводник будет указателем на узел, и он сначала укажет на корень, а затем, если указатель корня на следующий узел указывает на что-то, «проводник» (не технический термин) будет установлен, чтобы указать на следующий узел.
Таким образом, список может быть пройден. Теперь, пока есть указатель на что-то, обход будет продолжаться. Как только он достигнет нулевого указателя (или фиктивного узла), то есть так как больше нет узлов (вагонов поезда), он окажется в конце списка, и при желании можно будет добавить новый узел.
Вот как это выглядит:
#include<stdio.h>
#include<stdlib.h>struct node{
int x;
struct node*next;
};intmain()
{
/* Это не изменится, иначе мы потеряем список в памяти */
structnode *root;
/* Это будет указывать на каждый узел по мере прохождения списка */
struct node *проводник;root = malloc( sizeof(structnode) );
root->next = 0;
root->x = 12;
conductor=root;
if (conductor != 0 ) {
while (conductor->next != 0)
{
conductor = conductor->next;
}
}
/* Создает узел в конце списка */
conductor->next = malloc( sizeof(struct node) );conductor = conductor->next;
if (conductor = = 0 )
{
printf( «Недостаточно памяти» );
return 0;
}
/* инициализация новой памяти */
conductor->next = 0;
conductor->x = 42;return 0;
}
Это основной код для обхода списка. Оператор if гарантирует, что память была правильно выделена перед обходом списка. Если условие в операторе if имеет значение true, то можно попытаться получить доступ к узлу, на который указывает проводник. Цикл while будет продолжаться до тех пор, пока в следующем есть еще один указатель. Проводник просто движется вперед. Он изменяет то, на что указывает, получая адрес проводника->далее.
Наконец, код в конце может быть использован для добавления нового узла в конец. Как только цикл while будет завершен, проводник укажет на последний узел в массиве. (Помните, проводник поезда будет двигаться дальше, пока не останется ничего, чтобы двигаться дальше?Он работает точно так же в цикле while.) Поэтому conductor->next имеет значение null, поэтому можно выделить новую область памяти для его указания (если бы она не была НУЛЕВОЙ, то хранение чего-то еще в указателе привело бы к потере памяти, на которую он указывал).
Когда мы выделяем память, мы делаем быструю проверку, чтобы убедиться, что у нас нет недостатка в памяти, а затем проводник пересекает еще один элемент (например, проводник поезда, переходящий к недавно добавленному вагону) и удостоверяется, что его указатель на следующий установлен в 0, так что список имеет конец. 0 функционирует как точка; это означает, что больше нет запредельного. Наконец, новый узел имеет свое значение x. (Он может быть установлен с помощью пользовательского ввода.Я просто написал в качестве примера «=42».)
Для печати связанного списка функция обхода почти такая же. В нашем первом примере необходимо убедиться, что последний элемент печатается после завершения цикла while. (Посмотрите, можете ли вы придумать лучший способ, прежде чем читать второй пример кода.)
Например:
conductor =root;
if (conductor != 0 ) { /* Удостоверяется, что есть место для начала */
while (conductor->next != 0 ) {
printf( «%d\n», conductor->x );
conductor = conductor->next;
}
printf( «%d\n», conductor->x );
}
Конечный вывод необходим, потому что цикл while не будет выполняться, как только он достигнет последнего узла, но все равно будет необходимо вывести содержимое следующего узла. Следовательно, последний вывод имеет дело с этим.
Мы можем избежать этой избыточности, позволив проводнику выйти из задней части поезда. Плохо для проводника (если бы это был реальный человек), но код проще, так как он также позволяет нам удалить начальную проверку на null (если root равен null, то проводник будет немедленно установлен в null и цикл никогда не начнется):
conductor =root;
while (conductor != NULL ) {
printf( «%d\n», conductor->x );
conductor = conductor->next;
}
Узел связанного списка определяется структурой C (struct), которая состоит из двух частей:
- значения или данные
- ссылки.
Мы определили часть значения как целое число, но это может быть что угодно. Значение может быть очень сложной структурой данных. Ссылка (далее) — это указатель, указывающий на ту же структуру данных. Он содержит указатель следующего узла, ожидаемый для последнего узла. Последний узел следующий указатель всегда равен нулю.
Головной указатель всегда указывает на первый узел. Изначально ему присваивается значение NULL, но он будет указывать на первый узел, если в связанном списке есть узлы. Вот программа на языке Си, которая создает и печатает связанный список.
#include<stdio.h>
#include <stdlib.h>struct node{
intval;
struct node * next;
};/*Печать связанного списка*/
voidprint_list(struct node *head)
{
printf(«H->»);while(head)
{
printf(«%d->», head->val);
head = head->next;
}printf(«|||\n»);
}/*Вставить элемент в начало списка*/
voidinsert_front(struct node **head, int value)
{
struct node * new_node = NULL;/*Выделение памяти для нового узла*/
new_node = (struct node *)malloc(sizeof(struct node));if (new_node == NULL)
{
printf(«Не удалось вставить элемент.Недостаточно памяти»);
}new_node->val = value;
/*Указание нового узла на то место, на которое в данный момент указывает head*/
new_node->next = *head;/*Указывающая головка на новый узел.*/
*head = new_node;
}void main()
{
int count = 0, i, val;
struct node * head = NULL;printf(«Введите количество элементов: «);
scanf(«%d», &count);for (i = 0; i < count; i++)
{
printf(«Введите %dthэлемент: «, i);
scanf(«%d», &val);
insert_front(&head, val);
}printf(«Связный список: «);
print_list(head);
}
Эта программа имеет две важные функции.
insert_front(): Он создает новый узел и вставляет его в начало списка. Эта функция принимает в качестве входных данных заголовок списка и значение. Сначала он создает новый узел и устанавливает входное значение для этого узла. Затем он указывает новому узлу следующий указатель туда, куда указывает head. Голова укажет на новый узел.
print_list(): Он печатает узлы связанного списка. Он принимает голову в качестве входных данных и пересекает список. На каждой итерации он выводит значение текущего узла.
Функция main() принимает целые числа в качестве входных данных и вставляет их в связанный список с помощью функции insert_front (). В конце он печатает весь список с помощью функции print_list ().
Вот результат:
Введите количество элементов: 4
Введите 0-й элемент: 41
Введите 1-й элемент: 53
Введите 2-й элемент: 56
Введите 3-й элемент: 76
Связанный список: H->76->56->53->41->|||
