Что такое линейный список

Что такое линейный список

«Щас по списку и пойдем. »

Реальное многообразие структур данных базируется всего на двух основных способах получения адреса хранимого элемента: вычисление (массив) и хранение (указатель). До сих пор основной компонентой структуры данных являлся массив (обычный массив, массив указателей). Если же попытаться построить структуру данных, исходя только из указателей, то получается цепочка (последовательность) элементов, содержащих указатели друг на друга. В простейшем случае она может быть линейной (список), в более сложных случаях – ветвящейся (деревья, графы). Итак, список – линейная последовательность элементов, каждый из которых содержит указатели (ссылается) на своих соседей.

рис. 63-1. Списковая структура

Сразу же отметим основную особенность: физическое размещение в памяти элементов списка не имеет никакого значения, все определяется наличием ссылок на него в других элементах и извне. У массива всегда есть «начало». У списка по определению отсутствует фиксированная привязка к памяти. Перечислим основные релятивистские свойства списка :

· элемент списка доступен в программе через указатель. «Смысл» этого указателя отражает функциональное назначение элемента списка в программе: первый, последний, текущий, предыдущий, новый и т.п.. Между указателем и элементом списка имеется такая же взаимосвязь, как между индексом в массиве и элементом массива;

· в программе список задается посредством заголовка – указателя на первый элемент списка;

· порядок следования элементов определяется последовательностью связей между элементами. Изменение порядка следования элементов (вставка, удаление) осуществляются изменением переустановкой указателей на соседние элементы.

· список удобен для использования именно как динамическая структура данных: элементы списка обычно создаются как динамические переменные, а связи между ними устанавливаются программно (динамически);

Отсюда следует, что преимущества списков проявляются в таких структурах данных, где операции изменения порядка превалируют над операциями доступа и поиска.

Определение списка и работа с ним

Повторим все то же самое, но уже в терминах языка программирования. Начнем с элемента списка. Он является составной (структурированной) переменной, содержащей собственно хранимые данные и указатели на соседей:

struct elem // определение структурированного типа

elem *next; // единственный указатель или

elem *next,*pre v ; // два указателя или

elem *links[10]; // ограниченное количество указателей (не больше 10) или

elem **plinks; // произвольное количество указателей (внешний МУ)

Переменная такого типа может содержать одну, две, не более 10 и произвольное (динамический массив) количество указателей на аналогичные переменные. Но это еще не список, а описание его составляющих (элементов) как типа данных. Из него следует только, что каждый из них ссылается на аналогичные элементы. Никак нельзя определить ни количества таких переменных в структуре данных, ни характера связей между ними (последовательный, циклический, произвольный). Следовательно, конкретный тип структуры данных (линейный список, дерево, граф) зависит от функций, которые с ней работают. Значит, структура данных «зашита» не столько в этом определении, сколько в алгоритмах, работающих с этим типом.

Списковые структуры данных обычно являются динамическими по двум причинам:

· сами переменные таких структур создаются как динамические переменные, то есть количество их может быть произвольным;

· количество связей между переменными и их характер также определяются динамически в процессе работы программы.

В зависимости от связей списки бывают следующих видов:

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

Источник

Динамические структуры данных: однонаправленные и двунаправленные списки

Цель лекции: изучить понятия, классификацию и объявление списков, особенности доступа к данным и работу с памятью при использовании однонаправленных и двунаправленных списков, научиться решать задачи с использованием списков на языке C++.

Понятие списка хорошо известно из жизненных примеров: список студентов учебной группы, список призёров олимпиады, список (перечень) документов для представления в приёмную комиссию, список почтовой рассылки, список литературы для самостоятельного чтения и т.п.

В основном они отличаются видом взаимосвязи элементов и/или допустимыми операциями.

Однонаправленные (односвязные) списки

Описание простейшего элемента такого списка выглядит следующим образом:

struct имя_типа поле ; адресное поле ; >;

где информационное поле – это поле любого, ранее объявленного или стандартного, типа;

адресное поле – это указатель на объект того же типа, что и определяемая структура, в него записывается адрес следующего элемента списка.

Информационных полей может быть несколько.

Основными операциями, осуществляемыми с однонаправленными списками, являются:

Особое внимание следует обратить на то, что при выполнении любых операций с линейным однонаправленным списком необходимо обеспечивать позиционирование какого-либо указателя на первый элемент. В противном случае часть или весь список будет недоступен.

Рассмотрим подробнее каждую из приведенных операций.

Для описания алгоритмов этих основных операций используется следующее объявление:

Создание однонаправленного списка

Печать (просмотр) однонаправленного списка

Источник

Реализация односвязного списка на c++

Эта картинка демонстрирует, как будет выглядеть односвязный список.

Реализация узла

Значение, которое будет задавать пользователь

Указатель на следующий элемент (по умолчанию nullptr)

Реализация односвязного списка

Указатель на первый узел

Указатель на последний узел

Функция проверки наличия узлов в списке

Функция добавления элемента в конец списка

Функция печати всего списка

Функция поиска узла в списке по заданному значению

Функция удаления первого узла

Функция удаления последнего узла

Функция удаления узла по заданному значению значению

Функция обращения к узлу по индексу (дополнительная функция)

Реализация 1-3 пункта

Функция проверки наличия узлов в списке

Функция добавления элемента в конец списка

Здесь надо рассмотреть два случая:

В обоих случаях надо создать сам узел со значением, которое мы передали в эту функцию.

Первый случай:

Здесь нам как раз пригодиться функция проверки наличия узлов. Если список пустой, тогда мы присваиваем указателю на первый узел и последний узел указатель на новый узел и выходим из функции.

Второй случай:

Нам уже не нужно проверка наличия узлов в списке, так как если первый случай не происходит, то в списке есть узлы. Раз мы добавляем в конец, надо указать, что новый узел стоит после последнего узла. Затем мы меняем значения указателя last.

Теперь в список можно добавлять элементы.

Функция печати всего списка

Тест уже написанных функций

Код который мы написали:

Функция поиска узла в списке по заданному значению

Также делаем проверку is_empty() и создаём указатель p на первый узел

Обходим список, пока указатель p не пустой и пока значение узла p не равно заданному значению. После цикла возвращаем наш узел

Функция удаления первого узла

Функция удаления последнего узла

Конец списка одновременно и начало

Когда размер списка больше одного

Первый случай:

Сравниваем указатель на первый узел и указатель на последний узел, если они равны, то вызываем функцию удаления первого узла.

Второй случай:

Функция удаления узла по заданному значению значению

Делаем проверку is_empty(). И рассматриваем уже три случая:

Узел, который нам нужен, равен первому

Узел, который нам нужен, равен последнему

Когда не первый и не второй случаи

Первый случай:

Сравниваем значение первого узла с заданным значением, если значения совпадают, тогда вызываем функцию удаления первого узла.

Второй случай:

Сравниваем значение последнего узла с заданным значением, если значения совпадают, тогда вызываем функцию удаления последнего узла.

Третий случай:

Функция обращения к узлу по индексу

Для этой функции надо перегрузить оператор []

Тест программы

Заключение

Вот Вы и научились реализовывать односвязный список, и, надеюсь, стали лучше его понимать.

Источник

Односвязный линейный список

Каждый узел однонаправленного (односвязного) линейного списка (ОЛС) содержит одно поле указателя на следующий узел. Поле указателя последнего узла содержит нулевое значение (указывает на NULL).

Узел ОЛС можно представить в виде структуры

Основные действия, производимые над элементами ОЛС:

Инициализация ОЛС

Инициализация списка предназначена для создания корневого узла списка, у которого поле указателя на следующий элемент содержит нулевое значение.

Добавление узла в ОЛС

Функция добавления узла в список принимает два аргумента:

Процедуру добавления узла можно отобразить следующей схемой:

Добавление узла в ОЛС включает в себя следующие этапы:

Таким образом, функция добавления узла в ОЛС имеет вид:

Возвращаемым значением функции является адрес добавленного узла.

Удаление узла ОЛС

В качестве аргументов функции удаления элемента ОЛС передаются указатель на удаляемый узел, а также указатель на корень списка.
Функция возвращает указатель на узел, следующий за удаляемым.

Удаление узла может быть представлено следующей схемой:

Удаление узла ОЛС включает в себя следующие этапы:

Удаление корня списка

Функция удаления корня списка в качестве аргумента получает указатель на текущий корень списка. Возвращаемым значением будет новый корень списка — тот узел, на который указывает удаляемый корень.

Вывод элементов списка

В качестве аргумента в функцию вывода элементов передается указатель на корень списка.
Функция осуществляет последовательный обход всех узлов с выводом их значений.

Взаимообмен узлов ОЛС

В качестве аргументов функция взаимообмена ОЛС принимает два указателя на обмениваемые узлы, а также указатель на корень списка. Функция возвращает адрес корневого элемента списка.

Взаимообмен узлов списка осуществляется путем переустановки указателей. Для этого необходимо определить предшествующий и последующий узлы для каждого заменяемого. При этом возможны две ситуации:

При замене соседних узлов переустановка указателей выглядит следующим образом:

При замене узлов, не являющихся соседними переустановка указателей выглядит следующим образом:

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

Функция взаимообмена узлов списка выглядит следующим образом:

Комментариев к записи: 77

using namespace std;
struct NODE <
char value;
struct NODE* next;
>;

struct DbCircleList <
size_t size;
struct NODE* head;
>;

void addNode(DbCircleList* list, char elem)
<
NODE* newElem = new NODE;
newElem->value = elem;
if (list->size == 0)
<
list->head = newElem;
list->head->next = list->head;
>
else
<
struct NODE* temp;
temp = list->head;
list->head = newElem;
newElem->next = temp;
>
++list->size;
>

void printList(DbCircleList* list)
<
NODE* tmp = list->head;
cout «List values: » endl;
for ( int i = 0; i size; ++i)
<
cout «Value: » tmp->value endl;
tmp = tmp->next;
>
>

int main()
<
DbCircleList* list = new DbCircleList;
list->size = 0;
list->head = NULL ;
DbCircleList* list1 = new DbCircleList;
list1->size = 0;
list1->head = NULL ;
DbCircleList* list2 = new DbCircleList;
list2->size = 0;
list2->head = NULL ;

addNode(list, ‘b’);
addNode(list, ‘b’);
addNode(list, ‘3’);
addNode(list, ‘c’);
addNode(list, ‘3’);
addNode(list, ‘7’);

delete list;
delete list1;
delete list2;
return 0;
>

#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#include

struct book
<
char name[30];
char author[30];
int num_page;
int year;
char style[30];
struct book* next;
>;
struct book* poperedbook, * element, * pershiy, * novii, * ostan;

void Stvorutu( void )
<
element = ( struct book*)malloc( sizeof ( struct book));
pershiy = element;

do
<
poperedbook = element;

ostan = poperedbook;
poperedbook->next = NULL ;
>

void hood( void )
<
element = pershiy;

int main()
<
SetConsoleCP(1251);
SetConsoleOutputCP(1251);

struct list <
int ptr;
list *next;
>;

void input_list(list *&first, int n) <
first = new list;
cinn >> first->ptr;
list *q = first;
for ( int i = 0; i next = new list;
q = q->next;
cin >> q->ptr;
>
q->next = 0;
>
void print_list(list *q) <
while (q) <
cout q->ptr » » ;
q = q->next;
>
cout endl;
>

void razbienie_list(list *&first) <
list *q = first;
list *chet = new list;
list *nechet = new list;
list *q1 = chet;
list *q2 = nechet;
list *w1 = q1;
list *w2 = q2;
while (p) <
if (q->ptr % 2) <
q2->ptr = p->ptr;
q2->next = new list;
w2 = q2;
q2 = q2->next;
>
else <
q1->ptr = p->ptr;
q1->next = new list;
q1 = q1;
q1 = q1->next;
>;
q = q->next;
>
w1->next = 0;
w2->next = 0;
>

int main() <
list *first = 0;
int n = 5;
input_list(first, n);
print_list(first);
razbienie_list(first);
print_list(first);
return 0;
>

int main()
<
char name[maxSize] = <'\0'>;
char type[maxSize] = <'\0'>;
double MaximumHeight;
double lifespan;

Wood* Head = nullptr;
int n;

//Вводим число деревьев, которые будем хранить в массиве
cout «Number of Wood = » ;
cin >> n;
//Вводим информацию о всех деревьях с помощью реализованной функции
for ( int i = 0; i // удаление элемента
cout » deleted Woods = » ;
cin >> lifespan;
DeleteWood(Head, WoodSearch(Head, lifespan)); // ЗДЕСЬ ОШИБКА
PrintWood(Head);

#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#include
struct list
<
int field;
struct list* ptr;
>;
// Инициализация списка (ОЛС)

struct list* init( int a)
<
struct list* head = ( struct list*)malloc( sizeof ( struct list));
head->field = a;
head->ptr = NULL ;
return (head);
>
// Добавление элемента (возвращает добавленный элемент) (ОЛС)
struct list* addelem( struct list* lst, int number)
<

struct list* temp, * p;
temp = ( struct list*)malloc( sizeof ( struct list)); // выделение памяти под узел списка
p = lst->ptr; // временное сохранение указателя
lst->ptr = temp; // предыдущий узел указывает на создаваемый
temp->field = number; // сохранение поля данных добавляемого узла
temp->ptr = p; // созданный узел указывает на следующий элемент
return (temp);
>

// Удаление корня списка (возвращает новый корень) (ОЛС)
struct list* deletehead( struct list* root)
<
struct list* temp;
temp = root->ptr;
free(root);
return (temp); // новый корень списка
>

struct list* add( struct list* head, int data)
<
struct list* temp, * p;
p = head->ptr;
temp = ( struct list*)malloc( sizeof ( struct list));
head->ptr = temp;
temp->field = data;
temp->ptr = p;
return (temp);
>

struct list* t1 = t->ptr;
while (t1)
<
if (t1->field == v)
<
t->ptr = t1->ptr;
free(t1);
return ;
>
t = t1;
t1 = t1->ptr;
>
>

void sub( struct list* a, struct list* b)
<
struct list* p2;
for ( struct list* p2 = b; p2; p2 = p2->ptr)
del(a, p2->field);
/* struct list* p2;
p2 = b;
while (p2)
<
del(a, p2->field);
p2 = p2->ptr;
>*/
/* struct list* p1, * p2;
p1 = a;
p2 = b;
while (p1)
<
while (p2)
<
if (p1->field == p2->field)
deletelem(p1, p1->field);
p2 = p2->ptr;
>
p1 = p1->ptr;
>*/
>
int main()
<
setlocale(LC_ALL, «Russian» );

/* struct list* p1 = ( struct list*)malloc( sizeof ( struct list));
struct list* p2 = ( struct list*)malloc( sizeof ( struct list));

p1 = init(5);
add(p1, 6);
add(p1, 9);
p2 = init(6);
add(p2, 7);

Источник

Связные списки

Связный список является простейшим типом данных динамической структуры, состоящей из элементов ( узлов, nodes ). Каждый узел включает в себя в классическом варианте два поля:

Элементы связанного списка можно помещать и исключать произвольным образом.

Классификация списков

По количеству полей указателей различают однонаправленный (односвязный) и двунаправленный (двусвязный) списки.

По способу связи элементов различают линейные и циклические списки.

Виды списков

Таким образом, различают 4 основных вида списков.

Сравнение массивов и связных списков

Односвязный линейный список

Каждый узел однонаправленного (односвязного) линейного списка (ОЛС) содержит одно поле указателя на следующий узел. Поле указателя последнего узла содержит нулевое значение (указывает на NULL).

Узел ОЛС можно представить в виде структуры

1. Инициализация односвязного линейного списка

Инициализация списка предназначена для создания корневого узла списка, у которого поле указателя на следующий элемент содержит нулевое значение.

2. Добавление узла в односвязный линейный список

Функция добавления узла в список принимает два аргумента:

Процедуру добавления узла можно отобразить следующей схемой:

Добавление узла в ОЛС включает в себя следующие этапы:

Таким образом, функция добавления узла в ОЛС имеет вид:

3. Вывод элементов списка

В качестве аргумента в функцию вывода элементов передается указатель на корень списка.
Функция осуществляет последовательный обход всех узлов с выводом их значений.

4. Поиск элемента списка

В качестве аргумента в функцию поиска элемента передается указатель на корень списка и значение, которое необходимо найти. В качестве возвращаемого значения получаем указатель на элемент списка с искомым значением.
Функция осуществляет последовательный обход всех узлов, сравнивая их значение с искомым, и останавливается на первом найденом элементе, возвращая указатель на него.

5. Удаление узла ОЛС

В качестве аргументов функции удаления элемента ОЛС передаются указатель на удаляемый узел, а также указатель на корень списка.
Функция возвращает указатель на узел, следующий за удаляемым.

Удаление узла может быть представлено следующей схемой:

Удаление узла ОЛС включает в себя следующие этапы:

Удаление корня списка

Взаимообмен узлов ОЛС

В качестве аргументов функция взаимообмена ОЛС принимает два указателя на обмениваемые узлы, а также указатель на корень списка. Функция возвращает адрес корневого элемента списка.

Взаимообмен узлов списка осуществляется путем переустановки указателей. Для этого необходимо определить предшествующий и последующий узлы для каждого заменяемого. При этом возможны две ситуации:

При замене соседних узлов переустановка указателей выглядит следующим образом:

При замене узлов, не являющихся соседними переустановка указателей выглядит следующим образом:

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

Функция взаимообмена узлов списка выглядит следующим образом:

Источник