Главная страница
Навигация по странице:

  • 5.3. Решение практических задач с использованием стеков

  • 5.4. Применение исключений и шаблонов

  • Розовая методичка. Огнева М. В., Кудрина Е. В. Структуры данных и алгоритмы программирование на языке c


    Скачать 1.93 Mb.
    НазваниеОгнева М. В., Кудрина Е. В. Структуры данных и алгоритмы программирование на языке c
    Дата14.05.2019
    Размер1.93 Mb.
    Формат файлаpdf
    Имя файлаРозовая методичка.pdf
    ТипДокументы
    #77078
    страница5 из 8
    1   2   3   4   5   6   7   8

    Замечание.
    1.
    Работу остальных членов-функций класса Stack рассмотрите самостоятельно.
    2.
    Описание класса Stack оформим в виде отдельного файла с именем stack.cpp. В дальнейшем при решении практических задач будем подключать данный файл к проекту с помощью директивы
    #include "stack.cpp" после using namespace std Обратите внимание на то, что сам файл stack.cpp должен находится в той же папке, что и файл с кодом программы.
    5.3. Решение практических задач с использованием стеков
    1. Дан текстовый файл input.txt, в котором через пробел записаны натуральные числа.
    Переписать его содержимое в файл output.txt в обратном порядке.
    43
    Оператор 1: определяется указатель г, который устанавливается на верхний элемент стека.

    #include
    using namespace std;
    #include
    "stack.cpp"
    //подключение файла с реализацией класса Stack
    int main()
    {
    Stack t; int i; ifstream in(
    "input.txt"
    ); ofstream out(
    "output.txt"
    );
    //пока не достигнут конец файла input.txt читаем из него элементы while
    (in >> i)
    t.Push(i);
    //и помещаем их в стек
    in.close(); while
    (!t.Empty())
    //пока стек не пуст
    out << t.Pop() <<
    " "
    ;
    //извлекаем из него элементы и выводим в файл
    out.close(); return
    0;
    }
    Результат работы программы:
    ________input.txt_________ ________output.txt________
    1 2 3 4 45 7 4 5 6 7 8 9 10 12 12 10 9 8 7 6 5 4 7 45 4 3 2 1 2. Дана последовательность натуральных чисел. Перед каждым элементом равным х вставить элемент равный у. Входная последовательность целых чисел и заданные числа х и у хранятся в файле input.txt (в первой строке файла через пробел записаны х и у, во второй - последовательность чисел), выходная последовательность целых чисел записывается в файл output.txt.
    Идея решения заключается в следующем. Перепишем все числа из файла input.txt в стек. По свойству стека все числа там будут находиться в обратном порядке. Нам надо сохранить прямой порядок, а кроме того, вставить символы. Поэтому введем второй стек и будем переписывать числа из первого во второй по следующему алгоритму. Берем число первого стека, переписываем во второй стек. Далее проверяем: если это число х, то во второй стек запишем число у. Таким образом, во втором стеке числа у будут вставлены после чисел х, но при извлечении из стека порядок поменяется на противоположный
    Следовательно, остается только извлекать по одному элементу из второго стека и переписывать в выходной файл.
    #include
    using namespace std;
    #include
    "stack.cpp"
    //подключение файла с реализацией класса Stack
    int main()
    {
    Stack t, t1;
    //инициализируем два стека
    int i, x, y;
    ifstream in(
    "input.txt"
    ); ofstream out(
    "output.txt"
    );
    44
    in >> x >> y; while
    (in >> i) t.Push(i); in.close();
    //пока стек t не пуст, переписываем из него числа в стек t1, вставляя
    //после каждого элемента со значением х элемент со значением у
    while
    (!t.Empty())
    { i = t.Pop(); t1.Push(i); if
    (i == x) t1.Push(y);
    }
    //переписываем содержимое стека t1 в выходной файл
    while
    (!t1.Empty())
    { out << t1.Pop() <<
    " "
    ;
    } out.close(); return
    0;
    }
    Результат работы программы:
    ________input.txt_________ ________output.txt________
    4 0 1 0 4 3 0 4 45 7 0 4 6 7 0 4 1 4 3 4 45 7 4 6 7 4
    3. В файле находится текст, в котором имеются скобки (). Используя стек, проверить, соблюден ли баланс скобок в тексте.
    Замечание. Теперь стек должен обрабатывать символы. Поэтому в классе Stack тип информационного поля стека изменяется на char. Таким же образом будут изменены типы соответствующих параметров методов класса и типы возвращаемых значений методов класса.
    #include
    using namespace std;
    #include
    "stack.cpp"
    //Функция, подсчитывающая баланс скобок. Возвращает:
    //0 - если баланс скобок соблюден;
    //1 - если имеется лишняя открывающая скобка;
    //-1 - если имеется лишняя закрывающая скобка.
    int
    Balans()
    {
    Stack t;
    //описываем стек, в который из всего текста будут
    //заноситься только открывающиеся скобки
    ifstream in(
    "input.txt"
    ); char c;
    45
    while
    (in >> c)
    { switch
    (c)
    { case
    '(': t.Push(c); break
    ; //если считанный символ (, то
    //записываем его в стек
    case
    ')':
    //если считанный символ ), то в стеке
    //должна находиться соответствующая ему (
    if
    (t.Empty())
    //если стек пуст
    return -1;
    // возвращаем -1 - код лишней закрывающейся скобки
    else
    //иначе выбираем из него одну открывающую скобку
    t.Pop();
    }
    } in.close();
    /* Если после того, как весь текст обработан, стек пустой, то баланс скобок
    в тексте соблюден - возвращаем код 0. В противном случае, в стеке находятся
    открывающиеся скобки, которым не соответствуют закрывающиеся - возвращаем
    код 1. */ if
    (t.Empty())
    return
    0; else return
    1;
    } int main()
    { ofstream out(
    "output.txt"
    ); int i = Balans();
    //вызываем функцию Balans0
    //обрабатываем значение, возвращенное функцией Balans
    if
    (i == 0) out <<
    "ok"
    ; if
    (i == 1) out <<
    "error: ("
    ; if
    (i == -1) out <<
    "error: )"
    ; out.close(); return
    0;
    }
    46

    Результат работы программы:
    ________input.txt_________ ________output.txt________
    (5-x*(4/x-(x+3)/(y-2)-y)-9 error: (
    ________input.txt_________ ________output.txt________
    (5-x)*(4/x-(x+3)/(y-2)-y)-9 ok
    ________input.txt_________ ________output.txt________
    (5-x)*(4/x-(x+3)/(y-2)-y))-9 error: )
    ________input.txt_________ ________output.txt________
    7+9-x/2+4-b*3 ok
    5.4. Применение исключений и шаблонов
    В пособии [9] был рассмотрен механизм обработки исключительных ситуаций в
    C++. Данный механизм очень полезен при работе со стеками. Так, извлечь элемент из стека или посмотреть значение верхнего элемента стека возможно только тогда, когда стек не пуст. Чтобы обработать указанную ситуацию, мы будет использовать следующий класс:
    #include

    #include

    using namespace std; class
    StackException
    : public exception
    { public
    :
    StackException(
    const string
    & message =
    ""
    ): exception
    (message.c_str()) {}
    };
    Данный класс оформим в отдельный файл exception.срр и подключим его к файлу stack.срр, в котором предложена реализация класса Stack.
    В пособии [9] был также рассмотрен механизм создания и использования шаблонов-функций. Аналогичным образом можно создавать классы-шаблоны.
    Рассмотрим подробно, как будет выглядеть класс Stack после добавления в него механизма обработки исключений и шаблонов:
    #include
    "exception.cpp"
    //подключение класса StackException
    template
    <
    class
    Item
    >
    //описание класса-шаблона, где Item тип данных
    class
    Stack
    //переданный в класс
    { struct
    Element
    {
    Item inf;
    47

    Element
    *next;
    Element (
    Item x,
    Element
    *p): inf(x), next(p) {}
    };
    Element
    *head; public
    :
    Stack(): head(0) {} bool
    Empty()
    { return head == 0;
    }
    Item
    Pop()
    { if
    (Empty())
    //если стек пуст, то генерируем исключение
    {
    throw
    StackException
    (
    "StackException: Pop — стек пуст"
    );
    } else
    //иначе извлекаем элемент из стека
    {
    Element
    *r = head;
    Item i = r->inf; head = r->next; delete r; return i;
    }
    } void
    Push(
    Item data)
    { head = new
    Element
    (data, head);
    }
    Item
    Top()
    { if
    (Empty())
    //если стек пуст, то генерируем исключение
    {
    throw
    StackException
    (
    "StackException: Top — стек пуст"
    );
    } else
    //иначе возвращаем значение верхнего элемента стека
    { return head->inf;
    }
    }
    };
    48

    Замечание. Далее при объектно-ориентированной реализации списков будем использовать классы-шаблоны. Более подробно познакомиться с разработкой и использованием классов- шаблонов можно изучив дополнительную литературу [6, 7, 10, 11].
    5.5.
    Очередь
    Очередь - это частный случай списка, добавление элементов в который выполняется в один конец (хвост - tail), а выборка и просмотр осуществляются с другого конца (головы - head). Другие операции с очередью не определены. При выборке элемент исключается из очереди. Говорят, что очередь реализует принцип обслуживания FIFO
    (fist in - fist out, первым пришел - первым вышел). Очередь проще всего представить в виде узкой трубы, в один конец которой бросают мячи, а из другого конца они вылетают.
    Понятно, что мяч, который был брошен в трубу первым, первым и вылетит.
    В программировании очереди применяются при математическом моделировании, диспетчеризации задач операционной системы, буферном вводе/выводе.
    Рассмотрим организацию очереди с помощью структуры, изображенной на рис.
    5.4. Отличие очереди от стека в том, что у очереди два указателя: первый (head) указывает на первый элемент очереди, второй (tail) - на последний элемент.
    Рис. 5.4. Очередь
    Базовый элемент очереди содержит:

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

    поле-указатель next, в котором хранится адрес следующего элемента очереди, и которое будет использоваться для организации связи элементов.
    Замечание. В общем случае базовый элемент очереди может содержать несколько информационных полей
    Предложенный базовый элемент очереди может быть описан следующим образом: struct
    Element
    {
    Item inf;
    //информационное поле типа Item
    Element
    *next;
    //указатель на следующий элемент очереди
    Element(
    Item x): inf(x), next(0) {}
    //конструктор
    };
    49

    Тогда указатели на первый и последний элементы очереди могут быть описаны следующим образом:
    Element
    *head,*tail;
    Как уже говорилось, доступ к элементам очереди возможен в двух точках: из одной точки - (головы) можно брать и просматривать элементы, во второй точке
    (хвост) можно добавлять элементы. С учетом вышеизложенного представим объектно-ориентированную реализацию очереди с помощью класса Queue:
    #include
    "exception.cpp"
    //подключаем класс QueueException, рассмотрим его позже
    template
    <
    class
    Item
    >
    //класс-шаблон очередь
    class
    Queue
    {
    struct
    Element
    {
    Item inf;
    Element
    *next;
    Element
    (Item x): inf(x), next(0) {}
    };
    Element
    *head, *tail;
    //указатели на начало и конец очереди
    public
    :
    Queue(): head(0), tail(0) {} bool
    Empty()
    //возвращает true, если очередь пуста, иначе false
    { return head == 0;
    }
    Item
    Get()
    { if
    (Empty())
    //если очередь пуста, то генерируем исключение
    throw
    QueueException
    (
    "QueueException: get - queue empty"
    ); else
    //иначе извлекаем элемент из головы очереди
    {
    Element
    *t = head;
    Item i = t->inf; head = t->next; if
    (head ==
    NULL
    ) tail =
    NULL
    ; delete t; return i;
    }
    }
    50
    void
    Put(
    Item data)
    {
    Element
    *t = tail;
    //устанавливаем вспомогательный указатель
    //на последний элемент очереди
    tail = new
    Element
    (data);
    //формируется новый элемент, на
    //который будет указывать tail
    if
    (!head)
    //если до этого очередь была пуста, то новый
    //элемент является и первым, и последним, поэтому
    //указатель head устанавливаем на tail
    head = tail; else t->next = tail;
    //иначе новый узел помещаем в конец очереди
    }
    };
    Примечание: В языке C++, NULL – это то же самое, что и 0.
    Более подробно рассмотрим базовые операции помещения элемента в очередь, предполагая, что у нас создан экземпляр класса Queue q. Это значит, что выполнился конструктор, который создал пустую очередь с указателями: head=NULL, tail=NULL.
    Первоначально добавим в очередь элемент 3, для чего выполним команду q.Put(3).
    Во вспомогательном указателе t (см. реализацию функции Put) сохраняется значение указателя на последний элемент, т.е. NULL.
    Затем происходит создание элемента, в информационную часть которого заносится значение 3, а в указатель next значение NULL. После чего tail становится указателем на этот элемент.
    Далее производится проверка: пуста ли очередь (указывает ли head на какой- то элемент или его значение NULL)? В данном случае очередь пуста, поэтому head будет указывать туда же, куда и tail, т.е. на новый элемент со значением 3. Таким образом получили очередь из одного элемента:
    51
    Или я не умею пользоваться вордом, или сам ворд такой кривой... Вот откуда здесь так много пустого места? Почему отступы такие кривые? Ыыыыыыыы……

    Теперь добавим в очередь элемент со значением 8, выполняя команду q.Put(8). При этом создается вспомогательный указатель, который указывает на последний (в нашем случае, единственный) элемент:
    Затем происходит создание элемента, в информационную часть которого заносится значение 8, а в указатель next значение NULL. После чего tail становится указателем на этот элемент:
    Далее производится проверка: пуста ли очередь (указывает ли head на какой-то элемент или его значение NULL)? В данном случае очередь не пуста, поэтому следующим за элементом, на который указывает t становится элемент, на который указывает tail.
    В итоге получаем очередь из двух элементов, которые находятся в очереди в том же порядке, в каком их туда поместили.
    Функция Get, которая извлекает верхний элемент из очереди, аналогична функции
    Put для стека. Отличием является следующий оператор, добавленный в функцию Get: if
    (head ==
    NULL
    ) tail =
    NULL
    ;
    52
    который говорит о том, что если после удаления элемента очередь становится пустой, то и указатель tail нужно «обнулить». Разберите данную функцию самостоятельно.
    Функция Empty полностью совпадает с соответствующей функцией для стека.
    Замечание. Класс QueueException помещен в отдельный файл exception.срр и выглядит следующим образом:
    #include

    #include

    using namespace std; class
    QueueException
    : public exception
    { public
    :
    QueueException(
    const string
    & message =
    ""
    ): exception
    (message.c_str()) {}
    };
    5.6.
    Решение практических задач с использованием очереди
    1.
    Даны файлы data1.txt и data2.txt, компонентами которых являются натуральные числа. Переписать содержимое файла data1.txt в файл data2.txt и наоборот без использования вспомогательного файла.
    #include

    #include

    using namespace std;
    //подключаем файл с реализацией класса-шаблона очередь
    #include
    "queue.срр"
    int main()
    {
    Queue
    <
    int
    > t; int i;
    //описываем входной поток и связываем его с data1.txt
    ifstream in(
    "data1.txt"
    );
    while
    (in >> i)
    //пока не конец файла считываем из него числа
    t.Put(i);
    //кладем их в очередь
    in.close();
    //закрываем поток, связанный с файлом data1.txt
    //описываем входной поток и связываем его с data2.txt
    ifstream in1(
    "data2.txt"
    );
    //описываем выходной поток и связываем его с data1.txt
    ofstream out(
    "data1.txt"
    );
    while
    (in1 >> i)
    //пока не конец файла data2.txt считываем из него числа
    out << i <<
    " "
    ;
    //записываем в файл data1.txt
    in1.close();
    //закрываем поток, связанный с файлом data2.txt
    53
    out.close();
    //закрываем поток, связанный с файлом data1.txt
    //описываем выходной поток и связываем его с data2.txt
    ofstream out1(
    "data2.txt"
    ); while
    (!t.Empty())
    //пока очередь не пуста
    //выбираем из нее элементы и записываем в data2.txt
    out1 << t.Get() <<
    "
    "
    ;
    out1.close();
    //закрываем поток, связанный с файлом data2.txt
    return
    0;
    }
    Результат работы программы:
    До запуска программы
    ___datal.txt___ ___data2.txt___
    7 515 46 46 25 8 12 45 6 6
    После запуска программы
    ___datal.txt___ ___data2.txt___
    25 8 12 45 6 6 7 515 46 46 2. Дана последовательность натуральных чисел. Создать из них очередь и каждый ее элемент, равный х заменить на элемент равный у. Входная последовательность целых чисел и заданные числа х и у хранятся в файле input.txt, выходная последовательность целых чисел записывается в файл output.txt.
    #include

    #include
    using namespace std;
    //подключаем файл с реализацией класса-шаблона очередь
    #include
    "queue.срр"
    int main()
    {
    Queue
    <
    int
    > t; int i, x, y; ifstream in(
    "input.txt"
    ); ofstream out(
    "output.txt"
    ); in >> x >> y;
    //пока файл не пуст, считываем из него очередной элемент
    //если он равен х, то в очередь помещаем у, иначе исходное число
    while
    (in >> i)
    { if
    (i == x) t.Put(y); else t.Put(i);
    }
    54
    in.close();
    //пока очередь не пуста, извлекаем из нее элементы и записываем
    //в выходной файл
    while
    (!t.Empty())
    out << t.Get() <<
    " "
    ; out.close(); return
    0;
    }
    Результата работы программы:
    ________input.txt________ _______output.txt_______
    70 0 0 1 3 0 5 2 5 0 2 0 9 3 0 0 7 7 1 3 7 5 2 5 7 2 7 9 3 7 7
    5.7.
    Однонаправленный список общего вида
    Мы рассмотрели частные случаи списков (стек и очередь) и их односвязную реализацию. Заметим, что стек имеет одну «точку доступа», очередь - две «точки доступа». В общем случае список можно представить в виде линейной связанной структуры с произвольным количеством «точек доступа» (см рис.5.5), что позволяет определить следующие операции над списком: инициализация списка, добавление и удаление элемента из произвольного места списка, поиск элемента в списке по ключу, просмотр всех элементов без их извлечения списка.
    Рис. 5.5. Структура однонаправленного списка с указателями head на начало списка и cur - на произвольный элемент списка
    Реализация однонаправленного списка зависит от решаемой задачи и предпочтений программиста. Рассмотрим объектно-ориентированную реализацию однонаправленного списка, представленного на рис.5.5.
    #include
    "exception.cpp" template
    <
    class
    Item
    > class
    List
    { struct
    Element
    {
    Item inf;
    Element
    *next;
    Element
    (Item x): inf(x), next(0) {}
    };
    55

    Element
    *head;
    //указатель на начало списка
    int size;
    //количество элементов в списке
    //возвращает указатель на элемент списка с номером index
    Element
    * Find(
    int index)
    { if
    ((index<1)||(index>size))
    //если индекс элемента списка
    {
    //находится вне диапазона, то
    return
    NULL
    ;
    //возвращаем NULL
    } else
    //иначе
    {
    //устанавливаем указатель на начало списка
    Element
    *cur = head;
    for
    (
    int i = 1; i < index; i++)
    //и перемещаемся по
    списку
    {
    //на элемент с номером index
    cur = cur->next;
    } return cur;
    //возвращаем указатель на требуемый элемент
    }
    } public
    :
    List(): head(0), size(0) {}
    //конструктор класса

    List()
    //деструктор класса
    { while
    (!Empty())
    //пока список не пуст
    Remove(1);
    //удаляем первый элемент списка
    } bool
    Empty()
    //проверка пустоты списка
    { return head == 0;
    } int
    GetLength()
    //возвращает количество элементов в списке
    { return size;
    }
    //возвращает значение элемента списка по его номеру
    Item
    Get(
    int index)
    { if
    ((index<1)||(index>size)) throw
    ListException
    (
    "ListException: get — list error"
    );
    56
    else
    {
    Element
    *r = Find(index);
    Item i = r->inf; return i;
    }
    }
    //осуществляет вставку элемента со значением data в позицию index
    void
    Insert(
    int index, Item data)
    { if
    ((index<1)||(index>size+1))
    { throw
    ListException
    (
    "ListException: insert — list error"
    );
    } else
    {
    //создаем новый элемент
    Element
    *newPtr = new
    Element
    (data); size
    = GetLength()+1;
    //увеличиваем размерность списка
    if
    (index == 1)
    //если вставку производим в позицию 1
    {
    //то см. рис. 5.6
    newPtr->next = head; head = newPtr;
    } else
    //иначе см. рис. 5.7
    {
    Element
    *prev = Find(index-1); newPtr->next = prev->next; prev->next = newPtr;
    }
    }
    }
    //осуществляет удаление элемента из списка с номером index
    void
    Remove(
    int index)
    { if
    ((index<1)||(index>size))
    { throw
    ListException
    (
    "ListException: remove — list error"
    );
    } else
    {
    Element
    *cur;
    //объявляем вспомогательный указатель
    --size;
    //уменьшаем размерность списка
    if
    (index==1)
    //если удаляем первый элемент
    {
    //то см. рис. 5.8
    cur = head; head = head->next;
    }
    57
    else
    //иначе см. рис.5.9
    {
    Element
    *prev = Find(index-1); cur = prev->next; prev->next = cur->next;
    } cur->next =
    NULL
    ; delete cur;
    }
    }
    //вывод элементов списка в глобальный поток out
    void
    Print()
    {
    for
    (
    Element
    *cur = head; cur!=
    NULL
    ; cur = cur->next)
    { out << cur->inf <<
    " "
    ;
    } out << endl;
    }
    };
    1   2   3   4   5   6   7   8


    написать администратору сайта