数据结构和算法部分经典例子

《数据结构和算法部分经典例子》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构和算法部分经典例子一、迭代法迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为f(x)=0，用某种数学方法导出等价的形式x=g(x)，然后按以下步骤执行：（1）选一个方程的近似根，赋给变量x0；（2）将x0的值保存于变量x1，然后计算g(x1)，并将结果存于变量x0；（3）当x0与x1的差的绝对值还小于指定的精度要求时，重复步骤（2）的计算。若方程有根，并且用上述方法计算出来的近似根序列收敛，则按上述方法求得的x0就认为是方程的根。上述算法用C程序的形式表示为：【算法】迭代法求方程的根{x0=初始近似根；do{

2、x1=x0；x0=g(x1)；/*按特定的方程计算新的近似根*/}while(fabs(x0-x1)>Epsilon)；printf(“方程的近似根是%f”，x0)；}迭代算法也常用于求方程组的根，令X=（x0，x1，…，xn-1）设方程组为：xi=gi(X)(I=0，1，…，n-1)则求方程组根的迭代算法可描述如下：【算法】迭代法求方程组的根{for(i=0;i

3、.0,i=0;idelta)delta=fabs(y[i]-x[i])；}while(delta>Epsilon)；for(i=0;i

4、始近似根选择不合理，也会导致迭代失败。二、穷举搜索法穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验，并从众找出那些符合要求的候选解作为问题的解。【问题】将A、B、C、D、E、F这六个变量排成如图所示的三角形，这六个变量分别取[1，6]上的整数，且均不相同。求使三角形三条边上的变量之和相等的全部解。如图就是一个解。程序引入变量a、b、c、d、e、f，并让它们分别顺序取1至6的证书，在它们互不相同的条件下，测试由它们排成的如图所示的三角形三条边上的变量之和是否相等，如相等即为一种满足要求的排列，把它们输出。当这些变量取尽所

5、有的组合后，程序就可得到全部可能的解。细节见下面的程序。【程序1】#includevoidmain(){inta,b,c,d,e,f;for(a=1;a<=6;a++)for(b=1;b<=6;b++){if(b==a)continue;for(c=1;c<=6;c++){if(c==a)

6、

7、(c==b)continue;for(d=1;d<=6;d++){if(d==a)

8、

9、(d==b)

10、

11、(d==c)continue;for(e=1;e<=6;e++){if(e==a)

12、

13、(e==b)

14、

15、(e==c)

16、

17、(e==

18、d)continue;f=21-(a+b+c+d+e);if((a+b+c==c+d+e))&&(a+b+c==e+f+a)){printf(“%6d,a);printf(“%4d%4d”,b,f);printf(“%2d%4d%4d”,c,d,e);scanf(“%*c”);}}}}}}按穷举法编写的程序通常不能适应变化的情况。如问题改成有9个变量排成三角形，每条边有4个变量的情况，程序的循环重数就要相应改变。对一组数穷尽所有排列，还有更直接的方法。将一个排列看作一个长整数，则所有排列对应着一组整数。将这组整数按从小到大的顺序排列排

19、成一个整数，从对应最小的整数开始。按数列的递增顺序逐一列举每个排列对应的每个整数，这能更有效地完成排列的穷举。从一个排列找出对应数列的下一个排列可在当前排列的基础上作部分调整来实现。倘若当前排列为1，2，4，6，5，3，并令其对应的长整数为124653。要寻找比长整数124653更大的排列，可从该排列的最后一个数字顺序向前逐位考察，当发现排列中的某个数字比它前一个数字大时，如本例中的6比它的前一位数字4大，这说明还有对应更大整数的排列。但为了顺序从小到大列举出所有的排列，不能立即调整得太大，如本例中将数字6与数字4交换得到的排列126

20、453就不是排列124653的下一个排列。为了得到排列124653的下一个排列，应从已经考察过的那部分数字中选出比数字大，但又是它们中最小的那一个数字，比如数字5，与数字4交换。该数字也是从后向前考察过程中第一个比4大的