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

Рисунок 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 с.: ил.
11. Сайт www.cyberguru.ru
12. Сайт www.compdoc.ru

 

 

 

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

#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;}

}

}

}