Лекция 13

4.9.3.1. Линейные списки

Один из простых способов организовать список – сделать так, чтобы каж­дый элемент содержал ссылку на следующий. Такой список называется однона­правленным (односвязным). Если добавить в каждый элемент вторую ссылку – на предыдущий элемент, то получится двунаправленный список (двусвязный). Если последний элемент связан указателем с первым, получается кольцевой список.

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

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

· начальное формирование списка (создание первого элемента);

· добавление элемента в конец списка;

· чтение элемента с заданным ключом;

· вставка элемента в заданное место списка (до или после элемента с заданным ключом);

· удаление элемента с заданным ключом;

· упорядочивание списка по ключу.

Рассмотрим двунаправленный линейный список. Для формирования списка и работы с ним нужен, по крайней мере, один указатель – на начало спис­ка. Нередко используется еще один – на конец списка. Для простоты допус­тим, что список состоит из целых чисел, то есть описание элемента списка выгля­дит следующим образом:

struct Node

{

int d;

Node *next;

Node *prev;

};

В этом случае ключом элемента является само число d. Ниже приведена программа, которая формирует список из 5 чисел, добавляет число в список, удаляет число из списка и выводит его на экран. Программа проектируется «сверху вниз» – реализация функций разрабатывается после создания основной программы, которая их использует. Указатель начала списка обозначен pbeg, конца списка – pend, вспомогательные указа­тели – pv и pkey.

#include <iostream>

using namespace std; // Для использования cin и cout

struct Node

{

int d;

Node *next;

Node *prev;

};

Node *first(const int d);

void add(Node **pend, const int d); // **, чтобы значение указателя менялось

Node *find(Node * const pbeg, const int d);

bool remove(Node **pbeg, Node **pend, const int key);

Node *insert(Node * const pbeg, Node **pend, const int key, const int d);

// Эти данные правильнее было бы вводить

const int N = 5; // Кол-во элементов в списке

const int nPos = 2; // Ключ позиции для вставки

const int nInsKey = 200; // Ключ вставляемого элемента

const int nDelKey = 5; // Ключ удаляемого

// Основная функция

int main ()

{

Node *pbeg = first(1); // Формирование начального элемента списка

Node *pend = pbeg; // Пока список заканчивается здесь же

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

for (int i = 2; i <= N; i++) add(&pend, i);

// Вставка элемента

insert(pbeg, &pend, nPos, nInsKey);

// Удаление элемента

if (!remove(&pbeg, &pend, nDelKey)) cout << "не найден";

// Вывод списка на экран

Node *pv = pbeg;

while (pv)

{

cout << pv->d << ” “;

pv = pv->next;

}

int i; cin >> i; // Задержать консольное окно для просмотра результатов

return 0;

}

/*** Определение вспомогательных функций ***/

// Формирование начального элемента

Node *first (const int d)

{

Node *pv = new Node;

pv->d = d; pv->next = 0; pv->prev = 0;

return pv;

}

// Добавление в конец списка

void add(Node **pend, const int d)

{

Node *pv = new Node;

pv->d = d; pv->next = 0; pv->prev = *pend;

(*pend)->next = pv;

*pend = pv;

}

// Поиск элемента по ключу (если не найдено, возвращает 0)

Node *find(Node * const pbeg, const int d)

{

Node *pv = pbeg;

while (pv)

{

if (pv->d == d) break;

pv = pv->next;

}

return pv;

}

// Удаление элемента (передаются двойные указатели, т.к. оба могут измениться)

bool remove(Node **pbeg, Node **pend, const int key)

{

if (Node *pkey = find (*pbeg, key))

{ // Найден удаляемый элемент

if (pkey == *pbeg)

{ // Удаляется начальный элемент списка

*pbeg = (*pbeg)->next; (*pbeg)->prev = 0;

}

else if (pkey == *pend)

{ // Удаляется последний элемент списка

*pend = (*pend)->prev; (*pend)->next = 0;

}

else

{ // Удаляется промежуточный элемент

(pkey->prev)->next = pkey->next;

(pkey->next)->prev = pkey->prev;

}

delete pkey; // Удаление из динамической памяти

return true; // Задача выполнена успешно

}

return false; // Указанный элемент не найден

}

// Вставка после элемента с заданным ключом

Node *insert(Node * const pbeg, Node **pend, const int key, const int d)

{

if (Node *pkey = find(pbeg, key))

{

Node *pv = new Node;

pv->d = d;

// Настройка связей

pv->next = pkey->next; // Связь нового узла с последующим

pv->prev = pkey; // Связь нового узла с предыдущим

pkey->next = pv; // Связь предыдущего узла с новым

if (pkey != *pend) (pv->next)->prev = pv; // Последующего узла с новым

else *pend = pv; // Обновление указателя конца списка

return pv;

}

return 0;

}

Результат работы программы:

1 2 200 3 4

Все параметры, не изменяемые внутри функций, рекомендуется передавать с моди­фикатором const. Указатели, содержимое которых может измениться (например, при удале­нии из списка последнего элемента указатель конца списка требуется скор­ректировать), передаются по адресу (можно также по ссылке).

Сортировка связанного списка заключается в изменении связей между элемента­ми. Ниже приведена функция формирования упорядоченного списка (предполагается, что первый элемент существует). Алгоритм состоит в том, что исходный список просматривается, и новый эле­мент вставляется на место, определяемое значением его ключа.

void add_sort(Node **pbeg, Node **pend, const int d)

{

Node *pv = new Node; // Добавляемый элемент

pv->d = d;

Node *pt = *pbeg;

while (pt)

{ // Просмотр списка

if (d < pt->d)

{ // Занести перед текущим элементом (pt)

pv->next = pt;

if (pt == *pbeg)

{ // В начало списка

pv->prev = 0; *pbeg = pv;

}

else

{ // В середину списка

(pt->prev)->next = pv; pv->prev = pt->prev;

}

pt->prev = pv;

return;

}

pt = pt->next;

}

// В конец списка

pv->next = 0; pv->prev = *pend; (*pend)->next = pv; *pend = pv;

}

Дата добавления: 2014-03-11; просмотров: 408; Нарушение авторских прав

Мы поможем в написании ваших работ!