在鏈接串列中，合并排序不能按預期作業 -有解無憂

前言：

我并不關心我的特定合并排序演算法的可行性。這并不是問題的關鍵所在。我很好奇為什么我已經寫好的程式會有這樣的表現，而不是為什么我應該使用 STL 或其他什么東西。這是為了學習的目的。

問題：

我有一個由Node*s組成的鏈接串列結構。我為這個特殊的結構寫了一個半遞回的合并排序演算法（我說半是因為實際的排序在技術上是迭代的），但它并沒有完全按照它應該的方式作業（升序排序）。當用除錯器瀏覽代碼時，實際的排序函式merge()似乎沒有在整個呼叫程序中保留新排序的串列，而我無法理解如何做到這點。誰能解釋一下？

這里有一個最小的可重復的例子：

#include <iostream>
struct Link {
    Link(int d=int(), Link* n=nullptr) {
        data = d;
        next = n;
    }
    int data;
    鏈接*下一個。
};

struct LinkList {
  鏈接*哨兵。
  size_t size。

 LinkList(Link* h=new Link, size_ts=0) {
    size = s;
    sentinel = h;
  }

  ~LinkList() {
    鏈接* current = sentinel;
    while (current != 0) {
      鏈接* next = current->next;
      delete current;
      current = next。
    }
    sentinel = 0;
  }
};

//使用f/s ptr演算法將子鏈接串列分割成開始和結束。
void split（Link* sentinel, Link*& beg, Link*& end）{
    Link* s = sentinel, * f = sentinel-> next;

    while (f != NULL) {
        f = f->接下來。
        if (f != NULL) {
            s = s->next;
            f = f->下一個。
        }
    }
    beg = sentinel;
    end = s->next;
    s->next = NULL;
}

//從兩個子鏈接串列中征服（合并）元素到新的sentinel。
Link* merge（Link* beg, Link* end） {
    Link* sentinel = new Link;
    鏈接*臨時工。
    for (tmp = sentinel; beg != NULL && end != NULL; tmp = tmp-> next) {
        if (beg-> data < end-> data) {
            tmp->next = beg;
            beg = beg->next;
        }
        else {
            tmp->next = end;
            end = end->next;
        }
    }
    if (beg == NULL)
        tmp->next = end;
    else (beg ==NULL)
        tmp->next = beg;
    return tmp;
}

//遞回拆分和合并
Link* sort_merge（Link* sentinel） {
    鏈接*開始，*結束。

    if (sentinel == NULL || sentinel->next == NULL)
        return sentinel。

    split（sentinel, beg, end）。
    sort_merge（beg）。
    sort_merge(end)。

    return merge（beg, end）。
}

//幫助函式呼叫 sort_merge。
void sort（LinkList &l） {
  sort_merge（l.sentinel）。
}

void print(LinkList & l) {
  for (Link* n = l.sentinel; n != NULL; n = n-> next) {
      std::cout << n->data << '
'。
    }
}

int main() {
  //設定鏈接的LinkList 5->4->3->2->1->nullptr。
  Link* sentinel = new Link（5 , new Link(4, new Link(3, new Link(2, new Link(1)))));
  LinkList l（sentinel,5）。

  sort（l）。
  print(l);

  return 0;

我想要的輸出結果是

但是它輸出

uj5u.com熱心網友回復：

幾個問題：

merge回傳合并串列的最后節點，而不是第一個。所以要改變：
```
return tmp;
```
to:
```
return head->next。
```
在msort中，遞回呼叫的回傳值被忽略了，但它很重要，因為它代表了排序操作后的第一個節點。所以要改變：
```
msort（left）。
msort(right)。
```
to:
```
left = msort（left）。
right = msort(right)。
```
在sort中，msort的回傳值被忽略了，所以串列的head參考從未被更新。所以要改變：
```
msort（l.head）。
```
到：
```
l.head = msort（l.head）。
```

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/315422.html

標籤：

上一篇：OpenCV去除水印

下一篇：為什么scanf("%d")在8位資料型別被投到int*時能作業，而printf卻不能？