网站开发的书,网站服务器制作,怎样做网站404,让php运行于wordpress在前一篇插入排序#xff1a;表插入中。我们用静态链表的存储方式。直接插入的策略#xff0c;构建了一种新的插入排序算法#xff1a;表插入。有人可能会想到#xff1a;相同是静态链表的形式#xff0c;为什么不使用更高效的折半插入策略呢#xff1f;这样的想法真的非… 在前一篇插入排序表插入中。我们用静态链表的存储方式。直接插入的策略构建了一种新的插入排序算法表插入。有人可能会想到相同是静态链表的形式为什么不使用更高效的折半插入策略呢这样的想法真的非常好假设做到了。显然是极大的优化。 我在网上还真看到了相关的内容大家可搜下《表插入方法的改进》里面有此想法的介绍。这篇博客就是介绍表插入的还有一种实现表折半插入。看完一定让你彻底理解它 与一般的折半插入相比有例如以下的几点变化 为了实现折半查找我们对静态链表的节点类型做了一些变化加入了一个前驱指针。它的意义非常显然曾经是highmid-1在单向链表中我们是做不到的(事实上能够换种方式做到只是相对麻烦)于是加入一指向其前驱的指针。构成双向链表方便进行此操作。while循环的结束条件有所不同。这个要细致理解其它细节代码中有详解 const int MAX100;
typedef struct rec
{int data;int pre; //前驱 int next; //后继
}Rec;
void InsertSort(int a[], int n) //表折半插入
{Rec *recnew Rec[n1];for(int i0; in; i){rec[i1].dataa[i];rec[i1].nextrec[i1].pre0;}rec[0].dataMAX;rec[0].nextrec[0].pre1;int low,high,mid;int p,k,l;for(int i2; in1; i){//依据下面的赋值我们能够看出。这里使用的是左闭右闭区间 lowrec[0].next; //low指向最小的 highrec[0].pre; //high指向最大的 li-1; //已有序的元素个数 while(low!0 high!0 rec[low].datarec[high].data) //循环结束条件得理解特别是前两个条件。准确的是。第一个条件能够不要 { midlow; k1; l/2; // l2 减半。为下次循环做好准备 while(kl) //寻找mid位置 { midrec[mid].next; k; } if(rec[i].datarec[mid].data) highrec[mid].pre; else lowrec[mid].next; } //插入第i个节点。相似于双向链表的插入 rec[rec[low].pre].nexti; rec[i].prerec[low].pre; //加入前驱指针的作用体如今这里 rec[i].nextlow; rec[low].prei; } //顺着next指针方向打印 printf(表折半插入排序后\n); prec[0].next; while(p!0) { printf(%-4d,rec[p].data); prec[p].next; } printf(\n); } 细致看完代码我想大多数人仅仅剩一个问题可能没明确那就是while循环的结束条件为什么还得加上low!0 和high!0 为了解释清楚。我们画一个图图中正在插入i2的节点 初始化后。low,mid,high显然都指向1经过下一步rec[i].data与rec[mid].data比較后不管结果如何循环都应结束。可假设rec[i].datarec[mid].data,就有highrec[mid].pre,即high1.此时显然有rec[low]rec[high],也就是说循环还得接着经进行下去。问题就出在这里讲到这里你应该明确即使出现low为0,它也会违反第三条件rec[low].datarec[high].data)(由于rec[0]的值域是最大的)。这就是为什么说第一个条件low!0能够去掉。 到此。你应该明确了代码中全部的凝视。 測试走起啊…… p.s 对rec数组1-n号元素进行重排也是能够的做法參照上一篇博客哦方法一模一样。 转载请注明出处本文地址http://blog.csdn.net/zhangxiangdavaid/article/details/28635157 若是写得好。顶一个哦。 代码就是折腾越折腾越进步 专栏文件夹看这里 数据结构与算法文件夹c指针
