问答题
【说明】
本程序将两个从小到大的有序链表合成一个新的从小到大的有序链表。链表的每一项由类 Node描述，而链表由List描述，类List的成员函数有以下几个：
creatList(): 创建从小到大的有序链表。
multiplyList(List L1, Llst L2): 将链表L1和链表L2合并。
print(): 打印链表。
【C++代码】
#include ＜iostream＞
using namespace std;
class List;
class Node{
friend class List;
public:
Node(int data){
{{U}} (1) {{/U}};
}
private:
int data;
Node *next;
};
class List{
public：
List(){list=NULL;}
void multiplyList(List L1, List L2);
void creatList();
void print();
private:
Node *list;
};
void List::creatList()
{
Node *p, *u, *pre;
int dara;
list=NULL;
wbile(1){
cout＜＜"输入链表的一项: (小于零，结束链表) "＜＜endl;
cin＞＞data;
if(dara＜0)break;//小于零，结束输入
p=list;
while(p !=NULL && dara＞p-＞data){//查找插入点
pre=p;
p=p-＞next;
}
u={{U}} (2) {{/U}};
if(p==list)list=u;
else pre-＞next=u;
{{U}} (3) {{/U}};
}
}
void List::multiplyList(List L1, List L2)
{
Node *pL1, *pL2, *pL, *u;
list = NULL;
pL1 = L1.list;
pL2 = L2.11st;
while(pL1 != NULL && pL2 != NULL){
if(pL1-＞data ＜ pL2-＞data){
u = new Node(pL1-＞data);
pL1 = pL1-＞next;
}else{
u = new Node(pL2-＞data);
pL2 = pL2-＞next;
}
if(list == NULL){
list ={{U}} (4) {{/U}};
}else{
pL-＞next=u;
pL=u;
}
}
pL1 = (pL1 != NULL)? pL1:pL2;
while(pL1 != NULL){
u={{U}} (5) {{/U}};
pL1 = pL1-＞next;
if(list == NULL){
list=pL=u;
}else{
pL-＞next=u;
pL=u;
}
}
}
void List::print()
{
Node *p;
p = list;
while(p !=NULL){
cout＜＜p-＞data＜＜"/t";
p=p-＞next;
}
cout＜＜end1;
}
void main()
{
List L1, L2, L;
cout＜＜"创建第一个链表/n";L1.creatList();
cout＜＜"创建第二个链表/n";L2.creatList();
L1.print();L2.print();
L.multiplyList(L1,L2);
L.print();
}
【正确答案】
【答案解析】(1) this-＞data=data,next=NULL
(2) new Node(data)
(3) u-＞next=p
(4) pL=u
(5) new Node(pL1-＞data)
[分析] 空(1)是进行一些初始化工作，类Node有两个成员变量data和next，故空(1)应填“this-＞data =data,next=NULL;”。
类List的createList方法中，通过while循环实现数据输入，为了升序存储链表，每读入一个数据，程序需要查找合适的插入点，亦通过一个while循环查找。因此空(2)是申请一个新的节点，应该调用Node的构造方法。故空(2)应填new Node(data)，注意Node类的构造函数是有参数的。
接着将节点u插入到链表中，当p为list，说明此时应将u插入到当前第一个节点前(亦即p节点之前)，将list赋值为u，否则，应将u插入到pre节点之后，p节点之前，将pre的next修改为u。这样，还需将u的next指向其下一个节点，即p，故空(3)应填u-＞next=p。
multiplyList负责将两个升序排列L1和L2的链表合并起来。通过while循环逐一比较，如果L1的当前节点的值大于L2的，则将L1的当前节点的值插入到结果链表list中，并将L1的当前节点指针下移，对L2同样处理。当list等于NULL时，因list初始化为NULL，则说明是结构链表的头节点。注意到else块中的pL变量的使用，可知pL变量是指向结构链表list的工作指针，故在结构链表生成第一节点时也需将其正确初始化。故空(4)应填pL=u。
while循环结束直到链表L1和L2有一个已经到达链尾。接着将剩余链表的指针赋给批L1，将剩余节点逐次加入到结果链表即可。故易得空(5)应填new Node(pL1-＞data)。