使用链表和指针的插入排序

Question

我需要使用插入排序对链表进行排序。元素看起来像这样 [ 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 ]

排序的结果应该是这样的 [ 0 0 0 0 0 1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 ]

问题是我的结果是这样的 [ 3 2 1 0 3 2 1 0 3 2 1 0 3 2 1 0 3 2 1 0 ]

我不确定为什么...我觉得它应该有效...但也许其他人会发现问题。

主要：

int main (int argc, char **argv) {

IntElement *ints[N_ELEMENTS];
for (int i = 0; i < N_ELEMENTS; i++) {
    ints[i] = new IntElement (i%4);
}
SortedList slist;
for (int i = 0; i < N_ELEMENTS; i++) {
    slist.addElement (ints[i]);
}
slist.print();
printf ("last = %s\n", slist.get (slist.size ()-1)->toString ());`

.cpp 文件中的排序函数

void SortedList::addElement(IElement * element)
{
entryPtr n = new entry;
n->next = NULL;
n->me = element;
curr = head;

if (curr == NULL) {
    //Executes when linked list is empty
    head = n;
    return;
}

if (n->me < curr->me)
{
    //Executes if given data is less than data in first node of linked list
    n->next = head;
    head = n;
    return;
}
else 
{
    while (curr != NULL)
    {
        if (n->me>curr->me)
        {
            //Traverse to location we want to insert the node + 1 node
            prev = curr;
            curr = curr->next;
            continue;
        }
        else
        {
            //Insert the node
            prev->next = n;
            n->next = curr;
            return;
        }
    }
    //Insert node at last
    prev->next = n;

}

}

.h 文件

class SortedList {

protected:

typedef struct entry {                                      // stores an element and a pointer to the next element in the list
    IElement *me;
    entry *next;
}*entryPtr;

entryPtr head;
entryPtr curr;
entryPtr prev;
entryPtr temp;

public:

SortedList();
 ~SortedList() {};

void addElement(IElement *element);           // adds element to the list and returns position, -1 if not added
IElement *get(int position);                  // returns element at given position
int size();                                   // returns the number of elements in the list
void print(FILE *file = stdout);             // prints all elements
};

感谢您的帮助

Answer 1

而不是比较像这样的语句中指针指向的值

if (n->me < curr->me)

你正在比较指针本身。

你应该像这样重写条件

if ( *n->me < *curr->me )

使用链表和指针的插入排序

insertion sort using linked list and pointers

c++

sorting

linked-list

insertion-sort

singly-linked-list