C语言程序设计2-算法

古城微笑少年丶 2021-06-24 16:11 426阅读 0赞

程序 = 数据结构 + 算法

#### 数据结构是什么？ ####

[数据][Link 1]结构是[计算机][Link 2]存储、组织[数据][Link 3]的方式。数据结构是指相互之间存在一种或多种特定关系的[数据元素][Link 4]的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储[效率][Link 5]。数据结构往往同高效的检索[算法][Link 6]和[索引][Link 7]技术有关。 \[1\]

数据结构名词定义：

*  数据结构是指**相互之间存在着一种或多种关系的**[**数据**][Link 3]**元素的集合和该集合中数据**[**元素**][Link 8]**之间的关系组成。记为：**  
    **Data\_Structure=(D,R)**

**其中**D**是数据元素的**[**集合**][Link 9]**，**R**是该集合中所有元素之间的关系的**[**有限集合**][Link 10]**。** \[2\]

###### 常用结构 ######

数组、栈、队列、链表、树、图、堆、散列表。

#### 算法 ####

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰[指令][Link 11]，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的[输入][Link 12]，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用[空间复杂度][Link 13]与[时间复杂度][Link 14]来衡量。

###### 算法特征 ######

1.  [有穷性][Link 15]
2.  [确切性][Link 16]
3.  [输入项][Link 17]
4.  [输出项][Link 18]
5.  [可行性][Link 19]

###### 算法分类 ######

算法可大致分为基本算法、数据结构的算法、[数论][Link 20]与代数算法、计算几何的算法、[图论][Link 21]的算法、[动态规划][Link 22]以及[数值分析][Link 23]、[加密算法][Link 24]、[排序算法][Link 25]、检索算法、随机化算法、并行算法，厄米变形模型，随机森林算法。

###### 算法描述方式 ######

描述算法的方法有多种，常用的有自然语言、结构化[流程图][Link 26]、[伪代码][Link 27]和[PAD图][PAD]等，其中最普遍的是流程图。

同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。[算法分析][Link 28]的目的在于选择合适算法和改进算法。一个算法的评价主要从[**时间复杂度**][Link 29]和[**空间复杂度**][Link 30]来考虑。

###### 时间复杂度 ######

算法的时间复杂度是指执行算法所需要的计算工作量。一般来说，计算机算法是问题规模n 的函数f(n)，算法的时间复杂度也因此记做。

T(n)=Ο(f(n))

因此，问题的规模n 越大，算法执行的时间的增长率与f(n) 的增长率正相关，称作[渐进时间复杂度][Link 31]（Asymptotic Time Complexity）。

###### 空间复杂度 ######

算法的空间复杂度是指算法需要消耗的内存空间。其计算和表示方法与时间[复杂度][Link 32]类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。

![2789632-69ec9fa7b8b753a7.png][]

算法描述方法

![2789632-822ca08597b74f66.png][]

算法描述方法实例

![2789632-3b419392e8ae2ed9.png][]

基本结构-顺序&选择

![2789632-04c229f306e0ea21.png][]

基本结构-循环

练习：  
百钱百鸡问题：公鸡一只：5钱，母鸡一只：3钱，鸡雏三只：1钱，百钱买百鸡，公鸡，母鸡，鸡雏各几只？

![2789632-705bcb7d0541bb0b.png][]

result

Code:

#include <stdio.h>
    
    void main() 
    {
        // cocks: 5, hens: 3, 3chicks:1
        // 0<= cocks <= 19, 0<=hens<=33, 0<=chicks<=100
        for (int i = 0; i <= 19; i++)
        {
            for (int j = 0; j <= 33; j++)
            {
                for (int k = 0; k <= 100; k++)
                {
                    if (i * 5 + j * 3 + k / 3 == 100 && i + j + k == 100)
                    {
                        printf("cocks: %d 只，hens: %d 只, chicks: %d 只。 计算：i * 5 = %d, j * 3 = %d, k/3 = %d\n", i, j, k, i * 5, j * 3, k/3);
                    }
                }
            }
        }
    
    }

![2789632-e1b0e5504d8f0d9a.png][]

张中华公众号

![2789632-4ff8125a3453df19.jpg][]

张中华微信

[Link 1]: https://links.jianshu.com/go?to=https%3A%2F%2Fbaike.baidu.com%2Fitem%2F%25E6%2595%25B0%25E6%258D%25AE%2F5947370
[Link 2]: https://links.jianshu.com/go?to=https%3A%2F%2Fbaike.baidu.com%2Fitem%2F%25E8%25AE%25A1%25E7%25AE%2597%25E6%259C%25BA%2F140338
[Link 3]: https://links.jianshu.com/go?to=https%3A%2F%2Fbaike.baidu.com%2Fitem%2F%25E6%2595%25B0%25E6%258D%25AE
[Link 4]: https://links.jianshu.com/go?to=https%3A%2F%2Fbaike.baidu.com%2Fitem%2F%25E6%2595%25B0%25E6%258D%25AE%25E5%2585%2583%25E7%25B4%25A0%2F715313
[Link 5]: https://links.jianshu.com/go?to=https%3A%2F%2Fbaike.baidu.com%2Fitem%2F%25E6%2595%2588%25E7%258E%2587%2F868847
[Link 6]: https://links.jianshu.com/go?to=https%3A%2F%2Fbaike.baidu.com%2Fitem%2F%25E7%25AE%2597%25E6%25B3%2595%2F209025
[Link 7]: https://links.jianshu.com/go?to=https%3A%2F%2Fbaike.baidu.com%2Fitem%2F%25E7%25B4%25A2%25E5%25BC%2595%2F5716853
[Link 8]: https://links.jianshu.com/go?to=https%3A%2F%2Fbaike.baidu.com%2Fitem%2F%25E5%2585%2583%25E7%25B4%25A0
[Link 9]: https://links.jianshu.com/go?to=https%3A%2F%2Fbaike.baidu.com%2Fitem%2F%25E9%259B%2586%25E5%2590%2588
[Link 10]: https://links.jianshu.com/go?to=https%3A%2F%2Fbaike.baidu.com%2Fitem%2F%25E6%259C%2589%25E9%2599%2590%25E9%259B%2586%25E5%2590%2588
[Link 11]: https://links.jianshu.com/go?to=https%3A%2F%2Fbaike.baidu.com%2Fitem%2F%25E6%258C%2587%25E4%25BB%25A4%2F3225201
[Link 12]: https://links.jianshu.com/go?to=https%3A%2F%2Fbaike.baidu.com%2Fitem%2F%25E8%25BE%2593%25E5%2585%25A5%2F32696
[Link 13]: https://links.jianshu.com/go?to=https%3A%2F%2Fbaike.baidu.com%2Fitem%2F%25E7%25A9%25BA%25E9%2597%25B4%25E5%25A4%258D%25E6%259D%2582%25E5%25BA%25A6%2F9664257
[Link 14]: https://links.jianshu.com/go?to=https%3A%2F%2Fbaike.baidu.com%2Fitem%2F%25E6%2597%25B6%25E9%2597%25B4%25E5%25A4%258D%25E6%259D%2582%25E5%25BA%25A6%2F1894057
[Link 15]: https://links.jianshu.com/go?to=https%3A%2F%2Fbaike.baidu.com%2Fitem%2F%25E7%25AE%2597%25E6%25B3%2595%2F209025%3Ffr%3Daladdin%231_1
[Link 16]: https://links.jianshu.com/go?to=https%3A%2F%2Fbaike.baidu.com%2Fitem%2F%25E7%25AE%2597%25E6%25B3%2595%2F209025%3Ffr%3Daladdin%231_2
[Link 17]: https://links.jianshu.com/go?to=https%3A%2F%2Fbaike.baidu.com%2Fitem%2F%25E7%25AE%2597%25E6%25B3%2595%2F209025%3Ffr%3Daladdin%231_3
[Link 18]: https://links.jianshu.com/go?to=https%3A%2F%2Fbaike.baidu.com%2Fitem%2F%25E7%25AE%2597%25E6%25B3%2595%2F209025%3Ffr%3Daladdin%231_4
[Link 19]: https://links.jianshu.com/go?to=https%3A%2F%2Fbaike.baidu.com%2Fitem%2F%25E7%25AE%2597%25E6%25B3%2595%2F209025%3Ffr%3Daladdin%231_5
[Link 20]: https://links.jianshu.com/go?to=https%3A%2F%2Fbaike.baidu.com%2Fitem%2F%25E6%2595%25B0%25E8%25AE%25BA
[Link 21]: https://links.jianshu.com/go?to=https%3A%2F%2Fbaike.baidu.com%2Fitem%2F%25E5%259B%25BE%25E8%25AE%25BA
[Link 22]: https://links.jianshu.com/go?to=https%3A%2F%2Fbaike.baidu.com%2Fitem%2F%25E5%258A%25A8%25E6%2580%2581%25E8%25A7%2584%25E5%2588%2592
[Link 23]: https://links.jianshu.com/go?to=https%3A%2F%2Fbaike.baidu.com%2Fitem%2F%25E6%2595%25B0%25E5%2580%25BC%25E5%2588%2586%25E6%259E%2590
[Link 24]: https://links.jianshu.com/go?to=https%3A%2F%2Fbaike.baidu.com%2Fitem%2F%25E5%258A%25A0%25E5%25AF%2586%25E7%25AE%2597%25E6%25B3%2595
[Link 25]: https://links.jianshu.com/go?to=https%3A%2F%2Fbaike.baidu.com%2Fitem%2F%25E6%258E%2592%25E5%25BA%258F%25E7%25AE%2597%25E6%25B3%2595
[Link 26]: https://links.jianshu.com/go?to=https%3A%2F%2Fbaike.baidu.com%2Fitem%2F%25E6%25B5%2581%25E7%25A8%258B%25E5%259B%25BE
[Link 27]: https://links.jianshu.com/go?to=https%3A%2F%2Fbaike.baidu.com%2Fitem%2F%25E4%25BC%25AA%25E4%25BB%25A3%25E7%25A0%2581
[PAD]: https://links.jianshu.com/go?to=https%3A%2F%2Fbaike.baidu.com%2Fitem%2FPAD%25E5%259B%25BE
[Link 28]: https://links.jianshu.com/go?to=https%3A%2F%2Fbaike.baidu.com%2Fitem%2F%25E7%25AE%2597%25E6%25B3%2595%25E5%2588%2586%25E6%259E%2590
[Link 29]: https://links.jianshu.com/go?to=https%3A%2F%2Fbaike.baidu.com%2Fitem%2F%25E6%2597%25B6%25E9%2597%25B4%25E5%25A4%258D%25E6%259D%2582%25E5%25BA%25A6
[Link 30]: https://links.jianshu.com/go?to=https%3A%2F%2Fbaike.baidu.com%2Fitem%2F%25E7%25A9%25BA%25E9%2597%25B4%25E5%25A4%258D%25E6%259D%2582%25E5%25BA%25A6
[Link 31]: https://links.jianshu.com/go?to=https%3A%2F%2Fbaike.baidu.com%2Fitem%2F%25E6%25B8%2590%25E8%25BF%259B%25E6%2597%25B6%25E9%2597%25B4%25E5%25A4%258D%25E6%259D%2582%25E5%25BA%25A6
[Link 32]: https://links.jianshu.com/go?to=https%3A%2F%2Fbaike.baidu.com%2Fitem%2F%25E5%25A4%258D%25E6%259D%2582%25E5%25BA%25A6
[2789632-69ec9fa7b8b753a7.png]: /images/20210615/5746ead098994588a2fb3d470074d2df.png
[2789632-822ca08597b74f66.png]: /images/20210615/0a19c8db7edc49c795e305195df38cf9.png
[2789632-3b419392e8ae2ed9.png]: /images/20210615/8e22ed09d85c4fe78c100b84f797f5f6.png
[2789632-04c229f306e0ea21.png]: /images/20210615/fcd2292cd1a840ab9e1da506f076d06a.png
[2789632-705bcb7d0541bb0b.png]: /images/20210615/48032d726d16411e9d73bf08200ab711.png
[2789632-e1b0e5504d8f0d9a.png]: /images/20210615/a1dbe6f7f34848eca7d268d045b3c8c2.png
[2789632-4ff8125a3453df19.jpg]: /images/20210615/72a20365b5d241048887667387f7a8c8.png