A.elem[i]<->A.elem[j]; }//reverse
4.试写一算法, 对单链表实现就地逆置。 单链表类型定义如下： struct LNode{ ElemType data; Struct LNode *next; } LNode *LinkList;
L p q s L p q s L p q s
void LinkList_reverse(Linklist &L)//链表的就地逆置;为简化算法,假设表长大于2 {
p=L->next;q=p->next;s=q->next;p->next=NULL; while(s->next) {
q->next=p;
p=q;q=s;s=s->next; //把L的元素逐个插入新表表头 }
q->next=p;s->next=q;L->next=s; }//LinkList_reverse
分析:本算法的思想是,逐个地把L的当前元素q插入新的链表头部,p为新表表头.
5 假设以两个元素依值递增有序排列的线性表A 和B 分别表示两个集合( 即同一表中的元素值各不相同) , 现要求另辟空间构成一个线性表C, 其元素为A 和B 中元素的交集, 且表C 中的元素也依值递增有序排列。试对顺序表编写求C 的算法。
6. 要求同5题。试对单链表编写求C的算法
A B p q p->data = = q->data s 第一个节点与第i个相同
C pc
s
C, pc void LinkList_Intersect(LinkList A,LinkList B,LinkList &C)//在链表结构上重做上题 {
p=A->next;q=B->next;
pc=(LNode*)malloc(sizeof(LNode)); C=pc;
while(p&&q) {
if(p->data
s=(LNode*)malloc(sizeof(LNode)); s->data=p->data; pc->next=s; pc=s; p=p->next; q=q->next; }
C=pc; ？
}//while
}//LinkList_Intersect
5 解：
void SqList_Intersect(SqList A,SqList B,SqList &C)//求元素递增排列的线性表A和B的元素的交集并存入C中 {
i=1;j=1;k=0;
while(A.elem[i]&&B.elem[j]) {
if(A.elem[i]
C.elem[++k]=A.elem[i]; //当发现了一个在A,B中都存在的元素, i++;j++; //就添加到C中 }
}//while
}//SqList_Intersect
7． 试编写算法, 将一个用循环链表表示的稀疏多项式分解成两个多项式, 使这两个多项式中各自仅含奇次项或偶次项, 并要求利用原链表中的结点空间来构成这两个链表。 struct PolyNode{ PolyTerm data;
Struct PolyNode *next; }PolyLink LinkedPoly;
L p A奇次 pa
B 偶次 pb
L pa A奇次 B 偶次 pb
如果是奇次 pa->next=p;pa=p; p=p->next;
p void Divide_LinkedPoly(LinkedPoly &L,&A,&B)//把循环链表存储的稀疏多项式L拆成只含奇次项的A和只含偶次项的B {
p=L->next;
A=(PolyNode*)malloc(sizeof(PolyNode)); B=(PolyNode*)malloc(sizeof(PolyNode)); pa=A;pb=B; while(p!=L) {
if(p->data.exp!=2*(p->data.exp/2)) {
pa->next=p;pa=p; } else {
pb->next=p;pb=p;