闽高校计算机二级C语言常用算法.docx

常用算法
1．求最大公约数与最小公倍数
例1：求两个正数的最大公约数。
⑴循环实现
用辗转相除法，m、n是两个正整数,r 是余数，用直到循环操作的流程图：
#include<stdio.h>
int main()
{
int m,n,r;
do
{
printf("Please input tow positive integert:");
scanf("%d %d",&m,&n);
}while(m<=0||n<=0);
do
{
r=m%n;
m=n;
n=r;
}while(r!=0);
printf("The greatest command factor is:%d\n",m);
return 0;
}

⑵函数递归调用实现
用递归算法求m与n的最大公约数。
设求m和n最大公约数的函数为gcd(m,n),根据辗转相除求最大公约数的思想，其递归算法为：

#include<stdio.h>
int gcd(int m,int n);
int main()
{
int m,n;
printf("Input tow number:\n");
scanf("%d %d",&m,&n);
printf("Greatest common divisor of %d and %d=%d\n",m,n,gcd(m,n));
return 0;
}
int gcd(int m,int n)
{
int g;
if(n==0) /*若除操作的余数为0*/
g=m; /*则除数为最大公约数*/
else
g=gcd(n,m%n);/*上次除操作的除数和余数作参数递归调用gcd()函数*/
return g;
}

2. 求阶乘
例2： 求1！+2！+……+n!。
⑴循环实现
#include <stdio.h>
int main(void)
{
int i,n;
long s=0,p=1;
printf("Input a integer:");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
p*=i;
s+=p;
}
printf("1!+2!+……+%d=%ld\n",n,s);
return 0;
}
⑵函数递归调用实现
#include <stdio.h>
long fact(int n)
{
long p;
if(n==1)
p=1;
else
p=n*fact(n-1);
return p;
}
int main(void)
{
int i,n;
long s=0,p=1;
printf("Input a integer:");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
s+=fact(i);
}
printf("1!+2!+……+%d=%ld\n",n,s);
return 0;
}

3．求素数
例3：求3至1000间的全部素数。
#include<stdio.h>
#include<math.h>
main()
{
int m,i,k,n=0;
short prime;
for(m=3;m<=1000;m=m+2)
{
prime=1;
k=(int)(sqrt(m));
for(i=2;i<=k;i++)
if(m%i==0)
{
prime=0;
break;
}
if(prime)
{
printf("%5d",m);
n=n+1;
}
if(n==10){n=0;printf("\n");}
}
printf("\n");
return 0;
}

4．Fibonacii数列
例4：求Fibonacci数列前20个数。这个数列有如下特点：第1、2个数为1、1，从第3个数开始，每个数是其前两个数和之和。即：
1，1，2，3，5，8，13，21，……
⑴循环实现
#include<stdio.h>
main()
{
long f1,f2;
int i;
f1=f2=1;
for(i=1;i<=20;i++)
{
printf("%-12ld %-12ld",f1,f2);/ *右对齐占12字符*/
if(i%2==0)printf("\n");
f1=f1+f2;
f2=f2+f1;
}
return 0;
}

⑵函数递归调用实现
#include<stdio.h>
int f(int i)
{
int fi;
if(i==1 || i==2)
fi=1;
else
fi=f(i-1)+f(i-2);
return fi;
}
main()
{
int i;
for(i=1;i<=20;i++)
{
printf("%-12ld ",f(i));/ *右对齐占12字符*/
if(i%4==0)printf("\n");
}
return 0;
}

5．整数各位数字的拆分
例5：输入一个正整数，要求以相反的顺序输出该数各位。
（1）用递归方法实现。
#include<stdio.h>
void f(int n)
{
if(n>0)
{
printf("%d ",n%10);
f(n/10);
}
}
int main()
{
int n;
printf("Input a integer:");
scanf("%d",&n);
f(n);
putchar('\n');
return 0;
}
例6：求一正长整型数的各位数字之和。
（2）用递归算法实现
#include<stdio.h>
int f(long n)
{
static int s=0;
if(n>0)
{
s+=n%10;
f(n/10);
}
return s;
}
void main()
{
long n;
printf("Input a integer:");
scanf("%ld",&n);
printf("digital sum=%d\n",f(n));
}
注：这里存储累加和的变量s必须定义为静态变量或全局变量，否则不能实现各位数字的累加。

6．排序
例7：编写程序，对10个数排序(按由小到大顺序)。
⑴冒泡法排序
[冒泡法]思路：想念两个数比较，小者前移，大者后移。
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
int main()
{
int a[10],i,j,t;
srand((unsigned)time( NULL));/ *初始化rand()函数*/
for(i=0;i<10;i++)
a[i]=rand()%100; /*用随机数为数组元素赋值*/
printf("Before sorted:\n");
for(i=0;i<10;i++)
printf("%d ",a[i]);
putchar('\n');
for(j=0;j<9;j++)
for(i=0;i<10-j;i++)
if(a[i]>a[i+1])
{
t=a[i];a[i]=a[i+1];a[i+1]=t;
}
printf("After sorted:\n");
for(i=0;i<10;i++)
printf("%d ",a[i]);
putchar('\n');
return 0;
}

⑵选择法排序
[选择法]
思路：用一个变量k保存当前最小元素的下标,不进行交换,直到完成一次内循环的比较后,把a(k)交换到希望的位置a(i):
①令k=0,a(k)与a(1)比较,若a(k)>a(1),令k=1,小者的下标存放在k中;
② a(k)又与a(2),a(3),……,直到a(10),重复①的工作,结束后,实现10个数中的最小者存放在a(k)中。
③a(1)与a(k)交换,把最小者存放在a(1)中。
④分别令k=1,2,3,….,9重复①②③的操作。
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
int main()
{
int a[10],i,j,t,k;
srand((unsigned)time( NULL));/ *初始化rand()函数*/
for(i=0;i<10;i++)
a[i]=rand()%100; / *用随机数为数组元素赋值*/
printf("Before sorted:\n");
for(i=0;i<10;i++)
printf("%d ",a[i]);
putchar('\n');
for(i=0;i<9;i++)
{
k=i;
for(j=i+1;j<10;j++)
if(a[k]>a[j])k=j;
t=a[i];a[i]=a[k];a[k]=t;
}
printf("After sorted:\n");
for(i=0;i<10;i++)
printf("%d ",a[i]);
putchar('\n');
return 0;
}

7．数组元素的查找
例8：对于已知的数组a，要求查找给定值key.
⑴直接查找
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
int intSearch(int a[],int key,int n)
{
int i,j;
for(i=0;i<n;i++)
{
if(key==a[i])
j=i;
}
return j;
}
int main()
{
int a[10],i,key,j;
srand((unsigned)time( NULL));/ *初始化rand()函数*/
for(i=0;i<10;i++)
{
a[i]=rand()%100; /*用随机数为数组元素赋值*/
printf("%d ",a[i]);
}
putchar('\n');
printf("Input a integer:");
scanf("%d",&key);
j=intSearch(a,key,10);
printf("%d : %d\n",j,a[j]);
return 0;
}

⑵二分查找
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
void intSort(int a[],int n)
{
int i,k,j,t;
for(i=0;i<n;i++)
{
k=i;
for(j=i+1;j<n;j++)
if(a[k]>a[j])k=j;
t=a[i];a[i]=a[k];a[k]=t;
}
}
int intSearch(int a[],int key,int n)
{
int j=-1,low,high,mid;
low=0;high=n-1;
do
{
mid=(low+high)/2;
if(key==a[mid])
{
j=mid;
break;
}
else if(key>a[mid])
low=mid+1;
else
high=mid-1;
}while(j==-1 && low<high);
return j;
}
void print(int a[],int n)
{
int i;
for(i=0;i<n;i++)
printf("%d ",a[i]);
putchar('\n');
}
int main()
{
int a[15],i,key,j;
srand((unsigned)time( NULL));/ *初始化rand()函数*/
for(i=0;i<15;i++)
a[i]=rand()%100; /*用随机数为数组元素赋值*/
print(a,15);
intSort(a,15);
print(a,15);
printf("Input a integer:");
scanf("%d",&key);
j=intSearch(a,key,10);
printf("%d : %d\n",j,a[j]);
return 0;
}

8．字符串处理
例9：函数reverse(s）的功能是将字符串s中的字符位置顺序颠倒过来（例如，字符串abcdefg 中的字符位置顺序颠倒后变为gfedcba )，测试用土函数如下所示，请编制函数reverse。
#include<stdio.h>
#include<string.h>
void main()
{
void reverse(char s[]);
char s1[80];
gets(s1);
reverse(s1);
puts(s1);
}
void reverse(char s[])
{
char c;
char *p1=s;
char *p2=s;
while(*p2!='\0')
p2++;
p2--;
while(p1<p2)
{
c=*p1;
*p1++=*p2;
*p2--=c;
}
}

9．文件操作
例10：把命令行参数中的前一个文件名标识的文件，复制到后一个文件名标识的文件中，如命令行中只有一个文件名则把该文件写到标准输出文件(显示器)中。
#include<stdio.h>
#include<stdlib.h>
#include<conio.h> /*引用函数getch()* /
main(int argc,char *argv[])
{
FILE *fp1,*fp2;
char ch;
if(argc==1)
{
printf("have not enter file name strike any key exit");
getch();
exit(0);
}
if((fp1=fopen(argv[1],"rt"))==NULL)
{
printf("Cannot open %s\n",argv[1]);
getch(); /*按任意键退出*/
exit(1);
}
if(argc==2) fp2=stdout;/ *命令行只有一个文件fp2指向标准输出*/
else if((fp2=fopen(argv[2],"wt+"))==NULL)
{
printf("Cannot open %s\n",argv[1]);
getch();
exit(1);
}
while((ch=fgetc(fp1))!=EOF)
fputc(ch,fp2);
fclose(fp1);
fclose(fp2);
}
说明：
stdout:是标准输出文件指针，即显示器。

10．链表的操作（结点的遍历、插入、删除）
⑴建立链表
例11: 写一个函数，建立5名学生数据的单向链表，每一个学生的数据块(结点)定义如下：
struct student
{
long num;
float score;
struct student ?next;
};
同时定义三个指向这种类型的指针变量head, p1, p2.
一开始head?null
p1: 新分配的结点地址
p2: 已分配的最后一个结点地址
约定：当输入学号=0时，结束，返回表头
#include<stdio.h>
#include<stdlib.h>
#define LEN sizeof(struct student)
struct student
{
long num;
float score;
struct student * next;
};
int n;
struct student *creat()
{
struct student *head, *p1, *p2;
n=0;
p1=p2=(struct student *)malloc(LEN);
scanf("%d, %f", &p1->num, &p1->score);
head=NULL;
while (p1->num!=0) /*输入0终止*/
{
n++;
if(n==1)head=p1; /*输入的第一组数据为头结点*/
else p2->next=p1;/ *以后输入的数据为前一个结点的后继*/
p2=p1; /* p2指向新输入的结点*/
p1=(struct student *)malloc(LEN);/ *为新结点分配空间*/
scanf("%ld, %f", &p1->num, &p1->score);
}
p2->next=NULL;/ *尾结点的后继置空*/
return(head); /*返回头结点*/
}
⑵输出链表（链表遍历）
void print(struct student * head)
{
struct student *p;
p=head;
if(p==NULL)return;
do
{
printf("%ld %5.1f \n", p->num, p->score);
p=p->next;
}while (p!=NULL);
}

⑶删除一个结点
一般给出某一条件，当某一条件成立时，则删除该结点：
表为空时，无任何删除；
当第一个结点被删除时，修改表头；
当最后一个结点不满足条件时，返回。
struct student * del(struct student * head,long num)
{
struct student *p1, *p2;
if(head==NULL)
{
printf("\n list null!=\n");
return (head);
}
p1=head;
while(num!=p1->num && p1->next!=NULL)
{
p2=p1; p1=p1->next;
}
if(num==p1->num)
{
if(p1==head)head=p1->next;
else p2->next=p1->next;
printf("delete: %ld \n", num);
n--;
}
else printf ("%ld not been found!\n", num);
return head;
}

⑷链表的插入操作
一般情况：链表中结点的关键数据已排好序，待插入结点的关键数据与链表中的关键数据一一比较，插入适当的位置。
方法：设链表中按num已排序好
struct student * insert(struct student * head, struct student * stud)
{
struct student * p0, * p1, * p2;
p1=head;
p0=stud;
if(head==NULL)
{
head=p0; p0->next=NULL;
}
else
{
while((p0->num>p1->num)&&(p1->next!=NULL))
{
p2=p1; p1=p1->next;
}
if(p0->num<=p1->num)
{
if(head==p1)
head=p0;
else
{
p2->next=p0;
p0->next=p1;
}
}
else
{
p1->next=p0;
p0->next=NULL;
}
}
n++;
return(head);
}
将以上函数集中，由main( )函数调用，可建立一个处理链表结构的程序。
void main( )
{
struct student * head, *stu;
long del_num;
printf("input records: \n ");
head=creat();
print(head);
printf(" \ninput the deleted number: ");
scanf("%ld", &del_num);
while(del_num!=0)
{
head=del(head, del_num);
print(head);
printf("input the deleted number: ");
scanf("%ld", &del_num);
}
printf("\ninput the inserted record: ");
stu=(struct student *)malloc(LEN);
scanf("%ld, %f", &stu->num, &stu->score);
while (stu->num!=0)
{
head=insert(head, stu);
printf("input the inserted record: ");
stu=(struct student *) malloc(LEN);
scanf("%ld, %f",&stu->num, &stu->score);
}
print(head);
}

11. 输出字符图形。
例12：以下程序打印如下图案，程序运行后输入4给变量n，请填空。

#include<stdio.h>
#define S ' '
void main()
{
int i,j,n;
printf("Enter n:");
scanf("%d",&n);
for(i=1;i<=n;i++) /*控制输出前年n行*/
{
for(j=1;j<=10;j++)putchar(S);
for(j=1;j<=n-i;j++)putchar(S);/ *每行的启始空格越来越少*/
for(j=1;j<i*2;j++)putchar('*');/ *每行的'*'越来越多*/
putchar('\n');
}
for(i=1;i<=n-1;i++) /*控制输出后n-1行*/
{
for(j=1;j<=10;j++)putchar(S);
for(j=1;j<=i;j++)putchar(S); /*每行的启始空格越来越多*/
for(j=1;j<(n-i)*2;j++)putchar('*');/ *每行的'*'越来越少*/
putchar('\n');
}
}

注：各星号之间带空格：

程序如下：
#include<stdio.h>
#define S ' '
void main()
{
int i,j,n;
printf("Enter n:");
scanf("%d",&n);
for(i=1;i<=n;i++) /*控制输出前n行*/
{
for(j=1;j<=10;j++)putchar(S);
for(j=1;j<=n-i;j++){putchar(S);putchar(S);}/ *每行的启始空格越来越少*/
for(j=1;j<i*2;j++){putchar('*');putchar(' ');}/* 每行的'*'越来越多*/
putchar('\n');
}
for(i=1;i<=n-1;i++) /*控制输出后n-1行*/
{
for(j=1;j<=10;j++)putchar(S);
for(j=1;j<=i;j++){putchar(S);putchar(S);}/ *每行的启始空格越来越多*/
for(j=1;j<(n-i)*2;j++){putchar('*');putchar(' ');}/ *每行的'*'越来越少*/
putchar('\n');
}
}

例13：编程输出下列图案：
AAAAAAAAAAAA
BBBBBBBBBB
CCCCCCCC
DDDDDD
EEEE
FF

#include<stdio.h>
void main()
{
int i,j,k;
char c='A';
for(i=6;i>0;i--) /*外循环控制输出6行*/
{
for(k=6-i;k>0;k--)putchar(' '); /*输出每行前的空格*/
for(j=1;j<=2*i;j++) /*输出一行字母*/
putchar(c);
c++;
putchar('\n'); /*一行结束回车换行*/
}
}