Хранение и обработка данных с использованием линейных списков

Размещено на http://www.allbest.ru/

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

1. РЕАЛИЗАЦИЯ ЛИНЕЙНЫХ СПИСКОВ

2. РАЗРАБОТКА И ВЫБОР АЛГОРИТМОВ

3. ОПИСАНИЕ РАБОТЫ ПРОГРАММЫ НА ПСЕВДОКОДЕ

4. СОСТАВЛЕНИЕ ПРОГРАММНОГО КОДА

5. ТЕСТИРОВАНИЕ И ОТЛАДКА ПРОГРАММЫ

6. РЕЗУЛЬТАТ РАБОТЫ ПРОГРАММЫ

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ

ПРИЛОЖЕНИЕ. ЛИСТИНГ ПРОГРАММЫ

ВВЕДЕНИЕ

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

Одним из решений этого вопроса является линейные списки. Список - это набор записей, выстроенных в определенной последовательности.[1] В повседневной жизни списки окружают нас повсюду, являясь довольно эффективным способом хранения нужной нам информации. Примерами могут служить список продуктов, который составляют при походе в магазин, список студентов в журнале, список дел на день, различные словари и т.д. Область применения линейных списков достаточно широка:

- в операционных системах (очередь задач, готовых к выполнению, очередь документов к принтеру; стек состояний прерванных процессов (задач);

- в системах имитационного моделирования (очередь заявок на обслуживание какой-либо системой массового обслуживания );

- в научном и исследовательском ПО и т. д.

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

Основными достоинствами линейных списков являются:

лёгкость добавления и удаления элементов;

размер ограничен только объёмом памяти компьютера и разрядностью указателей;

динамическое добавление и удаление элементов.

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

уяснить поставленную задачу;

выбрать реализацию линейного списка;

выбрать алгоритмы для реализации функций линейного списка;

написать, протестировать и отладить программу.

интерфейс алгоритм линейный псевдокод

1. РЕАЛИЗАЦИЯ ЛИНЕЙНЫХ СПИСКОВ

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

Проблема эффективного управления данными является важнейшей для любой реализации списка. Список представляет совокупность связанных между собой узлов. Любой узел представляет собой структуру (в смысле struct), содержащую, по крайней мере, два поля: для хранения данных и для указателя. Полей данных и указателей может быть несколько. Поля данных могут быть любого типа: основного, составного или типа указатель. Описание простейшего элемента (компоненты, узла) выглядит следующим образом:

struct Node

{

Data d; // тип данных Data должен быть определен ранее

Node *next; // указатель на следующий элемент списка

Node *prev; // указатель на следующий элемент (если используется двусвязный список)

};

Список, каждый элемент которого содержит указатель только на следующий за ним элемент, называется однонаправленным или односвязным. Если добавить в каждый элемент вторую ссылку -- на предыдущий элемент, получится двунаправленный список (двусвязный), если последний элемент связать указателем с первым, получится кольцевой список. [2] На рисунке 1 приведена структура односвязного списка. На нем поле INF - информационное поле (данные), NEXT - указатель на следующий элемент списка. Каждый список должен иметь особый элемент, называемый указателем начала списка или головой списка, который обычно по формату отличен от остальных элементов. В поле указателя последнего элемента списка находится специальный признак nil, свидетельствующий о конце списка.

Рисунок 1 - Структура односвязного списка

Однако, обработка односвязного списка не всегда удобна, так как отсутствует возможность продвижения в противоположную сторону. Такую возможность обеспечивает двусвязный список, каждый элемент которого содержит два указателя: на следующий и предыдущий элементы списка. Структура линейного двухсвязного списка приведена на рисунке 2, где поле NEXT - указатель на следующий элемент, поле PREV - указатель на предыдущий элемент. В крайних элементах соответствующие указатели должны содержать nil, как и показано на рисунке 2:

Рисунок 2 - Структура двусвязного списка

Для удобства обработки списка добавляют еще один особый элемент - указатель конца списка. Наличие двух указателей в каждом элементе усложняет список и приводит к дополнительным затратам памяти, но в то же время обеспечивает более эффективное выполнение некоторых операций над списком. [3]

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

Рисунок 3 - Структура кольцевого списка

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

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

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

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

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

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

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

2. РАЗРАБОТКА И ВЫБОР АЛГОРИТМОВ

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

Будем исходить из того, что все функции должны быть независимы, чтобы изменения в одной функции не могли влиять на поведение другой. Для этого всё, что функциям необходимо получать извне, будем передавать им через параметры.

Элементы списка представим в виде структуры с именем Node, содержащей информационное поле (собственно хранимый символ) и два указателя: на предыдущий элемент и на следующий.

struct Node

{

char d;

Node *next;

Node *prev;

};

Теперь определим интерфейс программы. Перечислим основные функции работы с элементами списка, которые нам понадобятся:

- добавление элемента;

- вставка элемента;

- удаление выбранного элемента;

- поиск заданного элемента;

- сортировка списка;

- выполнение задания курсовой работы;

- вывод списка на экран.

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

Добавление элемента.

Чтобы добавить новый элемент в список, нужно знать, что и куда добавлять. Иными словами в функцию в качестве параметров нужно передать указатели на начало списка и конец списка, а внутри нее организовать ввод элемента. При этом указатели на начало и конец списка должны быть изменены внутри функции, следовательно, следует передать их по ссылкам. Алгоритм работы функции добавления следующий: ввести элемент, затем обнулить указатель на следующий элемент (т.к. добавление происходит в конец списка), а в указатель на предыдущий элемент записать адрес предыдущего элемента или обнулить его (если список пуст).

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

Чтобы вставить новый элемент в список, нужно знать после какого элемента будет произведена вставка. Следовательно, алгоритм работы функции вставки такой: ввести вставляемый элемент, ввести элемент, после которого будет произведена вставка и если такой элемент найден, произвести вставку и скорректировать указатели головы и хвоста списка.

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

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

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

Тривиальным алгоритмом для решения поставленной задачи является последовательный, или линейный, поиск. Я решил использовать его в своей программе, т.к. его реализация достаточно проста. Он заключается в том, что мы поочередно сравниваем какой-либо элемент со всеми элементами последовательности. Обнаружив совпадение, мы возвращаем индекс найденного элемента (в нашем случае указатель на него).[4] В качестве параметров в функцию поиска будут передаваться указатель на начало списка и искомый элемент.

Сортировка списка.

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

Рисунок 4 - Пример пузырьковой сортировки

Вывод на экран.

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

Функция, выполняющая задание курсовой работы.

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

Текстовое меню.

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

3. ОПИСАНИЕ РАБОТЫ ПРОГРАММЫ НА ПСЕВДОКОДЕ

После разработки и выбора необходимых алгоритмов, целесообразно представить алгоритм работы программы на псевдокоде, чтобы было легче перейти к составлению программного кода. Псевдокод - формализованное текстовое описание алгоритма (текстовая нотация).[5] Т.к. работа всей программы сводится к выполнению индивидуального задания на курсовую работу, то представим псевдокод функции, отвечающей за его выполнение.

Назовем ее relize.

Функция relize

Дано: целые переменные k, m и n - количество элементов первого, второго и третьего списка соответственно; указатели на начало и конец каждого из списков; i, j, z - счетчики циклов.

Вводим k, m и n.

i=0

Пока ( i меньше k )

{

Добавить элемент в первый список и увеличить i на единицу

}

j=0

Пока ( j меньше m )

{

Добавить элемент во второй список и увеличить j на единицу

}

z=0

Пока ( z меньше n )

{

Добавить элемент в третий список и увеличить z на единицу

}

Пока (не кончится первый список)

{

Если (текущий элемент найдется во втором и в третьем списке одновременно)

Тогда (выводим его на экран и ставим пробел)

Переходим к следующему элементу

}

4. СОСТАВЛЕНИЕ ПРОГРАММНОГО КОДА

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

struct Node

{

char d;

Node *next;

Node *prev;

};

Перейдем к кодированию функций. Исходя из разработанных алгоритмов, все функции, за исключением поиска и вывода на экран, будут получать в качестве параметров ссылки на указатели начала и конца списка, чтобы после работы функции мы имели возможность работать с измененной последовательностью. Для ввода и вывода во всех функциях будем использовать операторы cin и cout из библиотеки iostream.h.

Добавление элемента.

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

void add (Node* &pbeg, Node* &pend)

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

char d;

cout << "Введите элемент: ";

cin >> d;

Node *pv = new Node; // Выделение памяти под новый элемент

pv->d = d;

if (pbeg==NULL) // Если указатель головы пуст, устанавливаем

// его на новый элемент

{

pbeg=pv;

pend=pv;

pv->next = 0;

pv->prev=NULL;

}

else

{

pv->next = 0;

pv->prev = pend;

pend->next=pv;

pend=pv;}

Поиск элемента по ключу.

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

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

Функция должна пройти по списку, начиная с головы, и проверить совпадение элемента, переданного в качестве параметра, с каждым его элементом. Если обнаружится совпадение, необходимо вернуть указатель на найденный элемент. Код:

Node *pv = pbeg;

while (pv)

{

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

pv = pv->next;

}

return pv;

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

В случае успешного удаления элкмента функция будет возвращать значение «истина», в случае неудачного - «ложь», поэтому в качестве типа возвращаемого значения установим bool. Bool - логический тип данных. Переменные этого типа могут принимать только значения true или false. [6] В теле функции организуем ввод элемента, который будет удален, поиск этого элемента по списку и соответствующую кооректировку указателей, в зависимости от того, из какой части списка будет удален элемент. Если удаление происходит из начала списка, следует указателю головы присвоить адрес следующего элемента; если из середины - указатели next предстоящего элемента и prev следующего изменить так, чтобы эти элементы указывали друг на друга; если из конца списка - сместить указатель хвоста на предыдущий элемент.

char key;

cout << "Введите элемент,который нужно удалить: ";

cin >> 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;

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

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

char d,key;

cout << "Введите вставляемый элемент: ";

cin >> d;

cout << "Введите элемент,после которого будет вставлен новый: ";

cin >> key;

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;// обновление указателя на конец списка

}

else cout << "Невозможно вставить после этого элемента!" << endl;

Вывод на экран.

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

while(pv != NULL)

{

cout << pv->d << " ";

pv = pv->next; // перейти к следующему узлу

}

Если список пуст, необходимо вывести соответствующее сообщение на экран.

if(pbeg==NULL) cout << "Список пуст!" << endl;

Сортировка.

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

char tmp = pv->next->d; // tmp - временная переменная

pv->next->d = pv->d;

pv->d = tmp;

Текстовое меню.

Меню будет представлять собой несколько текстовых пунктов, которые будут отображаться на экране, пока пользователь не нажмет клавишу. Для этого используем цикл do while. Символьная строка, которая будет отвечать за нажатую клавишу, преобразуется с помощью функции atoi (преобразует символьную строку в значение типа int [7]) и является возвращаемым значением функции.

char buf[10];

int option;

cin >> buf;

option = atoi(buf);

Функция relize.

Функция relize играет главную роль в моей программе. Для её реализации нам понадобятся три отдельных списка, т.е. необходимо созлать по паре указателей на начало и на конец для каждого из списков.

Node *pbeg_s=NULL,*pend_s=NULL // указатели начала и конца первого

Node *pbeg_t=NULL,*pend_t=NULL // второго

Node *pbeg_u=NULL,*pend_u=NULL // и третьего списков

После того как пользователь введет количество элементов каждого из списков, с помощью цикла for осуществим ввод элементов. Ниже приведен фрагмент кода для заполнения одного из списков.

for(int i=0; i<k; i++) // k - количество элементов списка

{

add(pbeg_s,pend_s);

}

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

while(pv) // pv1 и pv2 - указатели головы первого и второго списков, в которых производится поиск

{

if (find(pv1,pv->d) && find(pv2,pv->d)) cout << pv->d << " ";

pv=pv->next;

}

5. ТЕСТИРОВАНИЕ И ОТЛАДКА ПРОГРАММЫ

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

Для достижения наилучшей работоспособности программы следует также провести ее тестирование, особенно если предполагается, что программой будут пользоваться другие.Тестирование следует провести на как можно большем количестве наборов входных данных, в том числе и заведомо неверных. [8]

Проверим функции добавления элемента и вывода на экран. Для примера добавим в список два символа - a и g - и выведем их на экран. Скриншот выполнения данных действий представлен ниже.



Рисунок 5 - Работа функции добавления и вывода на экран

Теперь попробуем вставить между ними букву M.

Рисунок 6 - Вставка элемента

Попробуем вставить новый элемент, после элемента, которого нет в списке.



Рисунок 7 - Работа функции вставки с неверными данных

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

Рисунок 8 - Проверка работы функции удаления из пустого списка

Добавим еще несколько элементов и проверим работу функции сортировки.



Рисунок 9 - Работа функции сортировки

Выйдем из программы и попробуем вывести пустой список.

Рисунок 10 - Попытка вывести пустой список

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

6. РЕЗУЛЬТАТ РАБОТЫ ПРОГРАММЫ

Представим в виде набора скриншотов результат работы программы.

Запускаем программу, выбираем шестой пункт меню, нажав на клавиатуре клавишу с цифрой 6. Для примера количество элементов первой последовательности зададим равным 10, второй - 15, третьей - 12.

Рисунок 11 - Ввод количества элементов

Последовательно добавляем 10 произвольных символов в первую последовательность

Рисунок 12 - Добавление символов в первую последовательность

Последовательно добавляем 15 произвольных символов во вторую последовательность

Рисунок 13 - Добавление символов во вторую последовательность

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

Рисунок 14 - Добавление символов в третью последовательность и вывод общих символов на экран

ЗАКЛЮЧЕНИЕ

После выполнения работы подведем основные итоги.

То, насколько эффективно программа работает с данными, является одним из главных показателей ее качества и надежности. От этого показателя зависит также и ее востребованность на рынке разработок, что является неплохим стимулом для усовершенствования методов работы с данными. На сегодняшний день применяется множество способов для обеспечения высокого уровня этого показателя.

Целью моей работы являлось создание программы, эффективно работающей с данными при помощи линейных списков. Считаю, что все поставленные для выполнения цели задачи были успешно выполнены. Программа верно выполняет все действия, перечисленные в задании, верно реагирует на попытку работы с неверными данными. Это означает, что все выбранные алгоритмы и построенные на их основе функции были реализованы успешно. Тестирование программы подтвердило этот факт. Программа имеет примитивный пользовательский интерфейс, но при этом не теряет многого в эффективности работы, т.к. такой интерфейс предельно понятен и доступен для любого пользователя.

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

СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ

1. Брукшир Дж. Информатика и вычислительная техника. 7-е изд. - СПб.: Питер, 2004. - 620 с.: ил.

2. Павловская Т.А. C/C++. Программирование на языке высокого уровня. - СПб.: Питер, 2003. - 461 с.: ил.

3. Кнут Д.Э. Искусство программирования, т.1.: Пер. с англ., 3-е издание - М.: Вильямс, 2010. - 720 с.

4. Красиков И.В. Алгоритмы. Просто как дважды два. - М.: Эксмо, 2007. - 256 с.

5. Иванова Г.С. Технология программирования: Учебник для вузов. - М.: Изд-во МГТУ им. Н.Э. Баумана, 2002. - 320 с.: ил.

6. Шилдт Г. Самоучитель C++: Пер. с англ., 3-е издание - СПб.: БВХ- Петербург, 2009. - 688 с.

7. Подбельский В.В., Фомин С.С. Программирование на языке Си: Учеб. пособие. - 2-е доп. изд. - М.: Финансы и статистика, 2004. - 600 с.: ил.

8. Динман Н.И. С++. Освой на примерах. - СПб.: БХВ-Петербург, 2006. 384 с.: ил.

9. Прата С. Язык программирования С++. Лекции и упражнения. - СПб.: ДиаСофтЮп, 2005. - 1104 с.

10. Культин Н.Б. С/С++ в задачах и примерах. - СПб.: БХВ-Петербург, 2005. - 288 с.: ил.

ПРИЛОЖЕНИЕ. ЛИСТИНГ ПРОГРАММЫ

#include <iostream>

#include <conio.h>

using namespace std;

struct Node

{

char d;

Node *next;

Node *prev;

};

void add(Node* &pbeg,Node* &pend);

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

bool remove(Node* &pbeg, Node* &pend);

Node *insert(Node *const pbeg, Node* &pend);

void print(Node *pbeg);

void sort(Node *pbeg);

int menu();

void relize();

void main()

{

Node *pbeg=NULL;

Node *pend=NULL;

setlocale(0,"Russian");

while(true)

{

switch(menu())

{

case 1:

add(pbeg,pend);

break;

case 2:

insert(pbeg,pend);

break;

case 3:

if(!remove(pbeg,pend))cout << "Элемент не найден!" << endl;

else remove(pbeg,pend);

break;

case 4:

print(pbeg);

break;

case 5:

sort(pbeg);

break;

case 6:

relize();

break;

case 7:

return;

default:

cout << "Надо вводить число от 1 до 7!" << endl;

}

}

_getch();

}

void add(Node* &pbeg, Node* &pend)// Добавление элемента

{

char d;

cout << "Введите элемент: ";

cin >> d;

Node *pv = new Node;

pv->d = d;

if(pbeg==NULL)

{

pbeg=pv;

pend=pv;

pv->next = 0;

pv->prev=NULL;

}

else

{

pv->next = 0;

pv->prev = pend;

pend->next=pv;

pend=pv;

}

}

Node *find(Node *const pbeg,char d) // Поиск элемента по ключу

{

Node *pv = pbeg;

while (pv)

{

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

pv = pv->next;

}

return pv;

}

bool remove(Node* &pbeg, Node* &pend)// Удаление элемента

{

char key;

cout << "Введите элемент,который нужно удалить: ";

cin >> key;

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

{

if (pkey == pbeg) // проверяется,находится ли удаляемый элемент в начале списка

{

pbeg = pbeg->next; // если да,то надо скорректировать указатель pbeg на начало списка так, чтобы он указывал на следующий элемент в списке, адрес которого находится в поле next первого элемента

pbeg->prev = 0; // обнуляется указатель на предыдущий элемент

}

else if (pkey == pend) // если удаляемый элемент находится в конце списка, требуется сместить указатель pend конца списка на предыдущий элемент, адрес которого можно получить из поля prev последнего элемента

{

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) // Вставка элемента

{

char d,key;

cout << "Введите вставляемый элемент: ";

cin >> d;

cout << "Введите элемент,после которого будет вставлен новый: ";

cin >> key;

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;

}

else cout << "Невозможно вставить после этого элемента!" << endl;

return 0;

}

void print(Node *pbeg)// Печать списка

{

if(pbeg==NULL)cout << "Список пуст!" << endl;

else

{

cout << "Список: ";

Node *pv = pbeg; // pv пробегает по списку, начиная с головы

while(pv != NULL) // пока не конец списка, печатать значение данных текущего узла

{

cout << pv->d << " ";

pv = pv->next; // перейти к следующему узлу

}

}

cout << endl;

}

int menu() // Текстовое меню

{

char buf[10];

int option;

do

{

cout << "===========МЕНЮ===========" << endl;

cout << "1 - Добавить элемент" << endl;

cout << "2 - Вставить элемент" << endl;

cout << "3 - Удалить элемент" << endl;

cout << "4 - Вывести на экран" << endl;

cout << "5 - Сортировать список" << endl;

cout << "6 - Ввести три последовательности,получить их общие символы" << endl;

cout << "7 - Выход" << endl;

cout << "Нажмите 1-7 для выбора: ";

cin >> buf;

option = atoi(buf);

}

while(!option);

return option;

cout << "\n" << endl;

}

void relize()

{

int k,m,n;

Node *pbeg_s=NULL,*pend_s=NULL;

Node *pbeg_t=NULL,*pend_t=NULL;

Node *pbeg_u=NULL,*pend_u=NULL;

cout << "Введите кол-во элементов первой последовательности: ";

cin >> k;

cout << "Введите кол-во элементов второй последовательности: ";

cin >> m;

cout << "Введите кол-во элементов третьей последовательности: ";

сin >> n;

сout << "Введите 1-ю последовательность:" << endl;

for(int i=0;i<k;i++)

{

add(pbeg_s,pend_s);

}

cout << "Введите 2-ю последовательность:" << endl;

for(int j=0;j<m;j++)

{

add(pbeg_t,pend_t);

}

cout << "Введите 3-ю последовательность:" << endl;

for(int z=0;z<n;z++)

{

add(pbeg_u,pend_u);

}

Node *pv = pbeg_s, *pv1 = pbeg_t, *pv2=pbeg_u;

cout << "Общие символы: ";

while(pv)

{

if(find(pv1,pv->d)&&find(pv2,pv->d))cout << pv->d << " ";

pv=pv->next;

}

cout << "\n" << endl;

}

void sort(Node *pbeg) // Сортировка

{

if(pbeg==NULL)cout << "Список пуст!" << endl;

else

{

Node *pv = pbeg;

while(pv->next)

{

if((pv->d)>(pv->next->d))

{

char tmp = pv->next->d;

pv->next->d = pv->d;

pv->d = tmp;

pv=pv->next;

sort(pbeg);

}

else {pv=pv->next;}

}

}

Размещено на Allbest.ru