Как вставить элемент в двусвязный список и сохранить его отсортированным - c ++ - PullRequest
Новая
       18

Как вставить элемент в двусвязный список и сохранить его отсортированным - c ++

0 голосов
/ 26 апреля 2019

Это реализация двусвязного списка в c ++. Я пытаюсь вставить элементы в свой связанный список, поэтому я добавил числа 2, 2, 2, 4, 8, 7 перед печатью, я вызываю функцию быстрой сортировки, которая заменяетпоследний элемент (7) с предыдущим элементом (8) ..print выводит результат: 2,2,2,4, 7, 7 Как этот код можно изменить, чтобы получить правильный результат Вот мой код ..

#include <iostream>
using namespace std ;

template <class T>
class node
{
public :

    T data;
    node * next;
    node * previous ;
};

template <class T>
class LinkedList
{

public:

    string delimeter; // optional: just for printing
    node<T>* addSorted(T v)
    {
       insert(T) ;
       _quicksort(first , last) ;

    }
    void swap ( T* a, T* b )
    {
        T t = *a;
        *a = *b;
        *b = t;
    }  


    node<T>* get(T v)
    {
        bool found = false ;
        node<T> * Curr = first ;
        while (!found)
        {
            if (Curr-> data == v )
                found = true;
            else
                Curr = Curr-> next;
        }
        return Curr ;
    }


    // operator overloading for printing
    friend ostream& operator<<(ostream& o, LinkedList<T> & c);


    LinkedList()
    {
        node<T> * curr = new node<T> ;

        first = last = curr;
        first->next = last ;
        first-> previous  = NULL;
    }


    LinkedList(T value, int initial_size)   // make n elements = value
    {
        node<T> * tempNode ;
        node<T> * curr = new node<T> ;

        first = last = curr;
        first->previous  =NULL;

        for(int i = 0 ; i < initial_size ; i++)
        {
            tempNode = new node<T>;
            tempNode->data = value ;
            tempNode->next = first;
            first->previous  = tempNode;
            first = tempNode ;

        }
    }


    ~LinkedList()
    {
        node<T> * current ;

        while (first  !=  last)
        {

            current = first ;
            first = first-> next;
            delete current;
        }
        delete last;
    }


    void print()
    {
        _quickSort(first, last);
       //bubbleSort(first) ;

        node<T> * Curr = first ;
        while (Curr != NULL)
        {
            cout << Curr-> data <<"\t";
            Curr = Curr-> next;
        }
        cout << endl;
    }

    int _size()        // returns No. of elements
    {
        int NumOfelements = 0;
        node<T> * temp = first ;
        while (temp != last)
        {
            NumOfelements++;
            temp = temp->next;
        }
        return NumOfelements ;
    }

    void insert(T value )
    {
        node<T> * temp = first ;
        node<T> * dummy ;
        node<T> * n = new node<T> ;
        n->data = value;

        last->data = value;
        last->next = n;
        n->previous = last;
        last = n;
        return;
        while (temp != nullptr)
        {
            dummy = temp ;
            temp = temp->next;
            if(temp==last)
            {
                return;
            }
        }

        dummy ->next = n ;
        n -> previous = dummy;
        n -> next = temp ;
        temp-> previous =n;

      // _quickSort(first, last) ;
       //bubbleSort(first) ;

    }

    /* Considers last element as pivot,  places the pivot element at its
    correct position in sorted array,  and places all smaller (smaller than
    pivot) to left of pivot and all greater elements to right of pivot */
    node<T>* pivot_partition(node<T> *f, node<T> *l)
    {
        // set pivot as l element
        T x = l->data;
        node<T> *i = f-> previous;

        for (node<T> *j = f; j != l; j = j->next)
        {
            if (j->data <= x)
            {
                if (i == NULL)
                    i = f ;
                else
                    i =  i-> next ;

                swap(&(i->data), &(j->data));
            }
        }
        i = (i == NULL)? f : i->next; // Similar to i++
        swap(&(i->data), &(l->data));
        return i;
    }

    /* A recursive implementation of quicksort for linked list */
    void _quickSort(node<T> *first, node<T> *last )
    {
        if (last != NULL && first != last && first != last->next)
        {
            node<T> *p = pivot_partition(first, last);
            _quickSort(first, p->previous);
            _quickSort(p->next, last);
        } 
    }

    T mylast () // even this returns 7 not 8
    {
        return last->data ;
    }

private:
    node<T> * first ;
    node<T> * last ;

};
int main (){
    LinkedList <int> l(2,3) ;


    l.insert(4) ;
    l.insert(8) ;
    l.insert(7) ;

l.print() ;
    return 0 ;
}

1 Ответ

0 голосов
/ 27 апреля 2019

Я исправил множество мелких проблем, таких как стиль и nullptr.Но большие проблемы были в конструкторе и в insert.Конструктор создал один элемент для многих и инициализировал его значением по умолчанию.Метод insert перезаписал последний элемент.В следующий раз, пожалуйста, используйте инструмент для стиля кода, прежде чем публиковать его здесь. 

#include <iostream>
using namespace std;

template <class T>
class node {
public:
    T data;
    node* next;
    node* previous;
};

template <class T>
class LinkedList {
public:
    string delimeter;
    node<T>* addSorted(T v) {
       insert(v);
       _quicksort(first , last);

    }

    void swap(T* a, T* b) {
        T t = *a;
        *a = *b;
        *b = t;
    }  

    node<T>* get(T v) {
        bool found = false;
        node<T>* Curr = first;
        while (!found) {
            if (Curr->data == v )
                found = true;
            else
                Curr = Curr->next;
        }
        return Curr;
    }

    friend ostream& operator<<(ostream& o, LinkedList<T>& c);

    LinkedList() {
        node<T>* curr = new node<T>;

        first = last = curr;
        first->next = last ;
        first->previous = nullptr;
    }

    LinkedList(T value, int initial_size) {
        if (initial_size <= 0) return;
        node<T>* tempNode;
        node<T>* curr = new node<T>;
        curr->data = value;

        first = last = curr;
        first->previous = nullptr;

        for(int i = 0; i < initial_size - 1; i++) {
            tempNode = new node<T>;
            tempNode->data = value;
            tempNode->next = first;
            first->previous = tempNode;
            first = tempNode;
        }
    }

    ~LinkedList() {
        node<T>* current;

        while (first !=  last) {
            current = first;
            first = first->next;
            delete current;
        }
        delete last;
    }

    void print() {
        _quickSort(first, last);

        node<T>* Curr = first;
        while (Curr != nullptr) {
            cout << Curr->data << "\t";
            Curr = Curr->next;
        }
        cout << endl;
    }

    int _size() {
        int NumOfelements = 0;
        node<T>* temp = first;
        while (temp != last) {
            NumOfelements++;
            temp = temp->next;
        }
        return NumOfelements;
    }

    void insert(T value) {
        node<T>* temp = first;
        node<T>* dummy;
        node<T>* n = new node<T>;
        n->data = value;

        last->next = n;
        n->previous = last;
        last = n;
        return;
        while (temp != nullptr) {
            dummy = temp;
            temp = temp->next;
            if (temp == last) {
                return;
            }
        }

        dummy->next = n ;
        n->previous = dummy;
        n->next = temp;
        temp->previous = n;
    }

    node<T>* pivot_partition(node<T>* f, node<T>* l) {
        T x = l->data;
        node<T>* i = f->previous;

        for (node<T>* j = f; j != l; j = j->next) {
            if (j->data <= x) {
                if (i == nullptr)
                    i = f;
                else
                    i = i->next;

                swap(&(i->data), &(j->data));
            }
        }
        i = (i == nullptr) ? f : i->next;
        swap(&(i->data), &(l->data));
        return i;
    }

    void _quickSort(node<T>* first, node<T>* last) {
        if (last != nullptr && first != last && first != last->next) {
            node<T>* p = pivot_partition(first, last);
            _quickSort(first, p->previous);
            _quickSort(p->next, last);
        } 
    }

    T mylast() {
        return last->data;
    }

private:
    node<T>* first;
    node<T>* last;
};

int main() {
    LinkedList<int> l(2,3);

    l.insert(4);
    l.insert(8);
    l.insert(7);

    l.print();
    return 0;
}
...