升序排序 - 链表

Question

我在了解这个函数如何工作以及我需要做什么方面遇到了一点麻烦。我的数据类型是 int 编号，节点 * 在我的节点类中下一个。我也有节点指针头，电流和温度。我的问题是我将如何按顺序排列整数列表？此外，升序和递减如何在单个链表中工作？

我的头文件：

#ifndef SDI_LL                      
#define SDI_LL                      
namespace SDI
{                                                       
    class LinkedList                                                                    
    {
        class Node                                      
        {
        public:
            int number;                                 //data element
            Node* next;                                 //pointer to next, node inside each node
        private:
        };
    private:
        Node *head;
        Node *current;                                  //head, current and temp node pointers
        Node *temp;
    public:
        LinkedList();                                   //constructor to access nodes from above
        ~LinkedList();                                  //destructor
        void insert(int add);                           
        void remove(int remove);                        //functions that access private data nodes above
        void display();
        void reverse();
        void search(int searchNum);
        void sortAscending();
        void sortDecending();
        void saveAll();
        void restoreAll();
    };
}
#endif

到目前为止，我的升序函数从头开始并搜索列表：

void LinkedList::sortAscending()
{
    current = head;
    for (current = head; current;)
    {
        temp = current;
        current = current->next;
    }
}

Answer 1

通常，应使用标准库中提供的容器，这些容器在适用的情况下提供有效的排序方法。

也就是说，如果你想出于学习目的这样做 - 因为你可能"至少应该一次" - 那么实施起来并不难。

for (current = head; current;)

这是一个有趣的for循环，我个人更喜欢：

current = head;
while(current)  // or current != nullptr to be more explicit

另请注意，您（当然，不必要地）将head分配给current两次 - 紧接在for循环之前，以及在初始化时。

一个简单的方案（但一点效率都没有！）可能是在循环访问列表时交换"无序"元素，直到不需要交换：

bool changeMade;
do{
    changeMade = false;
    current = head;
    while( current ){
        temp = current;
        current = current->next;
        if( current && current->data < temp->data ){
            changeMade = true;
            swap( temp->data, current->data );
        }
    }
} while( changeMade );

这假设data字段是节点中唯一的另一个字段 - 因为它实际上并不交换节点，只是交换数据。（做前者并不是更困难 - 但是如果没有看到你的节点类型声明，我会编造名称并冒着混淆问题的风险。

Answer 2

我没有

看到任何当前、头部和临时的声明，但我认为它们是指向节点的指针。你决定排序算法了吗？排序算法是否需要高效，或者具有气泡排序性能的东西是否正常？使用类似于气泡排序的逻辑，可以将具有最大值的节点重复移动到列表的末尾。或者为了节省一点时间，您可以从原始列表中删除具有最大值的节点，并将其插入到按排序顺序结束的新列表的前面。更高效的算法使用基于合并排序的逻辑。

若要删除或交换节点，使用指针到指针可以避免对列表的第一个节点（此示例中 pList 指向的节点）进行特殊处理：

NODE * SortList(NODE * pList)
{
NODE * pNew = NULL;                     /* sorted list */
NODE **ppNode;                          /* ptr to ptr to node */
NODE **ppLargest;                       /* ptr to ptr to largest node */
NODE * pLargest;                        /* ptr to largest node */
    while(pList != NULL){               /* while list not empty */
        ppLargest = &pList;             /*  find largest node */
        ppNode = &((*ppLargest)->next);
        while(NULL != *ppNode){
            if((*ppNode)->data > (*ppLargest)->data)
                ppLargest = ppNode;
            ppNode = &((*ppNode)->next);
        }
        pLargest = *ppLargest;          /* move node to new */
        *ppLargest = pLargest->next;
        pLargest->next = pNew;
        pNew = pLargest;
    }    
    return(pNew);
}