专升本数据结构试题解析(7)

第2部分 习题解析 亱店↘打烊oO

元素。

【算法源代码】

void reverse_merge(LinkList A,LinkList B,LinkList *C)

{ LinkList pa,pb,pre;

pa=A->next;pb=B->next; /*pa和pb分别指向A和B的当前元素*/

pre=NULL;

while(pa||pb)

{ if(pa->data<pb->data||!pb) /*将A的元素插入新表*/

{ pc=pa;q=pa->next;pa->next=pre;pa=q; }

else /*将B的元素插入新表*/

{ pc=pb;q=pb->next;pb->next=pre;pb=q; }

pre=pc;

}

*C=A;

A->next=pc; /*构造新表头*/

}/*reverse_merge*/

10．已知A，B和C为三个递增有序的线性表，现要求对A表作如下操作：删去那些既在B表中出现又在C表中出现的元素。试对顺序表编写实现上述操作的算法，并分析你的算法的时间复杂度（注意：题中没有特别指明同一表中的元素值各不相同）。

【算法分析】先从B和C中找出共有元素，记为same，再在A中从当前位置开始， 凡小于same的元素均保留(存到新的位置)，等于same的就跳过，到大于same时就再找下一个same。

【算法源代码】

void SqList_Intersect_Delete(SqList *A,SqList B,SqList C)

{i=0;j=0;k=0;m=0; /*i指示A中元素原来的位置，m为移动后的位置*/

while(i<(*A).length&&j<B.length&& k<C.length)

{ if(B.elem[j]<C.elem[k]) j++;

else if(B.elem[j]>C.elem[k]) k++;

else{

same=B.elem[j]; /*找到了相同元素same*/

while(B.elem[j]==same) j++;

while(C.elem[k]==same) k++; /*j和k后移到新的元素*/

while(i<(*A).length&&(*A).elem[i]<same)

(*A).elem[m++]=(*A).elem[i++]; /*需保留的元素移动到新位置*/

while(i<(*A).length&&(*A).elem[i]==same) i++; /*跳过相同的元素*/

}

}/*while*/

while(i<(*A).length)

(*A).elem[m++]=(*A).elem[i++]; /*A的剩余元素重新存储*/

(*A).length=m;

}/* SqList_Intersect_Delete*/

11．设L为单链表的头结点地址，其数据结点的数据都是正整数且无相同的，试设计利用直接插入的原则把该链表整理成数据递增的有序单链表的算法。

【算法分析】本题明确指出单链表带头结点，其结点数据是正整数且不相同，要求利用直接插入原则把链表整理成递增有序链表。这就要求从第二结点开始，将各结点依次插入到有序链表中。

【算法源代码】

void InsertSort (LinkList la)

{if(la->next!=NULL) /*链表不为空表*/

{p=la->next->next; /*p指向第一结点的后继*/

la->next->next=NULL;

/*直接插入原则认为第一元素有序，然后从第二元素起依次插入*/

while(p!=NULL)

{r=p->next;/*暂存p的后继*/

q=la;

while(q->next!=NULL&&q->next->data<p->data)q=q->next;/*查找插入位置*/