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

  • Проход по списку в обратном порядке

  • Замечание

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


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

    Замечание. Класс ListException помещен в отдельный файл exception.срр и выглядит следующим образом:
    #include
    "exception"
    #include
    "string"
    using namespace std; class
    ListException
    : public exception
    { public
    :
    ListException
    (
    const string
    & message=
    ""
    ): exception
    (message.c_str()) {}
    };
    Более подробно основные операции с однонаправленными списками рассмотрим на примере членов-функций класса List.
    1. Проход по списку (например, член-функции Print)
    Для реализации этого действия необходим вспомогательный указатель, который вначале устанавливается на первый элемент списка, а потом «пробегает» весь список, указывая поочередно на каждый элемент.
    Чтобы установить указатель на первый элемент списка выполняем команду:
    Element
    *cur=head;
    Для вывода содержимого текущего узла в глобальный поток out используется оператор: out<inf;
    Для перехода на следующий узел используется команда: cur=cur->next;
    58

    И заканчивается проход по списку тогда, когда указатель cur примет значение
    NULL.
    В результате получаем цикл: for (
    Element
    *cur = head; cur!=
    NULL
    ; cur = cur-> next)
    { cout << cur->inf <<
    " "
    ;
    }
    Замечание Аналогичный прием используется в функции Find, которая возвращает указатель на элемент списка с номером index Отличие только в том, что мы завершаем перемещение по списку тогда, когда найдем элемент с заданным номером.
    2. Вставка нового элемента в список в заданную позицию (на примере член- функции Insert).
    Существует два варианта вставки элемента в список.
    Вариант первый - это вставка элемента в начало списка. В этом случае, нам необходимо последовательно выполнить две команды: newPtr->next = head;
    //1
    head = newPtr;
    //2
    Заметим, что вставка в пустой список - это вставка элемента в начало списка, у которого head=NULL.
    Второй вариант - вставка элемента в середину списка. В этом случае нам необходимо знать указатель на предшествующий элемент. Это можно сделать с помощью команды:
    Element
    *prev=Find(index-1);
    Следующие команды позволят нам вставить новый элемент в заданную позицию: newPtr->next = prev->next;
    //1
    prev->next = newPtr;
    //2
    59

    Рис. 5.7. Вставка элемента в середину списка
    Заметим, что вставка элемента в конец списка пройдет корректно, т.к. указатель prev определен и указатель prev->next равен NULL,
    3. Удаление элемента из списка (на примере член-функции Remove)
    Так же как и при вставке элемента в список существует два варианта. Первый вариант - удаление первого элемента из списка. В этом случае, нам необходимо последовательно выполнить две команды: cur = head;
    //1
    head = head->next;
    //2
    Рис. 5.8. Удаление первого элемента из списка
    Второй вариант - вставка элемента в середину списка. В этом случае нам необходимо знать указатель на предшествующий элемент. Это можно сделать с помощью команды:
    Element
    *prev = Find(index-1);
    Следующие команды позволят нам удалить требуемый элемент: cur = prev->next;
    //1
    prev->next = cur->next;
    //2
    Рис. 5.9. Удаление элемента из середины списка
    Заметим, что удаление элемента из конца списка пройдет корректно, т.к. указатель prev определен и указатель prev->next равен NULL.
    Замечание. При работе со стеком и очередью нам не требовался деструктор, т.к. обработка стека и очереди подразумевает извлечение из них элементов. В результате чего в конце работы указанные виды списков остаются пустыми. При работе со списками общего
    60
    вида элементы из него могут и не извлекаться. Поэтому нам требуется корректно освободить память, выделенную под список. Что и делает деструктор.
    5.8.
    Решение практических задач с использованием однонаправленных
    списков
    1.
    Дана последовательность натуральных чисел. Создать из них список и после каждого элемента равного х вставить элемент равный у. Входная последовательность целых чисел и заданные числа х и у хранятся в файле input.txt, выходная последовательность целых чисел записывается в файл output.txt.
    #include

    #include

    using namespace std;
    //подключаем файл с реализацией класса-шаблона список
    #include
    "list.cpp"
    //подключаем глобальные потоки
    ifstream in(
    "input.txt"
    ); ofstream out(
    "output.txt"
    ); int main()
    {
    List
    <
    int
    > l; int value, x, y; in >> x >> y;
    //пока файл не пуст, считываем из него очередной элемент и
    //помещаем в список; позиция, в которую вставляем новый элемент
    //будет на 1 больше, чем количество элементов в списке
    while
    (in >> value)
    l.lnsert(l.GetLength()+1.value); in.close(); out <<
    "Исходный список: "
    ; l.Print();
    //просматриваем список поэлементно
    for
    (
    int i = 1; i <= l.GetLength(); i++)
    { if
    (l.Get(i)==x)
    //если значение элемента в i-той позиции равно х
    { l.lnsert(i+1 ,у);
    //вставляем элемент у в эту позицию
    i++;
    }
    } out <<
    "Измененный список:"
    ; l.Print();
    61
    l.

    List();
    //вызываем деструктор
    out.close(); return
    0;
    }
    Результата работы программы:
    ______input.txt ________ __________________ output.txt _______________________
    7 0
    Исходный список: 7 7 1 3 7 5 2 5 7 2 7 9 3 7 7 7 7 1 3 7 5 2 5 7 2 7 9 3 7 7
    Измененный список: 7 0 7 0 1 3 7 0 5 2 5 7 0 2 7 0 9 3 7 0 7 0 2.
    Дана последовательность натуральных чисел. Создать из них очередь и каждый ее элемент, равный х заменить на элемент равный у. Входная последовательность целых чисел и заданные числа х и у хранятся в файле input.txt, выходная последовательность целых чисел записывается в файл output.txt.
    Решение данной задачи можно свести к применению двух член-функций Insert и
    Remove. Так в функции main можно перебрать все элементы списка и, если встречаем элемент равный х, то удаляем его, а на его место вставляем элемент равный у. Этот алгоритм можно реализовать следующим способом: for
    (
    int i = 1; i <= l.GetLength(); i++)
    { if
    (l.Get(i) == x)
    { l.Remove(i); l.lnsert(i,y);
    }
    }
    Однако для решения данной задачи более рационально добавить новую член- функцию Change в класс List. В функции Change мы просматриваем все элементы списка и, если значение очередного элемента совпадает со значением х, то заменяем значение этого элемента на у. Это алгоритм можно реализовать следующим способом: void
    Change(
    ltem х,
    Item у)
    {
    Element
    *cur = head;
    //устанавливаем указатель на начало списка
    //перебираем элементы списка по очереди
    for
    (
    Element
    *cur = head; cur !=
    NULL
    ; cur = cur->next)
    { if
    (cur->inf == x)
    //если элемент равен x
    { cur->inf = y;
    //заменяем его на у
    }
    }
    }
    Второй способ решения задачи соответствует идеологии ООП, а добавление новой член-функции в класс List, существенно расширяет его функциональные возможности.
    62

    Теперь полное решение данной задачи выглядит следующим образом:
    #include

    #include

    using namespace std;
    #include
    "list.cpp"
    //не забудьте добавить функцию Change в класс List
    ifstream in(
    "input.txt"
    ); ofstream out(
    "output.txt"
    ); int main()
    {
    List
    <
    int
    > l; int value, x, y; in >> x >> y; while
    (in >> value)
    { l.lnsert(l.GetLength()+1,value);
    } in.close(); out <<
    "Исходный список:"
    ; l.Print(); l.Change(x, y);
    //вызов член-функции Change
    out <<
    "Измененный список:"
    ; l.Print(); lList(); out.close(); return
    0;
    }
    Результата работы программы:
    ______input.txt_______ _____________output.txt_______________
    7 0
    Исходный список: 7 7 1 3 7 5 2 5 7 2 7 9 3 7 7 7 7 1 3 7 5 2 5 7 2 7 9 3 7 7
    Измененный список: 0 0 1 3 0 5 2 5 0 2 0 9 3 0 0
    5.9.
    Двунаправленный список
    До сих пор мы рассматривали однонаправленные списки. В таких списках можно передвигаться лишь в одном направлении, а чтобы, например, удалить элемент, необходимо иметь указатель на предыдущий элемент. Однако иногда требуется одинаково эффективно передвигаться по списку в обоих направлениях. В этом случае используют двунаправленные списки, когда в каждом узле имеются два указателя: на следующий и на предыдущий элемент:
    63

    Рис. 5.10. Структура двунаправленного списка
    Базовый элемент двунаправленного списка содержит:

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

    поля-указатели next и prev, в которых хранятся адреса следующего и предыдущего элементов двунаправленного списка соответственно, и которые будут использоваться для организации связи элементов.
    Замечание В общем случае базовый элемент списка может содержать несколько информационных полей
    Предложенный базовый элемент двунаправленного списка может быть описан следующим образом: struct
    Element
    {
    Item inf;
    //информационное поле типа Item
    Element
    *next;
    //указатель на следующий элемент списка
    Element
    *prev;
    //указатель на предыдущий элемент списка
    Element(
    Item х): inf(x), next(0), prev(0) {}
    }
    Поскольку в каждом узле такого списка задействовано два указателя вместо одного, механизм операций вставки и удаления будет несколько усложнен по сравнению с односвязными списками. Зато можно удалять элемент, на который есть указатель, и вставлять элементы до и после заданного, не задействуя дополнительные указатели.
    Приведем объектно-ориентированную реализацию двунаправленного списка, а затем подробно рассмотрим базовые операции с данным видом списка.
    Внимание! Код ниже не редактировался (сил уже моих нет), там могут быть опечатки! Лучше смотрите его в печатной версии методички или качайте исходники с гитхаба (ссылка на второй странице).
    #include
    "exception.cpp"
    template
    <
    class
    Item
    > class
    DoubleLinkedList
    { struct
    Element
    {
    Item inf;
    Element
    *next;
    Element
    *prev;
    Element(
    Item x): inf(x), next(0), prev(0) {}
    };
    64

    Element
    *head;
    Element
    *tail; int size;
    //возвращает указатель на элемент списка с номером index
    Element
    *Find (
    int index)
    { if
    ((index<1)||(index>size))
    { return
    NULL
    ;
    } else
    {
    Element
    *cur=head; for
    (int i=1; i{ cur=cur->next;
    } return cur;
    }
    } public
    :
    DoubleLinkedList():head(0),tail(0),size(0)
    //конструктор
    {
    }
    DoubleLinkedList()
    //деструктор
    { while
    (!Empty())
    {
    Remove(1);
    }
    } bool
    Empty()
    //проверяет список на пустоту
    { return head==0;
    } int
    GetLength()
    //возвращает количество элементов в списке
    { return size;
    }
    //возвращает значение элемента списка по его номеру
    Item
    Get(
    int index)
    { if
    ((index<1)||(index>size))
    {
    65
    throw
    DoubleListException
    (
    "Exception: get— double-linked list error"
    );
    } else
    {
    Element
    *r=Find(index);
    Item i=r->inf; return i;
    }
    }
    //осуществляет вставку элемента со значением data слева от
    //элемента с позицией index
    void lnsertLeft(
    int index,
    Item data)
    { if
    ((index<1)||(index>size+1))
    { throw
    DoubleListException
    (
    "Exception:
    insert — double-linked list error
    ");
    } else
    {
    Element
    *newPtr = new
    Element
    (data); size = GetLength()+1;
    //увеличиваем размерность списка
    //устанавливаем указатель на элемент списка с заданным
    номером
    Element
    *cur=Find(index);
    //если этот указатель NULL, то список был пуст, поэтому
    //новый элемент будет и первым и последним
    if
    (cur==
    NULL
    )
    //см. рис. 5.11.
    { head = newPtr; tail = newPtr;
    } else
    //иначе производим вставку в непустой список, при этом
    //есть два случая: 1 -частный случай (вставка перед
    //первым элементом списка), 2 - общий случай
    { newPtr->next=cur; newPtr->prev=cur->prev; cur->prev=newPtr; if
    (cur==head)
    { head=newPtr;
    //случай 1
    } else
    { newPtr->prev->next=newPtr;
    //случай 2
    66

    }
    }
    }
    }
    //осуществляет вставку элемента со значением data слева от
    //элемента с позицией index
    void lnsertRight(
    int index,
    Item data)
    { if
    ((index<1&&head!=
    NULL
    )||(index>size+1))
    { throw
    DoubleListException
    (
    "Exception: insert — double-linked list error"
    );
    } else
    {
    Element
    *newPtr=
    new
    Element
    (data); size= GetLength()+1;
    //увеличиваем размерность списка
    //устанавливаем указатель на элемент списка с заданным
    номером
    Element
    *cur=Find(index);
    //если этот указатель NULL, то список был пуст, поэтому
    //новый элемент будет и первым и последним
    if
    (cur==
    NULL
    )
    { head=newPtr; tail=newPtr;
    } else
    //иначе производим вставку в непустой список, при этом
    //есть два случая: 1 - вставка после последнего элемента
    //списка, 2 - вставка в середину списка
    { newPtr->next=cur->next; newPtr->prev=cur; cur->next=newPtr; if
    (cur==tail)
    { tail=newPtr;
    //случай 1
    } else
    { newPtr->next->prev=newPtr;
    //случай 2
    }
    }
    }
    }
    //осуществляет удаление элемента с номером index из списка
    67

    //выделяем четыре случая: 1 - после удаления список становится
    пустым,
    //2 - удаляем первый элемент, 3 - удаляем последний элемент,
    // 4 - общий случай
    void
    Remove(
    int index)
    { if
    ((index<1)||(index>size))
    { throw
    DoubleListException
    (
    "Exception: remove — double- linked list error"
    );
    } else
    {
    //устанавливаем указатель на заданный элемент
    Element
    *cur=Find(index);
    --size
    //уменьшаем размерность списка
    if
    (size==0)
    //случай 1
    { head=
    NULL
    ; tail=
    NULL
    ;
    } else if
    (cur==head)
    //случай 2
    { head=head->next; head->prev=
    NULL
    ;
    } else if
    (cur==tail)
    //случай 3
    { tail=tail->prev; tail->next=
    NULL
    ;
    } else
    //общий случай, см.рис. 5.14
    {
    cur->prev->next=cur->next; cur->next->prev=cur->prev;
    } cur->next=
    NULL
    ; cur->prev=
    NULL
    ; delete cur;
    }
    }
    //вывод элементов списка в глобальный поток out в прямом порядке
    void
    PrintLeftToRight()
    { for
    (
    Element
    *cur = head; cur!=
    NULL
    ; cur = cur->next)
    { out << cur->inf<<
    " "
    ;
    } out<68

    }
    //вывод элементов списка в глобальный поток out в обратном порядке
    void
    PrintRightToLeft ()
    { for
    (Element *cur = tail; cur!=
    NULL
    ; cur = cur->prev)
    { out << cur->inf<<
    " "
    ;
    } out<}
    };
    Замечание. Класс DoubleListException помещен в отдельный файл exception.cpp и выглядит следующим образом:
    #include
    "exception"
    #include
    "string"
    using namespace std; class
    DoubleListException
    : public exception
    { public
    :
    DoubleListException(
    const string
    & message=
    ""
    ): exception
    (message.c_str()) {}
    };
    Более подробно основные операции с двунаправленными списками рассмотрим на примере член-функций класса DoubleLinkedList.
    1. Проход по списку в обратном порядке (на примере член-функции
    PrintRightToLeft)
    Для реализации этого действия необходим вспомогательный указатель, который вначале устанавливается на последний элемент списка, а потом «пробегает» весь список в обратном порядке по указателям prev.
    Чтобы установить указать на первый элемент списка, выполняем команду:
    Element *cur=head;
    Для вывода содержимого текущего узла в глобальный поток out используется оператор: out<inf;
    Для перехода на следующий узел используется команда: cur=cur->prev;
    И заканчивается проход по списку тогда, когда указатель cur примет значение
    NULL.
    В результате получаем цикл: for
    (
    Element
    *cur = tail; cur!=
    NULL
    ; cur = cur-> prev)
    { out << cur->inf <<
    " "
    ;
    }
    69

    Замечание. Проход по списку в прямом порядке используется в функции
    PrintLeftToRight. Рассмотрите данную функцию самостоятельно.
    2.
    Вставка нового элемента в список слева от заданной позиции (на примере член-функции InsertLeft).
    При вставке нового элемента в двунаправленный список слева от заданной позиции нужно рассмотреть несколько возможных ситуаций.
    Если первоначально список пустой, то новый элемент станет одновременно первым и последним. Для этого необходимо установить указатели head и tail на новый элемент:
    Рис. 5.11. Добавление элемента в пустой список
    Если список не пустой, то возможны два случая: частный - вставка перед первым элементом в списке (см. рис 5.12), и общий случай - вставка в произвольное место списка
    (5.13). Рассмотрим фрагмент функции InsertLeft более подробно на рисунках: newPtr->next=cur;
    //1 newPtr->prev=cur->prev;
    //2 cur->prev=newPtr;
    //3
    if
    (cur==head)
    //4
    { head=newPtr;
    //5
    } else
    { newPtr->prev->next=newPtr;
    //6
    }
    Рис. 5.12 Частный случай вставки нового элемента в начало двунаправленного списка
    70

    Рис. 5.13 Общий случай вставки нового элемента в двунаправленный список слева от заданной позиции
    Как видно из рисунков, вставка элемента в список требует аккуратной работы с указателями. В противном случае, будет нарушена целостность списка, а также последовательность расположения элементов в списке.
    1   2   3   4   5   6   7   8


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