Блог

Я пишу код для сортировки вставки для целочисленных данных в связанный список на c , я ссылался на алгоритмы в Интернете и, наконец, взял следующий код, используя array в качестве базовой концепции для моей версии. однако сортировка всегда игнорирует мой первый элемент (но все остальные элементы упорядочены хорошо).

Я попытался проверить свой оператор цикла, проверяя адрес указателя во время цикла (потому что мой цикл с ключевым указателем в первый раз не попал в цикл указателя судьи), проверяя механизм переключения при сравнении, но я не могу найти свою логическую проблему.

(Я знаю, что кто-то сказал бы, что я не предоставляю достаточно данных, чтобы вы могли мне помочь, но я проверял эти вещи в течение двух дней, в том числе спрашивал друзей и искал решения, существующие на веб-сайте. Поэтому я действительно надеюсь, что кто-нибудь сможет ответить мне без вины, спасибо.)

версия массива (в Интернете)

 #include <iostream>
void InsertionSort(int *arr, int size){
    for (int i = 1; i < size; i  ) {
        int key = arr[i];
        int j = i - 1;
        while (key < arr[j] amp;amp; j >= 0) {
            arr[j 1] = arr[j];
            j--;
        }
        arr[j 1] = key;
    }
}
  

версия связанного списка (моя собственная)

Класс узла, используемый в моей версии

 class Node
{
public:
    Node()
    {
        next = NULL;
        pre = NULL;
    }
    Node(int n)
    {
        data = n;
        next = NULL;
        pre = NULL;
    }
    int getData() { return data; }
    Node *getNext() { return next; }
    Node *getPre() { return pre; }
    void setData(int d) { data = d; }
    void setNext(Node *n) { next = n; }
    void setPre(Node *p) { pre = p; }
private:
    int data;
    Node *next, *pre;
};
  

 class List
{
public:
    List() { list = NULL; }
    List(int n) { generate(n); }

    void generate(int n)
    {
        int j;
        list = NULL;
        for(j = 0;j < n;j   )
            generate();
    }

    void generate()
    {
        Node *buf = new Node(rand());
        buf->setNext(list); //list->NODE2.next->NODE1.next->NULL
        if(list != NULL)
            list->setPre(buf);
        list = buf;
    }
    void insertionSort()
    {
        bool breakByCompare;
        Node* keyptr;
        Node* judgeptr;// judge is the value that is going to compare with key
        int key;
        for(keyptr = list->getNext(); keyptr != NULL; 
            keyptr = keyptr->getNext()){
            //if we set list as 5,7,6 ; 6 is key
            key = keyptr->getData();//store the key value for the setting after shifting
            breakByCompare = 0;

            for(judgeptr = keyptr->getPre() ; judgeptr->getPre()!= NULL; 
                judgeptr= judgeptr->getPre()){
                //list: 5,7,6 ; 7 is judge

                if(judgeptr->getData() > key){
                    // 7>6, so we shift 7 to the position which was for 6

                    judgeptr->getNext()->setData(judgeptr->getData());// list: 5,7,7 ;
                    cout << judgeptr->getData() << " , " << keyptr->getData() << endl;
                }
                else{
                    break;
                }
            }
            judgeptr->getNext()->setData(key);// list: 5,6,7
        }
    }
    void print()
    {
        Node *cur = list;
        while(cur != NULL)
        {
            cout<<cur->getData()<<" ";
            cur = cur->getNext();
        }
        cout<<endl;
    }
private:
    Node *list;
};
  

 #include <iostream>
#include <cstdlib>
#include <cstdio>
#include <ctime>
#define SIZE 100
int main()
{
    srand(time(NULL));
    List *l = new List(10);
    l->print();
    l->insertionSort();
    l->print();

}
  

Одно из наиболее важных различий между связанным списком и массивом заключается в том, что иногда требуется обрабатывать первый элемент как особый случай.

Вот исправленная версия вашего метода сортировки :

 void insertionSort()
{
    bool breakByCompare;
    Node* keyptr;
    Node* judgeptr;
    int key;
    for(keyptr = list->getNext(); keyptr != NULL;  keyptr = keyptr->getNext()){
        
        key = keyptr->getData();
        breakByCompare = 0;
        
        // I replaced judgeptr->getPre() by judgeptr in the condition
        // to allow the backward loop to go until the root
        for(judgeptr = keyptr->getPre() ; judgeptr != NULL;  judgeptr= judgeptr->getPre()){
            
            if(judgeptr->getData() > key){
                judgeptr->getNext()->setData(judgeptr->getData());
                cout << judgeptr->getData() << " , " << key << endl;
            }
            else break;
        }
        // Here is the special case : we must support a null judgeptr 
        // and replace its next element by the list
        if (judgeptr) judgeptr->getNext()->setData(key);
        else list->setData(key);
    }
}