c - C中的嵌套合并排序不起作用

Question

我有一个链表节点为:

typedef struct Record{
  char name[100];
  int branch_id;
  struct Record *next;
}record; 

我想做的是首先对name 上的链表进行排序，然后对相同的name 进行branch_id 排序>. 但它只对 name 进行排序。我在这里做错了什么？

record *merge_sort( record * );
record *divide(record *);
record *merge(record *,record *);  

record *merge_sort( record *p )
{
  record *q;
  record *head=p;
  if(p!=NULL && p->next!=NULL){
    q=divide(p);
    p=merge_sort(p);
    q=merge_sort(q);
    head=merge(p,q);
  }
  return head;
}

record *divide(record *p)
{
  record *q,*r;
  q=p;
  r=p->next->next;
  while(r!=NULL){
    r=r->next;
    q=q->next;
    if(r!=NULL){
      r=r->next;
    }
  }
  r=q;
  q=q->next;
  r->next=NULL;
  return q;
}

record *merge(record *p,record *q)
{
  record *head,*tail;
  if(p==NULL || q==NULL){
    printf("Both the sub elements are empty\n");
  }
  if(strcmp(p->name,q->name)<0){
    head=p;
    p=p->next;
  }
  else if((strcmp(p->name,q->name)==0) && (p->branch_id < q->branch_id)){
    head=p;
    p=p->next;
  }
  else if((strcmp(p->name,q->name)==0) && (p->branch_id > q->branch_id)){
    head=q;
    q=q->next;
  }
  else{
    head=q;
    q=q->next; 
  }
  tail=head;
  while(p!=NULL && q!=NULL){
    if(strcmp(p->name,q->name)<0){
      tail->next=p;
      tail=p;
      p=p->next;
    }
    else if((strcmp(p->name,q->name)==0) && (p->branch_id < q->branch_id)){
      tail->next=p;
      tail=p;
      p=p->next;
    }
    else if((strcmp(p->name,q->name)==0) && (p->branch_id > q->branch_id)){
      tail->next=p;
      tail=p;
      p=p->next;
    }
    else{
      tail->next=q;
      tail=q;
      q=q->next;
    }
  }
  if(p!=NULL){
    tail->next=p;
  }
  else{
    tail->next=q;
  }
  return head;
}

Answer 1

在merge()中，特别是在

while(p!=NULL && q!=NULL){
  if(strcmp(p->name,q->name)<0){
    tail->next=p;
    tail=p;
    p=p->next;
  }
  else if((strcmp(p->name,q->name)==0) && (p->branch_id < q->branch_id)){
    tail->next=p;
    tail=p;
    p=p->next;
  }
  else if((strcmp(p->name,q->name)==0) && (p->branch_id > q->branch_id)){
    tail->next=p;
    tail=p;
    p=p->next;
  }
  else{
    tail->next=q;
    tail=q;
    q=q->next;
  }
}

第二种和第三种情况的代码是相同的，将 p 分配给 tail 。但是，在循环 header 中，我看到对于第三种情况，您正在分配 q。也许您在复制粘贴循环标题时错过了它？

我还可以建议您实现一个功能吗？这似乎是一个很好的因式分解，可以避免这个错误。

int reccmp(record *p,record *q){
    int ret = strcmp(p->name,q->name), diff;

    if(!ret){
        diff = p->branch_id > q->branch_id;

        ret = diff < 0 ? -1 : (diff > 0 ? 1 : 0);
    }

    return ret;
}