尝试仅通过操作指针对链接的列表排序 [英] Trying to Sort a Linked List only by Manipulating Pointers

问题描述

我想使用选择排序来排序链接列表。我只能操纵链表的指针，而不是改变键。我认为我有功能逻辑，但我只是返回原始的未排序序列。

I am trying to use Selection Sort to sort a Linked list. I can only manipulate the linked lists pointers and not change the keys. I think I have functional logic but, I just return the original unsorted sequence.

bool nodeSwap(Node* head){

  Node* next = head->next;
  if(next == NULL){ return head;}
  head->next = next->next;
  next->next = head;
  head = next;
  return next;
}
Node* sort_list(Node* head){

for(Node* n = head; n->next != NULL; n = n->next){
    for(Node* n1 = head->next; n1 != NULL; n1 = n1->next){
        if(n-> key > n1->key){
            nodeSwap(n);


            }
    }
}
return head;
}

---

/ strong>

---

EDIT

好的，所以我经历了，并添加了更多的一些逻辑，这实际上是有一些意义这一次，我有我的功能几乎工作...只有问题是它总是跳过列表中前两个元素的排序，并且不会在排序后返回。任何想法为什么会发生？

Ok so I went through and added more and some logic which actually makes some sense this time and I have my function almost working... Only problem is it always skips sorting over whatever the first two elements are in the list and doesn't return after the sort. Any thoughts on why that might occur?

Node* sort_list(Node* head){

Node* curr;
Node* prev;

  for(curr = head; curr->next != NULL; curr = curr->next){
      if(curr == head){
             head = curr->next;
             curr->next = head->next;
             head->next = curr;
             prev = head;
         }
     else if(curr->key > curr->next->key){
                  head = curr->next;
                  curr->next = head->next;
                  head->next = curr;
                  prev = head;
              } else if(curr -> next -> next != NULL){

                  prev->next = curr->next;
                  curr->next = prev->next->next;
                  prev->next->next = curr;

                  }else if(head != curr){
                        prev = prev->next;
                    }else{}
    }


 return head;
}

推荐答案

链表？你提到只交换数据，但是你不提供一个指针定义（仅键，或键和数据指针？），

Single linked list, or double linked list? You mention swapping only data, but you don't provide a pointer definition (key only, or key&data pointers?),

如果你想交换内容两个节点，你需要在nodeSwap函数中为两个节点提供指针，

If you want to swap the contents of the two nodes, you need to provide pointers to both nodes in the nodeSwap function,

bool nodeSwap(Node* a, node* b)
{
    if(!a) return false;
    if(!b) return false;
    int temp = a->key;
    a->key = b->key
    b->key = temp;
    void* dtemp = a->data;
    a->data = b->data;
    b->data = dtemp;
    return true;
}

如果要交换整个节点，则需要提供以前的指针，或去找它们（下面假设一个双向链表，或你看到'prev'你去找它），

If you want to swap the entire nodes, then you need to provide previous pointers, or go find them (the below assumes a doubly linked list, or where you see 'prev' you go find it),

bool nodeSwap(Node* a, node* b, Node* head)
{
    if(!a) return false;
    if(!b) return false;
    Node* ap=NULL, *bp=NULL;
    //double linked list
    ap = a->prev;
    bp = b->prev;
    //single linked list, get ap (a.previous),
    if( a!=head )
        for( ap=head; ap!=a->next; )
            ap=np->next;
    //single linked list, get bp (b.previous)
    if( b!=head )
        for( bp=head; bp!=b->next; )
            bp=bp->next;
    Node* temp;
    temp = a;
    //fix a->prev->next, b->prev->next
    ap->next = b; //was a
    bp->next = a; //was b
    //swap a->next, b->next
    temp    = a->next;
    a->next = b->next;
    b->next = temp;
    //swap a->prev, b->prev for double-linked list
    temp    = a->prev; //double linked list
    a->prev = b->prev; //double linked list
    b->prev = temp;    //double linked list
    //swap keys, not needed, you moved the Node*
    return true;
}

这里是带有两个指针的nodeSwap，

And here is the nodeSwap with both pointers,

Node* sort_list(Node* head){
    for(Node* n = head; n->next != NULL; n = n->next){
        for(Node* n1 = head->next; n1 != NULL; n1 = n1->next){
            if(n-> key > n1->key){
                nodeSwap(n,n1);
                //nodeSwap(n,n1,head);
            }
        }
    }
    return head;
}

这篇关于尝试仅通过操作指针对链接的列表排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！