双链表c++中的插入排序

Question

我正在使用插入排序制作一个已排序的双链表，但我似乎遇到了问题。给定的列表是

50 20 60 40 30 100 80 70 90 10

正下方是我编写的部分代码 (void InsertNode(int v))，但结果是 10 20 30 40 60 70 80 90 100 50。 50 排在列表末尾，而它应该在 40 到 60 之间。非常感谢您的帮助。

void InsertNode(int v){
    DblListNode *newNode=new DblListNode; 
    DblListNode *current, *previous;

    newNode->data=v;
    current=previous=first;

    while(current->right!=first){
        if(current->data<v){
            previous=current;
            current=current->right;
        }else break;
    }

    if(newNode==NULL){
        cout<<"No memory for newNode."<<endl;
        exit(1);
    }
    Insert(newNode, previous);
}



void Insert(DblListNode *p, DblListNode *x){
    p->left=x; 
    p->right=x->right;
    x->right->left=p;
    x->right=p;
}

Answer 1

您可以将 while 循环更改为：

do{
    if(current->data<v){
        previous=current;
        current=current->right;
    }else break;
}while(current != first);

否则，您永远不会将 current->right 等于 first 的元素（即最后一个元素）的值与您的值 v.[=14= 进行比较]

双链表c++中的插入排序

Insertion sort in Double Linked List c++

c++

linked-list

insertion-sort