非常全的C语言常用算法.pdf

《非常全的C语言常用算法.pdf》由会员分享，可在线阅读，更多相关《非常全的C语言常用算法.pdf（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-一、根本算法 1交换两量交换借助第三者 例 1、任意读入两个整数，将二者的值交换后输出。main()int a,b,t;scanf(%d%d,&a,&b);printf(%d,%dn,a,b);t=a;a=b;b=t;printf(%d,%dn,a,b);【解析】程序中加粗局部为算法的核心，如同交换两个杯子里的饮料，必须借助第三个空杯子。假设输入的值分别为 3、7，则第一行输出为 3，7；第二行输出为 7，3。其中 t 为中间变量，起到“空杯子的作用。注意：三句赋值语句赋值号左右的各量之间的关系！【应用】例 2、任意读入三个整数，然后按从小到大的顺序输出。main()int a,b,c,t;

2、scanf(%d%d%d,&a,&b,&c);/*以下两个 if 语句使得 a 中存放的数最小*/if(ab)t=a;a=b;b=t;if(ac)t=a;a=c;c=t;/*以下 if 语句使得 b 中存放的数次小*/if(bc)t=b;b=c;c=t;printf(%d,%d,%dn,a,b,c);2累加 累加算法的要领是形如“s=s+A的累加式，此式必须出现在循环中才能被反复执行，从而实现累加功能。“A通常是有规律变化的表达式，s 在进入循环前必须获得适宜的初值，通常为 0。例 1、求 1+2+3+100 的和。main()int i,s;s=0;i=1;while(i=100)s=s+i

3、;/*累加式*/i=i+1;/*特殊的累加式*/printf(1+2+3+.+100=%dn,s);【解析】程序中加粗局部为累加式的典型形式，赋值号左右都出现的变量称为累加器，其中“i=i+1为特殊的累加式，每次累加的值为 1，这样的累加器又称为计数器。-3累乘 累乘算法的要领是形如“s=s*A的累乘式，此式必须出现在循环中才能被反复执行，从而实现累乘功能。“A通常是有规律变化的表达式，s 在进入循环前必须获得适宜的初值，通常为 1。例 1、求 10！分析10！=12310 main()int i;long c;c=1;i=1;while(i=10)c=c*i;/*累乘式*/i=i+1;pri

4、ntf(1*2*3*.*10=%ldn,c);二、非数值计算常用经典算法 1穷举 也称为“枚举法，即将可能出现的每一种情况一一测试，判断是否满足条件，一般采用循环来实现。例 1、用穷举法输出所有的水仙花数即这样的三位正整数：其每位数位上的数字的立方和与该数相等，比方：13+53+33=153。法一 main()int*,g,s,b;for(*=100;*=999;*+)g=*%10;s=*/10%10;b=*/100;if(b*b*b+s*s*s+g*g*g=*)printf(%dn,*);【解析】此方法是将 100 到 999 所有的三位正整数一一考察，即将每一个三位正整数的个位数、十位数、

5、百位数一一求出各数位上的数字的提取算法见下面的“数字处理，算出三者的立方和，一旦与原数相等就输出。共考虑了 900 个三位正整数。法二 main()int g,s,b;for(b=1;b=9;b+)for(s=0;s=9;s+)for(g=0;g=9;g+)if(b*b*b+s*s*s+g*g*g=b*100+s*10+g)printf(%dn,b*100+s*10+g);【解析】此方法是用 1 到 9 做百位数字、0 到 9 做十位和个位数字，将组成的三位正整数与每一组的三个数的立方和进展比拟，一旦相等就输出。共考虑了 900 个组合外循环单独执行的次数为 9，两个循环单独执行的次数分别为

6、10 次，故 if 语句被执行的次数为 91010=900，即900 个三位正整数。与法一判断的次数一样。-2排序 1冒泡排序起泡排序 假设要对含有 n 个数的序列进展升序排列，冒泡排序算法步骤是：从存放序列的数组中的第一个元素开场到最后一个元素，依次对相邻两数进展比拟，假设前者大后者小，则交换两数的位置；第趟完毕后，最大数就存放到数组的最后一个元素里了，然后从第一个元素开场到倒数第二个元素，依次对相邻两数进展比拟，假设前者大后者小，则交换两数的位置；重复步骤n-1 趟，每趟比前一趟少比拟一次，即可完成所求。例 1、任意读入 10 个整数，将其用冒泡法按升序排列后输出。*define n 10

7、 main()int an,i,j,t;for(i=0;in;i+)scanf(%d,&ai);for(j=1;j=n-1;j+)/*n 个数处理 n-1 趟*/for(i=0;iai+1)t=ai;ai=ai+1;ai+1=t;for(i=0;in;i+)printf(%dn,ai);2选择法排序 选择法排序是相对好理解的排序算法。假设要对含有 n 个数的序列进展升序排列，算法步骤是：从数组存放的 n 个数中找出最小数的下标算法见下面的“求最值，然后将最小数与第1 个数交换位置；除第 1 个数以外，再从其余 n-1 个数中找出最小数即 n 个数中的次小数的下标，将此数与第 2 个数交换位置；

8、重复步骤n-1 趟，即可完成所求。例 1、任意读入 10 个整数，将其用选择法按升序排列后输出。*define n 10 main()int an,i,j,k,t;for(i=0;in;i+)scanf(%d,&ai);for(i=0;in-1;i+)/*处理 n-1 趟*/k=i;/*总是假设此趟处理的第一个即全部数的第 i 个数最小，k 记录其下标*/for(j=i+1;jn;j+)if(aj ak)k=j;if(k!=i)t=ai;ai=ak;ak=t;for(i=0;ian-2)an-1=*;/*比最后一个数还大就往最后一个元素中存放*/else /*查找待插位置*/j=0;while

9、(jaj)j+;/*从最后一个数开场直到待插位置上的数依次后移一位*/for(k=n-2;k=j;k-)ak+1=ak;aj=*;/*插入待插数*/for(j=0;j=n-1;j+)printf(%d ,aj);插入法排序的要领就是每读入一个数立即插入到最终存放的数组中，每次插入都使得该数组有序。例 2、任意读入 10 个整数，将其用插入法按降序排列后输出。*define n 10 main()int an,i,j,k,*;scanf(%d,&a0);/*读入第一个数，直接存到 a0中*/for(j=1;jn;j+)/*将第 2 至第 10 个数一一有序插入到数组 a 中*/scanf(%d,

10、&*);if(*aj-1)aj=*;/*比原数列最后一个数还小就往最后一个元素之后存放新读的数*/else /*以下查找待插位置*/i=0;while(*ai&i=i;k-)ak+1=ak;ai=*;/*插入待插数*/for(i=0;in;i+)printf(%dn,ai);4归并排序 即将两个都升序或降序排列的数据序列合并成一个仍按原序排列的序列。例 1、有一个含有 6 个数据的升序序列和一个含有 4 个数据的升序序列，将二者合并成一个含有10 个数据的升序序列。*define m 6*define n 4 main()int am=-3,6,19,26,68,100,bn=8,10,12,

11、22;int i,j,k,cm+n;-i=j=k=0;while(im&jn)/*将 a、b 数组中的较小数依次存放到 c 数组中*/if(ai=m&j=n&im)/*假设 b 中数据全部存放完毕，将 a 中余下的数全部存放到 c 中*/ck=ai;k+;i+;for(i=0;im+n;i+)printf(%d ,ci);3查找 1顺序查找即线性查找 顺序查找的思路是：将待查找的量与数组中的每一个元素进展比拟，假设有一个元素与之相等则找到；假设没有一个元素与之相等则找不到。例 1、任意读入 10 个数存放到数组 a 中，然后读入待查找数值，存放到*中，判断 a 中有无与*等值的数。*defin

12、e N 10 main()int aN,i,*;for(i=0;iN;i+)scanf(%d,&ai);/*以下读入待查找数值*/scanf(%d,&*);for(i=0;iN;i+)if(ai=*)break;/*一旦找到就跳出循环*/if(iN)printf(Found!n);else printf(Not found!n);2折半查找即二分法 顺序查找的效率较低，当数据很多时，用二分法查找可以提高效率。使用二分法查找的前提是数列必须有序。二分法查找的思路是：要查找的关键值同数组的中间一个元素比拟，假设一样则查找成功，完毕；否则判别关键值落在数组的哪半局部，就在这半局部中按上述方法继续比拟

13、，直到找到或数组中没有这样的元素值为止。例 1、任意读入一个整数*，在升序数组 a 中查找是否有与*等值的元素。*define n 10 main()int an=2,4,7,9,12,25,36,50,77,90;int*,high,low,mid;/*为关键值*/scanf(%d,&*);high=n-1;low=0;mid=(high+low)/2;while(amid!=*&lowhigh)if(*amid)high=mid-1;/*修改区间上界*/-else low=mid+1;/*修改区间下界*/mid=(high+low)/2;if(*=amid)printf(Found%d,%

14、dn,*,mid);else printf(Not foundn);三、数值计算常用经典算法：1级数计算 级数计算的关键是“描述出通项，而通项的描述法有两种：一为直接法、二为间接法又称递推法。直接法的要领是：利用项次直接写出通项式；递推法的要领是：利用前一个或多个通项写出后一个通项。可以用直接法描述通项的级数计算例子有：11+2+3+4+5+21+1/2+1/3+1/4+1/5+等等。可以用间接法描述通项的级数计算例子有：11+1/2+2/3+3/5+5/8+8/13+21+1/2!+1/3!+1/4!+1/5!+等等。1直接法求通项 例 1、求 1+1/2+1/3+1/4+1/5+1/100

15、 的和。main()float s;int i;s=0.0;for(i=1;i=100;i+)s=s+1.0/i;printf(1+1/2+1/3+.+1/100=%fn,s);【解析】程序中加粗局部就是利用项次 i 的倒数直接描述出每一项，并进展累加。注意：因为 i 是整数，故分子必须写成 1.0 的形式！2间接法求通项即递推法 例 2、计算以下式子前 20 项的和：1+1/2+2/3+3/5+5/8+8/13+。分析此题后项的分子是前项的分母，后项的分母是前项分子分母之和。main()float s,fz,fm,t,fz1;int i;s=1;/*先将第一项的值赋给累加器 s*/fz=1;

16、fm=2;t=fz/fm;/*将待加的第二项存入 t 中*/for(i=2;i=20;i+)s=s+t;/*以下求下一项的分子分母*/fz1=fz;/*将前项分子值保存到 fz1 中*/fz=fm;/*后项分子等于前项分母*/-fm=fz1+fm;/*后项分母等于前项分子、分母之和*/t=fz/fm;printf(1+1/2+2/3+.=%fn,s);下面举一个通项的一局部用直接法描述，另一局部用递推法描述的级数计算的例子：例 3、计算级数2!102xnnnn的值，当通项的绝对值小于 eps 时计算停顿。*include float g(float*,float eps);main()floa

17、t*,eps;scanf(%f%f,&*,&eps);printf(n%f,%fn,*,g(*,eps);float g(float*,float eps)int n=1;float s,t;s=1;t=1;do t=t*/(2*n);s=s+(n*n+1)*t;/*加波浪线的局部为直接法描述局部，t 为递推法描述局部*/n+;while(fabs(t)eps);return s;2一元非线性方程求根 1牛顿迭代法 牛顿迭代法又称牛顿切线法：先任意设定一个与真实的根接近的值*0作为第一次近似根，由*0求出 f(*0),过(*0，f(*0)点做 f(*)的切线，交*轴于*1，把它作为第二次近似根

18、，再由*1求出 f(*1),过(*1，f(*1)点做 f(*)的切线，交*轴于*2，如此继续下去，直到足够接近比方|*-*0|=1e-5);printf(%fn,*);2二分法 算法要领是：先指定一个区间*1,*2，如果函数 f(*)在此区间是单调变化的，则可以根据 f(*1)和 f(*2)是否同号来确定方程 f(*)=0 在区间*1,*2是否有一个实根；如果 f(*1)和 f(*2)同号，则 f(*)在-区间*1,*2无实根，要重新改变*1和*2的值。当确定 f(*)在区间*1,*2有一个实根后，可采取二分法将*1,*2一分为二，再判断在哪一个小区间中有实根。如此不断进展下去，直到小区间足够

19、小为止。具体算法如下：1输入*1和*2的值。2求 f(*1)和 f(*2)。3如果 f(*1)和 f(*2)同号说明在*1,*2 无实根，返回步骤1，重新输入*1和*2的值；假设 f(*1)和 f(*2)不同号，则在区间*1,*2必有一个实根，执行步骤4。4求*1和*2的中点：*0=*1+*2/2。5求 f(*0)。6判断 f(*0)与 f(*1)是否同号。如果同号，则应在*0,*2中寻找根，此时*1已不起作用，用*0代替*1，用 f(*0)代替 f(*1)。如果不同号，则应在*1,*0中寻找根，此时*2已不起作用，用*0代替*2，用 f(*0)代替 f(*2)。7判断 f(*0)的绝对值是否

20、小于*一指定的值例如 10-5。假设不小于 10-5，则返回步骤4重复执行步骤4、5、6；否则执行步骤8。8输出*0的值，它就是所求出的近似根。例如，用二分法求方程 2*3-4*2+3*-6=0 在(-10，10)之间的根。*include math.h main()float*1,*2,*0,f*1,f*2,f*0;do printf(Enter*1&*2);scanf(%f%f,&*1,&*2);f*1=2*1*1*1-4*1*1+3*1-6;f*2=2*2*2*2-4*2*2+3*2-6;while(f*1*f*20);do*0=(*1+*2)/2;f*0=2*0*0*0-4*0*0+3

21、*0-6;if(f*0*f*1)1e-5);printf(%fn,*0);3梯形法计算定积分 定积分badxxf)(的几何意义是求曲线 y=f(*)、*=a、*=b 以及*轴所围成的面积。可以近似地把面积视为假设干小的梯形面积之和。例如，把区间a,b分成 n 个长度相等的 小区间，每个小区间的长度为 h=(b-a)/n，第 i 个小梯形的面积为 f(a+(i-1)h)+f(a+ih)h/2，将 n 个小梯形面积加起来就得到定积分的近似值：根据以上分析，给出“梯形法求定积分的 N-S 构造图：输入区间端点：a，b-输入等分数 n h=(b-a)/2,s=0 i 从 1 到 n si=(f(a+(

22、i-1)*h)+f(a+i*h)*h/2 s=s+si 输出 s 上述程序的几何意义比拟明显，容易理解。但是其中存在重复计算，每次循环都要计算小梯形的上、下底。其实，前一个小梯形的下底就是后一个小梯形的上底，完全不必重复计 算。为此做出如下改良：矩形法求定积分则更简单，就是将等分出来的图形当作矩形，而不是梯形。例如：求定积分40)2*3*(dxxxx的值。等分数 n=1000。*include math.h float DJF(float a,float b)float t,h;int n,i;float HSZ(float*);n=1000;h=fabs(a-b)/n;t=(HSZ(a)+H

23、SZ(b)/2;for(i=1;i=1;day-)peach=(peach+1)*2;printf(The first day:%dn,peach);又如，用迭代法求*=a的根。求平方根的迭代公式是：*n+1=0.5(*n+a/*n)算法 1设定一个初值*0。2用上述公式求出下一个值*1。3再将*1代入上述公式，求出下一个值*2。4如此继续下去，直到前后两次求出的*值*n+1和*n满足以下关系：|*n+1-*n|=1e-5);printf(%fn,*1);2进制转换 1十进制数转换为其他进制数 一个十进制正整数 m 转换成 r 进制数的思路是，将 m 不断除以 r 取余数，直到商为 0 时止，

24、以反序输出余数序列即得到结果。注意，转换得到的不是数值，而是数字字符串或数字串。例如，任意读入一个十进制正整数，将其转换成二至十六任意进制的字符串。void tran(int m,int r,char str,int*n)char sb=0123456789ABCDEF;int i=0,g;dog=m%r;stri=sbg;m=m/r;i+;while(m!=0);*n=i;main()int*,r0;/*r0 为进制基数*/int i,n;/*n 中存放生成序列的元素个数*/-char a50;scanf(%d%d,&*,&r0);if(*0&r0=2&r0=0;i-)printf(%c,a

25、i);printf(n);else e*it(0);2其他进制数转换为十进制数 其他进制整数转换为十进制整数的要领是：“按权展开，例如，有二进制数 101011，则其十进制形式为 125+024+123+022+121+120=43。假设 r 进制数 ana2a1n 位数转换成十进制数，方法是 anr n-1+a2r1+a1r0。注意：其他进制数只能以字符串形式输入。例 1、任意读入一个二至十六进制数字符串，转换成十进制数后输出。*include string.h*include ctype.h main()char*20;int r,d;gets(*);/*输入一个 r 进制整数序列*/sc

26、anf(%d,&r);/*输入待处理的进制基数 2-16*/d=Tran(*,r);printf(%s=%dn,*,d);int Tran(char*p,int r)int d,i,cr;char fh,c;d=0;fh=*p;if(fh=-)p+;for(i=0;i=A)cr=toupper(c)-A+10;elsecr=c-0;d=d*r+cr;if(fh=-)d=-d;return(d);3矩阵转置 矩阵转置的算法要领是：将一个 m 行 n 列矩阵即 mn 矩阵的每一行转置成另一个 nm 矩阵的相应列。例 1、将以下 23 矩阵转置后输出。-即将 1 2 3 转置成 1 4 4 5 6

27、2 5 3 6 main()int a23,b32,i,j,k=1;for(i=0;i2;i+)for(j=0;j3;j+)aij=k+;/*以下将 a 的每一行转存到 b 的每一列*/for(i=0;i2;i+)for(j=0;j3;j+)bji=aij;for(i=0;i3;i+)/*输出矩阵 b*/for(j=0;j2;j+)printf(%3d,bij);printf(n);4字符处理 1字符统计：对字符串中各种字符出现的次数的统计。典型例题：任意读入一个只含小写字母的字符串，统计其中每个字母的个数。*include stdio.h main()char a100;int n26=0;

28、int i;/*定义 26 个计数器并置初值 0*/gets(a);for(i=0;ai!=0;i+)/*n0中存放a的个数，n1 中存放b的个数*/nai-a+;/*各字符的 ASCII 码值减去a的 ASCII 码值，正好得到对应计数器下标*/for(i=0;i26;i+)if(ni!=0)printf(%c:%dn,i+a,ni);2字符加密 例如、对任意一个只含有英文字母的字符串，将每一个字母用其后的第三个字母替代后输出字母*后的第三个字母为 A，字母 Y 后的第三个字母为 B，字母 Z 后的第三个字母为 C。*include stdio.h*include string.h main

29、()char a80=China;int i;for(i=0;i=*&ai=*&ai=Z)ai=ai-26+3;else ai=ai+3;puts(a);5整数各数位上数字的获取-算法核心是利用“任何正整数整除 10 的余数即得该数个位上的数字的特点，用循环从低位到高位依次取出整数的每一数位上的数字。例 1、任意读入一个 5 位整数，输出其符号位及从高位到低位上的数字。main()long*;int w,q,b,s,g;scanf(%ld,&*);if(*0)printf(-,);*=-*;w=*/10000;/*求万位上的数字*/q=*/1000%10;/*求千位上的数字*/b=*/100%

30、10;/*求百位上的数字*/s=*/10%10;/*求十位上的数字*/g=*%10;/*求个位上的数字*/printf(%d,%d,%d,%d,%dn,w,q,b,s,g);例 2、任意读入一个整数，依次输出其符号位及从低位到高位上的数字。分析此题读入的整数不知道是几位数，但可以用以下例如的方法完成此题：例如读入的整数为 3796，存放在*中，执行*%10 后得余数为 6 并输出；将*/10 得 379 后赋值给*。再执行*%10 后得余数为 9 并输出；将*/10 得 37 后赋值给*直到商*为 0 时终止。main()long*;scanf(%ld,&*);if(*0)printf(-);

31、*=-*;do /*为了能正确处理 0，要用 do_while 循环*/printf(%d ,*%10);*=*/10;while(*!=0);printf(n);例 3、任意读入一个整数，依次输出其符号位及从高位到低位上的数字。分析此题必须借助数组将依次求得的低位到高位的数字保存后，再逆序输出。main()long*;int a20,i,j;scanf(%ld,&*);if(*=0;j-)printf(%d ,aj);printf(n);6辗转相除法求两个正整数的最大公约数-该算法的要领是：假设两个正整数为 a 和 b，先求出前者除以后者的余数，存放到变量 r 中，假设 r 不为 0，则将

32、b 的值得赋给 a，将 r 的值得赋给 b；再求出 a 除以 b 的余数，仍然存放到变量 r 中如此反复，直至 r 为 0 时终止，此时 b 中存放的即为原来两数的最大公约数。例 1、任意读入两个正整数，求出它们的最大公约数。法一：用 while 循环时，最大公约数存放于 b 中 main()int a,b,r;doscanf(%d%d,&a,&b);while(a=0|b=0);/*确保 a 和 b 为正整数*/r=a%b;while(r!=0)a=b;b=r;r=a%b;printf(%dn,b);法二：用 dowhile 循环时，最大公约数存放于 a 中 main()int a,b,r;

33、doscanf(%d%d,&a,&b);while(a=0|b=0);/*确保 a 和 b 为正整数*/do r=a%b;a=b;b=r;while(r!=0);printf(%dn,a);【引申】可以利用最大公约数求最小公倍数。提示：两个正整数 a 和 b 的最小公倍数=ab/最大公约数。例 2、任意读入两个正整数，求出它们的最小公倍数。法一：利用最大公约数求最小公倍数 main()int a,b,r,*,y;doscanf(%d%d,&a,&b);while(a=0|b=0);/*确保 a 和 b 为正整数*/*=a;y=b;/*保存 a、b 原来的值*/r=a%b;while(r!=0)

34、a=b;b=r;r=a%b;printf(%dn,*y/b);法二：假设其中一数的最小倍数也是另一数的倍数，该最小倍数即为所求 main()int a,b,r,i;do scanf(%d%d,&a,&b);while(a=0|b=0);/*确保 a 和 b 为正整数*/i=1;-while(a*i%b!=0)i+;printf(%dn,i*a);7求最值 即求假设干数据中的最大值或最小值。算法要领是：首先将假设干数据存放于数组中，通常假设第一个元素即为最大值 或最小值，赋值给最终存放最大值 或最小值 的 ma*或 min变量中，然后将该量 ma*或 min的值与数组其余每一个元素进展比拟，一旦

35、比该量还大或小，则将此元素的值赋给 ma*或 min 所有数如此比拟完毕，即可求得最大值 或最小值。例 1、任意读入 10 个数，输出其中的最大值与最小值。*define N 10 main()int aN,i,ma*,min;for(i=0;iN;i+)scanf(%d,&ai);ma*=min=a0;for(i=1;ima*)ma*=ai;elseif(aimin)min=ai;printf(ma*=%d,min=%dn,ma*,min);8判断素数 素数又称质数，即“只能被 1 和自身整除的大于 1 的自然数。判断素数的算法要领就是依据数学定义，即假设该大于 1 的正整数不能被 2 至自

36、身减 1 整除，就是素数。例 1、任意读入一个正整数，判断其是否为素数。main()int*,k;do scanf(%d,&*);while(*=1);/*确保读入大于 1 的正整数*/for(k=2;k=*-1;k+)if(*%k=0)break;/*一旦能被 2自身-1 整除，就不可能是素数*/if(k=*)printf(%d is sushun,*);elseprintf(%d is not sushun,*);以上例题可以用以下两种变形来解决需要使用辅助判断的逻辑变量：【变形一】将“2自身-1的围缩小至“2自身的一半 main()int*,k,flag;doscanf(%d,&*);w

37、hile(*=1);flag=1;/*先假设*就是素数*/for(k=2;k=*/2;k+)if(*%k=0)flag=0;break;/*一旦不可能是素数，即置 flag 为 0*/if(flag=1)printf(%d is sushun,*);-else printf(%d is not sushun,*);【变形二】将“2自身-1的围缩小至“2自身的平方根*include math.h main()int*,k,flag;do scanf(%d,&*);while(*=1);flag=1;/*先假设*就是素数*/for(k=2;k=(int)sqrt(*);k+)if(*%k=0)fl

38、ag=0;break;/*一旦不可能是素数，即置 flag 为 0*/if(flag=1)printf(%d is sushun,*);elseprintf(%d is not sushun,*);例2、用筛选法求得100以的所有素数。算法为：1定义一维数组a，其初值为：2，3，100；2假设ak不为0，则将该元素以后的所有ak的倍数的数组元素置为0；3a中不为0的元素，均为素数。*include *include main()int k,j,a101;clrscr();/*清屏函数*/for(k=2;k101;k+)ak=k;for(k=2;ksqrt(101);k+)for(j=k+1;j

39、101;j+)if(ak!=0&aj!=0)if(aj%ak=0)aj=0;for(k=2;k101;k+)if(ak!=0)printf(%5d,ak);9数组元素的插入、删除 1数组元素的插入 此算法一般是在已经有序的数组中再插入一个数据，使数组中的数列依然有序。算法要领是：假设待插数据为*，数组 a 中数据为升序序列。先将*与 a 数组当前最后一个元素进展比拟，假设比最后一个元素还大，就将*放入其后一个元素中；否则进展以下步骤；先查找到待插位置。从数组 a 的第 1 个元素开场找到不比*小的第一个元素，设其下标为 i；将数组 a 中原最后一个元素至第 i 个元素依次一一后移一位，让出待插

40、数据的位置，即下标为 i的位置；将*存放到 a(i)中。例题参见前面“排序中插入法排序的例 1。2数组元素的删除 此算法的要领是：首先要找到也可能找不到待删除元素在数组中的位置即下标，然后-将待删元素后的每一个元素向前移动一位，最后将数组元素的个数减 1。例 1、数组 a 中有假设干不同考试分数，任意读入一个分数，假设与数组 a 中*一元素值相等，就将该元素删除。*define N 6 main()int fsN=69,90,85,56,44,80,*;int i,j,n;n=N;scanf(%d,&*);/*任意读入一个分数值*/*以下查找待删分数的位置，即元素下标*/for(i=0;in;

41、i+)if(fsi=*)break;if(i=n)printf(Not found!n);else /*将待删位置之后的所有元素一一前移*/for(j=i+1;jn;j+)fsj-1=fsj;n=n-1;/*元素个数减 1*/for(i=0;in;i+)printf(%d ,fsi);10二维数组的其他典型问题 1方阵的特点 行列相等的矩阵又称方阵。其两条对角线中“方向的为主对角线，“/方向的为副对角线。主对角线上各元素的下标特点为：行列值相等；副对角线上各元素的下标特点为：行列值之和都为阶数加 1。主对角线及其以下局部行值大于列值称为下三角。例 1、输出如下 5 阶方阵。1 2 2 2 2

42、3 1 2 2 2 3 3 1 2 2 3 3 3 1 2 3 3 3 3 1*define N 5 main()int aNN,i,j;for(i=0;iN;i+)for(j=0;jN;j+)if(i=j)aij=1;else if(ij)aij=2;else aij=3;for(i=0;iN;i+)for(j=0;jN;j+)printf(%3d,aij);-printf(n);例 2、输出如下 5 阶方阵。1 2 3 4 5 2 3 4 5 6 3 4 5 6 7 4 5 6 7 8 5 6 7 8 9*define N 5 main()int aNN,i,j;for(i=0;iN;i+

43、)for(j=0;jN;j+)aij=i+j+1;/*沿副对角线平行线方向考察每个元素，其值等于行列值之和+1*/for(i=0;iN;i+)for(j=0;jN;j+)printf(%3d,aij);printf(n);2辉三角形 辉三角形的每一行是(*+y)n的展开式各项的系数。例如第一行是(*+y)0，其系数为 1；第二行是(*+y)1，其系数为 1，1；第三行是(*+y)2，其展开式为*2+2*y+y2，系数分别为 1，2，1；直观形式如下：1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 分析以上形式，可以发现其规律：是 n 阶方阵的下三角，第一

44、列和主对角线均为 1，其余各元素是它的上一行、同一列元素与上一行、前一列元素之和。例 1、编程输出辉三角形的前 10 行。*define N 10 main()int aNN,i,j;for(i=0;iN;i+)ai0=aii=1;for(i=2;iN;i+)for(j=1;j=i-1;j+)aij=ai-1j-1+ai-1j;for(i=0;iN;i+)-for(j=0;j=i;j+)printf(%4d,aij);printf(n);例 2、以等腰三角形的形状输出辉三角形的前 5 行。1 1 1 1 2 1 1 3 3 1 1 4 6 4 1*define N 5 main()int aNN,i,j;for(i=0;iN;i+)ai0=aii=1;for(i=0;iN;i+)for(j=1;ji;j+)aij=ai-1j-1+ai-1j;for(i=0;i=0;j-)printf();/*输出时每行前导空格递减*/for(j=0;j=i;j+)printf(%4d,aij);printf(n);