数据结构与算法线性表复习习题【5】[1]

试写一算法对单链表实现就地逆置

解

// 带头结点的单链表的逆置

Status ListOppose_L(LinkList &L)

{

LinkList pq;

p=L;

p=p>next;

L>next=NULL;

while(p){

q=p;

p=p>next;

q>next=L>next;

L>next=q;

}

return OK;

}

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

解

// 将合并逆置后的结果放在C表中并删除B表

Status ListMergeOppose_L(LinkList &ALinkList &BLinkList &C)

{

LinkList papbqaqb;

pa=A;

pb=B;

qa=pa;// 保存pa的前驱指针

qb=pb;// 保存pb的前驱指针

pa=pa>next;

pb=pb>next;

A>next=NULL;

C=A;

while(pa&&pb){

if(pa>data<pb>data){

qa=pa;

pa=pa>next;

qa>next=A>next;//将当前最小结点插入A表表头

A>next=qa;

}

else{

qb=pb;

pb=pb>next;

qb>next=A>next;//将当前最小结点插入A表表头

A>next=qb;

}

}

while(pa){

qa=pa;

pa=pa>next;

qa>next=A>next;

A>next=qa;

}

while(pb){

qb=pb;

pb=pb>next;

qb>next=A>next;

A>next=qb;

}

pb=B;

free(pb);

return OK;

}

假设以两个元素依值递增有序排列的线性表A和B分别表示两个集合（即同一表中的元素值各不相同）现要求另辟空间构成一个线性表C其元素为A和B中元素的交集且表C中的元素有依值递增有序排列试对顺序表编写求C的算法

解

// 将AB求交后的结果放在C表中

Status ListCross_Sq(SqList &ASqList &BSqList &C)

{

int i=j=k=;

while(i<Alength && j<Blength){

if(Aelem[i]<Belem[j])i++;

else

if(Aelem[i]>Belem[j])j++;

else{

ListInsert_Sq(CkAelem[i]);

i++;

k++;

}

}

return OK;

}

[] [] []