文档介绍：九常用算法
字符串
将字符串S复制到串T。
void strcopy(char *S,char *T)
{
int i;
for(i=0;____;i++)______;
______;
}
S[i]!=0 或者 S[i]
T[i]=S[i]
T[i]=0
九常用算法
字符串
判断串是否为空串。空串返回1,否则返回0
int strempty(char *S)
{
return(______);
}
S[0]=='\0'
!S[0]
*S=='\0'
!*S
九常用算法
字符串
两个字符串s,t的大小比较,如果s>t返回一个正数,如果s=t返回0,如果s<t返回一个负数。
int strcmp(char *s,char *t)
{
int i;
for(i=0;_____;i++);
return(_______);
}
s[i]!=0 && t[i]!=0 && s[i]==t[i]
s[i]-t[i]
九常用算法
字符串
求字符串s的长度。
int strlength(char *s)
{int i;
____________
return i;
}
for(i=0;s[i]!=0;i++);
九常用算法
字符串
将两个字符串s1,s2合并为一个新的串t。
void concat(char *s1,char *s2,char *t)
{int i=0,j=0;
for(i=0;s1[i]!=0;i++)_______;
for(j=0;s2[j]!=0;j++)_______;
______
}
t[i]=s1[i]
t[i++]=s2[j] 或 t[i+j]=s2[j]
t[i]=0; 或t[i+j]=0
九常用算法
字符串
求一个串s中从位置pos起长度为len的子串。如果位置超出,则子串为空串,如果长度超出,则到结束为止。
void substr(char *sub,char *s,int pos,int len)
{int i,j;
for(i=0;i<pos && s[i]!=0;i++);
if(s[i]==0)______;
else{
for(j=0;s[i]!=0 && len>0;j++,i++,len--)
______;
_______;
}
}
sub[0]=0
sub[j]=s[i]
sub[j]=0
九常用算法
查找算法
对于数组的元素的查找,通常有2种方法:
(1)顺序查找
(2)折半查找(要求有序)
如:
2, 6, 7, 11, 14, 15, 19, 20,26,28
查找11
2, 6, 7, 11, 14, 15, 19, 20,26,28
↑
2, 6, 7, 11
↑
7, 11
↑
11
↑
平均查找次数:约log2n
<=
return mid
high=mid-1
low=mid+1
折半查找值为e的元素,返回找到的位置,如果找不到,返回-1
int bisearch(float r[],int n,float e)
{
int low,high
low=0;high=n-1;
while(low____high){
mid=(low+high)/2;
if(r[mid]==e)_______;
if(e<r[mid])_______;
else ____________;
}
return –1;
}
九常用算法
其他算法
两变量a,b交换值:
(1)用中间变量交换
t=a;a=b;b=t;
(2)用函数交换
swap(&a,&b);
.......
void swap(int *a,int *b)
{ int t;
t=*a;*a=*b;*b=t;}
(3) 不用临时变量(整型、字符型、实型)
a=a+b;
b=a-b;
a=a-b;
(4)不用临时变量,用异或实现(整型、字符型)
a=a^b;
b=a^b;
a=a^b;
九常用算法
其他算法
求两整数a,b的最大公约数
辗转相除法
辗转相除,取余数
126
328
126
76
50
26
24
2
0
最大公约数
九常用算法
其他算法
求两整数a,b的最大公约数
318
126
66
60
6
0
最大公约数