Читайте также:
|
Сейчас для хранения больших объёмов данных мы пользуемся динамическими массивами. Работа с ними очень проста, но не всегда эффективна. Если нам нужно удалить j-тый элемент массива a длиной len, нужно выполнить код:
--len;
for(i=j; i<len; ++i) a[i]=a[i+1];
a=(int*)realloc(a, len);
Этот цикл совершит len-j присваиваний. Если операция удаления элемента встретится в каком-нибудь алгоритме внутри тела цикла, то время работы алгоритма будет пропорционально квадрату количества элементов массива, а если внутри двух циклов – то кубу. В общем случае, время работы алгоритма будет пропорционально количеству элементов массива в некоторой степени. Такие алгоритмы называются полиномиальными, и считаются быстрыми. Однако есть способы обрабатывать данные ещё быстрее.
Для хранения наборов значений, основная часть задач по обработке которых состоит в изменении не самих значений, а их взаимного расположения, хранят не в массивах, а в связных списках. Связным списком называется упорядоченный набор элементов, каждый из которых содержит в том или ином виде ссылку на другой элемент, считающийся "следующим" по отношению к данному. Также он может содержать ссылку на ещё один элемент, который считается "предыдущим". Главной особенностью связного списка является отсутствие прямых связей между элементами, не являющимися в описанной иерархии соседними. Списки, в которых каждый элемент связан только со следующим, называют односвязными, а те, в которых есть также связи с предыдущими – двусвязными. Список, не содержащий ни одного элемента, называется пустым. Первый элемент списка называется головой (head), а весь остальной список (в том числе пустой) – хвостом (tail).
Односвязный список в языке Си реализуется с помощью следующей структуры[33]:
typedef struct ONEWAY
{
void* data;
struct ONEWAY* next;
} oneway;
Поле data отвечает за данные, хранящиеся в списке. Это поле может иметь любой тип, но здесь рассматривается общий случай: безтиповый указатель. С помощью преобразований типов можно такую структуру использовать для обработки любого списка. Непосредственно в списке лучше всего хранить именно указатели на данные, кроме случаев, когда данные меньше указателя[34].
Поле next – это указатель на следующий элемент списка. В случае, если данный элемент является последним в списке, next указывает на NULL. Таким образом, расположение связного списка в памяти выглядит примерно следующим образом: 
При этом реальное расположение каждого элемента не имеет абсолютно никакого значения: они связаны только указателями.
Приведём несколько примеров работы с односвязными списками.
Для начала список надо создать. Ясно, что являясь полностью изменяемой структурой, список может лежать только в динамической памяти. Поэтому будем считать, что библиотека stdlib к нашей программе уже подключена, а тип oneway объявлен. В таком случае функция создания списка из len элементов будет выглядеть таким образом:
oneway* create(int len)
{
typeof(oneway*) head, current;
int i;
head=(oneway*)malloc(sizeof(oneway));
head->data=NULL;
current=head;
for(i=1; i<=len; ++i)
{
current->next=(oneway*)malloc(sizeof(oneway));
if(current->next) current=current->next; else break;
current->data=NULL;
}
current->next=NULL;
return head;
}
Поскольку проход по односвязному списку возможен только в одну сторону – вперёд – исключительную роль в нём играет его голова: только начиная проход с неё моно получить доступ к любому их элементов. Поэтому под указатель на голову выделяется отдельная переменная, а сама голова создаётся отдельно.
Также для работы со списком всегда нужен указатель на текущий элемент, ведь связи есть только между соседними элементами, и иных способов пройти по списку нет:
while(current->next) current=current->next;
При создании списка все указатели на данные заполняются нулями. Это действие не является обязательным, но существенно повышает безопасность работы: большинство функций, работающих с указателями, умеет обрабатывать ситуацию обращения к указателю NULL, но если в создаваемом указателе будет лежать мусор, обращение к нему вызовет зависание или аварийное завершение программы.
Поскольку переход по нулевому указателю невозможен, добавлена строка, обрабатывающая ситуацию невозможности выделить память:
if(current->next) current=current->next; else break;
После завершения создания списка в указатель next последнего его элемента записывается NULL, делая этот элемент последним не только реально, но и с точки зрения функций обработки списка.
Гораздо проще, чем с массивами выглядит операция добавления нового элемента в список после данного:
void add(oneway* current, void* data)
{
oneway *temp=current->next;
current->next=(oneway*)malloc(sizeof(oneway));
if(!(current->next)) return;
current->next->next=temp;
current->next->data=data;
}
Чтобы понять работу этой функции, нужно представить себе, как вставка элемента должна выглядеть в памяти. Для начала у нас есть элемент, после которого нужно вставить новый. Поскольку мы не знаем, что находится перед ним, его можно называть головой. Соответственно, последующие элементы хвостом: 
Нужно с одной стороны записать в next головы указатель на новый элемент, а с другой – сохранить указатель на хвост. Для этого создаём временную переменную, в которую записываем адрес хвоста:
Затем мы записываем в next созданного элемента адрес хвоста, а в его data – соответствующий аргумент функции:
Как видите, данная функция совершает всего 4 присваивания, против j-len в случае массива. На самом деле, стоило бы добавить в неё проверку, не равен ли current нулю, потому как в этом случае добавление элемента было бы невозможным. Но тогда лучше саму функцию сделать возвращающей указатель на голову. В таком случае добавление элемента в пустой список создавало бы сам список. Так что здесь для упрощения и наглядности приведён упрощённый и небезопасный вариант функции.
Поскольку список находится в динамической памяти, когда он становится ненужным, его надо удалить. После завершения программы вся выделенная ей динамическая память освобождается, однако злоупотреблять этим свойством не рекомендуется.
void wipe(oneway* head)
{
oneway *current=head;
while(current->next)
{
current=current->next;
free(head->data);
free(head);
head=current;
}
free(head->data);
free(head);
}
Односвязные списки просты в реализации, но их не очень удобно использовать: всегда надо хранить указатель на голову. Поэтому также применяются двусвязные списки. В двусвязном списке каждый элемент имеет указатель не только на следующий элемент, но и на предыдущий[35]:
typedef struct BIDIRECTIONAL
{
void* data;
struct BIDIRECTIONAL* next;
struct BIDIRECTIONAL* prev;
} bidirectional;
Благодаря этому, по двусвязному списку возможно двигаться в обе стороны, что сильно упрощает работу с ним. Достаточно иметь указатель на любой элемент списка, чтобы получить доступ к любому другому. У первого элемента на NULL указывает prev, а у последнего – next. Переход с произвольного элемента двусвязного списка на последний выглядит как:
while(current->next) current=current->next;
а на первый:
while(current->prev) current=current->prev;
Функция создания двусвязного списка будет выглядеть так:
bidirectional* create(int len)
{
bidirectional *current;
int i;
current=(bidirectional*)malloc(sizeof(bidirectional));
current->prev=NULL;
current->data=NULL;
for(i=1; i<=len; ++i)
{
current->next=(bidirectional*)malloc(sizeof(bidirectional));
if(current->next) current->next->prev=current; else break;
current->next->data=NULL;
current=current->next;
}
current->next=NULL;
while(current->prev) current=current->prev;
return current;
}
Отличие от односвязного в том, что в создаваемый элемент записывается также указатель на текущий. Также, поскольку можно легко найти голову списка, не требуется отдельный указатель на неё, она находится строкой
while(current->prev) current=current->prev;
Двусвязные списки проще обрабатывать: чтобы, например, удалить элемент достаточно иметь указатель только на него, тогда как в односвязном нужно знать ещё и указатель на предыдущий. Такая же ситуация и с обменом элементов. Поэтому двусвязные списки предпочтительнее односвязных.
Дата добавления: 2015-11-13; просмотров: 50 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Лекция 8: структуры и объединения. | | | Часть 2: бинарные деревья. |