С++: Двусвязные Списки

Тема в разделе "C/C++/C#", создана пользователем inek, 9 май 2012.

Наш партнер Genesis Hackspace
  1. inek

    inek Гость

    Дан шаблон класса для работы с двунаправленным некольцевым списком.
    В шаблоне реализовала следующие действия:
    добавление звена в начало списка;
    удаление звена из начала списка;
    добавление звена в произвольное место списка, отличное от начала (например, после звена, указатель на которое задан);
    удаление звена из произвольного места списка, отличного от начала (например, после звена, указатель на которое задан);
    проверка, пуст ли список;
    очистка списка;
    формирование списка;
    печать списка.

    ЗАДАЧА: Необходимо удалить все элементы между минимальным и максимальным элементами.

    Функцию нахождения минимума и максимума написала, помогите дописать ее для удаления элементов между min и max.

    Вот шаблон:
    Код (C++):
    #include <iostream>

    using namespace std;

    template <typename T>
    class ListD
    {
    struct Node
    {
    T data;
    Node *next, *prev;
    Node(T d, Node *n = 0, Node *p = 0):data(d), next(n), prev(p) {}
    };
    Node *head;
    public:
    ListD(Node *h = 0):head(h){}
    ~ListD();
    bool isEmpty();
    void insertAfter(Node *pre, T d);
    void removeAfter(Node *pre);
    void pushFront(T d);
    T popFront();
    void print();
    Node *search(T d);
    void create(int k);
    Node *searchMinMax();
    // void MinMax();
    //void createFrom(List<T> *L1);
    };

    template <typename T>
    ListD<T>::~ListD()
    {
    while (!isEmpty())
    popFront();
    }

    template <typename T>
    bool ListD<T>::isEmpty()
    {
    return !head;
    }

    template <typename T>
    void ListD<T>::insertAfter(Node *pre, T d)
    {
    if(!pre) return;
    Node *newNode = new Node(d,0,0);
    newNode->prev = pre;
    newNode->next = pre->next;
    pre->next = newNode;
    }

    template <typename T>
    void ListD<T>::removeAfter(Node *pre)
    {
    if (!pre || !pre->next) return;
    Node *tmp = pre->next;
    if (!tmp->next)
    {
    pre->next = NULL;
    }
    else
    {
    tmp->next->prev = pre;
    pre->next = tmp->next;
    }
    delete tmp;
    }

    template <typename T>
    void ListD<T>::pushFront(T d)
    {
    Node *newNode = new Node(d,0,0);
    if(!head) {
    head = newNode;
    return;
    }
    newNode->next = head;
    newNode->prev = NULL;
    head->prev = newNode;
    head = newNode;
    }

    template <typename T>
    T ListD<T>::popFront()
    {
    T data;              
    if(!head) return data;
    Node *tmp = head;
    data = head->data;
    if(head->next) {
    head = head->next;
    head->prev = NULL;
    delete tmp;
    return data;
    }
    delete tmp;
    head = NULL;
    return data;
    }

    template <typename T>
    typename ListD<T>::Node* ListD<T>::search(T d)
    {
    if(!head) return NULL;
    Node* cur = head;
    while(cur) {
    if(cur->data == d) return cur;
    cur = cur->next;
    }
    return NULL;
    }


    template <typename T>
    void ListD<T>::print()
    {
    if(!head) return;
    Node *cur = head;
    while(cur) {
    cout << cur->data << "; ";
    cur = cur->next;
    }
    cout << endl;
    }

    template <typename T>
    void ListD<T>::create(int k)
    {
    T d;
    for (int i = 1; i <= k; i++)
    {
    cout << "Enter " << i << "-i element: ";
    cin >> d;
    pushFront(d);
    }
    }

    template <typename T>
    typename ListD<T>::Node* ListD<T>::searchMinMax()
    { T min;
    T max;
    Node* cur = head;
    min = cur->data;
    max = cur->data;
    while(cur) {
    if(min > cur->data ) {min = cur->data;}
    if(max < cur->data ) {max = cur->data;}
    cur = cur->next;
    }
    cout << "Min " << min << ": ";
    cout << "Max " << max << ": ";
    }
    Функция main:
    Код (C++):
    #include "List.h"
    #include "ListD.h"
    #include <string>
    #include <iostream>

    using namespace std;

    int main()
    {

    ListD<string> *L = new ListD<string>();
    L->create(7);
    L->print();
    L->searchMinMax();

    system("PAUSE");
    return EXIT_SUCCESS;
    }
    Заранее благодарна!
     
  2. rrrFer

    rrrFer Well-Known Member
    Команда форума C\C++ Team

    Регистрация:
    6 сен 2011
    Сообщения:
    1.319
    Симпатии:
    45
    поправил ваш код, допишите сами?
    Код (Text):
    template <typename T>
    typename ListD<T>::Node* ListD<T>::searchMinMax(){
    Node* min = head, *max = head;
    Node* cur = head;

    int nmin, nmax, i, t;

    min = max = cur;
    for( nmin = nmax = i = 0;cur;i++) {
    if(min ->data > cur->data ) {
    min = cur;
    nmin = i;
    }
    if(max ->data < cur->data ) {
    max = cur;
    nmax = i;
    }
    cur = cur->next;
    }

    if( nmin < nmax ) {
    i = nmax - nmin;
    cur = min;
    }
    else {
    cur = max;
    i = nmin - nmax;
    }

    //осталось удалить i элементов начиная с указателя cur


    cout << "Min " << min << ": ";
    cout << "Max " << max << ": ";

    return 0;
    }
     
  3. inek

    inek Гость

    спасибо! буду пробовать!
     
Загрузка...

Поделиться этой страницей