首页 26考研 在职考研 直播好课 25复试

新东方在线 > 考研 > 计算机 > 考研计算机资料 > 正文

扫码加入训练营

牢记核心词

学习得礼盒

计算机考研：数据结构常用算法精析(9)

2013-12-12 15:18:39来源：新东方在线编辑

　　一个元素的堆调整算法：

　　//已知H.R[s...m]除H.R[s]之外，均满足堆的定义，本函数只是将H.R[s]放到已经是堆的堆中

　　void HeapAdjust (SqList& H, int s, int m) ∥将(H.R[s]……H.R[m])调整成大根堆∥

　　{

　　rc=H.R[s]; ∥暂存H.R[s]∥

　　for(j=2*s;j<=m; j*=2 )//沿key较大的孩子结点向下筛选

　　{

　　if (jL.R[j].key) j++; ∥令j为s的左右孩子key最大者的序号

　　if (rc.key>L.R[j].key)

　　break;//说明H.R[s]已经比当前堆中的所有元素大，已经是堆了，不需要调整了

　　L.R[s]=L.R[j]; ∥把最大的放到根结点

　　s=j; ∥把s与j交换，使得s与下层的堆比较

　　}

　　L.R[s]=rc; ∥最初的根回归∥

　　}

　　void Heapsort (SqList& H) ∥ 堆排序算法∥

　　{

　　//初始建堆

　　for (i=L.len/2; i>=1; i--) //从完全二叉树的最后一个非叶子结点开始

　　HeapAdjust (L,i,L.len); ∥调整(R[i]……R[n])为堆∥

　　//每次取下根(最大的元素)所谓的取下，只是放到数组最后，改变一下数组的下界

　　for (i=L.len;i>=2;i--) ∥总共摘n-1次∥

　　{ temp=F.R[1]; ∥根与当前最后一个结点互换∥

　　F.R[1]=F.R[i];

　　F.R[i]=temp;

　　HeapAdjust (L ,1,i-1); ∥把最后一个元素调整到合适的位置∥

　　}

　　}

　　二路归并排序：(稳定的，时间复杂度O(nlogn)又稳定又效率高，但需要辅助空间TR[1....n]

　　二路归并得核心操作是将一维数组中前后相邻的两个有序序列归并为一个有序序列

　　(注意这就是线型表中我们常考的那个，两个有序链表合成一个新的有序表)

　　算法描述如下：

　　void Merge(RcdType SR[],RcdType&TR[],int i,int m,int n)

　　//将有序的SR[i...m]和SR[m+1....n]归并为有序的TR[i....n]

　　{

　　for(j=m+1,k=i; i<=m&&j<=n; ++k) //谁小就先将谁放进TR

　　{ if(SR[i].key<=SR[j].key)

　　TR[k]=SR[i++];

　　else

　　TR[k]=SR[j++];

　　}

　　if(i<=m) //将剩余的SR 直接放到TR

　　TR[k....n]=SR[i...m];

　　if(j<=n) //将剩余的SR 直接放到TR

　　TR[k...n]=SR[j....n];

　　}

　　void MSort(RcdType SR[], RcdType&TR1[], int s, int t)

　　{ //将SR[s...t]归并排序为TR1[s...t]

　　if(s= =t) //只有一个元素

　　TR1[s]=SR[s];

　　else

　　{

　　m=(s+t)/2;//将SR[]平分为两半

　　MSort(SR, TR2, s, m);

　　MSort(SR, TR2, m+1, t);

　　Merge(TR2, TR1, s, m, t);

　　}

　　}


考研公开课小程序

本文关键字: 计算机 考研 数据结构

上一页 1 2 3 下一页

考研英语核心词汇营

背词+听课+练习+督学，学习得礼盒

更多资料

添加班主任领资料

添加考研班主任
免费领取考研历年真题等复习干货资料

  • 1.打开手机微信【扫一扫】，识别上方二维码；
  • 2.添加班主任，可领取学习资料。
更多>>
更多内容
报班学 MBA 优惠券 0元学 院校库

关注新东方在线考研服务号

获得21考研真题及答案解析

1. 打开手机微信【扫一扫】，识别上方二维码；
2.点击【关注公众号】，获取资料大礼包。

真题解析

历年考研真题及答案解析下载

英语一 英语二 政治 数学一 数学二 数学三 西医综合 教育综合 心理学综合
立即下载
近10年考研真题及答案免费下载
更多>>
更多公开课>>
更多>>
更多资料
我要
反馈 返回
首页
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10