c语言中有三分查找法吗?

Python025

c语言中有三分查找法吗?,第1张

这个呀，楼主很有创造力，其实算法都是人设计的嘛，你想有就可以有的。

具体思想应该跟二分查找法差不多吧。给出n个已经排好序的数，在n/3和2n/3处各取一个数，跟待查的数比较，确定待查数所在的范围。编程复杂度应该比二分法大一些，因为需要考虑的情况很多，所以我就不写了。时间复杂度上，应该是一样大，系数在理想情况下三分法的平均值可能略好一些些(1和0.95的区别），但实际上，由于三分法需要考虑的情况很多，很难写出一个简洁的代码，很可能比二分法差。

#include <stdlib.h>

#include <string.h>

#include <stdio.h>

int Three_Parties(char* data, int data_length)

{

typedef unsigned char UCHAR

int i, index

char* dict

UCHAR* polybius_index

//检查讯息的合法性

for(i = 0 i < data_length i++)

{

if(data[i] >= 'a' && data[i] <= 'z')

{

//小写转化为大写

data[i] &= 0xDF //小写字母第5位置为0即变为大写

//data[i] -= 'a' - 'A' //这种写法也可以，但没有上一种效率高

}

else if(data[i] < 'A' || data[i] > 'Z')

{

//包含非字母的字符

return 1

}

}

dict = "LEOCBFQSTNARGHJUWXDVIKMPYZ/"

polybius_index = (UCHAR*)malloc(3 * data_length) 

for(i = 0 i < data_length i++)

{

index = strchr(dict, data[i]) - dict

polybius_index[i] = index / 9

index %= 9

polybius_index[i + data_length] = index / 3

polybius_index[i + 2 * data_length] = index % 3

}

for(i = 0 i < 3 * data_length i += 3)

{

index = polybius_index[i]*9 + polybius_index[i+1]*3 + polybius_index[i+2]

data[i/3] = dict[index]

}

free(polybius_index)

return 0

}

int main(int argc, char* argv[])

{

char data[] = "helloworld"

if(Three_Parties(data, strlen(data)) == 0)

{

printf("%s", data)

}

else

{

printf("input error")

}

return 0

}

//加密部分还可以改成建索引表，那样效率会更高，但代码稍微复杂些。