【DS专题活动】第五期（10月27日～11月2日）解答
B组解答：
//第一题,完成者:tristsesame
/***************************************************************************
函数：IsValidList
功能：验证顺序表的合法性
参数：顺序表指针
返回值：int
非0值:合法
0：非法
*******************************************************************************/
int IsValidList(SqList* AList)
{
return AList != NUll &&
AList->length >= 0 &&
AList->listsize >= AList->length &&
AList->elem != NULL;
}
/**********************************************************
函数：SeqList_Reverse
功能：顺序表置逆
参数：
SqList sqlist，顺序表，必须是有效顺序表。
***********************************************************/
void SeqList_Reverse(SqList sqlist)
{
ElemType temp;
int i,j;
assert(IsValidList(&sqlist));
for(i = 0,j = sqlist->length - 1;i < j; i++,j--)
{
temp = sqlist->elem[i];
sqlist->elem[i] = sqlist->elem[j];
sqlist->elem[j] = temp;
}
}
//第二题,完成者:xiaoyige886
/**********************************************************
函数：Reverse
功能：单链表置逆
参数：
LinkList L，单链表节点指针，无头节点的单链表首节点。
返回值：
LinkList，逆转后的单链表首节点指针。
***********************************************************/
LinkList Reverse(LinkList L)
{
LinkList p,s;
p = L;
L = NULL;//L设置为NULL,作为末尾
while(p != NULL)
{
s = p;
p = p->next;
s->next = L;//向第一结点前插入
L = s;
}
return L;
}
//第二题,完成者:xiaoyige886
/**********************************************************
函数：Union
功能：交叉合并单链表
参数：
LinkList m，LinkList n，将合并的两个
单链表节点指针，无头节点的单链表首节点。
返回值：
LinkList，合并后的单链表首节点指针。
说明：
线性表A=（a1，a2，...,am），B=（b1，b2，...,bn），按下列规则合并A、B为
线性表C，即使得：
C=（a1，b1，...,am，bm，bm+1，...,bn） 当m<=n时；
C=（a1，b1，...,an，bn，an+1，...,am） 当m>n时；
线性表A，B和C均以单链表作存储结构，且C表利用A表和B表的存储空间
***********************************************************/
LinkList Union(LinkList m, LinkList n)
{
LinkList pm = m;
LinkList pn = n;
LinkList s,t;
while(pm && pn)
{
s = pm->next;
pm->next = pn;//把n链的第(2*k-1)个元素插入m链第(2*k-1)之后
if(s)
{
t = pn->next;
pn->next = s;//把m链的第(2*k)个元素插入n链第(2*k)之后
}
pn = t;
pm = s;
}
if (m == NULL)
m = n;
return m;
}
问题点数：0、回复次数：12Top
1 楼tristsesame（小小的芝麻）回复于 2003-11-03 14:50:53 得分 0
第三题的回答有点小问题:
当pm->next为NULL时,
pm->next = pn会出错.
if(s)
{
t = pn->next;
pn->next = s;//把m链的第(2*k)个元素插入n链第(2*k)之后
}
当s == NULL时
pn = t;也会出错
Top
2 楼plainsong（短歌)(）回复于 2003-11-03 15:41:23 得分 0
不会出错的，你仔细想一想。Top
3 楼tristsesame（小小的芝麻）回复于 2003-11-03 18:05:17 得分 0
呵呵
我前面的说错了
pm->next = pn;没有错,我糊涂了。
但是之前
若循环第一次运行是s为NULL
那么t没有定义初值.
pn = t;会出错
Top
4 楼plainsong（短歌)(）回复于 2003-11-03 18:10:20 得分 0
仍然没有问题：
这时执行了pn = t和pm=s。
而s==NULL，所以pm==NULL，循环不会在继续。虽然这时pn中的值未定义，但它不会再被使用，所以也没有问题。Top
5 楼xiaoyige886（素还真）回复于 2003-11-03 21:45:01 得分 0
upTop
6 楼ZhangYv（迎着朝阳,走向地狱）回复于 2003-11-03 22:25:11 得分 0
// 写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表
// (a[1]，a[2]，...,a[n])逆置为(a[n]，a[n-1]，...,a[1])。
void Reverse( SqList &list )
{
ElemType temp;
int n = list.nLen / 2;
int nLastPos = list.nLen - 1;
for (int i = 0; i < n; ++i)
{
temp = list.pElem[i];
list.pElem[i] = list.pElem[nLastPos];
list.pElem[nLastPos--] = temp;
}
}
2、实现单链表的就地逆置。
void TransElem(LinkList &L){
Lnode *p, *q, *r = L;
if (!L->next)
return;
p = r->next;
q = p->next;
p->next = NULL;
while (q){
r = p; //3个节点都步进1格
p = q;
q = q->next;
p->next = r;
}
L->next = p;
}
3、线性表A=（a1，a2，...,am），B=（b1，b2，...,bn），按下列规则合并A、B为
线性表C，即使得：
C=（a1，b1，...,am，bm，bm+1，...,bn） 当m<=n时；
C=（a1，b1，...,an，bn，an+1，...,am） 当m>n时；
线性表A，B和C均以单链表作存储结构，且C表利用A表和B表的存储空间（注
意：单链表的长度m，n未显示存储）
LinkList *Union(LinkList *LA,LinkList *LB){
LNode *p,*q,*r;
p=LA;
q=LB;
r=LB->next;
while (p->next && q->next){
p=p->next;
q->next=r->next;
r->next=p->next;
p->next=r;
p=p->next;
r=LB->next;
}
return LA;
}
Top
7 楼ZhangYv（迎着朝阳,走向地狱）回复于 2003-11-03 22:27:44 得分 0
我上面第二题转置链表是带表头节点的!Top
8 楼plainsong（短歌)(）回复于 2003-11-03 22:41:49 得分 0
是否有头节点都没有关系，我在上期第二题的解答中就说过了，无头链表的算法也可以用有头链表的算法来实现，反之亦然。
Top
9 楼fanever（我的老婆是Sorbet）回复于 2003-11-04 14:15:17 得分 0
copy回去看先Top
10 楼playcs（playcs）回复于 2003-11-04 16:49:08 得分 0
好，学习一下Top
11 楼ZhangYv（迎着朝阳,走向地狱）回复于 2003-11-05 08:07:48 得分 0
无头链表的算法是不可以用有头链表的算法来实现的.Top
12 楼plainsong（短歌)(）回复于 2003-11-05 14:15:06 得分 0
void TransElem(LinkList &L);//Head-list edition
void TransElem2(LinkList & L)//Non-head-list edition
{
LNode Head;
LinkList PHead;
Head->next = L;
PHead = &Head;
TransElem(PHead);//Implemented by head-list edition
L = Head->next;
}Top
