Лекция № 8
Тема: «Линейный
однонаправленный список: основные понятия и операции»
План лекции
1.
Списки. Основные свойства.
2.
Работа со списками
1. Списки. Основные свойства
Список
– линейная
последовательность элементов, каждый из которых содержит указатели (ссылается)
на своих соседей.
Основные релятивистские свойства списка:
элемент списка доступен в программе
через указатель. «Смысл» этого указателя отражает функциональное назначение
элемента списка в программе: первый, последний, текущий, предыдущий, новый и
т.п. Между указателем и элементом списка имеется такая же взаимосвязь, как
между индексом в массиве и элементом массива;
в программе список задается
посредством заголовка – указателя на первый элемент
списка;
порядок следования элементов
определяется последовательностью связей между элементами. Изменение порядка
следования элементов (вставка, удаление) осуществляются изменением
переустановкой указателей на соседние элементы.
список является структурой данных с
последовательным доступом. Для получения n-го по счету элемента необходимо последовательно
пройти по цепочке от элемента, на который имеется указатель (например, от
заголовка);
список удобен для использования именно
как динамическая структура
данных: элементы списка обычно создаются как динамические переменные, а связи
между ними устанавливаются программно (динамически);
список обладает свойством локальности изменений: при вставке/удалении элемента изменения касаются только
текущего и его соседей. Вспомним массив: при вставке/удалении его элементов
происходит физическое перемещение (сдвиг) всех элементов от текущего до конца.
Отсюда следует, что преимущества списков проявляются в
таких структурах данных, где операции изменения порядка превалируют над
операциями доступа и поиска.
Повторим все то же самое, но уже в терминах языка
программирования. Начнем с элемента списка. Он является составной
(структурированной) переменной, содержащей собственно хранимые данные и
указатели на соседей:
struct spisok // определение структурированного типа
{
int value; // значение элемента (хранимые данные)
spisok *next; //
единственный указатель или
spisok *next,*prev; // два указателя или
Переменная такого типа может содержать один, два и большее
количество указателей на аналогичные переменные. Но это еще не список, а описание
его составляющих (элементов) как типа данных. Из него следует только, что
каждый из них ссылается на аналогичные элементы. Никак нельзя определить
ни количества таких переменных в структуре данных, ни характера связей между
ними (последовательный, циклический, произвольный). Следовательно, конкретный
тип структуры данных (линейный список, дерево, граф) зависит от функций,
которые с ней работают. Значит, структура данных «зашита» не столько в этом
определении, сколько в алгоритмах, работающих с этим типом.
Списковые структуры данных обычно являются
динамическими по двум причинам:
сами переменные таких структур
создаются как динамические переменные, то есть количество их может быть
произвольным;
количество связей между
переменными и их характер также определяются динамически в процессе работы
программы.
В зависимости от связей списки бывают следующих видов:
односвязные - каждый элемент
списка имеет указатель на следующий;
двусвязные - каждый элемент списка имеет
указатель на следующий и на предыдущий элементы;
циклические - первый и последний
элементы списка ссылаются друг на друга и цепочка представляет собой кольцо.
Отсюда же следует, что «обычные» (разомкнутые) списки имеют
в качестве ограничителя последовательности NULL-указатель. Соответственно, возможет случай пустого списка,
в котором заголовок - указатель на первый элемент также содержит значение NULL.
Оставим пока за кадром вопрос, а как же создаются списки.
Ибо в динамической структуре данных мы попадаем в замкнутый круг: чтобы
работать со структурой данных, необходимо ее создать, а при создании нужно
знать технологические приемы работы с ней.
2. Работа со списками
Итак, положим, что список существует. Работа со списками
осуществляется исключительно через указатели. Каждый из них может перемещаться
по списку (переустанавливаться с элемента на элемент), приобретая одну из
смысловых интерпретаций – указатель на первый, последний, текущий, предыдущий,
новый и т.п. элементы списка. Здесь уместной является аналогия с
массивом и индексом в нем, но при условии, что индекс меняется линейно, а не
произвольно, а текущее количество заполненных элементов в массиве задано
отдельной переменной. В результате получим следующие выражения, определяющие
базовые действия со списком.
|
|
Список |
|
|
Определение |
struct spisok
{int val; spisok *next, *prev;
}; |
int A[100]; int n; |
|
Пустой список |
spisok *head=NULL; |
n=0; |
|
Первый |
spisok *p; p= head; |
Int i=0; |
|
Следующий |
p->next |
i+1 |
|
Предыдущий |
p->prev |
i-1 |
|
К следующему |
p=p->next |
i++ |
|
К предыдущему |
p=p->prev |
i-- |
|
Просмотр |
for (p= head; p!=NULL; p=p->next) …p->val… |
for (i=0; i<n; i++) …A[i]… |
|
Проверка на последний |
p->next ==NULL |
i==n-1 |
|
К последнему |
for (p= head; p->next!=NULL; p=p->next); |
i=n-1 |
|
Новый |
spisok *q = new list; q->val = v; |
int v; |
|
Включить последним |
for (p= head; p->next!=NULL; p=p->next); q->next=NULL; p->next=q; |
A[n++]=v; |
|
Включить первым |
q->next=head; head=q; |
for (i=n; i>0; i--) A[i]=A[i-1]; A[0]=v; |
Рассмотрим на примере создание списка, его просмотр и
удаление.
#include <iostream.h>
#include <iomanip.h>
#include <ctime>
//структура, содержащая хранимые данные и указатель на
следующий элемент
struct spisok
{
int value; //значение
spisok *next; //указатель
на переменную типа структура spisok
};
int main()
{
system("chcp 1251>nul");
//создание списка
spisok *head=NULL; //создание пустого списка
int i,n;
cout<<"Введите количество элементов
списка"<<endl;
cin>>n;
for(i=1;
i<=n; i++)
{
spisok *tmp=new spisok; //создание
нового элемента типа spisok
cout<<"Введите элемент списка ";
cin>>tmp->value; //запись нового
значения
cout<<endl;
tmp->next=head; //введенный
элемент сделать первым в списке
head=tmp; //первым
элементом стал введенный элемент tmp
}
//просмотр списка
spisok *tmp=head;
//определяем указатель, который изначально
равен адресу начала списка
while (tmp!=NULL) //пока не встретит пустое значение, т.е. последний
элемент
{
cout<<tmp->value<<"
"; //выведет значение элемента tmp->value из списка
tmp=tmp->next;
//переходим
на следующий элемент
}
//добавить в начало списка, т.е. перед головой
tmp=new spisok; //создание нового элемента типа spisok
cout<<"Введите новое значение" ;
cin>>tmp->value; //запись нового значения
tmp->next=head; //введенный
элемент сделать первым в списке
head=tmp; //меняем голову списка
//запомним последний элемент списка
tmp=head; //ставим указатель в начало списка
list *last; //новая переменная - будет содержать последний элемент
while (tmp!=NULL) //пока не встретит пустое значение, т.е. последний
элемент
{
/*
переменная last будет хранить все элементы по очереди
– сначала первый, затем второй и т.д. и когда произойдет выход из цикла, будет
содержать последний элемент */
last=tmp;
tmp=tmp->next; //переходим на следующий элемент, двигаясь по списку
}
//выводим последний
элемент для проверки правильности работы кода
cout<<"Последний
элемент = "<<last->value;
//добавление в конец списка
tmp=new spisok; //выделяем
память под новый элемент
cout<<"Введите новое значение в конец списка" ;
cin>>tmp->value; //считываем новое значение
last->next=tmp; //ставим указатель последнего элемента списка на новый
элемент
tmp->next=NULL;
//новый
элемент указывает на NULL
//удаление из начала списка
//во временную переменную
запишем элемент, следующий за головой списка, т.е. второй элемент
tmp=head->next;
delete head; //удаляем голову списка
head=tmp; //второй элемент спсика делаем
головой
//запомним последний и предпоследний элементы
tmp=head; //становимся на начало списка
spisok *plast; //объявляем новую переменную для хранения предпоследнего
элемента
while (tmp->next !=NULL)
{
plast=tmp; //будет хранить предпоследний элемент
last=tmp->next; //будет хранить последний элемент
tmp=tmp->next; //переходим
на следующий элемент
}
//удаление из конца списка
plast->next =NULL; //ставим указатель предпоследнего элемента на NULL
delete last; //удаляем
последний элемент
//нахождение максимального значения
int max=head->value; // максимальным элементом сделать первый элемент списка
tmp=head;
while(tmp!=NULL)
{
if (tmp->value
> max)
max=tmp->value;
tmp=tmp->next;
}
cout<<"Максимальный элемент = "<<max<<endl;
//удаление списка из памяти
while (head!=NULL) //пока не
встретится пустой адрес, т.е. последний элемент
{
//временная переменная для хранения адреса
следующего элемента
spisok *tmp=head->next;
delete head; //освобождаем
адрес, обозначающий начало
head=tmp; //меняем адрес
головы на следующий
}
system("pause");
return 0;
}
Контрольные вопросы
1.
Дайте понятие списка.
2.
Что такое заголовок списка?
3.
Что означает «структура данных с последовательным доступом»?
4.
Раскройте понятие локальности изменений
для списков.
5.
Как определить структурированный тип для списка?
6.
Как создать пустой список?
7.
Как обратиться к следующему элементу списка?
8.
Как перейти к следующему элементу списка?
9.
Как создать и удалить список?
10.
Как просмотреть список и вывести его элементы на экран?
11.
Как выполнить поиск в списке?