严蔚敏版数据结构习题及参考答案(10)

(3) 14 26 27 34 38 46 [53 65] 74 86 (4) 14 26 27 34 38 46 53 65 74 86 4.

(0) [46 74 53 14 26 38 86 65 27 34] (1) 14 [74 53 46 26 38 86 65 27 34] (2) 14 26 [53 46 74 38 86 65 27 34] (3) 14 26 27 [46 74 38 86 65 53 34] (4) 14 26 27 34 [74 38 86 65 53 46] (5) 14 26 27 34 38 [74 86 65 53 46] (6) 14 26 27 34 38 46 [86 65 53 74] (7) 14 26 27 34 38 46 53 [65 86 74] (8) 14 26 27 34 38 46 53 65 [86 74] (9) 14 26 27 34 38 46 53 65 74 [86] 5. 构成初始堆（即建堆）的过程：

1 2 3 4 5 6 7 8 9 10 (0) 46 74 53 14 26 38 86 65 27 34 (1) 46 74 53 14 26 38 86 65 27 34 (2) 46 74 53 14 26 38 86 65 27 34 (3) 46 74 38 14 26 53 86 65 27 34 (4) 46 14 38 27 26 53 86 65 74 34 (5) 14 26 38 27 34 53 86 65 74 46 进行堆排序的过程：

(0) 14 26 38 27 34 53 86 65 74 46 (1) 26 27 38 46 34 53 86 65 74 [14] (2) 27 34 38 46 74 53 86 65 [26 14] (3) 34 46 38 65 74 53 86 [27 26 14] (4) 38 46 53 65 74 86 [34 27 26 14] (5) 46 65 53 86 74 [38 34 27 26 14] (6) 53 65 74 86 [46 38 34 27 26 14] (7) 65 86 74 [53 46 38 34 27 26 14] (8) 74 86 [65 53 46 38 34 27 26 14] (9) 86 [74 65 53 46 38 34 27 26 14] 6.

(0) [46] [74] [53] [14] [26] [38] [86] [65] [27] [34] (1) [46 74] [14 53] [26 38] [65 86] [27 34] (2) [14 46 53 74] [26 38 65 86] [27 34] (3) [14 26 38 46 53 65 74 86] [27 34] (3) [14 26 27 34 38 46 53 65 74 86]

-46-

四、算法设计题 1.

void Bubble_Sort2(int a[ ],int n) //相邻两趟是反方向起泡的冒泡排序算法 { low=0;high=n-1; //冒泡的上下界 change=1;

while (low

for(i=low;ia[i+1]) { a[i]<->a[i+1]; change=1; }

high--; //修改上界

for (i=high;i>low;i--) //从下向上起泡 if (a[i]a[i-1]; change=1; }

low++; //修改下界 }//while }//Bubble_Sort2 2.

void LinkList_Select_Sort(LinkList &L) //单链表上的简单选择排序算法 { for (p=L;p->next->next;p=p->next) { q=p->next; x=q->data;

for (r=q,s=q;r->next;r=r->next) //在q后面寻找元素值最小的结点 if (r->next->datanext->data; s=r; }

if (s!=q) //找到了值比q->data更小的最小结点s->next { p->next=s->next; s->next=q; t=q->next; q->next=p->next->next; p->next->next=t;

} //交换q和s->next两个结点 }//for

}//LinkList_Select_Sort

-47-