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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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 произвольных символов во вторую последовательность