Курсовая работа (т): Хранение и обработка данных с использованием линейных списков

d;<< "Введите элемент: ";>> d;*pv = new Node; // Выделение памяти под новый элемент>d = d;(pbeg==NULL) // Если указатель головы пуст, устанавливаем

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

{=pv;=pv;>next = 0;>prev=NULL;

}

{>next = 0;>prev = pend;>next=pv;=pv;}

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

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

*find (Node *const pbeg,char d)

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

*pv = pbeg;(pv)

{(pv->d == d)break;= pv->next;

}pv;

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

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

key;<< "Введите элемент,который нужно удалить: ";>> key;(Node *pkey = find(pbeg, key))

{ (pkey == pbeg) // Удаление из начала

{ = pbeg->next;>prev = 0;

}if (pkey == pend) // Удаление из конца

}// Удаление из середины

{

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

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

}pkey;true;

}false;

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

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

d,key;<< "Введите вставляемый элемент: ";>> d;<< "Введите элемент,после которого будет вставлен новый: ";>> key;(Node *pkey = find(pbeg, key))

{*pv = new Node;>d = d;>next = pkey->next;// установление связи нового узла с последующим>prev = pkey;// установление связи нового узла с предыдущим>next = pv;// установление связи предыдущего узла с новым(pkey != pend)(pv->next)->prev = pv;// установление связи последующего узла с новымpend = pv;// обновление указателя на конец списка

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

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

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

(pv != NULL)

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

}

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

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

Сортировка.

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

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

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

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

buf[10];option;>> buf;= atoi(buf);

Функция relize.

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

*pbeg_s=NULL,*pend_s=NULL // указатели начала и конца первого *pbeg_t=NULL,*pend_t=NULL // второго*pbeg_u=NULL,*pend_u=NULL // и третьего списков

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

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

{(pbeg_s,pend_s);

}

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

{(find(pv1,pv->d) && find(pv2,pv->d)) cout << pv->d << " ";=pv->next;

}

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

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

Для достижения наилучшей работоспособности программы следует также провести ее тестирование, особенно если предполагается, что программой будут пользоваться другие.Тестирование следует провести на как можно большем количестве наборов входных данных, в том числе и заведомо неверных. [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 с.: ил.

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

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

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

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

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

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

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

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

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

#include <iostream>

#include <conio.h>namespace std;Node

{d;*next;*prev;

};add(Node* &pbeg,Node* &pend);*find(Node *const pbeg, char d);remove(Node* &pbeg, Node* &pend);*insert(Node *const pbeg, Node* &pend);print(Node *pbeg);sort(Node *pbeg);menu();relize();main()

{*pbeg=NULL;*pend=NULL;(0,"Russian");(true)

{(menu())

{1:(pbeg,pend);;2:(pbeg,pend);;3:(!remove(pbeg,pend))cout << "Элемент не найден!" << endl;remove(pbeg,pend);;4:(pbeg);;5:(pbeg);;6:();;7:;:<< "Надо вводить число от 1 до 7!" << endl;

}

}

_getch();

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

{d;<< "Введите элемент: ";>> d;*pv = new Node;>d = d;(pbeg==NULL)

{=pv;=pv;>next = 0;>prev=NULL;

}

{>next = 0;>prev = pend;>next=pv;=pv;

}

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

{*pv = pbeg;(pv)

{(pv->d == d)break;= pv->next;

}pv;

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

{key;<< "Введите элемент,который нужно удалить: ";>> key;(Node *pkey = find(pbeg, key))

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

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

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

{ = pend->prev;>next=0; // обнуляется указатель на следующий элемент

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

{

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

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

}pkey;true;

}false;

}*insert (Node *const pbeg, Node* &pend) // Вставка элемента

{d,key;<< "Введите вставляемый элемент: ";>> d;<< "Введите элемент,после которого будет вставлен новый: ";>> key;(Node *pkey = find(pbeg, key))

{*pv = new Node;>d = d;>next = pkey->next; // установление связи нового узла с последующим>prev = pkey; // установление связи нового узла с предыдущим>next = pv; // установление связи предыдущего узла с новым(pkey != pend)(pv->next)->prev = pv; // установление связи последующего узла с новымpend = pv; // обновление указателя на конец списка,если узел вставляется в конецpv;

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

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

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

{<< "Список: ";*pv = pbeg; // pv пробегает по списку, начиная с головы(pv != NULL) // пока не конец списка, печатать значение данных текущего узла

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

}

}<< endl;

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

{buf[10];option;

{<< "===========МЕНЮ===========" << endl;<< "1 - Добавить элемент" << endl;<< "2 - Вставить элемент" << endl;<< "3 - Удалить элемент" << endl;<< "4 - Вывести на экран" << endl;<< "5 - Сортировать список" << endl;<< "6 - Ввести три последовательности,получить их общие символы" << endl;<< "7 - Выход" << endl;<< "Нажмите 1-7 для выбора: ";>> buf;= atoi(buf);

}(!option);option;<< "\n" << endl;

}relize()

{k,m,n;*pbeg_s=NULL,*pend_s=NULL;*pbeg_t=NULL,*pend_t=NULL;*pbeg_u=NULL,*pend_u=NULL;<< "Введите кол-во элементов первой последовательности: ";>> k;<< "Введите кол-во элементов второй последовательности: ";>> m;<< "Введите кол-во элементов третьей последовательности: ";

сin >> n;

сout << "Введите 1-ю последовательность:" << endl;(int i=0;i<k;i++)

{(pbeg_s,pend_s);

}<< "Введите 2-ю последовательность:" << endl;(int j=0;j<m;j++)

{(pbeg_t,pend_t);

}<< "Введите 3-ю последовательность:" << endl;(int z=0;z<n;z++)

}*pv = pbeg_s, *pv1 = pbeg_t, *pv2=pbeg_u;<< "Общие символы: ";(pv)

{(find(pv1,pv->d)&&find(pv2,pv->d))cout << pv->d << " ";=pv->next;

}<< "\n" << endl;

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

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

{*pv = pbeg; (pv->next)

{ ((pv->d)>(pv->next->d))

{ tmp = pv->next->d; >next->d = pv->d; >d = tmp; =pv->next;(pbeg);

} {pv=pv->next;}

}

}