问答题

【函数1说明】
函数compare(SqList A, SqList B)的功能是：设A=(al，…，am)和B=(b1，…，bn)均为顺序表，“比较”，两个顺序表A和B的大小。设A’ 和B’ 分别为A和B中除去最大共同前缀后的子表(例如，A=(y，x，x，z，x，z)，B=(y，x，x，2，y，x，x，z)，则两者中最大的共同前缀为 (y，x，x，z)，在两表中除去最大共同前缀后的子表分别为A’=(x，z)和B’=(y，x，x，z))。若 A’=B’=空表，则A=B；若A’=空表，而B’≠空表，或者两者均不为空表，且A’的首元小于 B’首元，则A＜B：否则A＞B。
提示：算法的基本思想为：若相等，则j+1，之后继续比较后继元素；否则即可得出比较结果。显然，j的初值应为0，循环的条件是j不超出其中任何一个表的范围。若在循环内不能得出比较结果，则循环结束时有3种可能出现的情况需要区分。
【函数1】
int compare ( SqListA, SqList B)
{
//若A＜B，则返回-1；若A=B，则返回0：若A＞B，则返回1
j =0;
while(i＜ (1) &&j＜B. length)
if(A. elem[j] ＜ B. elem[j] )return(-1)
else if(A. elem[j] ＞ B. elem[j] )return(1);
else (2) ;
if(A. length == B. length) return(0);
else if(A. length＜B. length)return(-1);
else return(1)
}//compare
//函数1的时间复杂度是 (3) 。
【函数2说明】
函数exchanse_L(SLnk＆L，int m)的功能是：用尽可能少的辅助空间将单链表中前m个结点和后n个结点的互换。即将单链表(a₁、a₂…，a_m，b₁，b₂，…，b_n)改变成(b₁，b₂，…，b_n，a₁， a₂，…，a_m，)。
【函数2】
void exchange_L(SLink &L, int m)
{
if( (4) &&L-＞next) //链表不空且Lm!=0
{
P = L-＞next; k=1；
while( k ＜ m&&p) //查找a_m,所在结点
{
P= (5) ;++k;
}
if( (6) &&p-＞next) //n! =0 时才需要修改指针
ha = L -＞ next; //以指针ha记a₁结点的位置
L -＞ next = p -＞ next; //将B₁结点链接在头结点之后
p -＞ next = NULL; //设a_m的后继为空
q= (7) ; //令q指向b₁结点
while(q-＞next)q = (8) ; //查找b_n结点
q-＞＞next= (9) ; //将a₁结点链接到b_n结点之后
}
}
}
//函数2的时间复杂度是 (10) 。