作业1-2+ 实验1(6)

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->datadata) p=p->next; else if(p->data>q->data) q=q->next; else {

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]B.elem[j]) j++; if(A.elem[i]==B.elem[j]) {

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;