如何在双向链表中插入一个元素并保持其排序 - c ++

Question

这是c ++中双向链表的实现..我尝试在链表中插入元素，所以我在打印前添加了数字2,2,2,4,8,7，我调用quicksort函数快速排序替换最后一个元素（ 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 ;
}

Answer 1

我解决了许多小问题，如造型和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;
}