08数据结构及算法篇

crypt（将密码或数据编码）
相关函数 getpass

表头文件 #define _XOPEN_SOURCE
#includeunistd.h

定义函数 char crypt (const char key,const char salt);

函数说明 crypt()将使用Data Encryption Standard(DES)演算法将参数key所指的字符串加以编码，key字符串长度仅取前8个字符，超过此长度的字符没有意义。参数salt为两个字符组成的字符串，由a-z、A-Z、0-9，“.”和“”所组成，用来决定使用4096 种不同内建表格的哪一个。函数执行成功后会返回指向编码过的字符串指针，参数key 所指的字符串不会有所更动。编码过的字符串长度为13 个字符，前两个字符为参数salt代表的字符串。

返回值 返回一个指向以NULL结尾的密码字符串。

附加说明 使用GCC编译时需加-lcrypt。

范例 #includeunistd.h
main()
{
char passwd[13];
char key;
char slat[2];
key= getpass(“Input First Password”);
slat[0]=key[0];
slat[1]=key[1];
strcpy(passwd,crypt(key slat));
key=getpass(“Input Second Password”);
slat[0]=passwd[0];
slat[1]=passwd[1];
printf(“After crypt(),1st passwd %sn”,passwd);
printf(“After crypt(),2nd passwd%s n”,crypt(key slat));
}

执行 Input First Password 输入test，编码后存于passwd[ ]
Input Second Password 输入test，密码相同编码后也会相同
After crypt () 1st Passwd teH0wLIpW0gyQ
After crypt () 2nd Passwd teH0wLIpW0gyQ






bsearch（二元搜索）
相关函数 qsort

表头文件 #includestdlib.h

定义函数 void bsearch(const void key,const void base,size_t nmemb,size_tsize,int (compar) (const void,const void));

函数说明 bsearch()利用二元搜索从排序好的数组中查找数据。参数key指向欲查找的关键数据，参数base指向要被搜索的数组开头地址，参数nmemb 代表数组中的元素数量，每一元素的大小则由参数size决定，最后一项参数compar 为一函数指针，这个函数用来判断两个元素之间的大小关系，若传给compar 的第一个参数所指的元素数据大于第二个参数所指的元素数据则必须回传大于0 的值，两个元素数据相等则回传0。

附加说明 找到关键数据则返回找到的地址，如果在数组中找不到关键数据则返回NULL。

范例 #includestdio.h
#includestdlib.h
#define NMEMB 5
#define SIZE 10
int compar(const void a,const void b)
{
return (strcmp((char )a,(char )b));
}
main()
{
char data[50][size]={“linux”,”freebsd”,”solaris”,”sunos”,”windows”};
char key[80],base ,offset;
int i, nmemb=NMEMB,size=SIZE;
while(1){
printf(“”);
fgets(key,sizeof(key),stdin);
key[strlen(key)-1]=’0’;
if(!strcmp(key,”exit”))break;
if(!strcmp(key,”list”)){
for(i=0;inmemb;i++)
printf(“%sn”,data[i]);
continue;
}
base = data[0];
qsort(base,nmemb,size,compar);
offset = (char ) bsearch(key,bas

e,nmemb,size,compar);
if( offset = =NULL){
printf(“%s not found!n”,key);
strcpy(data[nmemb++],key);
printf(“Add %s to data arrayn”,key);
}else{
printf(“found %s n”,offset);
}
}
}

执行 hello 输入hello字符串
hello not found! 找不到hello 字符串
add hello to data array 将hello字符串加入
.list 列出所有数据
freebsd
linux
solaris
sunos
windows
hello
hello
found hello






lfind（线性搜索）
相关函数 lsearch

表头文件 #includestdlib.h

定义函数 void lfind (const void key,const void base,size_t nmemb,size_t
size,int( compar) (const void ,const void ));

函数说明 lfind()利用线性搜索在数组中从头至尾一项项查找数据。参数key指向欲查找的关键数据，参数base指向要被搜索的数组开头地址，参数nmemb代表数组中的元素数量，每一元素的大小则由参数size决定，最后一项参数compar为一函数指针，这个函数用来判断两个元素是否相同，若传给compar 的异地个参数所指的元素数据和第二个参数所指的元素数据相同时则返回0，两个元素数据不相同则返回非0值。Lfind()与lsearch()不同点在于，当找不到关键数据时lfind()仅会返回NULL，而不会主动把该笔数据加入数组尾端。

返回值 找到关键数据则返回找到的该笔元素的地址，如果在数组中找不到关键数据则返回空指针(NULL)。

范例 参考lsearch()。






lsearch（线性搜索）
相关函数 lfind

表头文件 #includestdlib.h

定义函数 void lsearch(const void key ,const void base ,size_t nmemb,size_t size, int ( compar) (const void ,const void ));

函数说明 lsearch()利用线性搜索在数组中从头至尾一项项查找数据。参数key指向欲查找的关键数据，参数base指向要被搜索的数组开头地址，参数nmemb 代表数组中的元素数量，每一元素的大小则由参数size 决定，最后一项参数compar 为一函数指针，这个函数用来判断两个元素是否相同，若传给compar 的第一个参数所指的元素数据和第二个参数所指的元素数据相同时则返回0，两个元素数据不相同则返回非0 值。如果lsearch（）找不到关键数据时会主动把该项数据加入数组里。

返回值 找到关键数据则返回找到的该笔元素的四肢，如果在数组中找不到关键数据则将此关键数据加入数组，再把加入数组后的地址返回。

范例 #includestdio.h
#includestdlib.h
#define NMEMB 50
#define SIZE 10
int compar (comst void a,const void b)
{
return (strcmp((char ) a, (char ) b));
}
main()
{
char data[NMEMB][SIZE]={“Linux”,”freebsd”,”solzris”,”sunos”,”windows”};
char key[80],base,offset;
int i, nmemb=NMEMB,size=SIZE;
for(i=1;i5;i++){
fgets(key,sizeof9key),stdin);
key[strlen(key)-1]=’0’;
base = data[0];
offset = (cha

r )lfind(key,base,&nmemb,size,compar);
if(offset ==NULL){
printf(“%s not found!n”,key);
offset=(char ) lsearch(key,base,&nmemb,size,compar);
printf(“Add %s to data arrayn”,offset);
}else{
printf(“found %s n”,offset);
}
}
}

执行 linux
foundlinux
os2
os2 not found!
add os2 to data array
os2
foundos2






qsort（利用快速排序法排列数组）
相关函数 bsearch

表头文件 #includestdlib.h

定义函数 void qsort(void base,size_t nmemb,size_t size,int ( compar)(const void , const void ));

函数说明 参数base指向欲排序的数组开头地址，参数nmemb代表数组中的元素数量，每一元素的大小则由参数size决定，最后一项参数compar为一函数指针，这个函数用来判断两个元素间的大小关系，若传给compar的第一个参数所指的元素数据大于第二个参数所指的元素数据则必须回传大于零的值，两个元素数据相等则回传0。

返回值

附加说明

范例 #define nmemb 7
#include stdlib.h
int compar (const void a ,const void b)
{
int aa=(int ) a,bb = (int )b;
if( aa bb)return 1;
if( aa == bb) return 0;
if( aa bb) return -1;
}
main( )
{
int base[nmemb]={ 3,102,5,-2,98,52,18};
int i;
for ( i=0; inmemb;i++)
printf(“%d “,base[i]);
printf(“n”);
qsort(base,nmemb,sizeof(int),compar);
for(i=0;inmemb;i++)
printf(“%d”base[i]);
printf(“n”);
}

执行 3 102 5 -2 98 52 18
-2 3 5 18 52 98 102






rand（产生随机数）
相关函数 srand，random，srandom

表头文件 #includestdlib.h

定义函数 int rand(void)

函数说明 rand()会返回一随机数值，范围在0至RAND_MAX 间。在调用此函数产生随机数前，必须先利用srand()设好随机数种子，如果未设随机数种子，rand()在调用时会自动设随机数种子为1。关于随机数种子请参考srand()。

返回值 返回0至RAND_MAX之间的随机数值，RAND_MAX定义在stdlib.h，其值为2147483647。

范例 产生介于1 到10 间的随机数值，此范例未设随机数种子，完整的随机数产生请参考
srand（）
#includestdlib.h
main()
{
int i,j;
for(i=0;i10;i++)
{
j=1+(int)(10.0rand()(RAND_MAX+1.0));
printf(“%d “,j);
}
}

执行 9 4 8 8 10 2 4 8 3 6
9 4 8 8 10 2 4 8 3 6






srand（设置随机数种子）
相关函数 rand，random srandom

表头文件 #includestdlib.h

定义函数 void srand (unsigned int seed);

函数说明 srand()用来设置rand()产生随机数时的随机数种子。参数seed必须是个整数，通常可以利用geypid()或time(0)的返回值来当做seed。如果每次seed都设相同值，rand()所产生的随机数值每次就会一样。

返回值

范例 产生介于1 到10 间的随机数值，此范例与执行结果可与rand（）参照
#includetime.h
#includestdlib.h
main()
{
int i,j;

srand((int)time(0));
for(i=0;i10;i++)
{
j=1+(int)(10.0rand()(RAND_MAX+1.0));
printf(“ %d “,j);
}
}

执行 5 8 8 8 10 2 10 8 9 9
2 9 7 4 10 3 2 10 8 7