C语言算法速查手册完整代码

<<C语言算法速查手册>> 配书源代码 C语言算法速查手册 目录 第1章　绪论　1 1.1　程序设计语言概述　1 1.1.1　机器语言　1 1.1.2　汇编语言　2 1.1.3　高级语言　2 1.1.4　C语言　3 1.2　C语言的优点和缺点　4 1.2.1　C语言的优点　4 1.2.2　C语言的缺点　6 1.3　算法概述　7 1.3.1　算法的基本特征　7 1.3.2　算法的复杂度　8 1.3.3　算法的准确性　10 1.3.4　算法的稳定性　14 第2章　复数运算　18 2.1　复数的四则运算　18 2.1.1　[算法1]　复数乘法　18 2.1.2　[算法2]　复数除法　20 2.1.3　【实例5】 复数的四则运算　22 2.2　复数的常用函数运算　23 2.2.1　[算法3]　复数的乘幂　23 2.2.2　[算法4]　复数的n次方根　25 2.2.3　[算法5]　复数指数　27 2.2.4　[算法6]　复数对数　29 2.2.5　[算法7]　复数正弦　30 2.2.6　[算法8]　复数余弦　32 2.2.7　【实例6】 复数的函数运算　34 第3章　多项式计算　37 3.1　多项式的表示方法　37 3.1.1　系数表示法　37 3.1.2　点表示法　38 3.1.3　[算法9]　系数表示转化为点表示　38 3.1.4　[算法10]　点表示转化为系数表示　42 3.1.5　【实例7】　系数表示法与点表示法的转化　46 3.2　多项式运算　47 3.2.1　[算法11]　复系数多项式相乘　47 3.2.2　[算法12]　实系数多项式相乘　50 3.2.3　[算法13]　复系数多项式相除　52 3.2.4　[算法14]　实系数多项式相除　54 3.2.5　【实例8】　复系数多项式的乘除法　56 3.2.6　【实例9】　实系数多项式的乘除法　57 3.3　多项式的求值　59 3.3.1　[算法15]　一元多项式求值　59 3.3.2　[算法16]　一元多项式多组求值　60 3.3.3　[算法17]　二元多项式求值　63 3.3.4　【实例10】　一元多项式求值　65 3.3.5　【实例11】　二元多项式求值　66 第4章　矩阵计算　68 4.1　矩阵相乘　68 4.1.1　[算法18]　实矩阵相乘　68 4.1.2　[算法19]　复矩阵相乘　70 4.1.3　【实例12】 实矩阵与复矩阵的乘法　72 4.2　矩阵的秩与行列式值　73 4.2.1　[算法20]　求矩阵的秩　73 4.2.2　[算法21]　求一般矩阵的行列式值　76 4.2.3　[算法22]　求对称正定矩阵的行列式值　80 4.2.4　【实例13】 求矩阵的秩和行列式值　82 4.3　矩阵求逆　84 4.3.1　[算法23]　求一般复矩阵的逆　84 4.3.2　[算法24]　求对称正定矩阵的逆　90 4.3.3　[算法25]　求托伯利兹矩阵逆的Trench方法　92 4.3.4　【实例14】 验证矩阵求逆算法　97 4.3.5　【实例15】 验证T矩阵求逆算法　99 4.4　矩阵分解与相似变换　102 4.4.1　[算法26]　实对称矩阵的LDL分解　102 4.4.2　[算法27]　对称正定实矩阵的Cholesky分解　104 4.4.3　[算法28]　一般实矩阵的全选主元LU分解　107 4.4.4　[算法29]　一般实矩阵的QR分解　112 4.4.5　[算法30]　对称实矩阵相似变换为对称三对角阵　116 4.4.6　[算法31]　一般实矩阵相似变换为上Hessen-Burg矩阵　121 4.4.7　【实例16】 对一般实矩阵进行QR分解　126 4.4.8　【实例17】 对称矩阵的相似变换　127 4.4.9　【实例18】 一般实矩阵相似变换　129 4.5　矩阵特征值的计算　130 4.5.1　[算法32]　求上Hessen-Burg矩阵全部特征值的QR方法　130 4.5.2　[算法33]　求对称三对角阵的全部特征值　137 4.5.3　[算法34]　求对称矩阵特征值的雅可比法　143 4.5.4　[算法35]　求对称矩阵特征值的雅可比过关法　147 4.5.5　【实例19】 求上Hessen-Burg矩阵特征值　151 4.5.6　【实例20】 分别用两种雅克比法求对称矩阵特征值　152 第5章　线性代数方程组的求解　154 5.1　高斯消去法　154 5.1.1　[算法36]　求解复系数方程组的全选主元高斯消去法　155 5.1.2　[算法37]　求解实系数方程组的全选主元高斯消去法　160 5.1.3　[算法38]　求解复系数方程组的全选主元高斯-约当消去法　163 5.1.4　[算法39]　求解实系数方程组的全选主元高斯-约当消去法　168 5.1.5　[算法40]　求解大型稀疏系数矩阵方程组的高斯-约当消去法　171 5.1.6　[算法41]　求解三对角线方程组的追赶法　174 5.1.7　[算法42]　求解带型方程组的方法　176 5.1.8　【实例21】 解线性实系数方程组　179 5.1.9　【实例22】 解线性复系数方程组　180 5.1.10　【实例23】 解三对角线方程组　182 5.2　矩阵分解法　184 5.2.1　[算法43]　求解对称方程组的LDL分解法　184 5.2.2　[算法44]　求解对称正定方程组的Cholesky分解法　186 5.2.3　[算法45]　求解线性最小二乘问题的QR分解法　188 5.2.4　【实例24】 求解对称正定方程组　191 5.2.5　【实例25】 求解线性最小二乘问题　192 5.3　迭代方法　193 5.3.1　[算法46]　病态方程组的求解　193 5.3.2　[算法47]　雅克比迭代法　197 5.3.3　[算法48]　高斯-塞德尔迭代法　200 5.3.4　[算法49]　超松弛方法　203 5.3.5　[算法50]　求解对称正定方程组的共轭梯度方法　205 5.3.6　[算法51]　求解托伯利兹方程组的列文逊方法　209 5.3.7　【实例26】 解病态方程组　214 5.3.8　【实例27】 用迭代法解方程组　215 5.3.9　【实例28】 求解托伯利兹方程组　217 第6章　非线性方程与方程组的求解　219 6.1　非线性方程求根的基本过程　219 6.1.1　确定非线性方程实根的初始近似值或根的所在区间　219 6.1.2　求非线性方程根的精确解　221 6.2　求非线性方程一个实根的方法　221 6.2.1　[算法52]　对分法　221 6.2.2　[算法53]　牛顿法　223 6.2.3　[算法54]　插值法　226 6.2.4　[算法55]　埃特金迭代法　229 6.2.5　【实例29】 用对分法求非线性方程组的实根　232 6.2.6　【实例30】 用牛顿法求非线性方程组的实根　233 6.2.7　【实例31】 用插值法求非线性方程组的实根　235 6.2.8　【实例32】 用埃特金迭代法求非线性方程组的实根　237 6.3　求实系数多项式方程全部根的方法　238 6.3.1　[算法56]　QR方法　238 6.3.2　【实例33】　用QR方法求解多项式的全部根　240 6.4　求非线性方程组一组实根的方法　241 6.4.1　[算法57]　梯度法　241 6.4.2　[算法58]　拟牛顿法　244 6.4.3　【实例34】 用梯度法计算非线性方程组的一组实根　250 6.4.4　【实例35】 用拟牛顿法计算非线性方程组的一组实根　252 第7章　代数插值法　254 7.1　拉格朗日插值法　254 7.1.1　[算法59]　线性插值　255 7.1.2　[算法60]　二次抛物线插值　256 7.1.3　[算法61]　全区间插值　259 7.1.4　【实例36】 拉格朗日插值　262 7.2　埃尔米特插值　263 7.2.1　[算法62]　埃尔米特不等距插值　263 7.2.2　[算法63]　埃尔米特等距插值　267 7.2.3　【实例37】 埃尔米特插值法　270 7.3　埃特金逐步插值　271 7.3.1　[算法64]　埃特金不等距插值　272 7.3.2　[算法65]　埃特金等距插值　275 7.3.3　【实例38】 埃特金插值　278 7.4　光滑插值　279 7.4.1　[算法66]　光滑不等距插值　279 7.4.2　[算法67]　光滑等距插值　283 7.4.3　【实例39】 光滑插值　286 7.5　三次样条插值　287 7.5.1　[算法68]　第一类边界条件的三次样条函数插值　287 7.5.2　[算法69]　第二类边界条件的三次样条函数插值　292 7.5.3　[算法70]　第三类边界条件的三次样条函数插值　296 7.5.4　【实例40】 样条插值法　301 7.6　连分式插值　303 7.6.1　[算法71]　连分式插值　304 7.6.2　【实例41】 验证连分式插值的函数　308 第8章　数值积分法　309 8.1　变步长求积法　310 8.1.1　[算法72]　变步长梯形求积法　310 8.1.2　[算法73]　自适应梯形求积法　313 8.1.3　[算法74]　变步长辛卜生求积法　316 8.1.4　[算法75]　变步长辛卜生二重积分方法　318 8.1.5　[算法76]　龙贝格积分　322 8.1.6　【实例42】 变步长积分法进行一重积分　325 8.1.7　【实例43】 变步长辛卜生积分法进行二重积分　326 8.2　高斯求积法　328 8.2.1　[算法77]　勒让德-高斯求积法　328 8.2.2　[算法78]　切比雪夫求积法　331 8.2.3　[算法79]　拉盖尔-高斯求积法　334 8.2.4　[算法80]　埃尔米特-高斯求积法　336 8.2.5　[算法81]　自适应高斯求积方法　337 8.2.6　【实例44】 有限区间高斯求积法　342 8.2.7　【实例45】 半无限区间内高斯求积法　343 8.2.8　【实例46】 无限区间内高斯求积法　345 8.3　连分式法　346 8.3.1　[算法82]　计算一重积分的连分式方法　346 8.3.2　[算法83]　计算二重积分的连分式方法　350 8.3.3　【实例47】 连分式法进行一重积分　354 8.3.4　【实例48】 连分式法进行二重积分　355 8.4　蒙特卡洛法　356 8.4.1　[算法84]　蒙特卡洛法进行一重积分　356 8.4.2　[算法85]　蒙特卡洛法进行二重积分　358 8.4.3　【实例49】 一重积分的蒙特卡洛法　360 8.4.4　【实例50】 二重积分的蒙特卡洛法　361 第9章　常微分方程(组)初值问题的求解　363 9.1　欧拉方法　364 9.1.1　[算法86]　定步长欧拉方法　364 9.1.2　[算法87]　变步长欧拉方法　366 9.1.3　[算法88]　改进的欧拉方法　370 9.1.4　【实例51】 欧拉方法求常微分方程数值解　372 9.2　龙格-库塔方法　376 9.2.1　[算法89]　定步长龙格-库塔方法　376 9.2.2　[算法90]　变步长龙格-库塔方法　379 9.2.3　[算法91]　变步长基尔方法　383 9.2.4　【实例52】 龙格-库塔方法求常微分方程的初值问题　386 9.3　线性多步法　390 9.3.1　[算法92]　阿当姆斯预报校正法　390 9.3.2　[算法93]　哈明方法　394 9.3.3　[算法94]　全区间积分的双边法　399 9.3.4　【实例53】 线性多步法求常微分方程组初值问题　401 第10章　拟合与逼近　405 10.1　一元多项式拟合　405 10.1.1　[算法95]　最小二乘拟合　405 10.1.2　[算法96]　最佳一致逼近的里米兹方法　412 10.1.3　【实例54】 一元多项式拟合　417 10.2　矩形区域曲面拟合　419 10.2.1　[算法97]　矩形区域最小二乘曲面拟合　419 10.2.2　【实例55】 二元多项式拟合　428 第11章　特殊函数　430 11.1　连分式级数和指数积分　430 11.1.1　[算法98]　连分式级数求值　430 11.1.2　[算法99]　指数积分　433 11.1.3　【实例56】 连分式级数求值　436 11.1.4　【实例57】 指数积分求值　438 11.2　伽马函数　439 11.2.1　[算法100]　伽马函数　439 11.2.2　[算法101]　贝塔函数　441 11.2.3　[算法102]　阶乘　442 11.2.4　【实例58】　伽马函数和贝塔函数求值　443 11.2.5　【实例59】　阶乘求值　444 11.3　不完全伽马函数　445 11.3.1　[算法103]　不完全伽马函数　445 11.3.2　[算法104]　误差函数　448 11.3.3　[算法105]　卡方分布函数　450 11.3.4　【实例60】　不完全伽马函数求值　451 11.3.5　【实例61】　误差函数求值　452 11.3.6　【实例62】　卡方分布函数求值　453 11.4　不完全贝塔函数　454 11.4.1　[算法106]　不完全贝塔函数　454 11.4.2　[算法107]　学生分布函数　457 11.4.3　[算法108]　累积二项式分布函数　458 11.4.4　【实例63】　不完全贝塔函数求值　459 11.5　贝塞尔函数　461 11.5.1　[算法109]　第一类整数阶贝塞尔函数　461 11.5.2　[算法110]　第二类整数阶贝塞尔函数　466 11.5.3　[算法111]　变型第一类整数阶贝塞尔函数　469 11.5.4　[算法112]　变型第二类整数阶贝塞尔函数　473 11.5.5　【实例64】　贝塞尔函数求值　476 11.5.6　【实例65】　变型贝塞尔函数求值　477 11.6　Carlson椭圆积分　479 11.6.1　[算法113]　第一类椭圆积分　479 11.6.2　[算法114]　第一类椭圆积分的退化形式　481 11.6.3　[算法115]　第二类椭圆积分　483 11.6.4　[算法116]　第三类椭圆积分　486 11.6.5　【实例66】　第一类勒让德椭圆函数积分求值　490 11.6.6　【实例67】　第二类勒让德椭圆函数积分求值　492 第12章　极值问题　494 12.1　一维极值求解方法　494 12.1.1　[算法117]　确定极小值点所在的区间　494 12.1.2　[算法118]　一维黄金分割搜索　499 12.1.3　[算法119]　一维Brent方法　502 12.1.4　[算法120]　使用一阶导数的Brent方法　506 12.1.5　【实例68】　使用黄金分割搜索法求极值　511 12.1.6　【实例69】　使用Brent法求极值　513 12.1.7　【实例70】　使用带导数的Brent法求极值　515 12.2　多元函数求极值　517 12.2.1　[算法121]　不需要导数的一维搜索　517 12.2.2　[算法122]　需要导数的一维搜索　519 12.2.3　[算法123]　Powell方法　522 12.2.4　[算法124]　共轭梯度法　525 12.2.5　[算法125]　准牛顿法　531 12.2.6　【实例71】　验证不使用导数的一维搜索　536 12.2.7　【实例72】　用Powell算法求极值　537 12.2.8　【实例73】　用共轭梯度法求极值　539 12.2.9　【实例74】　用准牛顿法求极值　540 12.3　单纯形法　542 12.3.1　[算法126]　求无约束条件下n维极值的单纯形法　542 12.3.2　[算法127]　求有约束条件下n维极值的单纯形法　548 12.3.3　[算法128]　解线性规划问题的单纯形法　556 12.3.4　【实例75】　用单纯形法求无约束条件下N维的极值　568 12.3.5　【实例76】　用单纯形法求有约束条件下N维的极值　569 12.3.6　【实例77】　求解线性规划问题　571 第13章　随机数产生与统计描述　574 13.1　均匀分布随机序列　574 13.1.1　[算法129]　产生0到1之间均匀分布的一个随机数　574 13.1.2　[算法130]　产生0到1之间均匀分布的随机数序列　576 13.1.3　[算法131]　产生任意区间内均匀分布的一个随机整数　577 13.1.4　[算法132]　产生任意区间内均匀分布的随机整数序列　578 13.1.5　【实例78】　产生0到1之间均匀分布的随机数序列　580 13.1.6　【实例79】　产生任意区间内均匀分布的随机整数序列　581 13.2　正态分布随机序列　582 13.2.1　[算法133]　产生任意均值与方差的正态分布的一个随机数　582 13.2.2　[算法134]　产生任意均值与方差的正态分布的随机数序列　585 13.2.3　【实例80】　产生任意均值与方差的正态分布的一个随机数　587 13.2.4　【实例81】　产生任意均值与方差的正态分布的随机数序列　588 13.3　统计描述　589 13.3.1　[算法135]　分布的矩　589 13.3.2　[算法136]　方差相同时的t分布检验　591 13.3.3　[算法137]　方差不同时的t分布检验　594 13.3.4　[算法138]　方差的F检验　596 13.3.5　[算法139]　卡方检验　599 13.3.6　【实例82】　计算随机样本的矩　601 13.3.7　【实例83】　t分布检验　602 13.3.8　【实例84】　F分布检验　605 13.3.9　【实例85】　检验卡方检验的算法　607 第14章　查找　609 14.1　基本查找　609 14.1.1　[算法140]　有序数组的二分查找　609 14.1.2　[算法141]　无序数组同时查找最大和最小的元素　611 14.1.3　[算法142]　无序数组查找第M小的元素　613 14.1.4　【实例86】　基本查找　615 14.2　结构体和磁盘文件的查找　617 14.2.1　[算法143]　无序结构体数组的顺序查找　617 14.2.2　[算法144]　磁盘文件中记录的顺序查找　618 14.2.3　【实例87】　结构体数组和文件中的查找　619 14.3　哈希查找　622 14.3.1　[算法145]　字符串哈希函数　622 14.3.2　[算法146]　哈希函数　626 14.3.3　[算法147]　向哈希表中插入元素　628 14.3.4　[算法148]　在哈希表中查找元素　629 14.3.5　[算法149]　在哈希表中删除元素　631 14.3.6　【实例88】　构造哈希表并进行查找　632 第15章　排序　636 15.1　插入排序　636 15.1.1　[算法150]　直接插入排序　636 15.1.2　[算法151]　希尔排序　637 15.1.3　【实例89】　插入排序　639 15.2　交换排序　641 15.2.1　[算法152]　气泡排序　641 15.2.2　[算法153]　快速排序　642 15.2.3　【实例90】　交换排序　644 15.3　选择排序　646 15.3.1　[算法154]　直接选择排序　646 15.3.2　[算法155]　堆排序　647 15.3.3　【实例91】　选择排序　650 15.4　线性时间排序　651 15.4.1　[算法156]　计数排序　651 15.4.2　[算法157]　基数排序　653 15.4.3　【实例92】　线性时间排序　656 15.5　归并排序　657 15.5.1　[算法158]　二路归并排序　658 15.5.2　【实例93】　二路归并排序　660 第16章　数学变换与滤波　662 16.1　快速傅里叶变换　662 16.1.1　[算法159]　复数据快速傅里叶变换　662 16.1.2　[算法160]　复数据快速傅里叶逆变换　666 16.1.3　[算法161]　实数据快速傅里叶变换　669 16.1.4　【实例94】　验证傅里叶变换的函数　671 16.2　其他常用变换　674 16.2.1　[算法162]　快速沃尔什变换　674 16.2.2　[算法163]　快速哈达玛变换　678 16.2.3　[算法164]　快速余弦变换　682 16.2.4　【实例95】　验证沃尔什变换和哈达玛的函数　684 16.2.5　【实例96】　验证离散余弦变换的函数　687 16.3　平滑和滤波　688 16.3.1　[算法165]　五点三次平滑　689 16.3.2　[算法166]　α-β-γ滤波　690 16.3.3　【实例97】　验证五点三次平滑　692 16.3.4　【实例98】　验证α-β-γ滤波算法　693