1

我正在尝试使用选择排序对链接列表进行排序。我只能操作链表指针而不能更改键。我想我有功能逻辑，但是我只返回原始的未排序序列。

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;
}

编辑

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

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;
}
4

3 回答 3

0

尝试放置可编译的代码和/或提出特定问题。

第 3 行： return head;

在一个应该返回布尔值的函数中

于 2013-10-24T21:53:20.873 回答
0

单链表还是双链表？您提到仅交换数据，但您没有提供指针定义（仅键，还是键和数据指针？），

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

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'你去找到它），

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，

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;
}
于 2013-10-24T23:00:53.297 回答
0

似乎您正在按值传递 n 。如果您需要在函数内修改 n 的值，您需要将其设为全局 (argh) 或传递 n 的地址：

bool nodeSwap(Node** head){
    [...]
}
于 2013-10-24T21:56:06.300 回答