Question

【数据结构·C语言】请高手帮忙检查一个关于【链表归并】的算法是否正确

假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许表中含有值相同的元素）排列的线性表C，并要求利用原表（即A表和B表）的结点空间构造C表。

malloc函数我不太会用啊，如何给C表分配一个只有元节点的空间？是下面那样吗？

status Decline_AB(LinkList &A,LinkList &B,LinkList &C)
{
C=(ElemType*)malloc(sizeof(LNode)); //给C表分配元结点
LinkList ha=A, hb=B , hc=C;
while(ha->next!=NULL&&hb->next!=NULL)
{
while(ha->next->next!=NULL) ha=ha->next;
while(hb->next->next!=NULL) hb=hb->next; //ha与hb指向A、B表的尾结点
if(ha->next->data>=hb->next->data)
{hc->next=ha->next ;
ha->next=NULL;
ha=A;
hc=hc->next;
}
else
{ hc->next=hb->next ;
hb->next = NULL ;
hb=B;
hc=hc->next;
}
}//while //相同位数内的比较与逆排
if(hb->next==NULL)
{ for(ha=A;A->next!=0;ha=A)
{while(ha->next->next!=NULL) ha=ha->next;
hc->next=ha->next;
ha->next=NULL;
hc=hc->next;
}//for
}//if
else
{ for(hb=B;B->next!-0;hb=b)
{while(hb->next->next!=NULL) hb=hb->next;
hc->next=hb->next;
hb->next=NULL;
hc=hc->next;
}//else
hc->next=NULL; free(A); free(B);
C.length=A.length+B.length;
return OK;
}//Decline_AB

Answer 1

1. 您的算法不符合题意，题意是不要创建新的结点就是用原来的空间，所以您 C=(ElemType*)malloc(sizeof(LNode));应该是多余的。
2. 您的算法因为AB是递增有序要改为递减有序，您就每次将指针移动到序列的最末端来进行比较和插入，由于是单向链表，这样你的算法会非常低效。
3. 您仅仅需要将两个链表的结点按照递减顺序插入到新的链表中即可。
4. 例如您可以先将A中的结点逆序，然后将B中的结点按照递减顺序一个一个插入到A中的合适位置，最终获得的A链表即为需要的C链表了。