|
…появляется необходимость
динамически выд5лять память, поэтому…
Список – базовая структура, позволяющая определить любую
структуру данных. Указатели вводятся в языки высокого уровня с целью
поддержания списковых структур. Элемент списка представляет собой объект,
содержащий информационное поле и 1 или несколько адресных полей,
предназначенных для связи с другими элементами списка. При отсутствии связи
адресное поле равно специальному значению указателя, гарантировано
ссылающемуся ни какой объект (NULL –
нулевой указатель).
Однонаправленный (односвязный) список
Элементом является структура, в число полей которой входит поле
адреса, в котором хранится ссылка на следующий элемент односвязного списка,
относят данную структуру хранения к связным, и поле данных, содержащее
информацию, предназначенную для хранения.
Связанный список определяется адресом начала (головы списка), конец
списка определяется элементом, в поле адреса которого хранится значение, не
ссылающееся ни на какую область памяти (NULL)
Создание связного списка.
Выделить память для хранения адреса головы;
Выделить память для хранения элементов списка;
Обнулить поле адреса;
Записать в поле данных содержащую информацию;
Сохранить адрес головы списка в переменной, хранящей ссылку на начало
списка.
Добавление элемента в конец списка.
Присвоить указателю адрес головы списка;
Проанализировать значение поля адреса. Пока оно не равно 0, присваивать
указателю значение поля адреса.
Создать элемент списка и записать его в поле адрес конца списка.
Просмотр связного списка.
создание списка
struct Node {
char word[40];
int count;
Node *next;
};
typedef Node *PNode;
создание узла
Pnode CreateNode ( char NewWord[] )
{
PNode NewNode = new Node;
strcpy(NewNode->word, NewWord);
NewNode->count = 1;
NewNode->next = NULL;
return NewNode;
}
доб узла в нач
void AddFirst(PNode NewNode)
{
NewNode->next = Head;
Head = NewNode;
}
Например, следующая процедура ищет в списке элемент, соответствующий заданному слову
(для которого поле word совпадает с заданной строкой NewWord), и возвращает его адрес или
NULL, если такого узла нет.
void Find (PNode Head, char NewWord[])
{
PNode q = Head;
while (q && strcmp(q->word, NewWord))
q = q->next;
return q;
}
доб после заданного
void AddAfter (PNode p, PNode NewNode)
{
NewNode->next = p->next;
p->next = NewNode;
}
доб перед заданным
void AddBefore(PNode p, PNode NewNode)
{
PNode q = Head;
if (Head == p) {
AddFirst(Head, NewNode);
return;
}
while (q && q->next!=p) q = q->next;
if (q) AddAfter(q, NewNode);
}
доб узла в конец списка
void AddLast(PNode NewNode)
{
PNode q = Head;
if (Head == NULL) {
AddFirst(Head, NewNode);
return;
}
while (q->next) q = q->next;
AddAfter(q, NewNode);
}
для всех значений поля адреса, начиная с головы списка, пока не
обнаружено нулевое значение адреса, выполнять сравнение поля данных с
требуемой информацией.
если сравнение дает положительный результат, то выдать элемент списка.
если достигнуто значение адреса 0, выдать сообщение, что элемент не
найден.
Добавление элемента в произвольное место списка.
Найти заданный элемент, сохранить значение его поля адреса, создать
новый элемент, записать адрес нового элемента в поле адреса заданного
(найденного) элемента.
Записать в поле адреса добавляемого элемента сохраненный адрес
следующего элемента.
Процедура добавления элемента в произвольное место списка показывает
преимущество связного хранения перед последовательным (массивы).
Удаление элемента из конца списка.
Найти последний элемент, освободить память, записать в поле адреса
предпоследнего элемента значение NULL. В
данной процедуре требуется хранить текущее значение адреса и адрес
предыдущего элемента.
Удаление произвольного элемента связного списка.
Найти удаляемый элемент, сохранить его адрес. В поле адреса
предыдущего элемента записать адрес следующего. Освободить память из-под
удаляемого элемента.
Кольцевой односвязный список
Структура аналогична структуре односвязного
однонаправленного списка, за исключением
того, что в поле адреса конечного элемента
хранится адрес головы списка.
Все процессы взаимодействия со списком аналогичны вышеописанным, за
исключением того, что проверка на конец списка осуществляется не с NULL, а со значением адреса головы списка.
Двунаправленный список
объявл
struct Node {
char word[40];
int count;
Node *next, *prev;
};
typedef Node *PNode;
доб в нач
void AddFirst(PNode NewNode)
{
NewNode->next = Head;
NewNode->prev = NULL;
if ( Head ) Head->prev = NewNode;
Head = NewNode;
if ( ! Tail ) Tail = Head;
}
конец head<->taid next<->prev
доб после задан
void AddAfter (PNode p, PNode NewNode)
{
if ( ! p->next )
AddLast (Head, Tail, NewNode);
else {
NewNode->next = p->next;
NewNode->prev = p;
p->next->prev = NewNode;
p->next = NewNode;
}
}
удаление void Delete(PNode &Head, PNode &Tail, PNode OldNode)
{
if (Head == OldNode) {
Head = OldNode->next;
if ( Head )
Head->prev = NULL;
else Tail = NULL;
}
else {
OldNode->prev->next = OldNode->next;
if ( OldNode->next )
OldNode->next->prev = OldNode->prev;
else Tail = NULL;
}
delete OldNode;
}
Каждый элемент списка содержит адрес не
только следующего элемента, но и
предыдущего. Голова списка в адресе
предыдущего элемента содержит NULL.
Кольцевой двунаправленный список
Поле предыдущий элемент головы списка
содержит адрес конца списка.
Двусвязный список
Каждый элемент списка содержит 2 ссылки
на 2 следующих элемента.
Двунаправленный (двусвязный) список
Элемент такого списка помимо ссылки на
левый и правый следующие
элементы
содержит ссылку на предыдущий элемент.
Многосвязный список
Каждый элемент содержит n-ссылок
на следующие элементы.
( Преимущество последовательного хранения: при
известном размере каждого элемента возможен доступ по индексу элемента.
Недостатки: необходимость
резервирования предполагаемого максимального размера, невозможность
добавления и исключения элементов, а только модификация.
Недостатки связного хранения:
множество дополнительных операций, приводящих к замедлению скорости; доступ к
элементам возможен только после просмотра предыдущих элементов.
Преимущества: отсутствие
необходимости резервирования максимально предполагаемого размера памяти;
отсутствие требований непрерывности используемой памяти; возможность
произвольного добавления и исключения элементов )
Дисциплина обслуживания.
Очередь: «first-in, first-out» (FIFO).
Стек:«last-in, first-out» (LIFO).
Дек – двунаправленная очередь – это
линейный список, у которого операции
добавления и удаления элементов и
доступа к элементам возможны как вначале так и в
конце списка.
стек
объявление
struct Stack {
PNode Head, Tail;
};
добавление на верш
void Push ( Stack &S, int i )
{
PNode NewNode;
NewNode = new Node;
NewNode->data = i;
NewNode->next = S.Head;
NewNode->prev = NULL;
if ( S.Head ) S.Head->prev = NewNode;
S.Head = NewNode;
if ( ! S.Tail ) S.Tail = S.Head;
}
удал с верш
int Pop ( Stack &S )
{
PNode TopNode = S.Head;
int i;
if ( ! TopNode ) return 0;
i = TopNode->data;
S.Head = TopNode->next;
if ( S.Head ) S.Head->prev = NULL;
else S.Tail = NULL;
delete TopNode;
return i;
}
дек
доб-у эл-та в конец
void PushTail ( Stack &S, int i )
{
PNode NewNode = new Node;
NewNode->data = i;
NewNode->prev = S.Tail;
NewNode->next = NULL;
if ( S.Tail ) S.Tail->next = NewNode;
S.Tail = NewNode;
if ( ! S.Head ) S.Head = S.Tail;
}
получ посл
int PopTail ( Stack &S )
{
PNode LastNode = S.Tail;
int i;
if ( ! LastNode ) return 0;
i = LastNode->data;
S.Tail = LastNode->prev;
if ( S.Tail ) S.Tail->next = NULL;
else S.Head = NULL;
delete LastNode;
return i;
}
|
