程序员考试补课笔记-第十五天

　　今天续着上堂的查找一章，上回已经讲了顺序查找和二分查找，这两个都是经常用到的。还有一种是特别的查找方法就是散列表（这里说明一下，这个查找方法是有几种不同的名字的，杂凑表和哈希表）。因为这个可能讲起来会用很多时间，老师也没有细详的解说，只是举了一个相对的思想出来，如下：
　　Ri　　 keyi
　a(0)　=　20
　a(1)　=　30
　a(2)　=　40
　a(3)　=　50　　　　addr(Ri)=H(keyi)
　　　　　　　　　　　Ri=keyi/10-2　这个关系

　　就是这样，它对不同的问题当然有不同的关系，只能只要知道这个思想就好了。教程里的查找也就是这三种了，现在开始讲排序了。排序相对查找来说多了很多的方法，我们之前也碰过好几种排序的方法了，就是前一章的二叉树排序就是了，还有很早之前讲过的冒泡排序，我想很多人都应该知道这个经典的排序了吧。现在下来要讲的是直接插入排序法，这种方法的优势在于已经排好序的结点插入一个新的结点，有顺序的这样就可以用到上章学过的折半查找就可以找到该插入的位置了。其实给出一个没有序的一排数组，可以把它划分为两大部份，一部份是已排好序的结点，而另一部分则是待插入的结点，这样就可以模拟这个算法了，看看第十五天图一
这里可以清楚看到整个的思路是如何的。下面我们就要用C语言来到描述这个排序算法了，一共有好种种版本，大家一个一个的对比看看，看谁的效率高。
　　int a[10]={8,7,10,30,5,1,7,10,0,25};
　　int i,j,k;
　　for(i=1;i<n;i++)
　　{
　　　　for(t=e[i],j=i-1;j>=0 && t<e[j];j--)
　　　　　　e[j+1]=e[j];
　　　　e[j+1]=t;
　　}

另一个

　　for(i=1;i<=9;i++)
　　　　for(j=0;j<=i-1;j++)
　　　　{
　　　　　　if(a[j]>a[i])
　　　　　　{
　　　　　　　　t=a[j];
　　　　　　　　a[j]=a[i];
　　　　　　　　a[i]=t;
　　　　　　}
　　　　}

再另一个

　　for(i=1;i<n;i++)
　　{
　　　　k=a[i];
　　　　for(j=i-1;j>=0;j--)
　　　　　　if(k>a[j]) break;
　　　　　　else a[j+1]=a[j];
　　　　a[j+1]=k;
　　}

　　以前三个程序请大家自己分析，一定要自己动过脑去想。好了，难题终于又是到最后出来了，就是把这个排序的算法变为链表形式的，大家有没有想到呢？我们都急着笔去试了，可是最后还是不行，如果对于至前没有接触过这类型的是正常的情况，所有我们都没有做出来。下面看看老师写的程序好了：

前一些定义之类的略
　　p=h->next;h->next=NULL;
　　while(p)
　　{
　　　　if(p->data<h->data)
　　　　{
　　　　　　q=p->next;
　　　　　　p->next=h;
　　　　　　h=p;p=q;
　　　　}
　　　　else
　　　　{
　　　　　　q=h;r=q->next;
　　　　　　while(r && p->data > r->data)
　　　　　　{
　　　　　　　　q=r;r=r->next;
　　　　　　}
　　　　　　q->next=p;p=p->next;
　　　　　　q->next->next=r;
　　　　}
　　}

　　今天我有些失落，可能是因为做题的事吧，反正整个人都不知道怎么的，不过我还是会坚持，我会继续加把劲，希望大家可以和我一齐努力吧！

原文转自：http://www.ltesting.net