Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

Лекция 9: связные списки.

Лекция 1: введение в программирование. | Лекция 2: представление данных в компьютере. | Часть 1: хранение данных в компьютере. | Часть 2: типы данных языка Си. | Часть 1: основные операторы и их приоритеты. | Часть 2: функции. | Лекция 5: Функция main, функции ввода-вывода, препроцессор. | Лекция 6: массивы и строки, библиотечные функции ввода-вывода. | Лекция 7: операторы выбора, безусловный переход, циклы. | Часть 3: динамическое программирование. |


Читайте также:
  1. Professional SPA Collection (Профессиональная СПА Коллекция).
  2. Виборчі (партійні) списки.
  3. Домашние задания по теме: « Фирма в рыночной экономике» (лекция № 2).
  4. Елементи форматування тексту. Списки. Таблиці.
  5. Крымская Натуральная Коллекция
  6. Крымская Натуральная Коллекция» не останавливается на достигнутом! Мы постоянно расширяем ассортимент наших продуктов.
  7. Лабораторная работа 3. Списки. Автофильтр, сортировка. Функции работы с датой и временем

Сейчас для хранения больших объёмов данных мы пользуемся динамическими массивами. Работа с ними очень проста, но не всегда эффективна. Если нам нужно удалить 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: бинарные деревья.

mybiblioteka.su - 2015-2024 год. (0.012 сек.)