}seqlist;
void heapInsert(seqlist *R,KeyType key)
{//原有堆元素在R->data[1]~R->data[R->length],
//将新的关键字key 插入到R->data[R->length+1]位置后， //以R->data[0]为辅助空间，调整为堆(此处设为大根堆) int large;//large 指向调整结点的左右孩子中关键字较大者
int low,high;//low 和high 分别指向待调整堆的第一个和最后一个记录 int i;
R->length++；R->data[R->length].key=key;//插入新的记录 for(i=R->length/2;i>0;i--)//建堆 {
low=i;high=R->length; 课后答案网 www.khdaw.com
R->data[0].key=R->data[low].key;//R->data[low]是当前调整的结点 for(large=2*low;large<=high;large*=2){
//若large>high，则表示R->data[low]是叶子，调整结束； //否则令large 指向R->data[low]的左孩子
if(large
{ R->data[low].key= R->data[large].key; low=large;//令low 指向新的调整结点 }
else break;//当前调整结点不小于其孩子结点的关键字，结束调整 }//endfor
R->data[low].key=R->data[0].key;//将被调整结点放入最终的位置上 }//end of for }end of heapinsert 算法分析：
设文件长度为n,则该算法需进行n/2 趟调整，总的时间复杂度与初建堆类似，最坏时间
复杂度为O(nlgn)，辅助空间为O(1).
22.写一个建堆算法：从空堆开始，依次读入元素调用上题中堆插入算法将其插入堆中。 答： void BuildHeap(seqlist *R) {
KeyType key;
R->length=0;//建一个空堆
scanf(\设MAXINT 为不可能的关键字 while(key!=MAXINT) {
heapInsert(R,key);
scanf(\
课后答案网 www.khdaw.com } }
23.写一个堆删除算法：HeapDelete(R,i),将R[i]从堆中删去，并分析算法时间，提示：先将
R[i]和堆中最后一个元素交换，并将堆长度减1，然后从位置i开始向下调整，使其满足堆 性质。
答： void HeapDelete(seqlist *R,int i)
{//原有堆元素在R->data[1]~R->data[R->length],
//将R->data[i]删除，即将R->data[R->length]放入R->data[i]中后， //将R->length 减1，再进行堆的调整，
//以R->data[0]为辅助空间，调整为堆(此处设为大根堆) int large;//large 指向调整结点的左右孩子中关键字较大者
int low,high;//low 和high 分别指向待调整堆的第一个和最后一个记录 int j;
if (i>R->length)
Error(\
R->data[i].key=R->data[R->length].key;
R->length--；R->data[R->length].key=key;//插入新的记录
for(j=i/2;j>0;j--)//建堆 {
low=j;high=R->length;
R->data[0].key=R->data[low].key;//R->data[low]是当前调整的结点 for(large=2*low;large<=high;large*=2){
//若large>high，则表示R->data[low]是叶子，调整结束； //否则令large 指向R->data[low]的左孩子
if(large
else break;//当前调整结点不小于其孩子结点的关键字，结束调整 }//endfor
R->data[low].key=R->data[0].key;//将被调整结点放入最终的位置上 }//end of for }end of HeapDelete
24.已知两个单链表中的元素递增有序，试写一算法将这两个有序表归并成一个递增有序的
单链表。算法应利用原有的链表结点空间。 答： typedef struct node{ KeyType key; //关键字域
OtherInfoType info; //其它信息域， struct node * next; //链表中指针域 }RecNode; //记录结点类型
typedef RecNode * LinkList ; //单链表用LinkList 表示 void mergesort(LinkList la,LinkList lb,LinkList lc) {RecNode *p,*q,*s,*r; lc=la;
p=la;//p 是la 表扫描指针，指向待比较结点的前一位置 q=lb->next;//q 是lb 表扫描指针，指向比较的结点 while(p->next)&&(q) if (p->next->key<=q->key) p=p->next; else {s=q;q=q->next;
s->next=p->next;p->next=s;//将s 结点插入到p 结点后 p=s;}
if (!p->next) p->next=q; 课后答案网 www.khdaw.com free(lb); }