如何在一个有序链表中找到目标值有很多种算法，常用的有时间为O(n)的确定性算法A，时间为O(√n)的确定性算法B，时间为O(n)的概率算法C，在这几种算法中，算法B效率最高，为进一步提高算法效率，写一Sherwood算法C，与算法A, B, D比较，给出实验结果。
首先定义了一个普通的有序链表，再定义一个特殊的有序链表，通过A、B、C、D四种算法在两个链表上的不同表现，得出结论。
程序源代码（C语言描述）：
#include <stdio.h> #include <stdlib.h> #include <time.h> #include <math.h> #define targ 18 int n=20,head=3,head1=0;//定义静态链表 int val[20]={2,17,11,1,7,15,20,3,19,14,8,5,18,10,13,6,4,12,16,9}; int ptr[20]={7,12,17,0,10,18,100,16,6,5,19,15,8,2,9,4,11,14,1,13}; int val1[20]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}; int ptr1[20]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,100}; void main() { printf("普通有序静态链表0\n"); printf("val[20]={2,17,11,1,7,15,20,3,19,14,8,5,18,10,13,6,4,12,16,9};\n"); printf("ptr[20]={7,12,17,0,10,18,100,16,6,5,19,15,8,2,9,4,11,14,1,13};\n"); printf("-----------------------------------------------------------\n"); printf("特殊有序静态链表1\n"); printf("val1[20]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};\n"); printf("ptr2[20]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,100};\n"); printf("-----------------------------------------------------------\n"); printf("A算法在链表0中查找%d:",targ); printf("目标位置i=%d\n",A(targ)); printf("B算法在链表0中查找%d:",targ); printf("目标位置i=%d\n",B(targ)); printf("C算法在链表0中查找%d:",targ); printf("目标位置i=%d\n",C(targ)); printf("D算法在链表0中查找%d:",targ); printf("目标位置i=%d\n",D(targ)); printf("-----------------------------------------------------------\n"); printf("A算法在链表1中查找%d:",targ); printf("目标位置i=%d\n",A1(targ)); printf("B算法在链表1中查找%d:",targ); printf("目标位置i=%d\n",B1(targ)); printf("C算法在链表1中查找%d:",targ); printf("目标位置i=%d\n",C1(targ)); printf("D算法在链表1中查找%d:",targ); printf("目标位置i=%d\n",D1(targ)); } int search(int x,int i) {int k=0;//记录查找的次数 while(x>val[i]) { i=ptr[i]; k++; } printf("共查找了%d次\n",k+1); return i; } int A(int x) //时间为O(n)的确定性算法 { return search(x,head); } int B(int x) //时间为O(√n)的确定性算法 { int j,y,i=head; int max=val[i]; //max初值是表val中的最小值 for(j=0;j<sqrt(n);j++) //在val的前√n个数中 //找不大于x的最大整数y相应的下标i { y=val[j]; if(max<y&&y<=x) { i=j; max=y; } } return search(x,i); //从y开始继续搜索 } int C(int x) //在算法B基础上改进的sherwood算法 { int j,k,i=head; int max=val[i]; srand( (unsigned)time(0)); for(j=0;j<sqrt(n);j++) {k=rand()%n; //在0-n中取√n个随机数作为下标，将这些下标对应的val值 //与x比较，找出不大于x的最大整数相应的下标i if(max<val[k]&&val[k]<=x) {i=k; max=val[k]; } } return search(x,i); } int D(int x) //时间为O(n)的概率算法 { int i=rand()%n; int y=val[i]; if(x<y) return search(x,head); else if(x>y) return search(x,ptr[i]); else return i; } int search1(int x,int i) {int k=0; while(x>val1[i]) { i=ptr1[i]; k++; } printf("共查找了%d次\n",k+1); return i; } int A1(int x) { return search1(x,head1); } int B1(int x) { int j,y,i=head1; int max=val1[i]; for(j=0;j<sqrt(n);j++) { y=val1[j]; if(max<y&&y<=x) { i=j; max=y; } } return search1(x,i); } int C1(int x) { int j,k,i=head1; int max=val1[i]; srand( (unsigned)time(0)); for(j=0;j<sqrt(n);j++) {k=rand()%n; if(max<val1[k]&&val1[k]<=x) {i=k; max=val1[k]; } } return search1(x,i); } int D1(int x) { int i=rand()%n; int y=val1[i]; if(x<y) return search1(x,head1); else if(x>y) return search1(x,ptr1[i]); else return i; }
运行结果：
可以取不同的targ 多运行几次。
结论：
1：时间为O(n)的确定算法A所需时间最长，效率最低
2：时间为O(n)的概率算法D随机性很大，对同一target，算法效率有时很高，有时很低。
3、时间为O(√n)的确定性算法B和在算法B基础上改进的sherwood算法C在普通有序链表中表现较好，旗鼓相当，但当遇到特殊有序表（val[]本身有序）时，算法效率急剧下降。而改进的sherwood算法C却依旧保持极高的效率。说明sherwood算法虽然并不比同类型确定性算法快，但他消除了最坏实例的影响。