数据结构考研分类复习真题 第二章 答案[34]

与本题类似的题的解答如下

()本题与第题基本相同不同之处仅在于插入B链表第j个元素之前的不是删除了len个元素的A链表而是被删除的len个元素按照上题这len个元素结点中第一个结点的指针p>next查找从第i个结点开始的第len个结点的算法修改为

k=;q=p>next;∥q指向第一个被删除结点

while(q!=null && k<len)∥查找成功时q指向自i起的第len个结点

{k++;q= q>next;}

if(k<len) {printf(给的%d太大\nlen);exit();}

．[题目分析] 在递增有序的顺序表中插入一个元素x首先应查找待插入元素的位置因顺序表元素递增有序采用折半查找法比顺序查找效率要高查到插入位置后从此位置直到线性表尾依次向后移动一个元素位置之后将元素x插入即可

void Insert(ElemType A[]int size ElemType x)∥ A是有size个元素空间目前仅有num(num<size)个元素的线性表本算法将元素x插入到线性表中并保持线性表的有序性

{low=;high=num;∥题目要求下标从开始

while(low<=high)∥对分查找元素x的插入位置

{mid=(low+high)/;

if(A[mid]==x){low=mid+;break;}

else if(A[mid]>x)high=mid ;else low=mid+ ;

}

for(i=num;i>=low;i) A[i+]=A[i];∥元素后移

A[i+]=x;∥将元素x插入

}算法结束

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []