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

[题目分析]把待查记录看作枢轴先由后向前依次比较若小于枢轴则从前向后直到查找成功返回其位置或失败返回为止

int index (RecType R[]int lhdatatype key)

{ int i=lj=h;

while (i<j)

{ while (i<=j && R[j]key>key) j;

if (R[j]key==key) return j;

while (i<=j && R[i]key<key) i++;

if (R[i]key==key) return i;

}

printf(Not find) ; return ;

}//index

() [题目分析]从第n个记录开始依次与其双亲(n/)比较若大于双亲则交换继而与其双亲的双亲比较以此类推直到根为止

void sift(RecType R[]int n)

{ //假设 R[n]是大堆本算法把R[n]调成大堆

j=n; R[]=R[j];

for (i=n/;i>=;i=i/)

if (R[]key>R[i]key){ R[j]=R[i];j=i;} else break;

R[j]=R[];

}//sift

()void HeapBuilder(RecType R[]int n)

{ for (i=;i<=n;i++) sift (Ri); }

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