c++ - 两个链表的merge_sort中使用的merge_lists函数

Question

我正在使用 merge_lists 函数来合并两个列表（最终合并排序）。它被编译但是当我运行它时，它冻结了。请帮忙看看有什么问题吗？

node* merge_lists(node* list1,node* list2){
    node* t;
    node* temp1;

    if(list1==NULL){
        return list2;
    }
    else if(list2==NULL){
        return list1;
    }

    if(((list1->head)->word)<=((list2->head)->word)){
        t->head=list1->head;
        temp1->head=list1->head->next;
        t->next=merge_lists(temp1,list2);
    }
    else{
        t->head=list2->head;
        temp1->head=list2->head->next;
        t->next=merge_lists(list1,temp1);
    }

    return t;
}

请注意，我的类节点定义如下：

class node{
    public:
    string word;
    node *next;
    node *head;
};

Answer 1

您的冻结/崩溃可能是因为您在t没有先初始化指针的情况下取消引用指针。这会导致未定义的行为。（当您使用未初始化的变量时，好的编译器会发出警告。）

t在尝试取消引用之前，您需要分配一个有效的指针。

temp1指针也存在同样的问题。

Answer 2

以下是一些评论：

• 您在分配之前使用tand 。temp1你应该node* t = new node();在一开始就做。
• 为什么您的节点同时具有head和word？我会消除head并让每个节点都带有 aword和 a next。列表的开头是t、list1或 `list2。

这是一个工作示例：

节点：

class node{
public:
  string* word;
  node *next;
};

合并：

node* merge_lists(node* list1,node* list2) {
  if(list1==NULL) {
    return list2;
  } else if (list2==NULL) {
    return list1;
  }

  // Create a new list to hold the merged result.
  node* t;
  if (*(list1->word)<=*(list2->word)) {
    t = list1;
    list1 = list1->next;
  } else {
    // Use list2
    t = list2;
    list2 = list2->next;
  }

  // Merge the remainder of the lists.
  t->next = merge_lists(list1, list2);
}

实用程序：

node* make_list(string strings[], int len, int pos=0) {
  node *list = NULL;
  if (pos < len) {
    list = new node();
    list->word = &(strings[pos]);
    list->next = make_list(strings, len, pos+1);
  }
  return list;
}

void display_list(node* list) {
  while (list != NULL) {
      cout << *(list->word) << "->";
    list = list->next;
  }
  cout << "." << endl;
}

int main(int argc, char* argv[]) {
  string s1[] = {"b", "d"};
  string s2[] = {"a", "c", "e"};
  node* l1 = make_list(s1, 2);
  node* l2 = make_list(s2, 3);
  cout << "List 1: ";
  display_list(l1);
  cout << "List 2: ";
  display_list(l2);
  node* sorted = merge_lists(l1, l2);
  cout << "Merged: ";
  display_list(sorted);
}  

Answer 3

您正在使用指针 t 和 temp1 而不为它们分配值。冻结只是众多可能性中的一种。